2 views

Skip to first unread message

Dec 9, 1993, 4:04:15â€¯AM12/9/93

to

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

********

Dec 10, 1993, 1:06:14â€¯AM12/10/93

to

Here are two programs which may interest you, by my friend David

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.

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 ]

Dec 10, 1993, 1:10:27â€¯AM12/10/93

to

/* This program computes the expected value of a position. The expected

* 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

*

*/

* 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);

}

Dec 9, 1993, 6:07:31â€¯PM12/9/93

to

c...@math.berkeley.edu (C. T. McMullen) writes:

>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.

Dec 10, 1993, 1:07:46â€¯AM12/10/93

to

/* This program computes the expected number of rolls a player needs to bear

* 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

* race4.hash. It then prints out the expected number of rolls to bear off.

* 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:

*

* $ race4 -r 64 3 2 3 3 2 1 0 1

* 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.

*/

* 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);

}

Dec 10, 1993, 3:25:11â€¯AM12/10/93

to

These are very easy problems ... but I'll use them as examples of

how to use race2.c.

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)

Dec 9, 1993, 2:17:28â€¯PM12/9/93

to

> 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.

>

> 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?

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu