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         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     // removePieceAt(&half, src);
  87     setPieceAt(&half, src, 0);
  88     half.turn ^= 1;
  89
  90     while (bitfield){
  91         const int dst = lowestBit(bitfield);
  92
  93         *child = half;
  94         setPieceAt(child, dst, piece);
  95         child->value[0] -= pieceValues[pos->board[dst]];
  96         child->value[1] += pieceValues[pos->board[dst]];
  97         child++;
  98
  99         bitfield &= ~TWOTOTHE(dst);
 100     }
 101     return child;
 102 }
 103
 104 #define MOVE_FUNCTION(x) \
 105     Position * x(const Position * const restrict pos, const int src, \
 106                        Position * restrict children, \
 107                  const Int64 ownerField, const Int64 opponentField)
 108 #define DEST_FUNCTION(x) \
 109     Int64 x(const Position * const restrict pos, const int src, \
 110             const Int64 occupancy[4])
 111
 112
 113 MOVE_FUNCTION(kingMoves){
 114     Int64 bitfield = kingFields[src] & ~(opponentField | ownerField);
 115     return extractBitsAsMoves(pos, src, bitfield, children);
 116 }
 117 MOVE_FUNCTION(kingCaptures){
 118     Int64 bitfield = kingFields[src] & opponentField;
 119     return extractBitsAsMoves(pos, src, bitfield, children);
 120 }
 121 DEST_FUNCTION(kingDestinations){ return kingFields[src]; }
 122
 123
 124 MOVE_FUNCTION(knightMoves){
 125     Int64 bitfield = knightFields[src] & ~(opponentField | ownerField);
 126     return extractBitsAsMoves(pos, src, bitfield, children);
 127 }
 128 MOVE_FUNCTION(knightCaptures){
 129     Int64 bitfield = knightFields[src] & opponentField;
 130     return extractBitsAsMoves(pos, src, bitfield, children);
 131 }
 132 DEST_FUNCTION(knightDestinations){ return knightFields[src]; }
 133
 134
 135 int promotionPieces[4] = {10, 4, 8, 6};
 136 Position * makePromotions(Position * children, const int howMany,
 137                 const Int64 moveField, const int side){
 138
 139     memcpy(children + howMany, children, howMany * sizeof(Position));
 140     memcpy(children + 2 * howMany, children, howMany * 2 * sizeof(Position));
 141     int k;
 142     int dsts[2] = {lowestBit(moveField), highestBit(moveField)};
 143     for (k = 0; k < 4 * howMany; k++){
 144         setPieceAt(&children[k], dsts[k & 1], promotionPieces[k / howMany] | side);
 145     }
 146     return children + 4 * howMany;
 147 }
 148
 149 MOVE_FUNCTION(pawnMoves){
 150     const int side = pos->board[src] & 1;
 151     Int64 moveField = pawnMoveFields[side][src] & ~(ownerField | opponentField);
 152
 153     // If a pawn on its starting row is blocked, then it cannot move at all.
 154     //    The bit fields leave the possibility that a pawn can move two squares;
 155     //    we prevent that here.
 156     if ((pawnFirstRowMask & (one << src)) BUT !(moveField & pawnSecondRowMask)){
 157         moveField &= pawnThirdRowMask;
 158     }
 159     Position * newChildren = extractBitsAsMoves(pos, src, moveField, children);
 160
 161     if (moveField && (src >> 3) == (side ? 1 : 6))
 162         return makePromotions(children, 1, moveField, side);
 163     else
 164         return newChildren;
 165 }
 166 MOVE_FUNCTION(pawnCaptures){
 167     const int side = pos->board[src] & 1;
 168     Int64 captureField = pawnCaptureFields[side][src] & opponentField;
 169     Position * newChildren = extractBitsAsMoves(pos, src, captureField, children);
 170     if (captureField && (src >> 3) == (side ? 1 : 6)){
 171         int howMany = (lowestBit(captureField) == highestBit(captureField)) ? 1 : 2;
 172         return makePromotions(children, howMany, captureField, side);
 173     } else
 174         return newChildren;
 175 }
 176 /* DEST_FUNCTION(pawnMoveDestinations){
 177     const int side = pos->board[src] & 1;
 178     Int64 moveField = pawnMoveFields[side][src] & ~(ownerField | opponentField);
 179     // If a pawn on its starting row is blocked, then it cannot move at all.
 180     //    The bit fields leave the possibility that a pawn can move two squares;
 181     //    we prevent that here.
 182     if ((pawnFirstRowMask & (one << src)) BUT !(moveField & pawnSecondRowMask)){
 183         moveField &= pawnThirdRowMask;
 184     }
 185     return moveField;
 186 }
 187 DEST_FUNCTION(pawnCaptureDestinations){
 188     const int side = pos->board[src] & 1;
 189     return pawnCaptureFields[side][src] & opponentField;
 190 } */
 191
 192
 193 extern const int x88FromDest[64];
 194 static inline Position * simpleMoves(const Position * const restrict pos,
 195           const int src, Position * restrict child, const int nds[4], const int ids[4]){
 196     int nd, id, i, dst, dindex;
 197     const char *destPiece;
 198
 199     Position * origChild = child;
 200
 201     Position half = *pos;
 202     const int piece = half.board[src];
 203     setPieceAt(&half, src, 0);
 204     half.turn ^= 1;
 205
 206     for (i = 0; i < 4; i++){
 207         nd = nds[i];  id = ids[i];
 208         for (dst = x88FromDest[src] + nd,
 209              dindex = src + id,
 210              destPiece = (&pos->board[dindex]);
 211                     !(dst & 0x88);
 212                     dst += nd, dindex += id, destPiece += id){
 213             if (*destPiece == 0){
 214                 *child = half;
 215                 setPieceAt(child++, dindex, piece);
 216             } else if (sameColorNotZero(pos->board[src], *destPiece)){
 217                 break;
 218             } else {
 219                 *child = half;
 220                 setPieceAt(child, dindex, piece);
 221                 child->value[0] -= pieceValues[*destPiece];
 222                 child->value[1] += pieceValues[*destPiece];
 223
 224                 // Make alphaBeta examine capture moves first:
 225                 // Craftily (crappily?) reuse half for swapping..
 226                 Position half = *origChild;
 227                 *origChild = *child;
 228                 *child = half;
 229
 230                 child++;
 231                 break;
 232             }
 233         }
 234     }
 235     return child;
 236 }
 237
 238
 239 MOVE_FUNCTION(bishopMoves){
 240     static int nds[] = {17, 15, -15, -17};
 241     static int ids[] = {9,   7,  -7, -9};
 242     return simpleMoves(pos, src, children, nds, ids);
 243 }
 244
 245
 246 extern const Int64 rookHorizontalDests[64][256];
 247 extern const Int64 rookVerticalDests[64][256];
 248 extern const int rookVerticalShift[64];
 249
 250 MOVE_FUNCTION(rookMoves){
 251     Int64 dests  = rookVerticalDests[src][
 252                         ((pos->white[1] | pos->black[1]) >> rookVerticalShift[src]) & (255ULL)];
 253     dests       |= rookHorizontalDests[src][
 254                         ((ownerField | opponentField) >> (src & ~7ULL)) & (255ULL)];
 255     return extractBitsAsMoves(pos, src,
 256                 dests & ~(opponentField | ownerField),  children);
 257 }
 258 MOVE_FUNCTION(rookCaptures){
 259     Int64 dests  = rookVerticalDests[src][
 260                         ((pos->white[1] | pos->black[1]) >> rookVerticalShift[src]) & (255ULL)];
 261     dests       |= rookHorizontalDests[src][
 262                         ((ownerField | opponentField) >> (src & ~7ULL)) & (255ULL)];
 263     return extractBitsAsMoves(pos, src,
 264                 dests & opponentField,  children);
 265 }
 266 DEST_FUNCTION(rookDestinations){
 267     Int64 dests  = rookVerticalDests[src][
 268                         (occupancy[1] >> rookVerticalShift[src]) & (255ULL)];
 269     return dests | rookHorizontalDests[src][
 270                         (occupancy[0] >> (src & ~7ULL)) & (255ULL)];
 271 }
 272
 273
 274 MOVE_FUNCTION(queenMoves){
 275     return rookMoves(pos, src, bishopMoves(pos, src, children, ownerField, opponentField),
 276                 ownerField, opponentField);
 277 }
 278 MOVE_FUNCTION(queenCaptures){
 279     return rookCaptures(pos, src, children, ownerField, opponentField);
 280 }
 281
 282
 283 MOVE_FUNCTION(noMoves){    return children + 0; }
 284 DEST_FUNCTION(noDestinations){    return 0ULL; }
 285
 286 typedef MOVE_FUNCTION((*MoveFunction));
 287 MoveFunction moveFunctions[14] = {noMoves, noMoves, pawnMoves, pawnMoves,
 288         knightMoves, knightMoves, bishopMoves, bishopMoves, rookMoves, rookMoves,
 289         queenMoves, queenMoves, kingMoves, kingMoves};
 290 MoveFunction captureFunctions[14] = {noMoves, noMoves, pawnCaptures, pawnCaptures,
 291         knightCaptures, knightCaptures, noMoves, noMoves, rookCaptures, rookCaptures,
 292         queenCaptures, queenCaptures, kingCaptures, kingCaptures};
 293
 294
 295 static inline Position * nextMoveChildren(const Position * const restrict pos,
 296                 Position * restrict children, Int64 * piecePlaces,
 297                 const Int64 ownerField, const Int64 opponentField){
 298     const int src = lowestBit(*piecePlaces);
 299     *piecePlaces ^= TWOTOTHE(src);
 300     return moveFunctions[pos->board[src]](pos, src, children, ownerField, opponentField);
 301 }
 302
 303 static inline Position * nextCaptureChildren(const Position * const restrict pos,
 304                 Position * restrict children, Int64 * piecePlaces,
 305                 const Int64 ownerField, const Int64 opponentField){
 306     const int src = lowestBit(*piecePlaces);
 307     *piecePlaces ^= TWOTOTHE(src);
 308     return captureFunctions[pos->board[src]](pos, src, children, ownerField, opponentField);
 309 }
 310
 311 // XXX Pass occupancyField too?  It is used a lot, and regenerating it all the time
 312 //      may be wasteful...
 313 int makeChildren(const Position * const restrict pos,
 314                        Position * const restrict children)
 315 {
 316     static int src;
 317     Position * child = (Position *) children;
 318     Int64 ownerField    = pos->white[  pos->turn  << 2];
 319     Int64 opponentField = pos->white[(!pos->turn) << 2];
 320     Int64 piecePlaces = ownerField;
 321
 322     while (piecePlaces){
 323         child = nextCaptureChildren(pos, child, &piecePlaces, ownerField, opponentField);
 324     }
 325
 326     piecePlaces = ownerField;
 327     while (piecePlaces){
 328         child = nextMoveChildren(pos, child, &piecePlaces, ownerField, opponentField);
 329     }
 330
 331     return child - children;
 332 }
 333
 334
 335 #include "check.c"
 336 // favor longer variations... but how?
 337 int alphaBeta(Position * const restrict pos, Position * const restrict children,
 338             const int depth,
 339             int alpha, const int beta, Int64 * const nodeCount,
 340             int * offswitch)
 341 {
 342     pos->branchLength = 1;
 343
 344     // early exits:
 345     if (*offswitch) return alpha;
 346     else if (pos->value[0] > 8000 || pos->value[1] > 8000){
 347         int returnValue = pos->value[pos->turn];
 348         // if (returnValue > 0)  returnValue += depth;
 349         // if (returnValue > 8000) return returnValue;
 350         // else  return -8000 - depth;
 351         returnValue = (returnValue > 0) ? 8000 : -8000;
 352         return returnValue;
 353     } else if (depth == 0){
 354         return pos->value[pos->turn];
 355     }
 356
 357     Position * restrict child, * restrict endOfChildren;
 358     int bestChild;
 359     int bestBranch[32];
 360     const int bSize = (depth - 1) * sizeof(int);
 361
 362     const Int64 ownerField    = pos->white[  pos->turn  << 2];
 363     const Int64 opponentField = pos->white[(!pos->turn) << 2];
 364     int value, i = 0, bestBranchSize = 0;
 365
 366             // if (inCheck(child, pos->turn)){
 367             //    i++;
 368             //    continue;
 369             // }
 370
 371 #define ALPHABETA_LOOP_BODY(nextChildrenFunc) \
 372     while (piecePlaces){ \
 373         endOfChildren = nextChildrenFunc(pos, children, &piecePlaces, ownerField, opponentField); \
 374         for (child = children; child < endOfChildren; child++){ \
 375             value = -alphaBeta(child, children + 32, depth-1, -beta, -alpha, nodeCount, offswitch); \
 376             if (value >= beta){ \
 377                 (*nodeCount) += i+1; \
 378                 return beta; \
 379             } else if (value > alpha || (value == alpha && child->branchLength > bestBranchSize)){ \
 380                 alpha = value; \
 381                 bestChild = ++i; \
 382                 memcpy(bestBranch, child->branch, bSize); \
 383                 bestBranchSize = child->branchLength; \
 384             } else \
 385                 ++i; \
 386         } \
 387     } \
 388
 389     Int64 piecePlaces = ownerField;
 390     ALPHABETA_LOOP_BODY(nextCaptureChildren);
 391     piecePlaces = ownerField;
 392     ALPHABETA_LOOP_BODY(nextMoveChildren);
 393
 394     if (i == 0){
 395         return pos->value[pos->turn];
 396     }
 397
 398     pos->branch[0] = bestChild - 1;
 399     memcpy(&pos->branch[1], bestBranch, bSize);
 400     pos->branchLength = bestBranchSize + 1;
 401
 402     (*nodeCount) += i;
 403     return alpha;
 404 }
 405