/* A little program to play the game of Oska.
 * The board looks like this:
 *
 *    x x x x
 *     x x x
 *      x x
 *     x x x
 *    x x x x
 *
 * Initially each player's 4 pieces are on her back rank.
 * Play alternates; a legal move is a move forward and left or right,
 * or a draughts-style capture jumping over a single enemy piece.
 * The object is to have *all* one's pieces on the opponent's
 * back rank; except that losing all one's pieces is a loss.
 *
 * We adopt a simple approach: minimax (strictly, alpha-beta) search
 * with a simple static evaluation function (difference between distances
 * from back rank).
 *
 * There are only 16 spaces on the board, so we can encode a position
 * very simply. The spaces are numbered 0..15 as follows:
 *
 *    C D E F
 *     9 A B
 *      7 8
 *     4 5 6
 *    0 1 2 3
 *
 * We store the player-0-pieces bitmap in the bottom 16 bits of
 * a word, and the player-1-pieces in the top 16 bits. (Player 0
 * is the one moving from bottom to top of the board.)
 * I'll call player 0 "Blue" and player 1 "Red", as in WW.
 * I'm not sure whether this agrees with the rules of the
 * original form of the game.
 */

#include <ctype.h>
#include <setjmp.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define FirstL (1ul<<0)
#define FirstLM (1ul<<1)
#define FirstRM (1ul<<2)
#define FirstR (1ul<<3)
#define SecondL (1ul<<4)
#define SecondM (1ul<<5)
#define SecondR (1ul<<6)
#define MiddleL (1ul<<7)
#define MiddleR (1ul<<8)
#define FourthL (1ul<<9)
#define FourthM (1ul<<10)
#define FourthR (1ul<<11)
#define BackL (1ul<<12)
#define BackLM (1ul<<13)
#define BackRM (1ul<<14)
#define BackR (1ul<<15)

/* The static evaluation is a simple "sum of scores of piece squares"
 * thing. We compute it by doing four table lookups: {blue,red} pieces in
 * {first,second} half of board.
 * The score is made up of two things. Firstly, there is a
 * negative score for distance away from the back rank. This
 * is the dominant factor; so generally it is better to lose
 * pieces. Secondly, there's a factor for "centrality". All
 * scores are negative, so actually there's a negative score
 * for non-centrality.
 * Each unit of advancement counts for 4 points of score.
 * The non-centrality term looks like this:
 *
 * ,----------------.
 * | xx  -1  -1  xx |
 * |   -1  xx  -1   |
 * |     xx  xx     |
 * |   -1  xx  -1   |
 * | -2  xx  xx  -2 |
 * `----------------'
 *
 * (The peculiar business on the back rank is because a piece
 * in the middle is more likely to be in the way of another
 * piece wanting to reach the back.)
 */

typedef unsigned char byte;
typedef unsigned long word;

/* Some tiresome stuff first. We need to catch SIGINT, so as to do
 * something sensible with <Escape>. Specifically, we want that to
 * return the player to a "Your move:" prompt, aborting the current
 * search if there is one.
 */
#define INITIALISING 0	/* Still setting things up at the start */
#define WAITING 1	/* Sitting at a prompt, or something */
#define THINKING 2	/* Contemplating the next move */
#define CONFUSING 3	/* Somewhere else */
#define SULKING	4	/* Will quit if interrupted again. */

/* And this variable holds the current state.
 */
static int state=INITIALISING;

/* When we're WAITING or THINKING, the following variable
 * describes where we should go if interrupted.
 */
static jmp_buf continuation;

static void handle_sigint(int sig) {
  if (sig!=SIGINT) return;	/* shouldn't really be needed */
  switch(state) {
    case INITIALISING:
      printf("[Ouch! You've killed me too early. I'm quitting.]\n");
      exit(1);
    case WAITING:
      printf("\n");
      signal(sig, &handle_sigint);
      longjmp(continuation, 1);
    case THINKING:
      signal(sig, &handle_sigint);
      longjmp(continuation, 1);
    case CONFUSING:
      signal(sig, &handle_sigint);
      printf("[Ouch! Now I'm all confused. I'm ignoring that.]\n");
      state=SULKING;
      return;
    case SULKING:
      printf("[OK, I get the message. I'm quitting.]\n");
      exit(1);
    default:
      printf("[This can't happen. Bye bye.]\n");
      exit(1);
  }
}

/* We have four 256-element arrays for computing the static
 * evaluation, measuring the total distance-to-back-rank
 * plus bad-piece-positions of Blue or Red pieces. Since the
 * distances are small, we can use arrays of bytes.
 * (It would be possible to use only two (larger) lookup tables,
 * but that would trash the cache. It would be possible to
 * use none, but that would be much slower.)
 */
static byte blue0to7static[256];
static byte blue8to15static[256];
static byte red0to7static[256];
static byte red8to15static[256];

static void setup_static_tables(void) {
  static const int count[16] = { 0,1,1,2,1,2,2,3, 1,2,2,3,2,3,3,4 };
  int i;
  for (i=0; i<256; ++i)
    blue0to7static[i] = 4*(4*count[i&15] + 3*count[(i>>4)&7] + 2*(i>>7))
                        + 2*((i&1) + ((i>>3)&1))
                        + ((i>>4)&1) + ((i>>6)&1);
  for (i=0; i<256; ++i)
    blue8to15static[i] = 4*(2*(i&1) + 1*count[(i>>1)&7] /* + 0*count[i>>4] */)
                         + ((i>>1)&1) + ((i>>3)&1)
                         + ((i>>5)&1) + ((i>>6)&1);
  for (i=0; i<256; ++i)
    red0to7static[i] = 4*(/*0*count[i&15]*/ + 1*count[(i>>4)&7] + 2*(i>>7))
                       + ((i>>1)&1) + ((i>>2)&1)
                       + ((i>>4)&1) + ((i>>6)&1);
  for (i=0; i<256; ++i)
    red8to15static[i] = 4*(2*(i&1) + 3*count[(i>>1)&7] + 4*count[i>>4])
                        + ((i>>1)&1) + ((i>>3)&1)
                        + 2*(((i>>4)&1) + ((i>>7)&1));
}

/* We make wins/losses slightly less extreme as the game proceeds,
 * so that the search prefers quick wins and slow losses.
 * To do this we need to remember what move it is. The variable
 * |ply_number| actually holds the ply number at the end of the
 * current search; subtracting |depth| from it in |Eval| gives
 * what we need. It's OK to be a little sloppy about this: it
 * won't affect the outcome, but only how quickly we get there.
 */
static int ply_number;

#define WIN 512
#define LOSE (-512)

/* |StaticEval(pos)| is the evaluation of |pos| from Blue's point of view.
 * Higher is better.
 * This doesn't take into account the special cases (game over, no move).
 */
#define StaticEval(pos) ((int)red8to15static[(pos)>>24] \
                        + (int)red0to7static[((pos)>>16)&255] \
                        - (int)blue8to15static[((pos)>>8)&255] \
                        - (int)blue0to7static[(pos)&255])

/* |Reverse(pos)| is the position obtained by reversing the roles of the
 * two players.
 */
#define Reverse(pos) (((word)rbyte[(pos)&255]<<24) \
                     + ((word)rbyte[((pos)>>8)&255]<<16) \
                     + ((word)rbyte[((pos)>>16)&255]<<8) \
                     + (word)rbyte[(pos)>>24])

/* The bulk of the work of reversal (which, incidentally, is just
 * bit-reversal) is contained in a lookup table:
 */
static byte rbyte[256];

static void setup_reverse_table(void) {
  static const int table16[] = { 0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15};
  int i;
  for (i=0; i<256; ++i) {
    rbyte[i] = table16[i>>4] + 16*table16[i&15];
  }
}

/* If neither player can move but neither has all pieces on
 * the back rank, the game is over and the winner is whichever
 * player has more pieces. (If the numbers are equal, the game
 * is drawn.)
 * We use lookup tables for this, too.
 */
static byte popcount[256];

static void setup_popcount_table(void) {
  static const int count[16] = { 0,1,1,2,1,2,2,3, 1,2,2,3,2,3,3,4 };
  int i;
  for (i=0; i<256; ++i) {
    popcount[i] = count[i&15] + count[i>>4];
  }
}

#define NBlue(pos) (popcount[(pos)&255]+popcount[((pos)>>8)&255])
#define NRed(pos) (popcount[((pos)>>16)&255]+popcount[(pos)>>24])
#define FinalScore(pos) (128*(NBlue(pos)-NRed(pos)))

/* We have a hash table, mapping positions to (depth,value,move)
 * triples. We use it in two ways.
 * 1. If we are evaluating a position and we find an eval of equal
 *    depth in the hash table, we return that at once.
 * 2. At each search iteration, we order moves according to the
 *    scores their corresponding positions have in the hash table.
 * It's OK if hash table entries go away sometimes (it might
 * slow us down but won't affect our answers much); it's not OK
 * if hash table entries contain misinformation.
 * We use simple linear hashing; if there's a collision, we keep
 * the newer entry. (This could use some experimentation.)
 *
 * A hash table entry contains:
 *  - The actual position it represents
 *  - The depth to which it has been analysed
 *  - The score it was assigned
 *  - Whether that score was exact, or the result of an alpha or beta cutoff
 *  - The apparently best move in the position.
 * Fitting this into 4 words is not difficult. Fitting it into 2 would
 * be impossible (without an expensive treatment of best moves).
 * Fitting it into 3 would be pretty easy but slow things down a little.
 */
typedef struct {
  word position;
  int depth_and_type;	/* depth in bits 8..15, type in 0..7 */
  int score;
  word move;			/* or 0 */
} HashEntry;

/* Score types:
 */
#define EXACT 0	/* e->score is the evaluation of e->position at depth e->depth */
#define LOWER 1	/* e->score is a lower bound on ... */
#define UPPER 2	/* e->score is an upper bound on ... */

static HashEntry * hash_table;

/* How many (16-byte) entries in the hash table?
 */
#ifndef HASH_SIZE
#define HASH_SIZE 131072
#endif

#if (HASH_SIZE&(HASH_SIZE-1))
#error HASH_SIZE must be a power of 2.
#endif

static void clear_hash_table(void) {
  memset(hash_table,0,HASH_SIZE*sizeof(HashEntry));
}

static void partially_clear_hash_table(void) {
  int i;
  for (i=0; i<HASH_SIZE; ++i) {
    HashEntry * entry = hash_table+i;
    int s = entry->score;
    switch(entry->depth_and_type & 255) {
      case EXACT: if (s<=-128 || s>=128) continue;
      case LOWER: if (s>=128) continue;
      case UPPER: if (s<=-128) continue;
    }
    /* We get here iff the score isn't enough to determine
     * that this is a win or a loss.
     */
#if 0
    entry->position=0;	/* enough to clear the entry */
#else
    /* Don't delete old entries; just make them very unattractive.
     * This means that they will only get used at leaf nodes.
     */
    entry->depth_and_type |= 0x80000000;
#endif
  }
}

static void setup_hash_table(void) {
  hash_table = malloc(HASH_SIZE*sizeof(HashEntry));
  if (!hash_table) {
    fprintf(stderr, "No room for hash table.\n");
    exit(1);
  }
  clear_hash_table();
}

/* If asked, we can display a lot of rather unexciting information
 * about how useful the hash table has been. The information is
 * collected in |Eval|, and stored in these variables.
 */
static size_t n_insertions;
static size_t n_collisions;
static size_t n_hits;
static size_t n_useless_hits;
static size_t n_nodes;

/* Display boring hash table stats or not?
 */
static int statsP=0;

static void clear_stats(void) {
  n_insertions=n_collisions=n_hits=n_useless_hits=0;
}

static void report_stats(void) {
  if (statsP) {
    size_t n_useful = n_hits-n_useless_hits;
    printf("Nodes:           %6d\n", n_nodes);
    printf("Hits:            %6d (%d%%)\n", n_hits, (100*n_hits)/n_nodes);
    printf("Conclusive hits: %6d (%d%% of nodes)\n", n_useful,
                                                     (100*n_useful)/n_nodes);
    printf("Insertions:      %6d\n", n_insertions);
    printf("Collisions:      %6d\n", n_collisions);
    printf("Real collisions: %6d (doesn't count inconclusive hits)\n",
                                     n_collisions-n_useless_hits);
  }
}

/* To make a position into a hash address we munge it a little
 * and then mask off all except the low bits. The munging
 * is rather arbitrary; it's derived from a couple of goodish
 * very simple RNGs, with a little tweaking to make it more
 * effective here.
 */
#define HASH(into,pos) { \
  into=pos^(pos>>16);\
  into*=69069;\
  into^=into<<13;\
  into^=into>>17;\
  into^=into<<5;\
  into*=69069;\
  into^=into>>16;\
  into&=HASH_SIZE-1; }

/* Record information about a position in the hash table.
 * This is only ever invoked when there is a suitable pointer
 * called |entry|, please note.
 */
#define REMEMBER(p,d,s,m) { \
  ++n_insertions; \
  if (entry->position) ++n_collisions; \
  entry->position = p; \
  entry->depth_and_type = d; \
  entry->score = s; \
  entry->move = m; }

/* Useful building blocks for |Enumerate| below.
 * |Maybe(from,to)| expands to code to try a plain move
 * from |from| to |to|; it doesn't consider the possibility
 * of jumps over |to|.
 * |MaybeJump(from,to,past)| expands to code that does
 * consider the possibility of a jump.
 */
#define Maybe(from,to) \
  if (!(occupied&(to))) { *space++ = Reverse(pos+((to)-(from))); }
#define MaybeJump(from,to,past) \
  if (!(occupied&(to))) { *space++ = Reverse(pos+((to)-(from))); } \
  else if (!(pos&(to)) && !(occupied&(past))) { \
    word p2 = pos+(past)-(from)-((to)<<16); \
    *space++ = Reverse(p2); }

/* Slightly higher-level building blocks.
 * |Maybexy(from,toL,[pastL],toR,[pastR])|
 * deals with all the possible moves from |from|.
 * |x| is 0/1 depending on whether one can leap over the |toL| space;
 * similarly for |y| and |toR|.
 * |Maybe0(from,to)| and |Maybe1(from,to,past)|
 * are just like |Maybe| and |MaybeJump| except that they
 * also check we have a piece at |from|.
 */
#define Maybe00(from,toL,toR) \
  if (pos&(from)) { Maybe(from,toL) Maybe(from,toR) }
#define Maybe01(from,toL,toR,pastR) \
  if (pos&(from)) { Maybe(from,toL) MaybeJump(from,toR,pastR) }
#define Maybe10(from,toL,pastL,toR) \
  if (pos&(from)) { MaybeJump(from,toL,pastL) Maybe(from,toR) }
#define Maybe11(from,toL,pastL,toR,pastR) \
  if (pos&(from)) { MaybeJump(from,toL,pastL) MaybeJump(from,toR,pastR) }
#define Maybe0(from,to) if (pos&(from)) { Maybe(from,to) }
#define Maybe1(from,to,past) if (pos&(from)) { MaybeJump(from,to,past) }

/* |Enumerate(pos,space)| enumerates legal moves from |pos|,
 * placing the resulting positions at |space[i]| for i from 0 upwards.
 * Blue (to play) has <= 4 pieces, each with <= 2 moves, so we
 * only need 8 words to record all the possible moves.
 * The return value points just after the last position stored.
 * This does a lot of branching; there might be a better way to
 * implement it.
 * NB that the positions produced are from the point of the
 * other player, whose turn it now is to move.
 */
static word * Enumerate(word pos, word * space) {
  word occupied = pos | (pos>>16);
  /*      from     toL      pastL    toR      pastR */
  Maybe1( FirstL,                    SecondL, MiddleL)
  Maybe01(FirstLM, SecondL,          SecondM, MiddleR)
  Maybe10(FirstRM, SecondM, MiddleL, SecondR)
  Maybe1( FirstR,  SecondR, MiddleR)
  /*      from     toL      pastL    toR      pastR */
  Maybe1( SecondL,                   MiddleL, FourthM)
  Maybe11(SecondM, MiddleL, FourthL, MiddleR, FourthR)
  Maybe1( SecondR, MiddleR, FourthM)
  /*      from     toL      pastL    toR      pastR */
  Maybe11(MiddleL, FourthL, BackL,   FourthM, BackRM)
  Maybe11(MiddleR, FourthM, BackLM,  FourthR, BackR)
  /*      from     toL      pastL    toR      pastR */
  Maybe00(FourthL, BackL,            BackLM)
  Maybe00(FourthM, BackLM,           BackRM)
  Maybe00(FourthR, BackRM,           BackR)
  return space;
}

/* Some handy stuff for debugging purposes:
 */

#ifdef THRESHOLD
#define D(stmt) if (depth>=THRESHOLD) { stmt }
static void ind(int d) {
  int i;
  for (i=d-2;i<THRESHOLD;++i) printf("  ");
  printf("[%d] ", ply_number-d);
}
#define I ind(depth)
#define I1 ind(depth-1)
#else
#define D(stmt)
#endif

#ifdef THRESHOLD
static char * compact(word pos) {
  static char result[21]={0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0};
  int i;
  char * cp=result;
  for (i=0; i<4; ++i) *cp++=".01"[((pos>>i)&1)+((pos>>(i+15))&2)];
  *cp++=':';
  for (i=4; i<7; ++i) *cp++=".01"[((pos>>i)&1)+((pos>>(i+15))&2)];
  *cp++=':';
  for (i=7; i<9; ++i) *cp++=".01"[((pos>>i)&1)+((pos>>(i+15))&2)];
  *cp++=':';
  for (i=9; i<12; ++i) *cp++=".01"[((pos>>i)&1)+((pos>>(i+15))&2)];
  *cp++=':';
  for (i=12; i<16; ++i) *cp++=".01"[((pos>>i)&1)+((pos>>(i+15))&2)];
  return result;
}
#endif

/* |Eval(pos,depth,alpha,beta)| is the evaluation of |pos|
 * by minimax (alpha-beta) search to depth |depth|,
 * from Blue's point of view.
 *
 * Alpha-beta means: what this is actually required to return
 * is a number satisfying the following constraints:
 *   - If the position evaluates to something in [alpha,beta]
 *     then this must be returned.
 *   - If it evaluates to something (x, say) in [-oo,alpha] then
 *     something in [x,alpha] must be returned.
 *   - If it evaluates to something (x, say) in [beta,oo] then
 *     something in [beta,x] must be returned.
 * The point is that we can do this recursively in much the same
 * way as we do minimax, but the cutoffs make life a bit easier.
 * So: to compute Eval(P,d,a,b), suppose we can move to M1, ..., Mn.
 * Then write Ek for {-E(-Mk,d-1,-b,-ak)} where a1=a and
 * a(k+1) = max(ak,Ek). (I'm writing -M for the reverse of position M.)
 *   - If some Ek is >= b, then -Mk is really at least as bad as -Ek,
 *     so this position is at least as good as Ek. So we can safely
 *     return Ek.
 *   - If all Ek are <= a, then every position we can move to
 *     is worth at least -a to the opponent; hence so is this
 *     one; hence it's worth <= a to us. So we can safely return a.
 *   - Otherwise, the biggest Ek we get is >= a. Since it's the
 *     biggest, it must also be >= ak. Hence, Ek is the actual
 *     value of Mk. And no position we can move to is better for
 *     us than this; so we can safely return Mk.
 * The real value of all this stuff is in that first clause: we
 * can terminate an evaluation as soon as we find anything whose
 * value is >= b.
 *
 * If |moveless| is true then the other player has just passed
 * for lack of a legal move, and we should do the right thing
 * if we can't move either.
 */
static int Eval(word pos, int depth, int alpha, int beta, int moveless) {
D(I1;printf("*** Eval(%s) in [%d,%d] ***\n",compact(pos),alpha,beta);)
++n_nodes;
  if ((pos>>16)==0) return WIN-(ply_number-depth);
  else if ((pos<<16)==0) return LOSE+(ply_number-depth);
  else if ((pos&0xFFF)==0) return WIN-(ply_number-depth);
  else if ((pos&0xFFF00000)==0) return LOSE+(ply_number-depth);
  --depth;
  /* Is everything about the position in the hash table already?
   */
  { HashEntry * entry;
    { word hash; HASH(hash,pos); entry=hash_table+hash; }
    if (entry->position==pos) {
      int edt = entry->depth_and_type;
D(I;printf("hashed[%d], score=%d%s\n",edt>>8,entry->score,
(edt&255)?(edt&1)?" (LOWER)":" (HIGHER)":"");)
      /* Prefer hashed score to full eval if it's at least as deep,
       * *or* if we're at depth zero (in which case, the hash entry
       * must be at least that deep really even if it's left over
       * from a previous game).
       */
      if (edt>>8 >= depth || depth==0) {
        ++n_hits;
        switch(edt&255) {
          case EXACT: return entry->score;
          case LOWER: if (entry->score >= beta) return beta;
                      break;
          case UPPER: if (entry->score <= alpha) return alpha;
        }
        ++n_useless_hits;
      }
      else {
        int s=entry->score;
        switch(edt&255) {
          case EXACT:
            if (s>=128 || s<=-128) {
              entry->depth_and_type=edt+100*256;
              ++n_hits;
              return s;
            }
            break;
          case LOWER:
            if (s>=128) {
              entry->depth_and_type=edt+100*256;
              ++n_hits;
              if (s>=beta) return beta; else ++n_useless_hits;
            }
            break;
          case UPPER:
            if (s<=-128) {
              entry->depth_and_type=edt+100*256;
              ++n_hits;
              if (s<=alpha) return alpha; else ++n_useless_hits;
            }
        }
      }
    }
    /* Too bad: we have to do some searching. So, enumerate moves
     * [and sort them into order according to their scores from
     * the hash table -- actually we don't do this].
     */
    { word moves[8];
      word * end = Enumerate(pos, moves);
      /* If there are no moves, take special action. Specifically:
       * if we weren't called with |moveless!=0| then we just need
       * to let the other side move; if we were, then we're looking
       * at a game-end position and need to work out who has won.
       */
      if (end==moves) {
        if (moveless) {
          alpha = FinalScore(pos);
          REMEMBER(pos, (depth<<8)+EXACT, alpha, Reverse(pos));
D(I;printf("returning %d [MOVELESS]\n",alpha);)
          return alpha;
        }
        else {
          int eval = depth ? -Eval(Reverse(pos),depth,-beta,-alpha,1)
                           : StaticEval(pos);
          int type = eval>alpha ? eval<beta ? EXACT : LOWER
                                : UPPER;
          REMEMBER(pos, (depth<<8)+type, eval, Reverse(pos));
D(I;printf("returning %d [MOVELESS]\n",eval);)
          return eval;
        }
      }
      /* If |depth| was 1 (so is now 0) then we just need to find
       * the best move according to the static evaluator.
       */
      if (depth==0) {
        word best_move=0;
        word * mp;
        for (mp=moves; mp!=end; ++mp) {
          word m=*mp;
          int e;
          /* |e| is to contain a static evaluation of this position,
           * considered as a position for the opponent to hold, but
           * with the eval from *our* perspective.
           */
          if ((m>>16)==0) e=(ply_number-depth)-WIN;
          else if ((m<<16)==0) {
            alpha=-LOSE-(ply_number-depth); best_move=m; break; }
          else if ((m&0xFFF)==0) e=(ply_number-depth)-WIN;
          else if ((m&0xFFF00000)==0) {
            alpha=-LOSE-(ply_number-depth); best_move=m; break; }
          else e=-StaticEval(m);
          if (e>alpha) {
            if (e>=beta) {
              REMEMBER(pos,LOWER,beta,m);
              return beta;
            }
            alpha=e; best_move=m;
          }
        }
        REMEMBER(pos, best_move ? EXACT : UPPER, alpha, best_move);
        return alpha;
      }
      /* If there is only one move, we have essentially nothing
       * to do.
       */
      if (end==moves+1) {
        int eval = -Eval(moves[0],depth,-beta,-alpha,0);
        REMEMBER(pos, eval>alpha ? eval<beta ? EXACT : LOWER : UPPER,
                 eval, moves[0]);
        return eval;
      }
      /* There is more than one move. If a previous evaluation of
       * the position has recommended a particular move, look at
       * that first. (I've tried more sophisticated attempts at
       * move ordering. They make everything worse.)
       */
      if (entry->position==pos && entry->move) {
        word m=entry->move;
        word * mp;
        for (mp=moves; mp!=end; ++mp) {
          if (*mp==m) {
            if (mp!=moves) { *mp=*moves; *moves=m; break; }
          }
        }
      }
      /* Now recursively evaluate each position, keeping alpha
       * valid and pruning with beta. This is the heart of the
       * alpha-beta algorithm.
       */
      { const word * mp = moves;
        word best_move = 0;
        while (mp!=end) {
          word move=*mp++;
          int eval;
D(I;printf("try: %s\n",compact(move));)
          eval=-Eval(move,depth,-beta,-alpha,0);
D(I;printf("trying %s yielded %d (for us)\n",compact(move),eval);)
          if (eval>alpha) {
            if (eval>=beta) {
D(I;printf("returning %d [BETA:%s]\n",beta,compact(move));)
              /* We can return. Note that our score is only a lower bound.
               */
              REMEMBER(pos, (depth<<8)+LOWER, eval, move);
              return eval;
            }
            /* |alpha| is no longer the best lower bound we know,
             * so it must be updated.
             */
D(I;printf("alpha changes from %d to %d\n",alpha,eval);)
            alpha=eval; best_move=move;
          }
        }
        /* Return |alpha|, updating the hash table.
         */
D(I;printf("returning %d [MOVE:%s]\n",alpha,compact(best_move));)
        REMEMBER(pos, (depth<<8) + (best_move?EXACT:UPPER), alpha, best_move);
        return alpha;
      }
    }
  }
}

/* A utility function for |move_string|. Returns the position
 * of the lowest 1-bit in a word. This doesn't have to be
 * efficient.
 */
static int find_bit(word w) {
  static int p[16] = { -1,0,1,0, 2,0,1,0, 3,0,1,0, 2,0,1,0 };
  int i;
  for (i=0; i<32; i+=4) {
    if (w&15) return i+p[w&15];
    w>>=4;
  }
  return -1;
}

/* Given two positions, determine what move Blue had to make
 * to get from one to the other; return it as a string in
 * human-readable form. If |humanp| then the move is a human
 * move (or, more likely, a computer-calculated move for the
 * human player) and the orientation of |old| is the one we
 * want; otherwise it's a computer move, and the orientation
 * of |new| is the one we want.
 */
static const char * move_string(word old, word new, int humanp) {
  static char result[16];
  if (!new || !old) return "none";
  new = Reverse(new);
  /* Find the bit positions of removed pieces and new pieces. */
  { int old_blue, captured_red, new_blue;
    new_blue = find_bit(new&~old);
    { word removed = old&~new;
      old_blue = find_bit(removed);
      removed &= ~(1ul<<old_blue);
      if (removed) captured_red = find_bit(removed>>16);
      else captured_red = -1;
    }
    if (!humanp) {
      old_blue = 15-old_blue;
      new_blue = 15-new_blue;
      if (captured_red>=0) captured_red = 15-captured_red;
    }
    if (captured_red>=0)
      sprintf(result, "%d (x%d) %d", old_blue, captured_red, new_blue);
    else
      sprintf(result, "%d %d", old_blue, new_blue);
  }
  return result;
}

/* |search_depth| is the number of ply |ChooseMove| below will
 * search.
 */
static int search_depth=30;

/* |ChooseMove(pos,humanp)| makes the best move it can, and returns
 * the resulting position (from the point of view of the other
 * player, as usual). |humanp| is passed through to |move_string|.
 */
static word ChooseMove(word pos, int humanp) {
  { int eval;
    time_t t = time(0);
    if (setjmp(continuation)) {
      word moves[8];
      word * end = Enumerate(pos,moves);
      printf("[You interrupted me! I'm making a random move.]\n");
      if (end==moves) return Reverse(pos);
      else return moves[0];
    }
    state=THINKING;
    /* Game obviously over? */
    if ((pos&0xFFF)==0 || (pos&0xFFF00000)==0) return 0;
    /* For some games, iterative deepening is a win because it
     * populates the hash table and helps with move ordering, thus
     * making alpha-beta more effective. It turns out that for
     * this game, move ordering doesn't matter too much and so
     * iterative deepening is useless. So we just call |Eval|,
     * and when it returns the chosen move will be sitting in
     * the hash table.
     */
    ply_number += search_depth;
    n_nodes=0; clear_stats();
    eval = Eval(pos, search_depth, -1024,1024, 0);
    ply_number -= search_depth;
    /* That's the work done. Now to report on it.
     */
    printf("[Eval at depth %d is %d (%d node%s)",
           search_depth, eval, n_nodes, n_nodes==1?"":"s");
    { HashEntry * entry;
      { word hash; HASH(hash,pos); entry = hash_table + hash; }
      if (entry->position != pos) { printf("; game is over]\n"); return 0; }
      printf("; move: %s]\n", move_string(pos,entry->move,humanp));
      report_stats();
      { int dt = time(0)-t;
        printf("[That took me %d second%s.]\n", dt, dt==1?"":"s");
      }
      return entry->move;
    }
  }
}

/* For purely cosmetic reasons, we allow the player to use pieces labelled
 * "X" or "O". The default is "X".
 */
static int blue_is_x = 0;

/* Display the position. (It would have been neater to combine these
 * two functions into one. They happen not to have been written that
 * way, and I'm too lazy to change them now.)
 */

static void display_position_small(word pos) {
  /* 18+1=19 chars per line */
  static char board[] =
",----------------.\n" /* 0*19 ... 1*19-1 */
"| xx  xx  xx  xx |\n" /* 1*19 ... 2*19-1 */
"|   xx  xx  xx   |\n" /* 2*19 ... 3*19-1 */
"|     xx  xx     |\n" /* 3*19 ... 4*19-1 */
"|   xx  xx  xx   |\n" /* 4*19 ... 5*19-1 */
"| xx  xx  xx  xx |\n" /* 5*19 ... 6*19-1 */
"`----------------'\n";/* 6*19 ... 7*19-1 */
/* 2 4 6 8 a c e */
  static int offsets[] = { 5*19+2, 5*19+6, 5*19+10, 5*19+14,
                              4*19+4, 4*19+8, 4*19+12,
                                  3*19+6, 3*19+10,
                              2*19+4, 2*19+8, 2*19+12,
                          1*19+2, 1*19+6, 1*19+10, 1*19+14 };
  static const char * pieces[] = { "::", "<>", "><", "::" };
  int i;
  if (pos==0) { printf("[--- The game is over. ---]\n"); return; }
  for (i=0; i<16; ++i) {
    int offset = offsets[i];
    word who = ((pos>>i)&1) + ((pos>>(i+15))&2);
    const char * piece = pieces[blue_is_x ? who^3 : who];
    board[offset]=piece[0];
    board[offset+1]=piece[1];
  }
  printf("%s",board);
  printf("[Static eval is %d]\n", StaticEval(pos));
}

static void display_position_large(word pos) {
  static char board[] =
/*12345678901234567890123456789012 so 33 characters per line including \n. */
",------.,------.,------.,------.\n"/*0*/
"|      ||      ||      ||      |\n"/*1*/
"`.    ,'`.    ,'`.    ,'`.    ,'\n"/*2*/
"  `.,'    `.,'    `.,'    `.,'  \n"/*3*/
"    `.    ,'`.    ,'`.    ,'    \n"/*4*/
"      `.,'    `.,'    `.,'      \n"/*5*/
"      ,'`.    ,'`.    ,'`.      \n"/*6*/
"    ,'    `.,'    `.,'    `.    \n"/*7*/
"  ,'`.    ,'`.    ,'`.    ,'`.  \n"/*8*/
",'    `.,'    `.,'    `.,'    `.\n"/*9*/
"|      ||      ||      ||      |\n"/*10*/
"`------'`------'`------'`------'\n"/*11*/;
  int i;
  int offset=9*33-5;
  if (pos==0) { printf("[--- The game is over. ---]\n"); return; }
  for (i=0; i<16; ++i) {
    word who = ((pos>>i)&1) + ((pos>>(i+15))&2);
    const char * piece = "    /\\\\/\\//\\    "+4*(blue_is_x ? who^3 : who);
    if (i==4) offset=7*33+7;
    else if (i==7) offset=5*33+11;
    else if (i==9) offset=3*33+7;
    else if (i==12) offset=33+3;
    else offset+=8;
    board[offset]=piece[0];
    board[offset+1]=piece[1];
    board[offset+33]=piece[2];
    board[offset+33+1]=piece[3];
  }
  printf("%s", board);
  printf("[Static eval is %d]\n", StaticEval(pos));
}

static int largep=1;

static void display_position(word pos) {
  if (largep) display_position_large(pos);
  else display_position_small(pos);
}

#define InitialPosition 0xF000000F

/* ghastly hacky front end */
int main(void) {
  word prev;
  int prev_pn;
  word pos;
  char line0[256];
  int displayP=1;
  printf(
"Welcome to GOSSIP: Gareth's Oska Searcher, Solver and Infallible Player.\n"
"Excuse me a few microseconds while I set up some tables.\n"
"Type '\?' for instructions; '\?\?' for a reminder of the space numbers.\n");
  signal(SIGINT, &handle_sigint);
  setup_static_tables();
  setup_popcount_table();
  setup_reverse_table();
  setup_hash_table();
Beginning:
  pos=InitialPosition; prev=0;
  ply_number=0; prev_pn=0;
  printf("\nInitial position:\n");
  while (1) {
    state=CONFUSING;
    if (displayP) display_position(pos); else displayP=1;
    printf("Your move: "); fflush(stdout);
    if (setjmp(continuation)) continue;
    state=WAITING;
    if (fgets(line0,256,stdin)) {
      char * line=line0;
      while (isspace(*line)) ++line;
      { char * cp=line;
        while (*cp) { *cp=tolower(*cp); ++cp; }
        if (cp!=line && cp[-1]=='\n') cp[-1]=0;
      }
      state=CONFUSING;
      if (!strcmp(line,"??")) {
        printf(
",----------------.\n"
"| 12  13  14  15 |\n"
"|   :9  10  11   |\n"
"|     :7  :8     |\n"
"|   :4  :5  :6   |\n"
"| :0  :1  :2  :3 |\n"
"`----------------'\n");
      }
      else if (!strcmp(line,"?") || !strcmp(line,"help")) {
        printf(
"Moves:\n"
"  To move, enter two numbers: the space you're moving from\n"
"  and the space you're moving to.\n"
"Commands:\n"
"  swap   change sides (computer plays, then it's your turn)\n"
"  play   make computer play your move, and then its; then it's your turn\n"
"  pass   make no move (this is cheating unless you have none)\n"
"  flip   rotate board (changing roles), but make no move\n"
"  undo   retract previous move (this is also cheating)\n"
"  large  use large diagrams to show positions\n"
"  small  use small diagrams to show positions\n"
"  show   display the current position\n"
"  quit   leave the program\n"
"  new    start a new game\n"
"  edit   (followed by a position) forcibly rearrange the board\n"
"  x,o    determine labelling of your pieces\n"
"  depth  (followed by a positive integer) determine how deeply GOSSIP searches\n"
"  clear  clear GOSSIP's hash table\n"
"  stats  (followed by 'on' or 'off') turn on/off display of boring statistics\n"
"Help:\n"
"  ?      display this information (or: 'help')\n"
"  ??     display a diagram showing the board numbering\n"
"Rules:\n"
"  Move a piece diagonally forward one space into a blank space;\n"
"  or jump a single opposing piece, removing it from the board.\n"
"  If you have no legal moves, you must pass.\n"
"  You win if (1) your opponent has no pieces left, or (2) all your\n"
"  pieces are on the opponent's back rank, or (3) neither player has\n"
"  a legal move and you have more pieces than your opponent.\n"
"Positions (for EDIT):\n"
"  16 characters, each . or o or x. Then a space, and o/x indicating\n"
"  which player is moving up the board and is to move. Omitting this\n"
"  means: same as at present. Positions are in numbered order.\n"
        );
        continue;
      }
      else if (!strcmp(line,"pass")) { ++ply_number; goto Move; }
      else if (!strcmp(line,"play")) {
        /* this means: get computer to play this move,
         * and then continue as itself.
         */
        prev = pos; prev_pn=ply_number;
        pos = ChooseMove(pos,1); state=CONFUSING;
        pos = Reverse(pos);
        ++ply_number;
        goto Move;
      }
      else if (!strcmp(line,"swap")) {
        /* this means: get computer to play this move,
         * and then make it your turn with roles reversed.
         */
        prev = pos; prev_pn = ply_number;
        printf("After rotating board:\n");
        blue_is_x ^= 1;
        display_position(Reverse(pos));
        pos = ChooseMove(pos,0); state=CONFUSING;
        ++ply_number;
        printf("After the computer's move:\n");
        continue;
      }
      else if (!strcmp(line,"flip")) {
        /* this means: rotate the board, and leave player at bottom still
         * to move. Sort of like SWAP if the computer chooses to pass.
         */
        pos=Reverse(pos); blue_is_x ^= 1;
        printf("After rotating board:\n");
        continue;
      }
      else if (!memcmp(line,"edit ",5)) {
        const char * cp=line+5;
        int i;
        word new_pos=0;
        while (isspace(*cp)) ++cp;
        for (i=0; i<16; ++i) {
          switch(*cp++) {
            case '.': continue;
            case 'o': new_pos |= 1ul<<i; continue;
            case 'x': new_pos |= 65536ul<<i; continue;
            default: printf("That doesn't make sense.\n"); goto EditFail;
          }
        }
        while (isspace(*cp)) ++cp;
        if (*cp=='x' || (*cp==0 && blue_is_x)) {
          new_pos=(new_pos>>16)|(new_pos<<16); blue_is_x=1; }
        else if (*cp=='o' || *cp==0) { blue_is_x=0; }
        else { printf("That doesn't make sense.\n"); goto EditFail; }
        prev=pos; pos=new_pos; prev_pn=ply_number; ply_number=0;
EditFail:
        continue;
      }
      else if (!strcmp(line,"undo")) {
        if (prev) { word t=prev; prev=pos; pos=t; ply_number=prev_pn; }
        else { printf("I can't do that.\n"); }
        continue;
      }
      else if (!strcmp(line,"x")) blue_is_x=1;
      else if (!strcmp(line,"o")) blue_is_x=0;
      else if (!strcmp(line,"new")) {
        partially_clear_hash_table();
        goto Beginning;
      }
      else if (!strcmp(line,"quit")) return 0;
      else if (!strcmp(line,"large")) { largep=1; continue; }
      else if (!strcmp(line,"small")) { largep=0; continue; }
      else if (!strcmp(line,"show")) continue;
      else if (!memcmp(line,"depth ",6)) {
        int d;
        if (!sscanf(line+6,"%d",&d)) printf("What depth?\n");
        else if (d<1) printf("Depth must be at least 1.\n");
        else printf("Searching %d ply from now on.\n", search_depth=d);
        displayP=0;
      }
      else if (!strcmp(line,"clear")) {
        clear_hash_table();
        printf("Hash table cleared.\n");
        displayP=0;
        continue;
      }
      else if (!memcmp(line,"stats ",6)) {
        const char * cp=line+6;
        while (isspace(*cp)) ++cp;
        if (!strcmp(cp,"on")) {
          printf("OK, stats display is on.\n");
          statsP=1;
        }
        else if (!strcmp(cp,"off")) {
          printf("OK, stats display is off.\n");
          statsP=0;
        }
        else printf("I don't understand whether you want stats on or off.\n");
        displayP=0;
      }
      else {
        int from,to;
        displayP=0;
        if (sscanf(line,"%d %d",&from,&to)!=2
            || from<0 || from>15 || to<0 || to>16) {
          printf("I don't understand.\n");
        }
        else {
          if (!(pos&(1ul<<from)))
            printf("You have no piece at %d.\n", from);
          else if ((pos|(pos>>16))&(1ul<<to))
            printf("There is a piece at %d.\n", to);
          else {
            static int r[16] = {0,0,0,0,1,1,1,2,2,3,3,3,4,4,4,4};
            static int s[5] = {0,3,5,7,10};
            int frow=r[from], trow=r[to];
            int fcol=from-s[frow], tcol=to-s[trow];
            if (trow==frow+1 && (tcol==fcol || tcol==fcol+1)) {
              prev=pos; prev_pn=ply_number;
              pos=pos-(1ul<<from)+(1ul<<to);
            }
            else if (trow==frow+2 && (tcol==fcol || tcol==fcol+2)) {
              int opp = s[frow+1]+fcol+((tcol-fcol)>>1);
              if (!(pos&(1ul<<(16+opp)))) {
                printf("There is no piece at %d.\n", opp);
                continue;
              }
              prev=pos; prev_pn=ply_number;
              pos=pos-(1ul<<from)+(1ul<<to) - (1ul<<(16+opp));
            }
            else { printf("Illegal move.\n"); continue; }
            ++ply_number;
            displayP=1;
Move:
            printf("After your move:\n");
            display_position(pos);
            pos = Reverse(pos);
            pos = ChooseMove(pos,0); state=CONFUSING;
            ++ply_number;
            printf("After the computer's move:\n");
          }
        }
      }
    }
    else exit(1);
  }
  return 0;
}