|
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.
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 (mnr@cs.cmu.edu)
/* 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
*
*/
#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);
}
|
![[Recommended reading]](pics/Star2.gif)
![[Long message]](pics/Long.gif)
![[GammOnLine forum]](pics/GammOnLine.gif)
From GammOnLine
![[Recent addition]](pics/New.gif)
Recent addition