GNU Backgammon

Forum Archive : GNU Backgammon

 
How rollouts work

From:   Gary Wong
Address:   gary@cs.arizona.edu
Date:   28 July 1999
Subject:   Re: How Reliable are Rollouts? [Was: Difficult Crawford checker play]
Forum:   rec.games.backgammon
Google:   wtk8rkfjb0.fsf@brigantine.CS.Arizona.EDU

> What's the basis for having any confidence in a rollout?   To make a
> thorough statistical evaluation of a position (which I suppose rollouts
> have been invented for) one needs to play each roll out of the 21
> possible rolls after every roll.  How may rolls does an average game
> take?  Due to the limitations of the output of my calculator let's say 38
> rolls by each player, a total of 76.  The number of positions to be
> evaluated is 21^76 = 37 * 10^99.

Whoa... being thorough is one thing, but performing over a googol
evaluations to roll out a single position is quite another!  Fortunately we
don't have to evaluate every position that could potentially result from
each play to come up with an answer we can have some reasonable confidence
in; by taking a shortcut here and there (and adding a dose of sampling
theory) we can get away with much less work than that.

The million dollar question is simple enough: out of all the games that
could result from playing this position, how many do we win (and how many
of our wins and losses are gammons, and how many are backgammons)?  The
model is exactly the same as if we had an urn with a googol balls in it
(it's a big urn), and many of the balls have "win" written on them, and
some say "gammon loss", and if we look hard enough there are a few that
read "backgammon win", and so on.  (Balls and urns are to probability
theorists what teapots and chequerboards are to computer graphics
researchers, or "squeamish ossifrage" is to cryptographers -- they seem to
come with the territory.) Instead of having the patience to count the
googol balls, we just give the urn a really good shake and then pull 100
balls out without looking, and say for instance "Well, I got 53 wins, 31
losses, 9 gammon wins, 6 gammon losses, and a backgammon win -- looks like
my equity's roughly +0.26." and go home. If we were a bit more thorough
(but there's still a long way between my "thorough" and yours!), we could
go a bit further and figure out that by cheating and measuring the sample
proportions instead of the population proportions, we introduced a standard
error of 0.06 into our result. (Of course, the trick is to select a sample
size that's big enough that you reduce the standard error to a tolerable
level, but small enough that the answer arrives before you get bored.)

It will come as no surprise that a rollout with a limited number of trials
follows exactly the same procedure.  It's sufficient to say that the
proportion of wins/gammons etc. that come up when Jellyfish plays against
itself (say) 1296 times, aren't likely to vary all that much from the
proportion we would get if we measured the proportion of results in every
game we could possibly get of Jellyfish playing against itself.  (Of
course, there may still be some doubt whether the results of JF vs. JF are
representative of the results of a perfect player vs. a perfect player, or
of you vs. Joe Average, but that's another story.)

> The correct answer about the rollout algorithm used by bots should come
> from their creators, but it's likely to be a trade secret.

Well, not all bot creators trade them, and they don't all keep secrets! :-)
In GNU Backgammon (ftp://ftp.cs.arizona.edu/people/gary/gnubg-0.0.tar.gz),
the function Rollout() in eval.c implements the procedure described above,
with the following improvements:

 * Truncation: instead of rolling out all the way to the end of the game,
     it can stop and pretend its evaluation after a few plies is perfect.
     This may obviously introduce some amount of systematic error, but
     in practice this may not matter because:
       - it makes rollouts much faster, which means you can do more of
         them (and thus trade sampling error for systematic error);
       - different positions will be reached in different trials, so
         the correlation between errors in each trial weakens and the
         errors cancel out to some extent;
       - if you are rolling out the positions after making different
         plays, then any remaining systematic error between the two
         rollouts is likely to be somewhat correlated and so the
         error in the comparison between the plays is hopefully
         small.  This implies that truncated rollouts are better for
         estimating _relative_ equity ("which is the better move here,
         13/10*/9 or 13/10* 6/5*?") than _absolute_ equity ("at this
         match score I need 29% wins to accept a dead cube; can I
         take in this position?").

 * Race database truncation: when the game enters its 2-sided bearoff
     database, gnubg can estimate the probability of winning from that
     position with no error at all (it can play and evaluate endgame
     positions perfectly), which saves time and avoids introducing the
     errors that can result from large equity variances at the end of
     the game.

 * Variance reduction: when using lookahead evaluations, it can reduce
     errors by making use of the equity difference from one ply to the
     next.  (This can be interpreted as either cancelling out the estimated
     "luck" (ie. the difference in equity evaluations before and after
     rolling) or using subsequent evaluations to estimate the error in
     prior ones; the two views are equivalent).  gnubg automatically
     performs variance reduction when looking ahead at least one ply.

 * Stratified sampling: uses quasi-random number generation instead of
     pseudo-random number generation (this is a standard technique in Monte
     Carlo simulations where having a near-perfect uniform distribution in
     your sample is more important than unpredictability).  gnubg only
     stratifies the first 2 plies of a rollout, though it would be easy
     enough to extend it to the remainder.

There are undoubtedly other possible heuristics, but I have only
implemented the above.  This description has glossed over many of the finer
points that are involved -- if you are interested in the details I
recommend that you examine the source code referred to above, or read some
earlier articles posted here that describe various topics with more
precision.  Look for articles by Michael Zehr, David Montgomery, Chuck
Bower and Brian Sheppard for starters.

Cheers,
Gary.
 
Did you find the information in this article useful?          

Do you have any comments you'd like to add?     

 

GNU Backgammon

Analyzing GamesGrid matches  (Roy Passfield, Dec 2001) 
Batch analysis tool  (Øystein Johansen, June 2004)  [GammOnLine forum]
Cache size  (Ned Cross+, Mar 2004)  [GammOnLine forum]
Compiling for Windows  (Øystein Johansen, Jan 2002) 
Edit mode removing checker from bar  (Scott Steiner+, May 2003) 
Entering an annotated match  (Albert Silver, Dec 2003)  [GammOnLine forum]
Error rates: Gnu vs. Snowie  (Raccoon, Mar 2006)  [GammOnLine forum]
Even-ply/odd-ply effect  (Raccoon, Nov 2004) 
Even-ply/odd-ply effect  (Tom Keith+, Oct 2003) 
Even-ply/odd-ply effect  (Scott Steiner+, Dec 2002) 
Filter settings  (Robert-Jan Veldhuizen, Nov 2004)  [GammOnLine forum]
Gnu 0.13 versus Jellyfish and Snowie  (Torsten Schoop, Aug 2003) 
Gnu 0.13 vs. Snowie 4  (Albert Silver, June 2003) 
Gnu 0.14 vs. Jellyfish  (Michael Howard+, July 2003) 
Gnu versus Snowie and Jellyfish  (Michael Depreli, Oct 2005) 
How luck factor is calculated  (Gregg Cattanach, Aug 2002) 
How rollouts work  (Gary Wong, July 1999) 
How to enter an illegal move  (Øystein Johansen, Aug 2003)  [GammOnLine forum]
Importing .gam files  (PAR+, Mar 2005) 
Importing PartyGammon matches  (rew+, July 2006) 
Improving your game using GnuBG  (D.U.G.+, Nov 2002) 
Installing on Windows  (maareyes, Oct 2001) 
Interpreting JSD's  (Adrian Wright+, Feb 2005)  [GammOnLine forum]
JSD's and confidence intervals  (Daniel Murphy+, Jan 2005) 
Logging rollouts  (Øystein Johansen, Oct 2004)  [GammOnLine forum]
Luck rate  (Kees van den Doel+, May 2002) 
MWC versus Equity (EMG)  (Ken+, Apr 2005)  [GammOnLine forum]
Manually entering first roll  (Andreas Graf+, Apr 2005) 
Match equity tables  (Raccoon, July 2005)  [GammOnLine forum]
Personal reflections  (Louis Nardy Pillards, Sept 2002) 
Playing two computers against each other  (Stanley E. Richards+, Mar 2008)  [GammOnLine forum]
Python scripting  (Øystein Johansen+, Nov 2004) 
Quasi-random dice in rollouts  (Ian Shaw, Mar 2004)  [GammOnLine forum]
Question marks in game list  (Jim Segrave, July 2005) 
Questions and answers  (Jim Segrave+, Jan 2003) 
Questions and answers  (Jørn Thyssen, Aug 2002) 
Restarting a rollout with different settings  (Jim Segrave, Apr 2005)  [GammOnLine forum]
Restarting a rollout with different settings  (Robert-Jan Veldhuizen, Apr 2004)  [GammOnLine forum]
Rollout settings  (geoff arnold+, Apr 2007) 
Rollout settings  (Stick+, Nov 2005)  [GammOnLine forum]
Rollout settings  (Robert-Jan Veldhuizen, Mar 2004)  [GammOnLine forum]
Rollout settings  (Ian Dunstan, Aug 2003)  [GammOnLine forum]
Rollout settings for the impatient  (Robert-Jan Veldhuizen, June 2004)  [GammOnLine forum]
Running rollouts in background  (Bruce+, Apr 2004)  [GammOnLine forum]
Saving rollout results from command-line interface  (Jeremy Bagai+, Apr 2006)  [GammOnLine forum]
Saving rollouts  (Mislav Radica+, May 2006)  [GammOnLine forum]
Setting GnuBG's playing strength  (JP White, Sept 2001) 
Setting skill level  (Jim Segrave, Apr 2004) 
Setting up and saving a rollout  (Albert Silver, Dec 2003)  [GammOnLine forum]
What's GNU?  (Gary Wong, Oct 2001) 
Which player is player 0?  (Neil Kazaross+, Oct 2004)  [GammOnLine forum]

[GammOnLine forum]  From GammOnLine       [Long message]  Long message       [Recommended reading]  Recommended reading       [Recent addition]  Recent addition
 

  Book Suggestions
Books
Cheating
Chouettes
Computer Dice
Cube Handling
Cube Handling in Races
Equipment
Etiquette
Extreme Gammon
Fun and frustration
GNU Backgammon
History
Jellyfish
Learning
Luck versus Skill
Magazines & E-zines
Match Archives
Match Equities
Match Play
Match Play at 2-away/2-away
Miscellaneous
Opening Rolls
Pip Counting
Play Sites
Probability and Statistics
Programming
Propositions
Puzzles
Ratings
Rollouts
Rules
Rulings
Snowie
Software
Source Code
Strategy--Backgames
Strategy--Bearing Off
Strategy--Checker play
Terminology
Theory
Tournaments
Uncategorized
Variations

 

Return to:  Backgammon Galore : Forum Archive Main Page