Analysis of Non-Contact Endgames (Long)
Alan Haas
I would like to see backgammon theory issues discussed to a
greater extent than what is currently seen in rec.games.
backgammon. One theory issue that interests me is roll off positions.
I am currently at phase one in my analysis of this area. The way I
started to look at roll off positions is to look at the game as
straight pip count. Phase one makes the assumption that there
will be no wastage of pip count. If x and y are the two pip
counts of the position, then I define P(x,y) as the probability
that player x will win if it is player x's turn. The recursion
formula of
P(x,y) = (1/36)*sum (i=1,36) (1.0 - P(y,x-roll(i)))
can be seen. Here, roll(i) is the array of the values of the
count of the 36 possible rolls of the die. From this recursion
formula, I wrote a program to give P(x,y). (If this article
generates enough interest and there is a demand, then I will be
happy to post the program) What this program does not take into account
is
i) the use of the cube
ii) the amount of pips wasted in a bear off.
iii) positional advantage ( for me, this is the same as ii.)
The next step I took was to take into account the use of the
cube. This was done by setting P(x,y) = 1.0 if P(x,y) > .75.
By reworking the recursion formula from the bottom up, this takes into
account that you will drop if the opponent gains enough of an
upperhand after accepting the double to redouble in a drop
situation for you. The underlying assumption here is that all cubes
will be dropped if P(x,y) > .75. This is slightly unrealistic
due to escalation of cube value (ie. the person taking the
double may redouble later with you taking and thus possibly win
more than just double the original cube value). For some cases,
I believe it is worth taking the cube if P(x,y) > .75, though it will
be very! rare for me to knowingly take such a cube.
One question to be asked is what is the use of this
information. For me, the use is to get a "rough" idea if I
should take or drop a given double in roll off situation. Taking
into account pip wastage, this is a tool I use to get an idea of
break points in a given range to take or drop. As I have not
read backgammon books, I would be interested in comparing
values suggested by books for drop and take points of doubles
given just pip count.
This simple experiment was easy due to being able to avoid
the combinatorial explosion of considering every possible
position in a roll off. My next phase is to examine roll off
situations where all of the men are in the home court, a bear off
situation. Though computationally expensive, I see how this might
be doable. The information to be gained here is twofold. One is to
obtain a probability assessment for winning a given position. The
other is to know what moves to make in difficult situations so as to
minimize the expected number of rolls to bear off. After this
phase, I plan to extrapolate to non-contact positions in general.
Two possibilities I see to achieve this are to use a learning model to
obtain the best moves until a bear off situation is achieved, or to test
various intelligent heuristic.
What work has been done in general to analize bear off situations?
I imagine that the non-contact situations are fairly well
understood, so this may not generate too much interest. For the
most part (so I exaggerate :-) ), I have no trouble moving or
deciding what cube action to take. However, for those occasions
that arise that are not so obvious, I hope to better prepared on
knowing what to do.
Other areas that interest me are
i) cube decisions in a match at various match scores. This is
really interesting to me. Especially how you modify your cube
decisions to take into account playing stronger and weaker
players. I have an idea similar to the one I gave above for this
area.
ii) probability assessment of backgame situations.
iii) rules you give yourself when playing in a chouette. I have
discovered that discipline is VERY important.
********
Alan Haas: Fun is all the more so when it is shared.
ah...@ecn.purdue.edu
********
--
********
Alan Haas: Fun is all the more so when it is shared.
ah...@ecn.purdue.edu
********
Marc Ringuette
Applegate. The first, "race4.c", computes the expected rolls to
bear off for a single player. The second, "race2.c", is even cooler:
it computes the exact winning probability and correct cube action
for a given position for both players given no contact. Both programs
exhaustively compute answers which are guaranteed correct.
These are computationally intensive tasks, but the programs are speedy
and use a hashtable to cache results for later. Of course, race2.c,
because it considers both sides of the board, can't handle as many checkers
on the board. Try them on small positions and then work up to ones with
more checkers. Both are in vanilla C for Unix.
Enjoy!
-- Marc Ringuette (m...@cs.cmu.edu)
[ programs to follow in separate messages ]
Marc Ringuette
* value is expressed as the expected winnings for the player to move.
* This program only works for end-game situations (ie, no possible hits),
* doesn't consider the possibilities of a gammon. In addition, only
* relatively small positions are computationally tractable.
*
* The program's usage is:
*
* race2 [-i hash_in] [-o hash_out] [-r roll] position1 - position2
*
* where position1 and position2 are sequences of numbers specifying the
* number of men on point 1, 2, 3, ..., for player1 (the player to move),
* and player2 (the other player), and roll is either one or two numbers
* between 1 and 6. In addition, one of the positions may have a 'c' to
* indicate that that player "owns" the cube. If neither position contains a
* 'c', the cube is assumed to be in the middle.
*
* race2 reads in an initial hash table, performs its evaluations, and then
* writes out the new hash table. hash_in and hash_out both default to
* race2.hash. It then prints out the expected value of the game for the
* first player. In addition, if a roll is specified, it prints the expected
* value of the position after each way of playing that roll, and then
* repeats the best play.
*
* An example:
*
* $ race2 4 0 2 c - 5
* initial hash stats: entries 48421 overwrites 0
* Eval <c 9|4 0 2 ... 5|10>...
* .....................
* Undoubled: 0.391289 Double accepted: 0.227452 declined 1.000000
* Value = 0.391289
* hash stats: queries: 49 hits 49 entries 48421 overwrites 1
* $
*
* which tells us that in the position
* - - - - - -
* O
* O
* O
* O
* O
*
* X
* X
* X X
* c X X
* - - - - - -
*
* X should not double, because to do so would reduce his expected winnings
* from (cubeval) * $.39 to (cubeval) * .23
*
*/
#include <stdio.h>
#include <sys/file.h>
#define INNERSIZE (6)
#define OUTERSIZE (6)
#define BOARDSIZE (INNERSIZE + OUTERSIZE + OUTERSIZE + INNERSIZE)
#define NSLOTS (BOARDSIZE+2)
#define NPIECES_SIDE (15)
#define NPIECES (NPIECES_SIDE + NPIECES_SIDE)
typedef struct position {
int toplay;
int cube;
struct board {
unsigned char maxloc;
unsigned char npieces[NSLOTS];
} player[2];
} position;
#define OTHER(p) (1-(p)->toplay)
#define CUBE_MIDDLE (-1)
#define CAN_DOUBLE(p) ((p)->cube == CUBE_MIDDLE || (p)->cube == (p)->toplay)
#define BIGVALUE (1e10)
int debug;
int depth = 0;
int quiet = 0;
char *hashin = "race2.hash";
char *hashout = "race2.hash";
int roll1 = 0, roll2 = 0;
#define DEPTH_INDENT (" "+20-depth)
char *sbrk();
double eval();
double pos_eval();
double double_val();
double best_move_val();
double best_val_double();
double best_val_notdouble();
int hash_queries = 0;
int hash_hits = 0;
int hash_entries = 0;
int hash_overwrites = 0;
main (ac, av)
int ac;
char **av;
{
position p;
double val;
initialize();
parseargs (ac, av, &p);
if (hashin) {
read_hash(hashin);
}
printf ("Eval <");
print_pos (&p);
printf (">...\n");
val = eval(&p);
printf ("Value = %f\n",val);
if (roll1) {
list_moves (&p, roll1, roll2);
}
printf ("hash stats: queries: %d hits %d entries %d overwrites %d\n",
hash_queries, hash_hits, hash_entries, hash_overwrites);
if (hashout) {
write_hash(hashout);
}
return 0;
}
double eval (p)
position *p;
{
double val;
unsigned int w1, w2;
hash_compress (p, &w1, &w2);
if (!hashcheck (w1, w2, &val) || depth == 0) {
if (debug) {
printf ("%s<", DEPTH_INDENT);
print_pos (p);
printf (">\n");
}
depth++;
val = pos_eval (p);
depth--;
if (debug) {
printf ("%s==> %f\n", DEPTH_INDENT, val);
}
hashstore (w1, w2, val);
} else {
if (debug) {
printf ("%s<", DEPTH_INDENT);
print_pos (p);
printf ("> ==> %f", val);
}
}
return val;
}
double pos_eval (p)
position *p;
{
double val1, val2;
int d1, d2;
if (p->player[OTHER(p)].npieces[0] == NPIECES_SIDE) {
return -1.0;
}
val1 = 0.0;
for (d1=6; d1>=1; d1--) {
val1 += best_move_val (p, d1, d1);
if (depth == 1 && !quiet) {
putchar ('.'); fflush (stdout);
}
for (d2=d1+1; d2<=6; d2++) {
val1 += 2.0 * best_move_val (p, d1, d2);
if (depth == 1 && !quiet) {
putchar ('.'); fflush (stdout);
}
}
}
val1 /= 36.0;
if (depth == 1 && !quiet) {
printf ("\nUndoubled: %f",val1);
}
if (CAN_DOUBLE(p)) {
val2 = double_val (p);
if (val2 > val1) {
val1 = val2;
}
} else {
if (depth == 1 && !quiet) {
printf (" cannot double\n");
}
}
return val1;
}
double double_val (p)
position *p;
{
int oldcube;
double val;
oldcube = p->cube;
p->cube = OTHER(p);
val = 2.0 * eval(p);
p->cube = oldcube;
if (depth == 1 && !quiet) {
printf (" Double accepted: %f declined %f\n",val,1.0);
}
if (val > 1.0) {
/* the opponent would decline */
val = 1.0;
}
return val;
}
double best_move_val (p, d1, d2)
position *p;
int d1, d2;
{
double v1, v2;
if (d1 == d2) {
return best_val_double(p, d1);
} else {
v1 = best_val_notdouble(p, d1, d2);
v2 = best_val_notdouble(p, d2, d1);
return v1 > v2 ? v1 : v2;
}
}
double best_val_double (p, die)
position *p;
int die;
{
int from1, from2, from3, from4;
int to1, to2, to3, to4;
double maxval = -BIGVALUE;
double val;
int me = p->toplay;
struct board *myboard = &p->player[me];
int maxloc = myboard->maxloc;
for (from1=0; from1<=maxloc; from1++) {
if (domove (myboard, from1, die, &to1)) {
for (from2=0; from2<=from1; from2++) {
if (domove (myboard, from2, die, &to2)) {
for (from3=0; from3<=from2; from3++) {
if (domove (myboard, from3, die, &to3)) {
for (from4=0; from4<=from3; from4++) {
if (domove (myboard, from4, die, &to4)) {
p->toplay = OTHER(p);
val = - eval(p);
p->toplay = me;
if (val > maxval) maxval = val;
unmove (myboard, from4, to4);
}
}
unmove (myboard, from3, to3);
}
}
unmove (myboard, from2, to2);
}
}
unmove (myboard, from1, to1);
}
}
return maxval;
}
double best_val_notdouble (p, die1, die2)
position *p;
int die1, die2;
{
int from1, from2;
int to1, to2;
double maxval = -BIGVALUE;
double val;
int me = p->toplay;
struct board *myboard = &p->player[me];
int maxloc = myboard->maxloc;
for (from1=0; from1<=maxloc; from1++) {
if (domove (myboard, from1, die1, &to1)) {
for (from2=0; from2<=from1; from2++) {
if (domove (myboard, from2, die2, &to2)) {
p->toplay = OTHER(p);
val = - eval(p);
p->toplay = me;
if (val > maxval) maxval = val;
unmove (myboard, from2, to2);
}
}
unmove (myboard, from1, to1);
}
}
return maxval;
}
domove (b, from, die, pto)
struct board *b;
int from;
int die;
int *pto;
{
int to;
if (b->npieces[from] == 0) return 0;
if (from < die && b->maxloc > from) return 0;
if (from == die && b->maxloc > INNERSIZE) return 0;
to = from - die;
if (to < 0) to = 0;
b->npieces[from]--;
b->npieces[to]++;
if (from == b->maxloc && b->npieces[b->maxloc] == 0) {
set_maxloc(b);
}
*pto = to;
return 1;
}
unmove (b, from, to)
struct board *b;
int from;
int to;
{
b->npieces[from]++;
b->npieces[to]--;
if (from > b->maxloc) b->maxloc = from;
}
ie1, die2)
position *p;
int die1, die2;
{
depth++;
if (die2 == 0) {
list_moves_single (p, die1);
} else if (die1 == die2) {
list_moves_double (p, die1);
} else {
list_moves_notdouble (p, die1, die2);
}
}
list_moves_double (p, d)
position *p;
int d;
{
int from1, from2, from3, from4;
int to1, to2, to3, to4;
int me = p -> toplay;
struct board *myboard = &p -> player[me];
int maxloc = myboard -> maxloc;
int best1, best2, best3, best4;
double bestval = -BIGVALUE, val;
for (from1 = 0; from1 <= maxloc; from1++) {
if (domove (myboard, from1, d, &to1)) {
for (from2 = 0; from2 <= from1; from2++) {
if (domove (myboard, from2, d, &to2)) {
for (from3 = 0; from3 <= from2; from3++) {
if (domove (myboard, from3, d, &to3)) {
for (from4 = 0; from4 <= from3; from4++) {
if (domove (myboard, from4, d, &to4)) {
p -> toplay = OTHER (p);
val = -eval (p);
if (val > bestval) {
best1 = from1;
best2 = from2;
best3 = from3;
best4 = from4;
bestval = val;
}
printf ("%d/%d %d/%d %d/%d %d/%d = %f\n",
from1, d, from2, d,
from3, d, from4, d,
val);
p -> toplay = me;
unmove (myboard, from4, to4);
}
}
unmove (myboard, from3, to3);
}
}
unmove (myboard, from2, to2);
}
}
unmove (myboard, from1, to1);
}
}
printf ("Best: %d/%d %d/%d %d/%d %d/%d = %f\n",
best1, d, best2, d, best3, d, best4, d, bestval);
}
list_moves_notdouble (p, d1, d2)
position *p;
int d1, d2;
{
int from1, from2;
int to1, to2;
int me = p -> toplay;
struct board *myboard = &p -> player[me];
int maxloc = myboard -> maxloc;
int best1, best2;
double bestval = -BIGVALUE, val;
for (from1 = 0; from1 <= maxloc; from1++) {
if (domove (myboard, from1, d1, &to1)) {
for (from2 = 0; from2 <= from1; from2++) {
if (domove (myboard, from2, d2, &to2)) {
p -> toplay = OTHER (p);
val = -eval (p);
if (val > bestval) {
best1 = from1;
best2 = from2;
bestval = val;
}
printf ("%d/%d %d/%d = %f\n", from1, d1, from2, d2, val);
p -> toplay = me;
unmove (myboard, from2, to2);
}
}
unmove (myboard, from1, to1);
}
}
for (from2 = 0; from2 <= maxloc; from2++) {
if (domove (myboard, from2, d2, &to2)) {
for (from1 = 0; from1 <= from2; from1++) {
if (domove (myboard, from1, d1, &to1)) {
p -> toplay = OTHER (p);
val = -eval (p);
if (val > bestval) {
best1 = from1;
best2 = from2;
bestval = val;
}
printf ("%d/%d %d/%d = %f\n", from1, d1, from2, d2, val);
p -> toplay = me;
unmove (myboard, from1, to1);
}
}
unmove (myboard, from2, to2);
}
}
printf ("Best: %d/%d %d/%d = %f\n", best1, d1, best2, d2, bestval);
}
list_moves_single (p, d)
position *p;
int d;
{
int from1;
int to1;
int me = p -> toplay;
struct board *myboard = &p -> player[me];
int maxloc = myboard -> maxloc;
int best1;
double bestval = -BIGVALUE, val;
for (from1 = 0; from1 <= maxloc; from1++) {
if (domove (myboard, from1, d, &to1)) {
p -> toplay = OTHER (p);
val = -eval (p);
if (val > bestval) {
best1 = from1;
bestval = val;
}
printf ("%d/%d = %f\n", from1, d, val);
p -> toplay = me;
unmove (myboard, from1, to1);
}
}
printf ("Best: %d/%d = %f\n", best1, d, bestval);
}
set_maxloc (b)
struct board *b;
{
int i = -1;
int sum = 0;
do {
i++;
sum += b->npieces[i];
} while (sum < NPIECES_SIDE);
b->maxloc = i;
}
#define HASHSIZE 500009
#define HASHLOC(w1, w2) ((3121 * (w1) + 479 * (w2)) % HASHSIZE)
struct hashent {
unsigned int word1;
unsigned int word2;
float value;
} hashtable[HASHSIZE];
hash_compress (p, w1, w2)
position *p;
unsigned int *w1;
unsigned int *w2;
{
int i;
unsigned char *s, *send;
unsigned int v1 = 0, v2 = 0;
i = 0;
for (s = p->player[p->toplay].npieces,
send = s + p->player[p->toplay].maxloc; s <= send; s++) {
i += *s;
if (i < 32) {
v1 |= (1 << i);
} else {
v2 |= (1 << (i-32));
}
i++;
}
i = 54;
for (s = p->player[OTHER(p)].npieces,
send = s + p->player[OTHER(p)].maxloc; s <= send; s++) {
i -= *s;
if (i < 32) {
v1 |= (1 << i);
} else {
v2 |= (1 << (i-32));
}
i--;
}
/* By making sure v2 != 0, we avoid needing to initialize hashtable */
if (p->cube == CUBE_MIDDLE) {
v2 |= (3<<23);
} else if (p->toplay == p->cube) {
v2 |= (1<<23);
} else if (OTHER(p) == p->cube) {
v2 |= (1<<24);
}
*w1 = v1;
*w2 = v2;
}
hashcheck (w1, w2, val)
unsigned int w1, w2;
double *val;
{
int loc;
hash_queries++;
loc = HASHLOC(w1,w2);
if (hashtable[loc].word1 == w1 && hashtable[loc].word2 == w2) {
*val = hashtable[loc].value;
hash_hits++;
return 1;
}
return 0;
}
hashstore (w1, w2, val)
unsigned int w1, w2;
double val;
{
int loc;
loc = HASHLOC(w1,w2);
if (hashtable[loc].word2) {
hash_overwrites++;
} else {
hash_entries++;
}
hashtable[loc].word1 = w1;
hashtable[loc].word2 = w2;
hashtable[loc].value = val;
}
read_hash (s)
char *s;
{
int d = open (s, O_RDONLY, 0);
int loc;
struct hashent new;
if (d < 0) {
return;
}
for (;;) {
if (read (d, (char *) &new, sizeof (new)) <= 0) {
break;
}
loc = HASHLOC (new.word1, new.word2);
if (hashtable[loc].word2) {
hash_overwrites++;
} else {
hash_entries++;
}
hashtable[loc] = new;
}
close (d);
printf ("initial hash stats: entries %d overwrites %d\n",
hash_entries, hash_overwrites);
}
write_hash (s)
char *s;
{
int d = open (s, O_WRONLY|O_CREAT|O_TRUNC, 0666);
int i;
if (d < 0) {
perror (s);
exit (1);
}
for (i=0; i<HASHSIZE; i++) {
if (hashtable[i].word2) {
write (d, (char *) &hashtable[i], sizeof (struct hashent));
}
}
close (d);
}
initialize()
{
}
print_pos(p)
position *p;
{
int i;
if (p->cube == p->toplay) {
printf ("c ");
}
printf ("%d|",p->player[p->toplay].npieces[0]);
for (i=1; i<=p->player[p->toplay].maxloc; i++) {
printf ("%d ",p->player[p->toplay].npieces[i]);
if (i == INNERSIZE || i == INNERSIZE + OUTERSIZE) {
printf ("| ");
}
}
printf ("...");
for (i=p->player[OTHER(p)].maxloc; i>=1; i--) {
if (i == INNERSIZE || i == INNERSIZE + OUTERSIZE) {
printf ("| ");
}
printf (" %d",p->player[OTHER(p)].npieces[i]);
}
printf ("|%d",p->player[OTHER(p)].npieces[0]);
if (p->cube == OTHER(p)) {
printf (" c");
}
fflush (stdout);
}
parseargs (ac, av, p)
int ac;
char **av;
position *p;
{
int c;
extern int optind;
extern char *optarg;
int i;
int sum;
int j;
while ((c = getopt (ac, av, "dqi:o:r:?")) != EOF) switch (c) {
case 'd': debug++; break;
case 'q': quiet++; break;
case 'i': hashin = optarg; break;
case 'o': hashout = optarg; break;
case 'r': roll1 = optarg[0] - '0';
if (optarg[1]) roll2 = optarg[1] - '0';
break;
case '?':
default: usage (av[0]); exit (1);
}
p -> cube = CUBE_MIDDLE;
p -> toplay = 0;
for (i = 0; i < NSLOTS; i++) {
p -> player[0].npieces[i] = 0;
p -> player[1].npieces[i] = 0;
}
for (j = 0; j < 2; j++) {
i = 1;
sum = 0;
while (optind < ac && i < NSLOTS && sum < NPIECES_SIDE) {
if (av[optind][0] == 'c') {
p -> cube = j;
} else if (av[optind][0] == '-') {
optind++;
break;
} else {
p -> player[j].npieces[i] = atoi (av[optind]);
sum += p -> player[j].npieces[i];
i++;
}
optind++;
}
p -> player[j].npieces[0] = NPIECES_SIDE - sum;
set_maxloc (&p->player[j]);
}
}
usage (s)
char *s;
{
fprintf (stderr, "Usage: %s [-d] [-q] [-r roll] [-i hashin] [-o hashout] first_pos - second_pos\n",s);
}
Alan Haas
>In article <CHrFv...@noose.ecn.purdue.edu>,
>Alan Haas <ah...@rainbow.ecn.purdue.edu> wrote:
>>
>> What work has been done in general to analize bear off situations?
>>
>> I imagine that the non-contact situations are fairly well
>>understood, so this may not generate too much interest.
>Here are 2 problems from Tim Holland's "Better Backgammon" (Reiss Games,
>1974) that involve no contact positions that you might test your
>program with:
> . X X . . . | X doubles. Should O accept?
> O O . . . . |
> X X X . . . |
> . O O O O . | O rolls 5-1. Move?
The analysis I wrote in my previous article dealt only with pip count
and not posisiton. My next stage of developement will be to
develop a program to analize positions.
Specific problems are interesting, but they are not the sort of
responses I was hoping to get, unless they illustrate a specific concept.
I was hoping to see what value other people thought of my analysis,
and general theoritical work (that can hopefully be applied to algorithms)
of various situations.
As far as the first problem, I would say 0 should accept, assuming
a money situation. In a match situation, length of match, current score,
and strength of opposition are factors I would need to take into account.
The reason to take is 11 of the 36 rolls that X has will let you win the
game. 11/36 > .25. In declining the double, money would be thrown away
in the long rong.
In the second position, it is desired to maximize the number of rolls
that will get you off in one turn, since that is the most number of turns
that you will get. Only doubles will get you off in the next run, so
maximize the number of doubles that will get you off. I see no way to
get double 1's to work, but there is a way to get 2's or better to work.
Take the 5 off and move the 3 to the 2.
I liked the second problem because it reflects on a general strategy
I use when I am down and I need at least one good set to win. In
the bear off, if you have a two or a one to move (but can't take a guy off)
you usually make the move so as to maximize the number of rolls that will
take two men off the next roll. In come from behind situations, I
change my strategy to maximize the number of doubles that will take 4 men
off, or at least make sure that all of the big doubles will help in a big
way. ie. Suppose you have 5 men on the 5 point and 3 men on the
four point. Using this idea that I need a set rather than better my
odds of getting 2 men off the next roll, I move a 1 to play from the
5 point to the 4 point so that double 4's will take 4 men off. If you
have to get lucky to win, then I play to get lucky. Sometimes trying
to minmize the expected number of rolls to bear off is not the correct
play.
Marc Ringuette
* off. Its usage is:
*
* race4 [-i hash_in] [-o hash_out] [-r roll] position
*
* where position is a sequence of numbers specifying the number of men on
* point 1, 2, 3, ..., and roll is either one or two numbers between 1 and 6.
*
* race4 reads in an initial hash table, performs its evaluations, and then
* writes out the new hash table. hash_in and hash_out both default to
* In addition, if a roll is specified, it prints the expected number of
* rolls after each way of playing that roll, and then repeats the best play.
*
* An example:
*
* initial hash stats: entries 10616 overwrites 0
* Eval <0 | 3 2 3 3 2 1 | 0 1 >...
* .....................
* Expected number of rolls = 7.926747; sigma = 0.961766
* 8/6 4/4 = 6.842434 0.821341
* 8/6 5/4 = 7.227027 0.803111
* 8/6 6/4 = 7.230616 0.806788
* 6/6 8/4 = 6.831183 0.905598
* Best: 6/6 8/4 = 6.831183 0.905598
* hash stats: queries: 17425595 hits 17302863 entries 19808 overwrites 113540
*
* This means that the position:
*
* X X X
* X X X X X
* X X X X X X X
* - - - - - - - -
* has an expected 7.93 rolls to bear off, with a standard deviation of .96,
* and that the correct way to play a 6 4 is to move from the 8 to the 4,
* and bear off the 6 point, resulting in 6.83 expected rolls remaining to
* bear off.
*
* The position is limited to points 1 through 17.
*/
#include <stdio.h>
#include <sys/file.h>
#define NPIECES (15)
#define NSLOTS (32-15+1)
#define INNERSIZE (6)
#define BIGNMOVES (1e10)
typedef struct position {
int maxloc;
unsigned char npieces[NSLOTS];
} position;
int debug;
int depth = 0;
int quiet = 0;
char *hashin = "race4.hash";
char *hashout = "race4.hash";
int roll1 = 0, roll2 = 0;
#define DEPTH_INDENT (" "+20-depth)
double eval();
double pos_eval();
double best_move_val();
double best_val_double();
double best_val_notdouble();
double sqrt();
int hash_queries = 0;
int hash_hits = 0;
int hash_entries = 0;
int hash_overwrites = 0;
main (ac, av)
int ac;
char **av;
{
position p;
double val, variance;
initialize();
parseargs (ac, av, &p);
if (hashin) {
read_hash(hashin);
}
printf ("Eval <");
print_pos (&p);
printf (">...\n");
val = eval(&p, &variance);
printf ("\nExpected number of rolls = %f; sigma = %f\n",val, sqrt(variance));
if (roll1) {
list_moves (&p, roll1, roll2);
}
printf ("hash stats: queries: %d hits %d entries %d overwrites %d\n",
hash_queries, hash_hits, hash_entries, hash_overwrites);
if (hashout) {
write_hash(hashout);
}
return 0;
}
/* eval
* Evaluate position. First look in hash table to see if it is there.
* Otherwise do the work.
*/
double eval (p, pvariance)
position *p;
double *pvariance;
{
double val, var;
unsigned int pos;
hash_compress (p, &pos);
if (!hashcheck (pos, &val, &var)) {
if (debug) {
printf ("%s<", DEPTH_INDENT);
print_pos (p);
printf (">\n");
}
depth++;
val = pos_eval (p, &var);
depth--;
if (debug) {
printf ("%s==> %f %f\n", DEPTH_INDENT, val, var);
}
hashstore (pos, val, var);
} else {
if (debug) {
printf ("%s<", DEPTH_INDENT);
print_pos (p);
printf ("> ==> %f %f", val, var);
}
}
*pvariance = var;
return val;
}
/* pos_eval
* For position p, calculate its value and variance recursively.
* (For all 36 rolls, find the value and variance resulting from
* the roll, and combine them.)
*/
double pos_eval(p, pvariance)
position *p;
double *pvariance;
{
double sum, mean, varsum, variance;
int d1, d2;
if (p->npieces[0] == NPIECES) {
*pvariance = 0.0;
return (double) 0.0;
}
sum = varsum = 0.0;
for (d1 = 6; d1 >= 1; d1--) {
sum += (mean = 1.0 + best_move_val (p, d1, d1, &variance));
varsum += variance + mean * mean;
if (depth == 1 && !quiet) {
putchar ('.'); fflush (stdout);
}
for (d2 = d1+1; d2 <= 6; d2++) {
sum += 2 * (mean = 1.0 + best_move_val (p, d1, d2, &variance));
varsum += 2 * (variance + mean * mean);
if (depth == 1 && !quiet) {
putchar ('.'); fflush (stdout);
}
}
}
mean = sum/36.0;
*pvariance = varsum / 36.0 - mean * mean;
return mean;
}
/* best_move_val
* For position p and roll (d1,d2), d1 != d2, find the best move that
* can be made and its variance.
*/
double best_move_val (p, d1, d2, pvariance)
position *p;
int d1, d2;
double *pvariance;
{
double v1, v2, variance1, variance2;
if (d1 == d2) {
return best_val_double(p, d1, pvariance);
} else {
v1 = best_val_notdouble(p, d1, d2, &variance1);
v2 = best_val_notdouble(p, d2, d1, &variance2);
if (v1 < v2)
{ *pvariance = variance1;
return v1;
}
else
{ *pvariance = variance2;
return v2;
}
/* return v1 < v2 ? v1 : v2; */
}
}
/* best_val_double
* For position p and double-roll (d,d), find the best move that
* can be made and its variance.
*/
double best_val_double (p, d, pvariance)
position *p;
int d;
double *pvariance;
{
int from1, from2, from3, from4;
int to1, to2, to3, to4;
double minmoves = BIGNMOVES;
double val, variance;
int maxloc = p->maxloc;
*pvariance = 0.0;
for (from1=0; from1<=maxloc; from1++) {
if (domove (p, from1, d, &to1)) {
for (from2=0; from2<=from1; from2++) {
if (domove (p, from2, d, &to2)) {
for (from3=0; from3<=from2; from3++) {
if (domove (p, from3, d, &to3)) {
for (from4=0; from4<=from3; from4++) {
if (domove (p, from4, d, &to4)) {
val = eval (p, &variance);
if (val < minmoves) {
minmoves = val;
*pvariance = variance;
}
unmove (p, from4, to4);
}
}
unmove (p, from3, to3);
}
}
unmove (p, from2, to2);
}
}
unmove (p, from1, to1);
}
}
return minmoves;
}
/* best_val_notdouble
* For position p and roll (d1,d2), find the best move that
* can be made and its variance.
*/
double best_val_notdouble (p, d1, d2, pvariance)
position *p;
int d1, d2;
double *pvariance;
{
int from1, from2;
int to1, to2;
double minmoves = BIGNMOVES;
double val, variance;
int maxloc = p->maxloc;
*pvariance = 0.0;
for (from1=0; from1<=maxloc; from1++) {
if (domove (p, from1, d1, &to1)) {
for (from2=0; from2<=from1; from2++) {
if (domove (p, from2, d2, &to2)) {
val = eval (p, &variance);
if (val < minmoves) {
minmoves = val;
*pvariance = variance;
}
unmove (p, from2, to2);
}
}
unmove (p, from1, to1);
}
}
return minmoves;
}
domove (p, from, die, to)
position *p;
int from;
int die;
int *to;
{
if (p->npieces[from] == 0) return 0;
if (from < die && p->maxloc > from) return 0;
if (from == die && p->maxloc > INNERSIZE) return 0;
*to = from - die;
if (*to < 0) *to = 0;
p->npieces[from]--;
p->npieces[*to]++;
if (from == p->maxloc && p->npieces[from] == 0) {
set_maxloc(p);
}
return 1;
}
unmove (p, from, to)
position *p;
int from;
int to;
{
p->npieces[from]++;
p->npieces[to]--;
if (from > p->maxloc) p->maxloc = from;
}
list_moves (p, die1, die2)
position *p;
int die1, die2;
{
if (die2 == 0) {
list_moves_single (p, die1);
} else if (die1 == die2) {
list_moves_double (p, die1);
} else {
list_moves_notdouble (p, die1, die2);
}
}
list_moves_double (p, d)
position *p;
int d;
{
int from1, from2, from3, from4;
int to1, to2, to3, to4;
int maxloc = p -> maxloc;
int best1, best2, best3, best4;
double bestval = 1e10, val, var, bestvar;
for (from1 = 0; from1 <= maxloc; from1++) {
if (domove (p, from1, d, &to1)) {
for (from2 = 0; from2 <= from1; from2++) {
if (domove (p, from2, d, &to2)) {
for (from3 = 0; from3 <= from2; from3++) {
if (domove (p, from3, d, &to3)) {
for (from4 = 0; from4 <= from3; from4++) {
if (domove (p, from4, d, &to4)) {
val = eval (p, &var);
if (val < bestval) {
best1 = from1;
best2 = from2;
best3 = from3;
best4 = from4;
bestval = val;
bestvar = var;
}
printf ("%d/%d %d/%d %d/%d %d/%d = %f %f\n",
from1, d, from2, d,
from3, d, from4, d,
val, sqrt(var));
unmove (p, from4, to4);
}
}
unmove (p, from3, to3);
}
}
unmove (p, from2, to2);
}
}
unmove (p, from1, to1);
}
}
printf ("Best: %d/%d %d/%d %d/%d %d/%d = %f %f\n",
best1, d, best2, d, best3, d, best4, d, bestval, sqrt(bestvar));
}
list_moves_notdouble (p, d1, d2)
position *p;
int d1, d2;
{
int from1, from2;
int to1, to2;
int maxloc = p -> maxloc;
int best1, best2;
double bestval = 1e10, val, var, bestvar;
for (from1 = 0; from1 <= maxloc; from1++) {
if (domove (p, from1, d1, &to1)) {
for (from2 = 0; from2 <= from1; from2++) {
if (domove (p, from2, d2, &to2)) {
val = eval (p, &var);
if (val < bestval) {
best1 = from1;
best2 = from2;
bestval = val;
bestvar = var;
}
printf ("%d/%d %d/%d = %f %f\n", from1, d1, from2, d2,
val, sqrt(var));
unmove (p, from2, to2);
}
}
unmove (p, from1, to1);
}
}
for (from2 = 0; from2 <= maxloc; from2++) {
if (domove (p, from2, d2, &to2)) {
for (from1 = 0; from1 <= from2; from1++) {
if (domove (p, from1, d1, &to1)) {
val = eval (p, &var);
if (val < bestval) {
best1 = from1;
best2 = from2;
bestval = val;
bestvar = var;
}
printf ("%d/%d %d/%d = %f %f\n", from1, d1, from2, d2,
val, sqrt(var));
unmove (p, from1, to1);
}
}
unmove (p, from2, to2);
}
}
printf ("Best: %d/%d %d/%d = %f %f\n", best1, d1, best2, d2, bestval, sqrt(bestvar));
}
list_moves_single (p, d)
position *p;
int d;
{
int from1;
int to1;
int maxloc = p -> maxloc;
int best1;
double bestval = 1e10, val, var, bestvar;
for (from1 = 0; from1 <= maxloc; from1++) {
if (domove (p, from1, d, &to1)) {
val = eval (p, &var);
if (val < bestval) {
best1 = from1;
bestval = val;
bestvar = var;
}
printf ("%d/%d = %f %f\n", from1, d, val, sqrt(var));
unmove (p, from1, to1);
}
}
printf ("Best: %d/%d = %f %f\n", best1, d, bestval, sqrt(bestvar));
}
set_maxloc (p)
position *p;
{
int i;
for (i=NSLOTS-1; i >= 0 && p->npieces[i] == 0; --i);
p->maxloc = i;
}
print_pos(p)
position *p;
{
int i;
for (i=0; i<=p->maxloc; i++) {
printf ("%d ",p->npieces[i]);
if (i % 6 == 0) {
printf ("| ");
}
}
}
#define HASHSIZE 500009
#define HASHLOC(pos) ((3121 * (pos)) % HASHSIZE)
struct hashent {
unsigned int pos;
float value, variance;
} hashtable[HASHSIZE];
hash_compress (p, pos)
position *p;
unsigned int *pos;
{
int i;
unsigned char *s, *send;
unsigned int v1 = 0;
i = 0;
for (s = p->npieces, send = s + p->maxloc; s <= send; s++) {
i += *s;
v1 |= (1 << i);
i++;
}
*pos = v1;
}
hashcheck (pos, val, var)
unsigned int pos;
double *val, *var;
{
int loc;
hash_queries++;
loc = HASHLOC(pos);
if (hashtable[loc].pos == pos) {
*val = hashtable[loc].value;
*var = hashtable[loc].variance;
hash_hits++;
return 1;
}
return 0;
}
hashstore (pos, val, var)
unsigned int pos;
double val, var
;
{
int loc;
loc = HASHLOC(pos);
if (hashtable[loc].pos) {
hash_overwrites++;
} else {
hash_entries++;
}
hashtable[loc].pos = pos;
hashtable[loc].value = val;
hashtable[loc].variance = var;
}
read_hash (s)
char *s;
{
int d = open (s, O_RDONLY, 0);
int loc;
struct hashent new;
if (d < 0) {
return;
}
for (;;) {
if (read (d, (char *) &new, sizeof (new)) <= 0) {
break;
}
loc = HASHLOC (new.pos);
if (hashtable[loc].pos) {
hash_overwrites++;
} else {
hash_entries++;
}
hashtable[loc] = new;
}
close (d);
printf ("initial hash stats: entries %d overwrites %d\n",
hash_entries, hash_overwrites);
}
write_hash (s)
char *s;
{
int d = open (s, O_WRONLY|O_CREAT|O_TRUNC, 0666);
int i;
if (d < 0) {
perror (s);
exit (1);
}
for (i=0; i<HASHSIZE; i++) {
if (hashtable[i].pos) {
write (d, (char *) &hashtable[i], sizeof (struct hashent));
}
}
close (d);
}
initialize()
{
}
parseargs (ac, av, p)
int ac;
char **av;
position *p;
{
int c;
extern int optind;
extern char *optarg;
int i;
int sum;
while ((c = getopt (ac, av, "dqi:o:r:?")) != EOF) switch (c) {
case 'd': debug++; break;
case 'q': quiet++; break;
case 'i': hashin = optarg; break;
case 'o': hashout = optarg; break;
case 'r': roll1 = optarg[0] - '0';
if (optarg[1]) roll2 = optarg[1] - '0';
break;
case '?':
default: usage (av[0]); exit (1);
}
for (i = 0; i < NSLOTS; i++) {
p -> npieces[i] = 0;
}
i = 1;
sum = 0;
while (optind < ac && i < NSLOTS && sum < NPIECES) {
p -> npieces[i] = atoi (av[optind]);
sum += p -> npieces[i];
i++;
optind++;
}
p -> npieces[0] = NPIECES - sum;
set_maxloc (p);
}
usage (s)
char *s;
{
fprintf (stderr, "Usage: %s [-d] [-q] [-r roll] [-i hashin] [-o hashout] position\n",s);
}
Marc Ringuette
how to use race2.c.
. X X . . . | X doubles. Should O accept?
O O . . . . |
X X X . . . |
. O O O O . | O rolls 5-1. Move?
% race2 0 1 1 c - 1 1
Eval <c 13|0 1 1 ... 1 1|13>...
.....................
Undoubled: 0.388889 Double accepted: 0.777778 declined 1.000000
Value = 0.777778
hash stats: queries: 514 hits 492 entries 22 overwrites 0
% race2 -r 51 0 1 1 1 1 c - 1 1 1
initial hash stats: entries 4657 overwrites 0
Eval <c 11|0 1 1 1 1 ... 1 1 1|12>...
.....................
Undoubled: -0.080933 Double accepted: -0.604167 declined 1.000000
Value = -0.080933
5/5 2/1 = -0.808642
5/5 3/1 = -0.760802
5/5 4/1 = -0.808642
4/5 5/1 = -0.808642
Best: 5/5 3/1 = -0.760802
hash stats: queries: 103 hits 103 entries 4657 overwrites 1
So ... double/take, and 5-off, 3-2.
-- Marc Ringuette (m...@cs.cmu.edu)
C. T. McMullen
>
> I imagine that the non-contact situations are fairly well
>understood, so this may not generate too much interest.
Here are 2 problems from Tim Holland's "Better Backgammon" (Reiss Games,
1974) that involve no contact positions that you might test your
program with:
. X X . . . | X doubles. Should O accept?