May 4, 2010
Steven Skiena has written a book, The Algorithm Design Manual, that is justly a favorite of Programming Praxis; it is an encyclopedia of common algorithms and data structures, with many pointers to original sources. Recently, I have been reading Skiena’s book, Calculated Bets, which describes a computer program, developed by Skiena and his students, for betting on the game jai alai.
Jai alai is similar to handball, played by teams of one or two players who alternately catch the ball in a basket worn on their wrist and throw it back to the front wall; a point is won when one team is unable to catch the ball and throw it back before it bounces twice, or for various other technical infractions. Although only two teams compete for each point, there are eight teams playing in a game; the first two teams start the game, with the remaining six teams forming a queue, and after each point the winner of the point scores, the loser goes to the back of the queue, and the first team in the queue competes against the previous winner. Each point has a value of 1 until each team has played once (that is, for the first eight points of a game), when the value of winning a point increases to 2. The team that first reaches seven points is the winner.
The purpose of the rule that increases the value of a point from 1 to 2 is to reduce the bias in favor of teams that start early in the queue (have a low “post position”). But, as Skiena points out, the rule isn’t perfect.
Your task is to write a program that simulates a large number of jai alai games and calculates the average winning percentage for each post position. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Pages: 1 2