src/moves.c

   1 /*  moves.c
   2     1 Mar 2007 */
   3
   4 /*
   5     This file is part of Arrocco, which is Copyright 2007 Thomas Plick
   6     (tomplick 'at' gmail.com).
   7
   8     Arrocco is free software; you can redistribute it and/or modify
   9     it under the terms of the GNU General Public License as published by
  10     the Free Software Foundation; either version 3 of the License, or
  11     (at your option) any later version.
  12
  13     Arrocco is distributed in the hope that it will be useful,
  14     but WITHOUT ANY WARRANTY; without even the implied warranty of
  15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16     GNU General Public License for more details.
  17
  18     You should have received a copy of the GNU General Public License
  19     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  20 */
  21
  22 #include <stdio.h>
  23 #include <time.h>
  24
  25 #define   BUT   &&
  26 #define   ON_BOARD(x)   (x >= 0 && x < 8)
  27
  28 // These are in _bits.c.
  29 extern const Int64 kingFields[64];
  30 extern const Int64 knightFields[64];
  31 extern const Int64 pawnMoveFields[2][64];
  32 extern const Int64 pawnCaptureFields[2][64];
  33 // extern const int areSquaresAdjacent[64][64];
  34
  35 const Int64 pawnFirstRowMask  = (255ULL <<  8) | (255ULL << 48);
  36 const Int64 pawnSecondRowMask = (255ULL << 16) | (255ULL << 40);
  37 const Int64 pawnThirdRowMask  = ~((255ULL << 24) | (255ULL << 32));
  38
  39
  40 // For the lowest bit functions, we assume x > 0.
  41
  42 #ifdef ASM
  43 #warning "Using ASM bit operations.  If this does not work, try 'make slow'."
  44
  45 int lowestBit(const Int64 x){
  46     return __builtin_ctzll(x);
  47 }
  48 int highestBit(const Int64 x){
  49     return 63 - __builtin_clzll(x);
  50 }
  51
  52 #else
  53
  54 int lowestBit(const Int64 x){
  55     int i;
  56     for (i = 0; i < 64; i++){
  57         if (x & (1ULL << i)) return i;
  58     }
  59     return 0;
  60 }
  61
  62 int highestBit(const Int64 x){
  63     int i;
  64     for (i = 63; i >= 0; i--){
  65         if (x & (1ULL << i)) return i;
  66     }
  67     return 0;
  68 }
  69
  70 #endif  /*  ifdef ASM  */
  71
  72
  73 int * extractBitsInto(Int64 bitfield, int * dests){
  74     while (bitfield){
  75         const int dst = lowestBit(bitfield);
  76         *dests++ = dst;
  77         bitfield ^= TWOTOTHE(dst);
  78     }
  79     return dests;
  80 }
  81
  82 Position * extractBitsAsMoves(const Position * const restrict pos, const int src, Int64 bitfield,
  83                     Position * restrict child){
  84     Position half = *pos;
  85     const int piece = half.board[src];
  86     setPieceAt(&half, src, 0);
  87     half.turn ^= 1;
  88
  89     const char * board = pos->board;
  90
  91     while (bitfield){
  92         const int dst = lowestBit(bitfield);
  93
  94         *child = half;
  95         setPieceAt(child, dst, piece);
  96
  97         const int captureWorth = pieceValues[board[dst]];
  98         child->value[0] -= captureWorth;
  99         child->value[1] += captureWorth;
 100         child++;
 101
 102         bitfield ^= TWOTOTHE(dst);
 103     }
 104     return child;
 105 }
 106
 107 #define MOVE_FUNCTION(x) \
 108     Position * x(const Position * const restrict pos, const int src, \
 109                        Position * restrict children, \
 110                  const Int64 ownerField, const Int64 opponentField)
 111 #define DEST_FUNCTION(x) \
 112     Int64 x(const Position * const restrict pos, const int src, \
 113             const Int64 occupancy[4])
 114
 115
 116 MOVE_FUNCTION(kingMoves){
 117     Int64 bitfield = kingFields[src] & ~(opponentField | ownerField);
 118     return extractBitsAsMoves(pos, src, bitfield, children);
 119 }
 120 MOVE_FUNCTION(kingCaptures){
 121     Int64 bitfield = kingFields[src] & opponentField;
 122     return extractBitsAsMoves(pos, src, bitfield, children);
 123 }
 124 DEST_FUNCTION(kingDestinations){ return kingFields[src]; }
 125
 126
 127 MOVE_FUNCTION(knightMoves){
 128     Int64 bitfield = knightFields[src] & ~(opponentField | ownerField);
 129     return extractBitsAsMoves(pos, src, bitfield, children);
 130 }
 131 MOVE_FUNCTION(knightCaptures){
 132     Int64 bitfield = knightFields[src] & opponentField;
 133     return extractBitsAsMoves(pos, src, bitfield, children);
 134 }
 135 DEST_FUNCTION(knightDestinations){ return knightFields[src]; }
 136
 137
 138 int promotionPieces[4] = {10, 4, 8, 6};
 139 Position * makePromotions(Position * children, const int howMany,
 140                 const Int64 moveField, const int side){
 141
 142     memcpy(children + howMany, children, howMany * sizeof(Position));
 143     memcpy(children + 2 * howMany, children, howMany * 2 * sizeof(Position));
 144     int k;
 145     int dsts[2] = {lowestBit(moveField), highestBit(moveField)};
 146     for (k = 0; k < 4 * howMany; k++){
 147         setPieceAt(&children[k], dsts[k & 1], promotionPieces[k / howMany] | side);
 148     }
 149     return children + 4 * howMany;
 150 }
 151
 152 MOVE_FUNCTION(pawnMoves){
 153     const int side = pos->board[src] & 1;
 154     Int64 moveField = pawnMoveFields[side][src] & ~(ownerField | opponentField);
 155
 156     // If a pawn on its starting row is blocked, then it cannot move at all.
 157     //    The bit fields leave the possibility that a pawn can move two squares;
 158     //    we prevent that here.
 159     if ((pawnFirstRowMask & (one << src)) BUT !(moveField & pawnSecondRowMask)){
 160         moveField &= pawnThirdRowMask;
 161     }
 162     Position * newChildren = extractBitsAsMoves(pos, src, moveField, children);
 163
 164     if (moveField && (src >> 3) == (side ? 1 : 6))
 165         return makePromotions(children, 1, moveField, side);
 166     else
 167         return newChildren;
 168 }
 169 MOVE_FUNCTION(pawnCaptures){
 170     const int side = pos->board[src] & 1;
 171     Int64 captureField = pawnCaptureFields[side][src] & opponentField;
 172     Position * newChildren = extractBitsAsMoves(pos, src, captureField, children);
 173     if (captureField && (src >> 3) == (side ? 1 : 6)){
 174         int howMany = (lowestBit(captureField) == highestBit(captureField)) ? 1 : 2;
 175         return makePromotions(children, howMany, captureField, side);
 176     } else
 177         return newChildren;
 178 }
 179 /* DEST_FUNCTION(pawnMoveDestinations){
 180     const int side = pos->board[src] & 1;
 181     Int64 moveField = pawnMoveFields[side][src] & ~(ownerField | opponentField);
 182     // If a pawn on its starting row is blocked, then it cannot move at all.
 183     //    The bit fields leave the possibility that a pawn can move two squares;
 184     //    we prevent that here.
 185     if ((pawnFirstRowMask & (one << src)) BUT !(moveField & pawnSecondRowMask)){
 186         moveField &= pawnThirdRowMask;
 187     }
 188     return moveField;
 189 }
 190 DEST_FUNCTION(pawnCaptureDestinations){
 191     const int side = pos->board[src] & 1;
 192     return pawnCaptureFields[side][src] & opponentField;
 193 } */
 194
 195
 196 extern const int x88FromDest[64];
 197 static inline Position * simpleMoves(const Position * const restrict pos,
 198           const int src, Position * restrict child, const int nds[4], const int ids[4]){
 199     int nd, id, i, dst, dindex;
 200     const char *destPiece;
 201
 202     Position * origChild = child;
 203
 204     Position half = *pos;
 205     const int piece = half.board[src];
 206     setPieceAt(&half, src, 0);
 207     half.turn ^= 1;
 208
 209     for (i = 0; i < 4; i++){
 210         nd = nds[i];  id = ids[i];
 211         for (dst = x88FromDest[src] + nd,
 212              dindex = src + id,
 213              destPiece = (&pos->board[dindex]);
 214                     !(dst & 0x88);
 215                     dst += nd, dindex += id, destPiece += id){
 216             if (*destPiece == 0){
 217                 *child = half;
 218                 setPieceAt(child++, dindex, piece);
 219             } else if (sameColorNotZero(pos->board[src], *destPiece)){
 220                 break;
 221             } else {
 222                 *child = half;
 223                 setPieceAt(child, dindex, piece);
 224                 child->value[0] -= pieceValues[*destPiece];
 225                 child->value[1] += pieceValues[*destPiece];
 226
 227                 // Make alphaBeta examine capture moves first:
 228                 // Craftily (crappily?) reuse half for swapping..
 229                 Position half = *origChild;
 230                 *origChild = *child;
 231                 *child = half;
 232
 233                 child++;
 234                 break;
 235             }
 236         }
 237     }
 238     return child;
 239 }
 240
 241
 242 MOVE_FUNCTION(bishopMoves){
 243     static int nds[] = {17, 15, -15, -17};
 244     static int ids[] = {9,   7,  -7, -9};
 245     return simpleMoves(pos, src, children, nds, ids);
 246 }
 247
 248
 249 extern const Int64 rookHorizontalDests[64][256];
 250 extern const Int64 rookVerticalDests[64][256];
 251 extern const int rookVerticalShift[64];
 252
 253 DEST_FUNCTION(rookDestinations){
 254     Int64 dests  = rookVerticalDests[src][
 255                         (occupancy[1] >> rookVerticalShift[src]) & (255ULL)];
 256     return dests | rookHorizontalDests[src][
 257                         (occupancy[0] >> (src & ~7)) & (255ULL)];
 258 }
 259 MOVE_FUNCTION(rookMoves){
 260     Int64 occupancy[4];
 261     for (int i = 0; i < 4; i++)
 262         occupancy[i] = pos->white[i] | pos->black[i];
 263     Int64 dests  = rookDestinations(pos, src, occupancy);
 264     return extractBitsAsMoves(pos, src,
 265                 dests & ~occupancy[0],  children);
 266 }
 267 MOVE_FUNCTION(rookCaptures){
 268     Int64 occupancy[4];
 269     for (int i = 0; i < 4; i++)
 270         occupancy[i] = pos->white[i] | pos->black[i];
 271     Int64 dests  = rookDestinations(pos, src, occupancy);
 272     return extractBitsAsMoves(pos, src,
 273                 dests & opponentField,  children);
 274 }
 275
 276
 277 MOVE_FUNCTION(queenMoves){
 278     return rookMoves(pos, src, bishopMoves(pos, src, children, ownerField, opponentField),
 279                 ownerField, opponentField);
 280 }
 281 MOVE_FUNCTION(queenCaptures){
 282     return rookCaptures(pos, src, children, ownerField, opponentField);
 283 }
 284
 285
 286 MOVE_FUNCTION(noMoves){    return children + 0; }
 287 DEST_FUNCTION(noDestinations){    return 0ULL; }
 288
 289 typedef MOVE_FUNCTION((*MoveFunction));
 290 MoveFunction moveFunctions[14] = {noMoves, noMoves, pawnMoves, pawnMoves,
 291         knightMoves, knightMoves, bishopMoves, bishopMoves, rookMoves, rookMoves,
 292         queenMoves, queenMoves, kingMoves, kingMoves};
 293 MoveFunction captureFunctions[14] = {noMoves, noMoves, pawnCaptures, pawnCaptures,
 294         knightCaptures, knightCaptures, noMoves, noMoves, rookCaptures, rookCaptures,
 295         queenCaptures, queenCaptures, kingCaptures, kingCaptures};
 296
 297
 298 static inline Position * nextMoveChildren(const Position * const restrict pos,
 299                 Position * restrict children, Int64 * piecePlaces,
 300                 const Int64 ownerField, const Int64 opponentField){
 301     const int src = lowestBit(*piecePlaces);
 302     *piecePlaces ^= TWOTOTHE(src);
 303     return moveFunctions[pos->board[src]](pos, src, children, ownerField, opponentField);
 304 }
 305
 306 static inline Position * nextCaptureChildren(const Position * const restrict pos,
 307                 Position * restrict children, Int64 * piecePlaces,
 308                 const Int64 ownerField, const Int64 opponentField){
 309     const int src = lowestBit(*piecePlaces);
 310     *piecePlaces ^= TWOTOTHE(src);
 311     return captureFunctions[pos->board[src]](pos, src, children, ownerField, opponentField);
 312 }
 313
 314 // XXX Pass occupancyField too?  It is used a lot, and regenerating it all the time
 315 //      may be wasteful...
 316 int makeChildren(const Position * const restrict pos,
 317                        Position * const restrict children)
 318 {
 319     static int src;
 320     Position * child = (Position *) children;
 321     Int64 ownerField    = pos->white[  pos->turn  << 2];
 322     Int64 opponentField = pos->white[(!pos->turn) << 2];
 323     Int64 piecePlaces = ownerField;
 324
 325     while (piecePlaces){
 326         child = nextCaptureChildren(pos, child, &piecePlaces, ownerField, opponentField);
 327     }
 328
 329     piecePlaces = ownerField;
 330     while (piecePlaces){
 331         child = nextMoveChildren(pos, child, &piecePlaces, ownerField, opponentField);
 332     }
 333
 334     return child - children;
 335 }
 336
 337
 338 #include "check.c"
 339 // favor longer variations... but how?
 340 int alphaBeta(Position * const restrict pos, Position * const restrict children,
 341             const int depth,
 342             int alpha, const int beta, Int64 * const nodeCount,
 343             int * offswitch)
 344 {
 345     pos->branchLength = 1;
 346
 347     // early exits:
 348     if (*offswitch) return alpha;
 349     else if (pos->value[0] > 8000 || pos->value[1] > 8000){
 350         int returnValue = pos->value[pos->turn];
 351         // if (returnValue > 0)  returnValue += depth;
 352         // if (returnValue > 8000) return returnValue;
 353         // else  return -8000 - depth;
 354         returnValue = (returnValue > 0) ? 8000 : -8000;
 355         return returnValue;
 356     } else if (depth == 0){
 357         return pos->value[pos->turn];
 358     }
 359
 360     Position * restrict child, * restrict endOfChildren;
 361     int bestChild;
 362     int bestBranch[32];
 363     const int bSize = (depth - 1) * sizeof(int);
 364
 365     const Int64 ownerField    = pos->white[  pos->turn  << 2];
 366     const Int64 opponentField = pos->white[(!pos->turn) << 2];
 367     int value, i = 0, bestBranchSize = 0;
 368
 369             // if (inCheck(child, pos->turn)){
 370             //    i++;
 371             //    continue;
 372             // }
 373
 374 #define ALPHABETA_LOOP_BODY(nextChildrenFunc) \
 375     while (piecePlaces){ \
 376         endOfChildren = nextChildrenFunc(pos, children, &piecePlaces, ownerField, opponentField); \
 377         for (child = children; child < endOfChildren; child++){ \
 378             value = -alphaBeta(child, children + 32, depth-1, -beta, -alpha, nodeCount, offswitch); \
 379             if (value >= beta){ \
 380                 (*nodeCount) += i+1; \
 381                 return beta; \
 382             } else if (value > alpha || (value == alpha && child->branchLength > bestBranchSize)){ \
 383                 alpha = value; \
 384                 bestChild = ++i; \
 385                 memcpy(bestBranch, child->branch, bSize); \
 386                 bestBranchSize = child->branchLength; \
 387             } else \
 388                 ++i; \
 389         } \
 390     } \
 391
 392     Int64 piecePlaces = ownerField;
 393     ALPHABETA_LOOP_BODY(nextCaptureChildren);
 394     piecePlaces = ownerField;
 395     ALPHABETA_LOOP_BODY(nextMoveChildren);
 396
 397     if (i == 0){
 398         return pos->value[pos->turn];
 399     }
 400
 401     pos->branch[0] = bestChild - 1;
 402     memcpy(&pos->branch[1], bestBranch, bSize);
 403     pos->branchLength = bestBranchSize + 1;
 404
 405     (*nodeCount) += i;
 406     return alpha;
 407 }
 408