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