% > w.race3
%
% This is a CWEB 3.x program.

\input gjm11mac
\def\title{race: a backgammon endgame equity calculator}

@* Introduction.
%
This program computes equities (with-cube) for backgammon endgames.
It does this completely accurately by exhaustive search; so it is
slow for complicated positions. Given an initial position, it will
work out the first player's equity; if it's possible for the first
player to double it will also work out his equity after doubling.

To speed up the search, we use a hash table of positions. The details
of this will become clear later.

Here is the traditional program outline.

@^equity@>
@^hash table@>

@c
/* (|#include|s and |#define|s will be put here) */
/* Next bit is to make this faster on my machine at home */
#ifdef RISC_OS
#include "load+save.h"
#endif
@<Typedefs@>
@<Global variables@>
@<Functions@>
int main(int argc, char *argv[]) @+ {
  @<Local variables for |main()|@>
  @<Parse command line@>
  @<Initialize@>
  @<Do the work@>
  @<Tidy up and exit@>
}


@ We need some include files.

@h <stdio.h>
@h <stdlib.h>
@h <string.h>


@* Arithmetic.
%
Floating-point arithmetic is slow on some computers. It's certainly slow
on mine. Since all we actually ever do is add and subtract equities and
multiply them by {\sl constants}, it's trivial to use fixed-point instead.
This way we get about 8 decimal places of accuracy, which is plenty.

@d ONE (1<<25)
@d TO_REAL(x) ((int)(x*ONE+.5))
@d TO_DOUBLE(x) (((double)x)/ONE)

@<Typedefs@>=
typedef int real;


@* Representing a position.
%
For normal use, we code each player's position into one word. The lower
6 nybbles contain the numbers of men on that player's 1,2,3,4,5,6-points.
The top byte is unused (unless I later think of something clever to do
with it).

@<Typedefs@>=
typedef int board;

@* The hash table.
%
I am indebted to the author of \.{race2} for the observation that
one can encode a position very simply in 64 bits, with space to spare.
Here's a way to see this: a position is specified by saying where
each of 30 men are; each man has a choice of 26 positions (24 on the
board and 2 off it). So, write down one `*' for each White man on White's
``0-point'', then a `/', then one `*' for each White man on White's
1-point, and so on until the White men are exhausted; then carry on
for Black. The result is a string of 25+30=55 symbols of two types;
obviously we can fit this into 55 bits.

Of course this is a lousy way of recording a position if we need to
do anything with it. But it's very compact, and will serve admirably
for recording positions in the hash table.

When we analyze a position we shall always compute {\sl three\/} equities
(no cube, cube with first player, cube with second player). This doesn't
cost much in performance, since we often want at least two of these anyway,
and it means that our hash table is effectively doubled in size.

@^hash table@>
@^combinatorial trickery@>
@.race2@>

@<Typedefs@>=
typedef unsigned int word;

typedef struct {
  word w1,w2;
  real equity0; /* no cube */
  real equity1;  /* player 1 has cube */
  real equity2;  /* player 2 has cube */
} hash_entry;


@ The hash table is pointed to by a global variable.

@<Global variables@>=
hash_entry *hash_table;


@ We need to be able to turn a position into a 64-bit code.

Here's a function that does that. In terms of the description in the
previous section, we represent `/' by `1' and `*' by `0'.

@<Functions@>=
void pos_to_64bit(board p1, board p2, hash_entry *h) @+ {
  int i,j=0,t;
  word *wp;
  h->w1=0; h->w2=0; @/
  @<Encode first player's position@>
  @<Encode second player's position@>
}

@ To encode the first player's position, we just loop through the points
as far as we need to, putting 1s in the right places.

@<Encode first player's position@>=
wp=&(h->w1);
t=p1;
for (i=0;t;++i) {
  j+=t&15;
  if (j>=32) { @+ j-=32; wp=&(h->w2); @+ }
  *wp |= 1<<j;
  ++j;
  t>>=4;
}

@ And the same goes for the second player's position, except that it all
goes sdrawkcab. Incidentally, you may have noticed that this is not quite
the encoding we described earlier, in that we don't bother inserting
the `/'s for points between the last one occupied by the first player
and the first one occupied by the second player. Clearly this doesn't
cause any trouble; we can still in principle recover the position from
the 64-bit coding. (Not that we ever need to.)

@<Encode second player's position@>=
wp=&(h->w2);
j=54-32;
t=p2;
for (i=0;i<=6;++i) {
  j-=t&15;
  if (j<0) { @+ j+=32; wp=&(h->w1); @+ }
  *wp |= 1<<j;
  --j;
  t>>=4;
}

@ Of course we don't actually want a hash table with $2^{64}$~entries. (Well,
we might {\sl want\/} one, but we can't have one.) So we need to be able to
turn a pair~$\langle w_1,w_2\rangle$ into a hash code of a more
manageable size. I've stolen the function used for this from \.{race2},
although my hash table is a different size. I don't imagine it makes much
difference exactly what numbers one chooses.

If we get hash collisions with small positions I shall change the numbers
until this stops happening.

@^hash table@>
@.race2@>

@d hash_size 100003
@d compute_hash(x) ((x.w1*3121+x.w2*479)%hash_size)


@ We'll collect some statistics about the hash table's performance
when the preprocessor symbol |HASH_STATS| is defined.

@d HASH_STATS

@<Global variables@>=
#ifdef HASH_STATS
int h_lookups=0;    /* attempts to find things in hash table */
int h_hits=0;       /* successes */
int h_misses=0;     /* failures */
int h_collisions=0; /* failures in which entry wasn't blank */
#endif

@ The actual hash-table lookup will be a part of the |analyze()| function,
which will be defined in just a moment.


@ An unallocated hash-table entry has |w1==0| and |w2==0|; actually it's
enough to check whether |w1==0| since that can never be true for a
real position. (If the player to move has no men left, the game ended
before the last move.)

@^hash table@>

@<Create empty hash table@>=
memset(hash_table,0,hash_size*sizeof(hash_entry));


@* Calculating equities.
%
This is, of course, the main work of the program. Here's what the code
looks like: |analyze()| returns the position in the hash table of the
analyzed position; by looking there we can find the equities. Of course
this doesn't have to do any real work if the position already happens
to be in the hash table.

If the position {\it isn't\/} in the hash table, it is inserted. If
there's already another position with the same hash code, we throw that
away.

The variables |avg0|, |avg1| and |avg2| in this function are certain
equity averages. The variables |e0|, |e1| and~|e2| are temporary
variables representing equities after particular rolls.

One of the main uses of this program is to make doubling decisions.
Of course it makes doubling decisions with every call to |analyze|,
but for the position the user entered we actually need to say what
decision was made and why. Therefore, when the global variable |first_call|
is non-zero on entry to |analyze()|, we record a little extra information.

@^hash table@>

@<Functions@>=
int analyze(board p1, board p2) @+ {
  board pp=p1;
  int i,j,k,l; /* loop variables */
  int d1,d2; /* die rolls */
  int n; /* number of position reached in calculation */
  hash_entry h;
  int hash;
  real avg0=0, avg1=0, avg2=0;
  real e0,e1,e2;
  int fc=first_call; @+ first_call=0; @/
  pos_to_64bit(p1,p2,&h); @+ hash=compute_hash(h);
  if (!fc) {
    @<Look up position in hash table, and |return| if found@>
  }
  @<Loop through all possible rolls, computing equities and
    accumulating them@>
  @<Put this position with its equities into the hash table@>
  if (fc) {
    @<Record information about doubling decision@>
  }
  return hash;
}


@ The first bit is dead easy.

@<Look up position in hash table, and |return| if found@>=
#ifdef HASH_STATS
  ++h_lookups;
#endif
if (hash_table[hash].w1==h.w1 && hash_table[hash].w2==h.w2) {
  #ifdef HASH_STATS
    ++h_hits;
  #endif
  return hash;
}
#ifdef HASH_STATS
else ++h_misses;
#endif


@ If we don't already know the answer, we'll have to work it out.
The equity of the position is the average over all possible rolls of the
equities of the resulting positions, taking proper cube actions into
account. Here's how it goes. (We shall accumulate equities in the
$avg_k$~variables.)

@<Loop through all possible rolls...@>=
for (d1=6;d1;--d1) {
  for (d2=d1-1;d2;--d2) {
    @<Enumerate, and deal with, moves for non-double roll@>
  }
}
avg0+=avg0; avg1+=avg1; avg2+=avg2; /* two ways to roll non-doubles */
for (d1=1;d1<=6;++d1) {
  @<Enumerate, and deal with, moves for double roll@>
}
avg0/=36; avg1/=36; avg2/=36;


@ Right. Now for the hard bit. Actually there are two hard bits here,
happening together. Firstly, we need to enumerate all the possible moves
for each roll; secondly, we need to piece together all this stuff to
determine the correct equities.

Let's deal with the equity calculations first. We need to work out the
equity for the given position for each of the three possible cube
positions.

{\sl If player 1 has the cube\/} then his equity if he doubles is
twice the average of the player-2-has-cube equities, or 1, whichever is
smaller. His equity if he doesn't double is the average of the
player-1-has-cube equities. The actual equity for the position is
the larger of these.

{\sl If player 2 has the cube\/} then player 1 cannot double. The
equity for this position is the average of the player-2-has-cube
equities.

{\sl If neither player has the cube\/} then player 1's equity
if he doubles is twice the average of the player-2-has-cube equities
or 1, as before; his equity if he doesn't double is the average
of the cube-in-centre equities. The actual equity is the larger of
these.

While this is fresh in our minds, let's do the last bit of |analyze()|.

@<Put this position with its equities into the hash table@>=
e2=2*avg2; if (e2>ONE) e2=ONE; /* equity from doubling, if possible */
h.equity0 = (e2>=avg0)?e2:avg0;
h.equity1 = (e2>=avg1)?e2:avg1;
h.equity2 = avg2;
#ifdef HASH_STATS
if (hash_table[hash].w1) ++h_collisions;
#endif
hash_table[hash]=h;


@ And, for those doubling decisions:

@<Record information about doubling decision@>=
undoubled_equity0=avg0;
undoubled_equity1=avg1;
doubled_equity=2*avg2;


@ Before proceeding, let's not forget the global variables for this
doubling stuff.

@<Global variables@>=
int first_call=1;
real doubled_equity,undoubled_equity0,undoubled_equity1;


@ Now for the gruesome business of move generation. First of all,
rolls which are not doubles. We deal first of all with cases in which
the first die roll is moved from a higher point than the second; then
with cases in which the second is moved from a higher point than the
first. There is some duplication of moves, but this is cheap except in
rare cases of hash collision, since the calculations will only need to
be done once.

I wish to apologise for the disgusting business with labels that
ensues. The point is that we can avoid a lot of special-casing if,
whenever we reach a position in which all of player 1's pieces are
off, we jump straight out of the move-enumeration loop, setting
the equities to their correct values.

@<Enumerate, and deal with, moves for non-double roll@>=
#undef BREAK
#define BREAK break2
e0=-2*ONE; e1=-2*ONE; e2=-2*ONE;
for (k=0;k<2;++k) {
  for (i=5;i>=0;--i) {
    @<Try to move |d1| from point |i|; |continue| if impossible@>
    for (j=i-k;j>=0;--j) {
      if (j==i-d1 && d1>d2) continue;
      @<Try to move |d2| from point |j|; |continue| if impossible@>
      @<Analyze position resulting from move, and update equities@>
      @<Undo move |d2,j|@>
    }
    @<Undo move |d1,i|@>
  }
  d1+=d2; d2=d1-d2; d1-=d2; /* swap die rolls */
}
BREAK:
if (d1<d2) { d1+=d2; d2=d1-d2; d1-=d2; }
if (fc) printf("equities after %d%d are %lf, %lf, %lf\n",d1,d2,
               TO_DOUBLE(e0),TO_DOUBLE(e1),TO_DOUBLE(e2));
avg0+=e0; avg1+=e1; avg2+=e2;


@ When doubles are thrown the code is almost identical.

@<Enumerate, and deal with, moves for double roll@>=
#undef BREAK
#define BREAK break4
e0=-2*ONE; e1=-2*ONE; e2=-2*ONE;
for (i=5;i>=0;--i) {
  @<Try to move |d1| from point |i|; |continue| if impossible@>
  for (j=i;j>=0;--j) {
    @<Try to move |d1| from point |j|; |continue| if impossible@>
    for (k=j;k>=0;--k) {
      @<Try to move |d1| from point |k|; |continue| if impossible@>
      for (l=k;l>=0;--l) {
        @<Try to move |d1| from point |l|; |continue| if impossible@>
        @<Analyze position resulting from move, and update equities@>
        @<Undo move |d1,l|@>
      }
      @<Undo move |d1,k|@>
    }
    @<Undo move |d1,j|@>
  }
  @<Undo move |d1,i|@>
}
BREAK:
avg0+=e0; avg1+=e1; avg2+=e2;
if (fc) printf("equities after %d%d are %lf, %lf, %lf\n",d1,d1,
               TO_DOUBLE(e0),TO_DOUBLE(e1),TO_DOUBLE(e2));


@ The equity calculations themselves are now straightforward:

@<Analyze position resulting from move, and update equities@>=
n=analyze(p2,pp);
if (-hash_table[n].equity0>e0) e0=-hash_table[n].equity0;
if (-hash_table[n].equity2>e1) e1=-hash_table[n].equity2;
if (-hash_table[n].equity1>e2) e2=-hash_table[n].equity1;


@ The next few bits of code are basically all the same. We can move
provided (1)~there is at least one man on the point we're moving from,
and (2)~we can use the full value of the roll {\sl or\/} there are no
men on higher-numbered points.

To save a bit of typing, we'll use ``symbolic names'' (!) for our
variables in this code.

@<Try to move |d1| from point |i|; |continue| if impossible@>=
#undef DIE
#undef POINT
#define DIE d1
#define POINT i
@<Do a move, or |continue|@>


@~ Here's the code itself.

@<Do a move...@>=
if ((pp>>(POINT<<2))&15) {
  if (pp<=15<<(POINT<<2)) { /* POINT==pp.maxpos */
    pp-=1<<((POINT<<2));
    if (POINT>=DIE) pp+=1<<((POINT-DIE)<<2);
  } else {
    if (POINT>=DIE) { pp+=1<<((POINT-DIE)<<2); pp-=1<<(POINT<<2); }
    else if (POINT==DIE-1) { pp-=1<<(POINT<<2); }
    else continue;
  }
} else continue;
if (!pp) { e0=ONE; e1=ONE; e2=ONE; pp=p1; goto BREAK; }


@ Now the other similar bits of code are easy. Unfortunately they need
a section apiece.

@<Try to move |d2| from point |j|...@>=
#undef DIE
#undef POINT
#define DIE d2
#define POINT j
@<Do a move...@>


@ Another.

@<Try to move |d1| from point |j|...@>=
#undef DIE
#undef POINT
#define DIE d1
#define POINT j
@<Do a move...@>


@ And another.

@<Try to move |d1| from point |k|...@>=
#undef DIE
#undef POINT
#define DIE d1
#define POINT k
@<Do a move...@>


@ And another. This is the last one, actually.

@<Try to move |d1| from point |l|...@>=
#undef DIE
#undef POINT
#define DIE d1
#define POINT l
@<Do a move...@>


@ There's some more repetitive code coming up. Undoing a move is,
fortunately, pretty simple.

@<Undo move |d1,i|@>=
#undef DIE
#undef POINT
#define DIE d1
#define POINT i
@<Undo a move@>


@ Let's do the repetitions first, and then sort out the code itself.

@<Undo move |d2,j|@>=
#undef DIE
#undef POINT
#define DIE d2
#define POINT j
@<Undo a move@>


@ And another one.

@<Undo move |d1,j|@>=
#undef DIE
#undef POINT
#define DIE d1
#define POINT j
@<Undo a move@>


@ And another.

@<Undo move |d1,k|@>=
#undef DIE
#undef POINT
#define DIE d1
#define POINT k
@<Undo a move@>


@ And the last one.

@<Undo move |d1,l|@>=
#undef DIE
#undef POINT
#define DIE d1
#define POINT l
@<Undo a move@>


@ And to undo a move\dots

@<Undo a move@>=
pp+=1<<(POINT<<2);
if (POINT>=DIE) pp-=1<<((POINT-DIE)<<2);


@* Dealing with specific rolls.
%
When the user has given us not only a position but a roll, we need to record
rather more information. Specifically, we need to remember each move we made
and what the resulting equities were.

Unfortunately, what we need to do here is similar but not identical to
what is done in the move-enumeration code above. We really don't want to
slow that down with case-checking, so there's going to have to be some
duplication. We can, however, re-use a lot of the stuff above.


@ We record a move-and-equities thing in a |hash_entry| structure. We'll
actually use the first two components of the structure to hold the move,
rather than the position. (In fact the move will fit into the first
component of the structure. One byte per thingy moved.)

How big does our array need to be? Surprisingly large. If we don't roll
doubles, our move is determined by saying which of 6 places each of two
pieces moved from, making 36 possibilities. If we do roll doubles, we
need to decide for 4 pieces, but their order doesn't matter, so we get
${6\choose4}+3{6\choose3}+(2+1){6\choose2}+6$ possibilities (I'll let
you work out why); that makes $15+60+45+6=126$. The correct number is
actually a bit smaller, since we've assumed that there are 4 men on every
point; I think this makes the right answer 105, but it's not worth worrying
about.

I've just noticed that there's a better way of thinking about the calculation
above (the one giving 126). It's {\sl obviously\/} $9\choose4$.

@<Global variables@>=
hash_entry move[126];
int move_n=0;


@ Here's the roll-analyzer. I am seriously beginning to think I should
just have put up with the inefficiency resulting from sticking an
arbitrary function-call in the middle of that move-generation stuff.
I apologise for all the screwing about that's resulted from trying to
reuse code fragments in a nasty way.

@<Functions@>=
#undef BREAK
#define BREAK break_roll
void analyze_roll(board p1, board p2, int d1, int d2) {
  int i=0,j=0,k=0,l=0;
  board pp=p1;
  real e0=0,e1,e2; /* dummies! */
  int h;
  first_call=0;
  if (d1==d2) {
    for (i=5;i>=0;--i) {
      @<Try to move |d1| from point |i|; |continue| if impossible@>
      for (j=i;j>=0;--j) {
        @<Try to move |d1| from point |j|; |continue| if impossible@>
        for (k=j;k>=0;--k) {
          @<Try to move |d1| from point |k|; |continue| if impossible@>
          for (l=k;l>=0;--l) {
            @<Try to move |d1| from point |l|; |continue| if impossible@>
            @<Analyze position resulting from move, and remember the result@>
            @<Undo move |d1,l|@>
          }
          @<Undo move |d1,k|@>
        }
        @<Undo move |d1,j|@>
      }
      @<Undo move |d1,i|@>
    }
  } else {
    for (k=0;k<2;++k) {
      for (i=5;i>=0;--i) {
        @<Try to move |d1| from point |i|; |continue| if impossible@>
        for (j=i-k;j>=0;--j) {
          if (j==i-d1 && d1>d2) continue;
          @<Try to move |d2| from point |j|; |continue| if impossible@>
          BREAK:
          @<Analyze position resulting from move, and remember the result@>
          @<Undo move |d2,j|@>
        }
        @<Undo move |d1,i|@>
      }
      d1+=d2; d2=d1-d2; d1-=d2; /* swap die rolls */
    }
  }
}


@ We need code to replace the equity-updating stuff. Here it is.

@<Analyze position resulting from move, and remember the result@>=
if (e0) { /* WIN */
  move[move_n].w1=i+(j<<8)+(k<<16)+(l<<24);
  move[move_n].equity0=-ONE; move[move_n].equity1=-ONE; move[move_n].equity2=-ONE;
  ++move_n;
  e0=0;
} else {
  h=analyze(p2,pp);
  move[move_n]=hash_table[h];
  move[move_n++].w1=i+(j<<8)+(k<<16)+(l<<24);
}


@* Getting started.
%
We now have all the really important code; it remains only to get things
set up, and to deal with input and output. We haven't decided yet what
should go on the command line; so let's do that now.

The command line will be in the same format as that for \.{race2}:
that is, there are three options \.{-i}, \.{-o}, \.{-r} giving respectively
the input hash table, the output hash table and the roll to look at;
and other than that the command line should contain two {\sl position\/}s
separated by a single minus sign. A position consists of a list of numbers,
meaning number of men on 1-point, number of men on 2-point and so on.

@^command line@>
@.race2@>

@<Parse command line@>=
--argc; ++argv;
player=&player1; point=0; men=0;
player1=0; player2=0;
while (argc) {
  if (!strcmp(*argv,"-r")) {
    @<Read a roll from the command line@> }
  else if (!strcmp(*argv,"-i")) {
    @<Read the input hashfile name from the command line@> }
  else if (!strcmp(*argv,"-o")) {
    @<Read the output hashfile name from the command line@> }
  else if (!strcmp(*argv,"-")) {
    if (player!=&player1) error("Backgammon only has two players");
    player=&player2; point=0; men=0; }
  else { char *cp; int x;
    x=(int)strtol(*argv,&cp,10);
    if (*cp || x<0 || x>15-men || point>=6) error("Illegal position");
    *player+=x<<(point<<2); men+=x; ++point;
  }
  --argc; ++argv;
}
if (player!=&player2) error("Backgammon needs two players");


@ We need some variables.

@<Local variables for |main()|@>=
board *player; int point; int men;
board player1,player2;
char *hash_in=0;
char *hash_out=0;
int d1=0,d2=0; /* roll */


@ A roll consists of two numbers between 1 and 6.

@<Read a roll from the command line@>=
--argc; ++argv;
if (argc<2) error("A roll needs 2 numbers");
d1=atoi(*argv); if (d1<=0 || d1>6) error("Dice can show only 1,2,3,4,5,6");
--argc; ++argv;
d2=atoi(*argv); if (d2<=0 || d2>6) error("Dice can show only 1,2,3,4,5,6");


@ A hashfile is just a string.

@<Read the input hashfile name...@>=
--argc; ++argv;
if (!argc) error("-i requires a filename");
hash_in=*argv;


@ Same for output.

@<Read the output hashfile name...@>=
--argc; ++argv;
if (!argc) error("-o requires a filename");
hash_out=*argv;


@ Once we have parsed the command line (and so know where our hashfiles
are), we can initialize everything. The |#ifdef|ed stuff is to improve
things on my machine at home, which has a slow hard disc and doesn't cope
well with trying to read a 2\thinspace Mb file in 4\thinspace Kb chumks.

@<Initialize@>=
hash_table=(hash_entry *)malloc(hash_size*sizeof(hash_entry));
if (!hash_table) error("No room for hash table");
if (hash_in) {
#ifdef RISC_OS
  int sz=file_size(hash_in);
  if (sz<0) @<Create empty hash table@>
  else if (sz!=hash_size*sizeof(hash_entry)) error("Bad hashfile");
  else load_file(hash_in,hash_table);
#else
  FILE *f; int x;
  f=fopen(hash_in,"rb");
  if (f) {
    x=fread(hash_table,sizeof(hash_entry),hash_size,f);
    fclose(f);
    if (x<hash_size) error("Bad hashfile"); }
  else {
    @<Create empty hash table@>
  }
#endif
}
else {
  @<Create empty hash table@>
}

@* Doing the work.
%
This is pretty easy now.

@<Do the work@>=
@<Describe initial position@>
if (d1) {
  analyze_roll(player1,player2,d1,d2);
  @<Describe results of roll-analysis@>
} else {
  analyze(player1,player2);
  @<Describe results of analysis@>
}
#ifdef HASH_STATS
printf("\n** hash table: %d lookups  %d hits  %d misses (%d collisions)\n",
       h_lookups,h_hits,h_misses,h_collisions);
#endif


@ Describing the initial position isn't really necessary, but it does
make it easier for the user to check that they haven't made a mistake.

@<Describe initial position@>=
{ int i;
  int t,p;
  printf("Position at start:\n");
  t=p=0; for(i=0;i<=5;++i) {
    t+=(player1>>(i<<2))&15;
    p+=(i+1)*((player1>>(i<<2))&15);
  }
  printf("Player 1 : %2d men, %2d pips : ",t,p);
  for(i=0;i<=5;++i)
    printf("%d ",(player1>>(i<<2))&15);
  t=p=0; for(i=0;i<=5;++i) {
    t+=(player2>>(i<<2))&15;
    p+=(i+1)*((player2>>(i<<2))&15);
  }
  printf("\nPlayer 2 : %2d men, %2d pips : ",t,p);
  for (i=0;i<=5;++i)
    printf("%d ",(player2>>(i<<2))&15);
  printf("\n\n");
}


@ And (remember, we aren't thinking about finding best moves at the moment)
describing the results of our analysis is easy too. We've already done all
the work.

@<Describe results of analysis@>=
{ double x;
  printf("\nResults of analysis:\n");
  printf("0. Cube in centre.\n");
  printf("   Equity (no double):       %lf\n",TO_DOUBLE(undoubled_equity0));
  printf("   Equity (double accepted): %lf\n",TO_DOUBLE(doubled_equity));
  printf("   Equity (double declined): %lf\n",1.);
  printf("1. Cube with player 1.\n");
  printf("   Equity (no double):       %lf\n",TO_DOUBLE(undoubled_equity1));
  printf("   Equity (double accepted): %lf\n",TO_DOUBLE(doubled_equity));
  printf("   Equity (double declined): %lf\n",1.);
  printf("2. Cube with player 2. (Player 1 cannot double.)\n");
  printf("   Equity:                   %lf\n\n",TO_DOUBLE(doubled_equity)/2);
  x=(doubled_equity>ONE?ONE:doubled_equity);
  if (x>undoubled_equity1)
    printf("Player 1 has a redouble");
  else if (x>undoubled_equity0)
    printf("Player 1 has an initial double (but no redouble)");
  if (x>undoubled_equity0)
    printf(", which player 2 should %s.\n",doubled_equity>ONE?"drop":"take");
  else printf("Player 1 should not double, wherever the cube is.\n");
}


@ It's even pretty easy when we have to describe the results of individual
moves. Here:

@<Describe results of roll-analysis@>=
{ int i;
  real e0=-2*ONE,e1=-2*ONE,e2=-2*ONE;
  real a0,a1,a2;
  int m0,m1,m2;
  printf("Results of analysis:\n\n");
  if (d1==d2)
    printf("Move            Centre   Player1  Player2\n");
  else
    printf("Move    Centre   Player1  Player2\n");
  for (i=0;i<move_n;++i) {
    a0=-move[i].equity0;
    a1=-move[i].equity2;
    a2=-move[i].equity1;
    printf("%s %lf %lf %lf\n",
      move_to_string(move[i].w1,d1,d2),
      TO_DOUBLE(a0),TO_DOUBLE(a1),TO_DOUBLE(a2));
    if (a0>e0) { e0=a0; m0=move[i].w1; }
    if (a1>e1) { e1=a1; m1=move[i].w1; }
    if (a2>e2) { e2=a2; m2=move[i].w1; }
  }
  printf("\nBest moves:\n");
  printf("Cube in centre:     %s %lf\n",move_to_string(m0,d1,d2),TO_DOUBLE(e0));
  printf("Cube with player 1: %s %lf\n",move_to_string(m1,d1,d2),TO_DOUBLE(e1));
  printf("Cube with player 2: %s %lf\n",move_to_string(m2,d1,d2),TO_DOUBLE(e2));
}


@ And we need to be able to convert a move into a string. This is easy; the
main difficulty is that when we have non-doubles, the third byte contains
0 or 1 depending on whether the dice are swapped! This is inelegant, but
fits well with the way the move-enumerator works\dots

@<Functions@>=
char *move_to_string(int m, int d1, int d2) {
  static char s[18];
  int i,j,k,l;
  i=m&255; j=(m>>8)&255; k=(m>>16)&255; l=(m>>24)&255;
  i++; j++; k++; l++;
  if (d1==d2)
    sprintf(s,"%d/%d %d/%d %d/%d %d/%d",
      i,(i-d1<0)?0:(i-d1), j,(j-d1<0)?0:(j-d1),
      k,(k-d1<0)?0:(k-d1), l,(l-d1<0)?0:(l-d1));
  else {
    if (k>1) { l=d1; d1=d2; d2=l; }
    sprintf(s,"%d/%d %d/%d",
      i,(i-d1<0)?0:(i-d1), j,(j-d2<0)?0:(j-d2));
  }
  return s;
}


@* Final stages.
%
When the program has finished running, we save the hashfile at the end
if asked to do so. This improves performance sometimes and makes it
worse sometimes; it depends on the speed of your hard disc and on
how similar each position you look at is to its predecessors.

The |#ifdef|ed stuff is to make the I/O go at an acceptable speed on
my machine at home.

@<Tidy up and exit@>=
if (hash_out) {
#ifdef RISC_OS
  if (save_file(hash_out,hash_table,hash_size*sizeof(hash_entry),0xFFD))
    error("Couldn't write hashfile");
#else
  FILE *f; int x;
  f=fopen(hash_out,"wb");
  if (f) {
    x=fwrite(hash_table,sizeof(hash_entry),hash_size,f);
    fclose(f);
    if (x<hash_size) error("Trouble writing hashfile"); }
  else error("Couldn't open output hashfile");
#endif
}
return 0;


@ The other way of leaving the program is through |error()|, whose argument
is a string describing what went wrong.

@<Functions@>=
void error(char *s) {
  fprintf(stderr,"! %s.\n",s);
  exit(8);
}