Spectacular Seven

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.

About these ads

Pages: 1 2

5 Responses to “Spectacular Seven”

  1. [...] Praxis – Spectacular Seven By Remco Niemeijer In today’s Programming Praxis exercise our task is to run a simulation of a ballgame to see if the scoring [...]

  2. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2010/05/04/programming-praxis-spectacular-seven/ for a version with comments):

    import Control.Applicative
    import Control.Monad
    import Data.List
    import System.Random
    
    match :: Int -> [(a, Int)] -> Int -> [(a, Int)]
    match ps ~(x:y:r) w = (p,s + if ps > 7 then 2 else 1) : r ++ [c]
        where ((p,s), c) = if w == 0 then (x,y) else (y,x)
    
    game :: IO Int
    game = f 0 (zip [1..8] [0,0..]) . randomRs (0,1) <$> newStdGen
           where f ps a ~(x:xs) = maybe (f (ps+1) (match ps a x) xs) fst $
                                  find ((>= 7) . snd) a
    
    simulate :: Int -> IO [Float]
    simulate n = (\ws -> map (\x -> 100 * (l x - 1) / l ws) . group .
                         sort $ ws ++ [1..8]) <$> replicateM n game
                 where l = fromIntegral . length
    
  3. Gambiteer said
    ;; for some reason a circular buffer seems most natural
    
    (define (seven-2 n)
      (let ((teams (list 0 1 2 3 4 5 6 7))
    	(scores (make-vector 8 0))
    	(wins   (make-vector 8 0)))
    
        (define last-pair
          (lambda (x)
    	(if (pair? (cdr x))
    	    (last-pair (cdr x))
    	    x)))
        
        (define (team-score team)
          (vector-ref scores team))
    
        (define (increment-wins! team)
          (vector-set! wins team (fx+ (vector-ref wins team) 1)))
    
        (define (increment-score! team score)
          (vector-set! scores team (fx+ (vector-ref scores team) score)))
    
        (define (reset-all-scores teams)
          (do ((i 0 (fx+ i 1))
    	   (teams teams (cdr teams)))
    	  ((fx= i 8) teams)
    	(vector-set! scores (car teams) 0)
    	(set-car! teams i)))
    
        (define (swap-teams! teams)
          (let ((temp (car teams)))
    	(set-car! teams (cadr teams))
    	(set-car! (cdr teams) temp)))
        
        (set-cdr! (last-pair teams) teams)
        
        (let loop ((k n)
    	       (teams teams)
    	       (points 0))
          (cond ((fxzero? k) ; simulation ends
    	     wins)
    	    ((fx<= 7 (team-score (car teams)))  ;; previous point winner wins game.
    	     (increment-wins! (car teams))
    	     (loop (fx- k 1) (reset-all-scores teams) 0))
                ((fxzero? (random-integer 2)) ; current winner wins point
    	     (increment-score! (car teams) (if (fx<= 7 points) 2 1))
    	     (swap-teams! teams)
    	     (loop k (cdr teams) (fx+ points 1)))
                (else ; current challenger wins point
    	     (increment-score! (cadr teams) (if (fx<= 7 points) 2 1))
    	     (loop k (cdr teams) (fx+ points 1)))))))
    
  4. Mike said

    In python:

    jai_alai_match() accepts a list of ratings to indicate the relative strengths of the players. The probablility of a player winning a point is the ratio of the players rating to the sum of both players ratings (see the threshold calculation below). The default is that each player is equally likely to win a point.

    from random import random
    
    ID  = 0
    RTG = 1
    PTS = 2
    
    def jai_alai_match(rating=[100]*8):
        queue = [[n,rating[n],0] for n in range(8)]
        pts = 0
        player1 = queue.pop(0)
        while player1[PTS] < 7:
            player2 = queue.pop(0)
            
            threshold = player1[RTG]/float(player1[RTG] + player2[RTG])
            if random() > threshold:
                player1,player2 = player2,player1
                
            player1[PTS] += (1 if pts<8 else 2)
            queue.append(player2)
    
            pts += 1
    
        return [player1] + queue
    
    def simulate(reps=10000,ratings=None):
        hist = [0]*8
        for n in range(reps):
            result = jai_alai_match(ratings) if ratings else jai_alai_match()
            winner = result[0]
            hist[winner[ID]] += 1
    
        for h in hist:
            print "{0:5.2}".format(h*100.0/reps),
        print
        
    #test
    simulate()
    simulate(ratings=[ 100, 100, 100, 100, 100, 100, 100, 160 ])
    
  5. slabounty said

    A Ruby implementation. There’s quite a few improvements to make, but I’m getting tired of looking at it ;-). This is quite a few more lines than the other implementations, but maybe someone will find it useful.

    I haven’t posted here before, but it looks like a great site.

    require 'getoptlong'
    
    class Team
        attr_reader :team_number
        attr_accessor :score
        attr_accessor :games_won
    
        def initialize(team_number)
            @score = 0
            @games_won = 0
            @team_number = team_number
        end
    
        def <=> (t)
            if @team_number < t.team_number 
                return -1
            elsif @team_number == t.team_number
                return 0
            else
                return 1
            end
        end
    end
    
    class Queue < Array
        alias :enqueue :<<
        alias :dequeue :shift
    end
    
    def sim_game(teams)
    
        # Sort the teams so they're in the initial starting order and
        # reset their scores to 0.
        teams.sort!
        teams.each { |t| t.score = 0 }
    
        winner = teams.dequeue
        total_points = 0
    
        while winner.score < 7 do
            challenger = teams.dequeue
            if rand <= 0.5 then
                winner.score += (total_points <= 7) ? 1 : 2
                teams.enqueue challenger
            else
                challenger.score += (total_points <= 7) ? 1 : 2
                teams.enqueue winner
                winner = challenger
            end
            total_points += 1
        end
    
        # Increment the winners game count.
        winner.games_won += 1
    
        # Put the winner back on the queue. Doesn't matter that it's at the end, as we'll resort later.
        teams.enqueue winner 
    end
    
    if __FILE__ == $PROGRAM_NAME
    
    # Set up the command line options
    opts = GetoptLong.new(
        ["--num_games", "-n", GetoptLong::REQUIRED_ARGUMENT],
        ["--verbose", "-v", GetoptLong::NO_ARGUMENT]
        )
    
    # Set the default values for the options
    num_games = 100
    $verbose = false
    
    # Parse the command line options. If we find one we don't recognize
    # an exception will be thrown and we'll rescue with a message.
    begin
        opts.each do | opt, arg|
            case opt
            when "--num_games"
                num_games = arg.to_i
            when "--verbose"
                $verbose = true
            end
        end
    rescue
        puts "Illegal command line option."
        exit
    end
    
    # Create the teams and initialize them.
    num_teams = 8
    teams = Queue.new
    1.upto(num_teams) do |t|
       teams.enqueue(Team.new(t))
    end
    
    # Run the simulation.
    1.upto(num_games) do
        sim_game(teams)
    end
    
    # Resort the teams and print out the winning percentages.
    teams.sort!
    teams.each do |t|
        puts "Team #{t.team_number} winning percentage is #{(t.games_won.to_f / num_games.to_f) * 100.0}"
    end
    
    end
    
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 632 other followers

%d bloggers like this: