search.c

   1 // search.c
   2 // Copyright 2008 Tom Plick.
   3 // Begorra is released under GPL v2: see file COPYING for info.
   4
   5 // Alpha-beta and related functions.
   6
   7 #include "types.c"
   8
   9 double getPreciseTime(){
  10     struct timeval tv;
  11     gettimeofday(&tv, NULL);
  12     return tv.tv_sec + tv.tv_usec / 1000000.0;
  13 }
  14
  15 abInfo newABInfo(){
  16     abInfo inf;
  17     inf.nodes = 0ULL;
  18     inf.aborted = 0;
  19     inf.startTime = getPreciseTime();
  20     return inf;
  21 }
  22
  23
  24 #define INSERT_INTO_TABLE(vEntry, vDepth, vPoint) \
  25     do { \
  26         if (!info->aborted && vDepth > vEntry->depth){ \
  27             vEntry->depth = vDepth; \
  28             vEntry->point = vPoint; \
  29         } \
  30     } while (0)
  31
  32 // XXX Remove the "best" fuss; just get the best afterward from the
  33 //      table.  This will force the table to be at least 1K...
  34
  35 int alphaBeta(Position * const restrict pos, const int depth,
  36               int * const restrict best,
  37               int alpha, const int beta, abInfo * const info)
  38 {
  39     if (info->aborted) return 0;
  40
  41     if (++info->nodes % (1 << POLL_FREQUENCY) == 0){
  42         pollForInput(info);
  43     }
  44
  45     if (depth == 0)
  46         return tallyPos(pos);
  47
  48     Position child;
  49     int q = 0;
  50
  51     unsigned int slot = pos->hash % HASHSIZE;
  52     HashEntry * entry = &TransTable[slot];
  53     const int firstPoint = entry->point;
  54
  55 #define ALPHA_BETA_STEP  \
  56     do { \
  57         copyPosition(&child, pos);  \
  58         placeStone(&child, pt); \
  59         int value = -alphaBeta(&child, depth - 1, &q, -beta, -alpha, info); \
  60         if (value >= beta){ \
  61             INSERT_INTO_TABLE(entry, depth, pt); \
  62             return beta; \
  63         } else if (value > alpha){ \
  64             alpha = value; \
  65             *best = pt; \
  66         } \
  67     } while(0);
  68
  69     do {
  70         const int pt = firstPoint;
  71         if (pt){
  72             if (pt == pos->lastMoves[0]) continue;
  73             if (getStone(pos, pt)) continue;
  74
  75             ALPHA_BETA_STEP;
  76         }
  77     } while (0);
  78
  79     int adjustment = 0;
  80     for (int i = 0; i < BFLENGTH; i++){
  81         BoardInt field = pos->empty[i];
  82         if (i == BFLENGTH - 1)
  83             field &= ((1 << (SIZE % BFWIDTH)) - 1);
  84         if (i == firstPoint / BFWIDTH)
  85             field  &=  ~(1 << (firstPoint % BFWIDTH));
  86         if (i == pos->lastMoves[0] / BFWIDTH)
  87             field  &=  ~(1 << (pos->lastMoves[0] % BFWIDTH));
  88
  89         while (field){
  90             int bit = getLowestBit(field);
  91             int pt = bit + adjustment;
  92
  93             ALPHA_BETA_STEP;
  94             field -= (1 << bit);
  95         }
  96         adjustment += BFWIDTH;
  97     }
  98
  99     // a passing move
 100
 101     passTurn(pos);
 102     int value = -alphaBeta(pos, depth - 1, &q, -beta, -alpha, info);
 103     passTurn(pos);
 104
 105     if (value >= beta){
 106         INSERT_INTO_TABLE(entry, depth, 0);
 107         return beta;
 108     }
 109     if (value > alpha){
 110         alpha = value;
 111         *best = 0;
 112     }
 113
 114     INSERT_INTO_TABLE(entry, depth, *best);
 115     return alpha;
 116 }