Non-contact Race Program - Backgammon Forum - Discuss Backgammon Strategy, Clubs and Books

Two Plus Two Forums Sports and Games Chess and Other Board Games Backgammon Forum hosted by Bill Robertie.

Non-contact Race Program

Post Reply Subscribe

...

10-25-2010 , 07:07 PM

Taper_Mike

adept

Join Date: Sep 2009 Posts: 1,030

I have been working recently with a program that calculates the expected number of rolls remaining in a non-contact race.

The program does not consider the opponent’s position. It seeks only to minimize the number of rolls left for the player who is on roll. This means that it cannot adjust for last-roll cirmcumstances where a player needs doubles, nor can it modify its strategy based on the position of the doubling cube or gammon considerations.

For the most part, the program recommends moves that are spot on. I’ve learned, for instance, that in many bear-off situations where an ace can be played from either the three point or the two, it is better to have two checkers on the two point than one on the one (and the two point bare). Here are two examples:

X to play 5-1

-------------------------------------
Move . . . . . Rolls Remaining
-------------------------------------
4/off, 3/2 . . . . . 1.8642
4/off, 2/1 . . . . . 1.89198
4/off . . . . . . . . 1.91975
-------------------------------------

X to play 6-1

-------------------------------------
Move . . . . . Rolls Remaining
-------------------------------------
6/off, 3/2 . . . . 1.88889
6/off, 2/1 . . . . 1.90432
6/off, 4/3 . . . . 1.91975
6/off . . . . . . . 1.9375
-------------------------------------

Every now and again, however, the program comes up with a move that GNUBG rollouts will not confirm. In the position below, for example, my impulse (and GNUBG’s) is to slot the three point:

X to play 2-1

-------------------------------------
Move . . . . . Rolls Remaining
-------------------------------------
5/2 . . . . . . . . 10.1854
5/3, 4/3 . . . . . 10.1989
6/3 . . . . . . . . 10.2011
4/2, 4/3 . . . . . 10.2036
5/3, 5/4 . . . . . 10.2058
6/4, 5/4 . . . . . 10.2061
6/4, 6/5 . . . . . 10.2191
6/5, 4/2 . . . . . 10.2351
4/1 . . . . . . . . 10.2372
-------------------------------------

Does this match up with your experience? Is the program making errors?

Quote

10-25-2010 , 07:49 PM

Aaron W.

Carpal \'Tunnel

Join Date: Sep 2002 Posts: 30,132

Quote:

Originally Posted by Taper_Mike

If this is the case...

Quote:

Every now and again, however, the program comes up with a move that GNUBG rollouts will not confirm.

I don't think GNU is capable of "confirming" your values. The problem is that GNU *DOES* adjust for last-roll circumstances (and cubes, and that sort of thing), so it will not be able to accurately measure what roll is "best" on your scale.

There is a chance you can make this work correctly by putting one player behind in the race so that the other player is very likely to win, but not so far behind that the race is hopeless (otherwise, it will make no difference what is played). But I don't know how you would ever decide how to establish that window in some non-arbitrary way.

You should also give the player behind the cube so that GNU won't cube out the trailer.

Quote

10-25-2010 , 08:17 PM

Taper_Mike

adept

Join Date: Sep 2009 Posts: 1,030

Thanks, Aaron, for the reply.

My real interest is to confirm that I can trust the program to do what it advertises: calculate the expected number of rolls remaining. After a thousand or so bear-off runs, I have begun to think it does.

For instance, in the third position above, are the numbers correct? Is 5/2 really better than 6/3 fifteen times out of 100,000? I think it is.

Ultimately, duplicating the rollouts from GNUBG is not necessary. As you suggest, however, I have done my best to configure GNUBG so that it is neither influenced by gammons nor the cube. Obviously, with margins this slim, the number of trials needs to be large.

Quote

10-25-2010 , 08:43 PM

Aaron W.

Carpal \'Tunnel

Join Date: Sep 2002 Posts: 30,132

Quote:

Originally Posted by Taper_Mike

The only way I can think of confirming it is to do some calculations by hand, or by having someone else try to write a similar program. I guess you can do manual rollouts to see if the numbers are in the right ballpark, but you won't find out whether your numbers are correct.

I assume you're simply doing it recursively? It would seem that if you are, then it you spot check a couple small cases, it should be pretty safe.

Quote

10-26-2010 , 12:06 AM

Taper_Mike

adept

Join Date: Sep 2009 Posts: 1,030

Quote:

Originally Posted by Aaron W.

...do some calculations by hand, or [have] someone else try to write a similar program.

I have done the former. For about two dozen of the simplest positions, manual calculation duplicates exactly the program results. In fact, the only discrepencies occurred in two positions where my hand calculations were in error! The first two positions are typical of the more complex checking I've been able to do. As for your second suggestion, that would be ideal. Many others have written this program, so perhaps I'll be able to compare results.

Quote:

Originally Posted by Aaron W.

I assume you're simply doing it recursively?

You guessed it.

If you start with no checkers on the board, it is trivial that the expected number of rolls until all checkers are off the board is zero. So, backup one checker to the one point, and, again, trivially observe that the expected number of rolls until the game is over is one. So, back it up again. And so on. Eventually, you reach a position where the result is not obvious. Then you have to form an average of the expected number of rolls remaining after each of the twenty-one possible rolls, and add one. The good news is that previous computation will already have produced the numbers you need to work with.

Adademia has had some fun with this. There are some good cites I've found through Google. These two describe what my program is doing:

Enumerating Backgammon Positions: The Perfect Hash
By Arthur Benjamin and Andrew M. Ross
http://ccdl.libraries.claremont.edu/...OPTR=312&REC=3

Efficient Approximation of Backgammon Race Equities
By Michael Buro
http://skatgame.net/mburo/ps/bgequ.pdf

Quote

10-26-2010 , 10:03 AM

uberkuber

veteran

Join Date: Jul 2009 Posts: 3,032

Quote:

Originally Posted by Taper_Mike

For the most part, the program recommends moves that are spot on. I’ve learned, for instance, that in many bear-off situations where an ace can be played from either the three point or the two, it is better to have two checkers on the two point than one on the one (and the two point bare).

One obvious exception is when, let's say, you have 3 checkers left, on the 2, 3 and 6 points. Then you roll 6-1. It's obviously better to play 6/0 2/1 than 6/0 3/2.

Quote

10-26-2010 , 11:33 AM

MordellWeil

newbie

Join Date: May 2010 Posts: 33

You can check to see if GNUBg's estimate is the same as your prgram's. Under Analysis there is a race theory submenu. Here you can look at one-sided rollouts giving the effective pipcount for non-contact positions. If your program gives you the expected number of rolls to bearoff all checkers, then multiply this by 49/6 to get the EPC and compare. If you want to do this programmatically, you will have to look into the source code for GNUBg as, to my knowledge, the race theory numbers have not been exported to the embedded Python compiler.

By the way, is it a program you have coded yourself ? Or is it one of: Bearoff Quizmaster , Smoothy/Junior or BOINQ ? If it is BOINQ or Bearoff Quizmaster where can one get that now ?

Quote

10-26-2010 , 11:40 AM

MordellWeil

newbie

Join Date: May 2010 Posts: 33

Ok, maybe gnu's race theory doesn't provide enough significant digits to make this check possible, dont remmeber how many digits is presented.

Quote

10-26-2010 , 11:51 AM

MordellWeil

newbie

Join Date: May 2010 Posts: 33

GNUBg gives you the EPC's with 3 digits. With your 21 to play slotting the 3-pt gives a position with an EPC of 83.087. MAkeing the 3-pt gives a position with an EPC of 83.199 according to gnu (which uses a onesided rollout db)

Quote

10-26-2010 , 01:36 PM

#10

Taper_Mike

adept

Join Date: Sep 2009 Posts: 1,030

Mike's Rule for early and middle bear-off positions:

Two checkers on the two point is better than one on the one (and the two point bare).

Quote:

Originally Posted by uberkuber

One obvious exception is when, let's say, you have 3 checkers left, on the 2, 3 and 6 points. Then you roll 6-1. It's obviously better to play 6/0 2/1 than 6/0 3/2.

The exception makes the rule. It's hackneyed, but true. I have been surprised how strong this rule is. It may be that the increased utility of doubles two on the very next turn is the reason.

I have a score of examples where the rule works. Here is one more:

Quote

10-26-2010 , 01:55 PM

#11

Taper_Mike

adept

Join Date: Sep 2009 Posts: 1,030

Quote:

Originally Posted by MordellWeil

Thanks for this boon! I'll spend some time this week studying up on EPC and GNUBG. By the way, in the wee hours of the morning, I found a web site in the UK that gives a handful of results, and they all matched what my program is generating. The site gives source code for what is essentially the same program, written in a language called J:

http://www.vector.org.uk/?vol=24&no=2&art=peelle

Quote:

Originally Posted by MordellWeil

By the way, is it a program you have coded yourself ?

Yes, it is. I've been playing around in C++. It has reached the point where useful results can be generated from a program that is very much "under construction." As to the Trice program, I've been looking for it, too. Now, I'll have to be on the lookout for the others you mention!

Last edited by Taper_Mike; 10-26-2010 at 02:04 PM.

Quote

10-26-2010 , 02:16 PM

#12

Taper_Mike

adept

Join Date: Sep 2009 Posts: 1,030

Quote:

Originally Posted by MordellWeil

After playing 5/2 in the third position above, GNUBG gives an EPC of 83.183, hence its preference for 6/3. This is a discrepency I need to mull over.

Quote

10-26-2010 , 02:55 PM

#13

MordellWeil

newbie

Join Date: May 2010 Posts: 33

Quote:

Originally Posted by Taper_Mike

After playing 5/2 in the third position above, GNUBG gives an EPC of 83.183, hence its preference for 6/3. This is a discrepency I need to mull over.

Perhaps it would be worth to look into how the numbers in gnubg's onesided bearoff db is generated. Perhaps its not your program that is wrong, although intuitively it is easy to believe that the slot should givre the most effective position, but hey, stranger things has happened !

I just checked, and there is a keyboard shortcut Ctrl-E for evaluation. In Non/contact bearoff positions this will include info on eg. EPC. So probably easier than using the menus. Best of all would of course be if this was available from the commandline and outputting the numbers.

Quote

10-26-2010 , 03:39 PM

#14

Taper_Mike

adept

Join Date: Sep 2009 Posts: 1,030

Quote:

Originally Posted by MordellWeil

Perhaps its not your program that is wrong, although intuitively it is easy to believe that the slot should give the most effective position, but hey, stranger things has happened!

I'm working on a theory that we are both right! Somehow GNUBG is calculating a slightly differrent statistic than I am. I may have to take a look at GNUBG's source code, but that's a week's work by itself! The code is C, rather than C++.

Interestingly, if you play the position out a few times -- something everyone should do for this BEST OF ALL BEAR OFF POSITIONS -- you will find that 5/2 is a great play. One turn later, and thoughout most of the bearoff, the slot of the 3 point will then be preferred. It is only on the first play from this position that slotting the 2 point is slightly better.

Quote

10-27-2010 , 03:52 AM

#15

MordellWeil

newbie

Join Date: May 2010 Posts: 33

Quote:

Originally Posted by Taper_Mike

I'm working on a theory that we are both right! Somehow GNUBG is calculating a slightly differrent statistic than I am. I may have to take a look at GNUBG's source code, but that's a week's work by itself! The code is C, rather than C++.

Interestingly, if you play the position out a few times -- something everyone should do for this BEST OF ALL BEAR OFF POSITIONS -- you will find that 5/2 is a great play. One turn later, and thoughout most of the bearoff, the slot of the 3 point will then be preferred. It is only on the first play from this position that slotting the 2 point is slightly better.

I think it is intended to be the same thing. Note that gnubg's EPC estimates are from onesided cubeless rollouts.

GNUBg is a wonderful program, in particular if you want to study things in depth and its developers who has contributed time, coding and ideas to the project for free deserves a *lot* of credit. Having said that, you will probably find, if choosing to study the source code, that modern software design qualities like level of documentation, reusability, modularity etc. have not been given high priority

Quote

10-27-2010 , 07:50 PM

#16

Taper_Mike

adept

Join Date: Sep 2009 Posts: 1,030

I have played this OPTIMAL BEAROFF POSITION many times, and I am still struck by the recommendation to slot the two point. After this turn, slotting the 3 point will be preferred almost all the way to the end, even when the 2 point is bare.

Is slotting the 2 point better because twos do not play so well from the 6 point? Or, perhaps, is it because a roll of doubles 2 picks up enough immediate equity to make the 2 point better?

GNUBG Position ID: uO8PAAC47w8AAA Hash X: 54213 Hash O: 54213

--------------------------------------------------------
No. . Move . . . . . Rolls Remaining
--------------------------------------------------------
1. 5/off, 4/2 . . . . 9.73932
2. 6/4, 5/off . . . . 9.74504
3. 5/off, 5/3 . . . . 9.76374
--------------------------------------------------------

White plays 5/off, 4/2.

Quote

10-27-2010 , 08:11 PM

#17

Aaron W.

Carpal \'Tunnel

Join Date: Sep 2002 Posts: 30,132

Quote:

Originally Posted by Taper_Mike

Is slotting the 2 point better because twos do not play so well from the 6 point? Or, perhaps, is it because a roll of doubles 2 picks up enough immediate equity to make the 2 point better?

I think you can find the answer to that question if you did a manual next roll analysis.

Quote

10-27-2010 , 09:32 PM

#18

Taper_Mike

adept

Join Date: Sep 2009 Posts: 1,030

Quote:

Originally Posted by Aaron W.

I think you can find the answer to that question if you did a manual next roll analysis.

I'm not sure what you mean. Hopefully, you're not suggesting pencil and paper calculation!

Still, is is not intriguing that the five point is stacked, and yet the play that leads to the lowest expected number of rolls remaining is to play off the much less-stacked four point? And the six point is -- by these standards -- over-stacked!

Quote

10-27-2010 , 09:40 PM

#19

Aaron W.

Carpal \'Tunnel

Join Date: Sep 2002 Posts: 30,132

Quote:

Originally Posted by Taper_Mike

I'm not sure what you mean. Hopefully, you're not suggesting pencil and paper calculation!

Not precisely. What i mean is that you can look at the next roll scenarios for both 5/off 5/3 and 5/off 4/2. Since the expected number of rolls is some average of those situations, you should be able to look at the possibilities from each situation side-by-side and see which situations favor one play over the other and by how much. Since your values were constructed recursively, these numbers should already be calculated and stored somewhere, and it's just a matter of pulling it out and looking at it.

If there's an effect (as you suggest) that a single roll plays significantly better in the next roll but everything else is just a wash, you should be able to see that in this type of comparison. It could be something less extreme, and simply a matter of several rolls simply being better, but even this will be evident upon a direct comparison.

Quote

10-27-2010 , 09:43 PM

#20

mute

Carpal \'Tunnel

Join Date: Apr 2005 Posts: 11,815

The positions with the 753 structure are hardly worth spending a lot time on over the board or off the board (imo), but I think that slotting the 2-point looks more reasonable with 2-1 than with 5-2.

In the first two positions (61 and 51) key is getting 2-2 as a working double next roll.

Quote

10-27-2010 , 10:56 PM

#21

Taper_Mike

adept

Join Date: Sep 2009 Posts: 1,030

Quote:

Originally Posted by Aaron W.

If there's an effect (as you suggest) that a single roll plays significantly better in the next roll but everything else is just a wash, you should be able to see that in this type of comparison.

I took a look at the subsequent rolls, and there's not much that is special about 2-2. The computer plays it the way you would: 6/off, 2/off. Equities don't change very much.

This makes me think the advantage is not just with 2-2, but with all rolls containing a 2. If you don't put a checker on the 2 point right away, it is hard to get a checker there later. Consider: 4, 5, and 6 bear off, 3 plays from the 6 point, 1 is used to smooth, and 2 is the odd man out. Moving 6/4 simply reinforces a four point that already has checkers. Yet, often that is the best 2, because the six point is heavily overstacked.

Quote

10-27-2010 , 11:11 PM

#22

Taper_Mike

adept

Join Date: Sep 2009 Posts: 1,030

Quote:

Originally Posted by mute

I can understand your thinking. Hyperbole aside, even though Kit Woolsey and Walter Trice have both called this the best bearoff position, it doesn't occur very often.

What I have found valuable, however, is to roll the thing out. Because half the home board points are open when you start, many instructive positions arise, with occassionally difficult decisions. I have learned more than I thought I would.

The other thing to take away from this position is that it is better to slightly overstack the six point in a close race than it is to smoothly bear in on the 4, 5 and 6 points. I've used my program to determine the optimal bearoff position for each pip count between 1 and 90, and those in the upper part of the range are often characterized by a wedge-shaped group of checkers with the thickest part on the six point. An example is 0-1-2-3-4-5, the ideal position for a pip count of 70 with no checkers borne off.

Last edited by Taper_Mike; 10-27-2010 at 11:18 PM.

Quote

12-05-2010 , 12:19 AM

#23

Taper_Mike

adept

Join Date: Sep 2009 Posts: 1,030

Many thanks to all of those who helped me think through this problem. The program I'm writing is now able to handle positions with checkers on or below the 9 point. There are approximately 1.3 million such positions! My plan right now is to stop at the 12 point, where there are over 17 million positions. But, I'll probably get carried away, so...

Anyway, with so many positions stored in the data file, it is not possible to bring them into memory all at once. Instead, I've created a paging system to bring in about 25,000 positions at a time (on an as needed basis). But there is the rub. I discovered a bug in the paging system! It was subtle, affecting something less than 3% of the positions, but, of course, it caused all the problems discussed in this thread. Here is the bottom line:

IT IS INCORRECT TO SLOT THE TWO POINT IN THE POSITIONS DISCUSSED HERE!
I know you all knew that already. That's what you've been telling me in this thread. Nevertheless, here are the latest results. Notice that 5/2 is worse than 6/3 by a little more than one part in 1,000:

Code:

GNUBG Match ID: IAEFAAAAAAA   Position ID: uO8PAAC47w8AAA

    +24-23-22-21-20-19------18-17-16-15-14-13-+  Player O
    |          O  O  O |   |                  |  0 points
    |          O  O  O |   |                  |
    |          O  O  O |   |                  |
    |             O  O |   |                  |
    |             O  7 |   |                  |
    |                  |BAR|                  |v Cash game (Cube 1)
    |             X  7 |   |                  |
    |             X  X |   |                  |
    |          X  X  X |   |                  |
    |          X  X  X |   |                  |  Rolled 2-1
    |          X  X  X |   |                  |  0 points
    +-1--2--3--4--5--6-------7--8--9-10-11-12-+  Player X

X to play 2-1
-------------------------------------------------------
 No.  Move            Rolls Remaining   Difference (%)
-------------------------------------------------------
  1.  6/3             10.174
  2.  5/2             10.1858           -0.116551%
  3.  5/3, 4/3        10.1877           -0.134816%
  4.  6/4, 6/5        10.1892           -0.14971%
  5.  6/4, 5/4        10.192            -0.177274%
  6.  5/3, 5/4        10.1954           -0.21073%
  7.  6/5, 4/2        10.1963           -0.219575%
  8.  4/1             10.2043           -0.298388%
  9.  4/2, 4/3        10.2086           -0.339946%
-------------------------------------------------------

Here is another roll that was discussed in this thread. Interestingly, slotting the 3 point is still incorrect in this one:

Code:

GNUBG Match ID: IAEFAAAAAAA   Position ID: uO8PAAC47w8AAA

    +24-23-22-21-20-19------18-17-16-15-14-13-+  Player O
    |          O  O  O |   |                  |  0 points
    |          O  O  O |   |                  |
    |          O  O  O |   |                  |
    |             O  O |   |                  |
    |             O  7 |   |                  |
    |                  |BAR|                  |v Cash game (Cube 1)
    |             X  7 |   |                  |
    |             X  X |   |                  |
    |          X  X  X |   |                  |
    |          X  X  X |   |                  |  Rolled 5-2
    |          X  X  X |   |                  |  0 points
    +-1--2--3--4--5--6-------7--8--9-10-11-12-+  Player X

X to play 5-2
-------------------------------------------------------
 No.  Move            Rolls Remaining   Difference (%)
-------------------------------------------------------
  1.  6/4, 5/off      9.68483
  2.  5/off, 5/3      9.69261           -0.080283%
  3.  5/off, 4/2      9.69675           -0.123065%
  4.  6/1, 5/3        9.71876           -0.350273%
  5.  6/1, 6/4        9.7266            -0.431287%
  6.  6/1, 4/2        9.73864           -0.555572%
-------------------------------------------------------

Quote

12-05-2010 , 10:28 AM

#24

Robertie

old hand

Join Date: May 2004 Posts: 1,954

You shouldn't just be thinking about which point to slot, but also about which point to unstack. The 6-point is loaded in your two examples, and you need to be smoothing out your distribution.

Last edited by Robertie; 12-05-2010 at 10:31 AM. Reason: spelling

Quote

Post Reply Subscribe

...