Monday, July 31, 2006

Polyfilla and Old Painters

If I had to name a single favourite construction material, it would probably be Polyfilla, a plaster for filling up holes and cracks in walls and ceilings. With regular gypsum powder it would be difficult to add exactly the amount of water which would make the paste stiff enough to stay in the crack, and after a few minutes all the paste you mixed would harden nearly instantaneously leaving you very little working time. Furthermore, gypsum shrinks when drying and thereby forms new smaller cracks which you will have to plaster up a second or third time. But then someone, apparently at Polycell UK, thought of adding cellulose to gypsum powder. Mixed with water the resulting paste is very pleasurable to handle, it hardens less dramatically and shrinks less. Where I have needed a little harder finish, for example in an outward corner, I've successfully added small amounts of cement.

Polyfilla is nowadays a worldwide brand, but recently I learned that old painters have used the basic idea for centuries: they cooked oat meal in water and mixed the resulting thin porridge instead of clear water to the gypsum powder the next day. Instead of oat they might also use other sources of polymeric carbohydrates, such as mashed potatoes, mouldy bread, old newspapers, etc. Supposedly a pair of old underwear has been spread in the walls of an architecturally renowned house in central Helsinki.

If slightly cheaper and tougher finish was required, the gypsum powder would be mixed with coke slag. This material, colloquially called "kananpaska" (chicken shit) or "karhunpaska" (bear shit) was the predominant material for building light walls in Helsinki: a mold would be erected on one side of the future wall, the wall would be constructed layer-by-layer by throwing the gypsum-ash paste on the mold or previous layer, the mold would be removed, and a finishing ashless layer would be plastered on both sides of the wall. The demeaning name probably follows from the messiness of the substance when demolishing the wall: the coke slag produces extreme amounts of slowly setting dust. When local coal heaters was replaced by district heating during the fifties and sixties this construction material has fortunately lost popularity.

Wednesday, July 12, 2006

Football World Cup Finals

I've been told the football world cup finals (FWCF) are in progression in Germany at the moment. Haven't followed them as I'm less interested in watching football played by others than the one I play myself with Konami's Pro Evolution Soccer 4 on my PS2.

The FWCF to some degree relates to an interesting algorithmic problem: the selection problem in which an algorithm must select the i'th largest element of n values with as few pairwise comparisons as possible. Author, mathematician, and reverend Lewis Carroll, officially Charles Dodgson, became puzzled over the same problem while following tennis tournaments. Barring luck (randomness in individual game outcomes), the common knockout tournament is obviously the best tournament system for selecting the winner. I've previously studied some specific selection problems, but never ones which involve unreliable comparisons.

The FWCF employs first a stage of eight parallel round-robin tournaments, each containing four teams. The two best teams of each group proceed to a knock-out tournament. The winning team has played seven games, and it is possible that two teams play against each other twice.

The Swiss tournament system was introduced in chess tournaments in the late 18'th century. As in round-robin tournaments, each player/team accumulates a score based on its wins, draws and losses. On each round players with equal scores are pitted against each other, but with additional rules that prevent same players meeting again. The Swiss tournament has nice advantages, such as rapid convergence and high entertainment value to players, but your average football fan might find it perplexing and, more importantly, the tournament doesn't necessarily end in a final climax.

Naturally I wouldn't be writing this blog entry unless I would be suggesting some wise-ass tournament schemes of my own. But first, as a basis for estimating the tournament systems I choose the probability of a win for player A against player B to follow the logistic curve, 1/(1+c^(a-b)), where c I choose to be 1.4, and a and b are the positions of players A and B if all players were ordered "correctly". Hence, the best player wins the second best player with probability 1/(1+1.4^(1-2)) = 0.5833... and the tenth best player with probability 0.9538...

A full round-robin tournament among all thirty-two FWCF finalists sounds fair albeit somewhat lengthy, lasting at least three months. Simulating such a round-robin tournament one million times on a computer with the above game outcome probabilities shows that the best player would be awarded the gold medal only with approximately a 47.5% probability, silver with 26.7% probability, and bronze with 14.5% probability. Adding a second round increases the likelihood of correct winner to approximately 58%.

The standard knockout tournament fares even worse: the correct winner is chosen only with approximately 38.5% probability. But there is a simple remedy to improve it: playing the final best-of-three improves the best player's chances to 42.3%, playing also the semifinals best-of-three yields 45.2%. The next improvement would be to play the final best-of-five, resulting in almost 47.6% chances of finding the best player, but such a lengthy final may already lead to loss of concentration in the audience and tolerance in the native inhabitants of the hosting cities. Furthermore, any best-of-N system implies uncertainty of when the final decisive game will be played, which in turn may be troublesome to broadcasting companies and organizers who would like to schedule everything well in advance.

The FWCF system is not particularly good, only slightly more reliable than the basic knockout tournament and it requires seven rounds of games - two more than the straight-forward knockout tournament. Exchanging the order of group and knockout stage would make the tournament more reliable, but that wouldn't ensure all teams have at least three occasions to play and that there's a final climax at a predetermined date.

For my tournament system proposal I chose the simple sorting network as the basic computational device. I decided to add an eighth round of games, and as the comparator function I use not only the result of the played game but the number of wins accumulated in all played games so far, with emphasis on later wins. Only the final round is played as earlier - winners of those games are honored with gold and bronze regardless of their game history - thus ensuring the final climax. I wrote an elementary genetic algorithm and a fitness function which tries to maximize the likelihood of also the dimmer medals for the best player and avoid same players meeting twice. A nightful of CPU cycles later I obtained the following network which I have post-processed and visualized:

The above tournament system would award gold to the best player with a 44.6% probability. There are duplicate games, such as players 1 and 5 meeting on the semifinal and quarter-final round, but this was an elective trade-off. On average slightly over five games are duplicates. The role of maintaining a score sheet of wins is interesting, because if the comparator function replaced with the traditional - winner moves to the upper line - the tournament still produces the best winner with 42.5% probability. The most significant drawback of the above tournament is that the chance of winning is not entirely independent of which line the player is initially placed on. On the other hand, the best player is better off in my tournament than in the current FWCF regardless of which line he is placed on.

There's one remaining question: how to deal with draws. FWCF employs extra time and penalty shootouts, the latter of which undoubtably brings an additional element of randomness to the results. The tournament system I proposed above might allow draws in some places, but if draws are easy to achieve, the player which considers a draw more beneficial may adjust his playing style accordingly. As this is generally considered dull for spectators I propose a few solutions amenable for football: instead of the penalty shootout, the winning team is the one granted more corner kicks when the ball was passed outside by the defending goal keeper, but not field player. Should also that statistic be drawn, during the first three and the last rounds ties are broken by penalty kicks, during the latter half a variant of the away goals rule is used: a zero-zero in goals is considered a win for the team on the lower line, otherwise the team on the upper line wins.

Should a FWCF follow my suggestions some day (yeah, right, chances are even worse than Finland winning the Eurovision Song Contest), I promise I'll buy a ticket and eat it.