1 //////////////////////////////////////////////////////////////////////
2 //
3 // FILE: position.cpp
4 // Position class methods
5 //
6 // Part of: Scid (Shane's Chess Information Database)
7 // Version: 3.5
8 //
9 // Notice: Copyright (c) 1999-2003 Shane Hudson. All rights reserved.
10 //
11 // Author: Shane Hudson (sgh@users.sourceforge.net)
12 //
13 //////////////////////////////////////////////////////////////////////
14
15 #include "common.h"
16 #include "position.h"
17 #include "attacks.h"
18 #include "misc.h"
19 #include "hash.h"
20 #include "sqmove.h"
21 #include "dstring.h"
22 #include "movegen.h"
23 #include <algorithm>
24
25 static uint hashVal [16][64];
26 static uint stdStartHash = 0;
27 static uint stdStartPawnHash = 0;
28
29 // HASH and UNHASH are identical: XOR the hash value for a (piece,square).
30 #define HASH(h,p,sq) (h) ^= hashVal[(p)][(sq)]
31 #define UNHASH(h,p,sq) (h) ^= hashVal[(p)][(sq)]
32
33 inline void
AddHash(pieceT p,squareT sq)34 Position::AddHash (pieceT p, squareT sq)
35 {
36 HASH (Hash, p, sq);
37 if (piece_Type(p) == PAWN) {
38 HASH (PawnHash, p, sq);
39 }
40 }
41
42 inline void
UnHash(pieceT p,squareT sq)43 Position::UnHash (pieceT p, squareT sq)
44 {
45 UNHASH (Hash, p, sq);
46 if (piece_Type(p) == PAWN) {
47 UNHASH (PawnHash, p, sq);
48 }
49 }
50
51 inline void
AddToBoard(pieceT p,squareT sq)52 Position::AddToBoard (pieceT p, squareT sq)
53 {
54 ASSERT (Board[sq] == EMPTY);
55 Board[sq] = p;
56 NumOnRank[p][square_Rank(sq)]++;
57 NumOnFyle[p][square_Fyle(sq)]++;
58 NumOnLeftDiag[p][square_LeftDiag(sq)]++;
59 NumOnRightDiag[p][square_RightDiag(sq)]++;
60 NumOnSquareColor[p][square_Color(sq)]++;
61 AddHash (p, sq);
62 }
63
64 inline void
RemoveFromBoard(pieceT p,squareT sq)65 Position::RemoveFromBoard (pieceT p, squareT sq)
66 {
67 ASSERT (Board[sq] == p);
68 Board[sq] = EMPTY;
69 NumOnRank[p][square_Rank(sq)]--;
70 NumOnFyle[p][square_Fyle(sq)]--;
71 NumOnLeftDiag[p][square_LeftDiag(sq)]--;
72 NumOnRightDiag[p][square_RightDiag(sq)]--;
73 NumOnSquareColor[p][square_Color(sq)]--;
74 UnHash (p, sq);
75 }
76
77 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
78 // initHashValues:
79 // Initialises the table of Zobrist hash values.
initHashValues(void)80 static void initHashValues (void)
81 {
82 // Ensure we set up the hash values only once:
83 static int firstCall = 1;
84 if (! firstCall) { return; }
85 firstCall = 0;
86
87
88 // First, set all values to 0:
89 uint sq;
90 for (uint p = 0; p < 16; p++) {
91 for (sq = A1; sq <= H8; sq++) { hashVal[p][sq] = 0; }
92 }
93
94 // Fill in the hash values for each valid [piece][square] index,
95 // using a table of pre-generated good values:
96 const unsigned int * hash = goodHashValues;
97 for (sq=A1; sq <= H8; sq++) { hashVal[WK][sq] = *hash; hash++; }
98 for (sq=A1; sq <= H8; sq++) { hashVal[WQ][sq] = *hash; hash++; }
99 for (sq=A1; sq <= H8; sq++) { hashVal[WR][sq] = *hash; hash++; }
100 for (sq=A1; sq <= H8; sq++) { hashVal[WB][sq] = *hash; hash++; }
101 for (sq=A1; sq <= H8; sq++) { hashVal[WN][sq] = *hash; hash++; }
102 for (sq=A1; sq <= H8; sq++) { hashVal[WP][sq] = *hash; hash++; }
103 for (sq=A1; sq <= H8; sq++) { hashVal[BK][sq] = *hash; hash++; }
104 for (sq=A1; sq <= H8; sq++) { hashVal[BQ][sq] = *hash; hash++; }
105 for (sq=A1; sq <= H8; sq++) { hashVal[BR][sq] = *hash; hash++; }
106 for (sq=A1; sq <= H8; sq++) { hashVal[BB][sq] = *hash; hash++; }
107 for (sq=A1; sq <= H8; sq++) { hashVal[BN][sq] = *hash; hash++; }
108 for (sq=A1; sq <= H8; sq++) { hashVal[BP][sq] = *hash; hash++; }
109
110 // Compute the hash values for the standard starting position:
111 uint h = 0;
112 // First the pawns:
113 HASH (h,WP,A2); HASH (h,WP,B2); HASH (h,WP,C2); HASH (h,WP,D2);
114 HASH (h,WP,E2); HASH (h,WP,F2); HASH (h,WP,G2); HASH (h,WP,H2);
115 HASH (h,BP,A7); HASH (h,BP,B7); HASH (h,BP,C7); HASH (h,BP,D7);
116 HASH (h,BP,E7); HASH (h,BP,F7); HASH (h,BP,G7); HASH (h,BP,H7);
117 stdStartPawnHash = h;
118 // Now the nonpawns:
119 HASH (h,WR,A1); HASH (h,WN,B1); HASH (h,WB,C1); HASH (h,WQ,D1);
120 HASH (h,WK,E1); HASH (h,WB,F1); HASH (h,WN,G1); HASH (h,WR,H1);
121 HASH (h,BR,A8); HASH (h,BN,B8); HASH (h,BB,C8); HASH (h,BQ,D8);
122 HASH (h,BK,E8); HASH (h,BB,F8); HASH (h,BN,G8); HASH (h,BR,H8);
123 stdStartHash = h;
124 }
125
126
127 ///////////////////////////////////////////////////////////////////////////
128 // sqDir[][]: Array listing the direction between any two squares.
129 // For example, sqDir[A1][B2] == UP_RIGHT, and sqDir[A1][C2] == NULL_DIR.
130 directionT sqDir[66][66];
131 struct sqDir_Init
132 {
sqDir_InitsqDir_Init133 sqDir_Init() {
134 // Initialise the sqDir[][] array of directions between every pair
135 // of squares.
136 squareT i, j;
137 directionT dirArray[] = { UP, DOWN, LEFT, RIGHT, UP_LEFT, UP_RIGHT,
138 DOWN_LEFT, DOWN_RIGHT, NULL_DIR };
139 // First, set everything to NULL_DIR:
140 for (i=A1; i <= NS; i++) {
141 for (j=A1; j <= NS; j++) {
142 sqDir[i][j] = NULL_DIR;
143 }
144 }
145 // Now fill in the valid directions:
146 for (i=A1; i <= H8; i++) {
147 directionT * dirptr = dirArray;
148 while (*dirptr != NULL_DIR) {
149 j = square_Move (i, *dirptr);
150 while (j != NS) {
151 sqDir[i][j] = *dirptr;
152 j = square_Move (j, *dirptr);
153 }
154 dirptr++;
155 }
156 }
157 }
158 } sqDir_Init_singleton;
159
160 ///////////////////////////////////////////////////////////////////////////
161 // PRIVATE FUNCTIONS -- small ones are inline for speed
162
163 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
164 // Position::CalcPinsDir():
165 // Look for a pinned piece in the direction 'dir' relative to
166 // the position of the king to move.
167 //
168 inline void
CalcPinsDir(directionT dir,pieceT attacker)169 Position::CalcPinsDir (directionT dir, pieceT attacker)
170 {
171 // Two pieces can pin along any path. A queen is always one,
172 // the other is a bishop or rook. To save calculating it here, the
173 // appropriate piece (BISHOP) or (ROOK) is passed along with the
174 // direction.
175
176 squareT king = GetKingSquare (ToMove);
177 squareT friendly = NULL_SQUARE;
178 squareT x = king;
179 squareT last = square_Last (king, dir);
180 int delta = direction_Delta (dir);
181
182 while (x != last) {
183 x += delta;
184 pieceT p = Board[x];
185 if (p == EMPTY) {
186 // Empty square, so keep searching.
187 } else if (piece_Color_NotEmpty(p) == ToMove) {
188 // Found a friendly piece.
189 if (friendly == NULL_SQUARE) {
190 // Found first friendly in this direction
191 friendly = x;
192 } else {
193 // Found second friendly in this direction, so stop.
194 return;
195 }
196 } else {
197 // Found an enemy piece
198 if (friendly != NULL_SQUARE) {
199 // Potential pin:
200 pieceT ptype = piece_Type(p);
201 if (ptype == QUEEN || ptype == attacker) {
202 Pinned[ListPos[friendly]] = dir;
203 }
204 }
205 return; // found an enemy piece, so end search
206 }
207 }
208 return;
209 }
210
211
212 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
213 // Position::AddLegalMove():
214 // Add a legal move to the move list.
215 //
216 inline void
AddLegalMove(MoveList * mlist,squareT from,squareT to,pieceT promo)217 Position::AddLegalMove (MoveList * mlist, squareT from, squareT to, pieceT promo)
218 {
219 ASSERT (mlist != NULL);
220 // We do NOT set the pre-move castling/ep flags, or the captured
221 // piece info, here since that is ONLY needed if the move is
222 // going to be executed with DoSimpleMove() and then undone.
223 mlist->emplace_back(from, to, promo, Board[from], Board[to]);
224 }
225
226
227 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
228 // Position::GenSliderMoves():
229 // Generate slider moves along a direction, for a sliding
230 // piece of the specified color from the specified square.
231 // If sqset != NULL, moves must be to a square in sqset.
232 inline void
GenSliderMoves(MoveList * mlist,colorT color,squareT fromSq,directionT dir,SquareSet * sqset,bool capturesOnly)233 Position::GenSliderMoves (MoveList * mlist, colorT color, squareT fromSq,
234 directionT dir, SquareSet * sqset, bool capturesOnly)
235 {
236 squareT dest = fromSq;
237 squareT last = square_Last (fromSq, dir);
238 int delta = direction_Delta (dir);
239
240 while (dest != last) {
241 dest += delta;
242 pieceT p = Board[dest];
243 if (p == EMPTY) {
244 if (! capturesOnly) {
245 if (sqset == NULL || sqset->Contains(dest)) {
246 AddLegalMove (mlist, fromSq, dest, EMPTY);
247 }
248 }
249 continue;
250 }
251 // We have reached a piece. Add the capture if it is an enemy.
252 if (piece_Color_NotEmpty(p) != color) {
253 if (sqset == NULL || sqset->Contains(dest)) {
254 AddLegalMove (mlist, fromSq, dest, EMPTY);
255 }
256 }
257 break;
258 }
259 }
260
261 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
262 // Position::GenKnightMoves():
263 // Generate knight moves.
264 // If sqset != NULL, moves must be to a square in sqset.
265 inline void
GenKnightMoves(MoveList * mlist,colorT c,squareT fromSq,SquareSet * sqset,bool capturesOnly)266 Position::GenKnightMoves (MoveList * mlist, colorT c, squareT fromSq,
267 SquareSet * sqset, bool capturesOnly)
268 {
269 const squareT * destPtr = knightAttacks[fromSq];
270 while (true) {
271 squareT dest = *destPtr;
272 if (dest == NULL_SQUARE) { break; }
273 destPtr++;
274 pieceT p = Board[dest];
275 if (capturesOnly && p == EMPTY) { continue; }
276 if (piece_Color(p) != c) {
277 if (sqset == NULL || sqset->Contains(dest)) {
278 AddLegalMove (mlist, fromSq, dest, EMPTY);
279 }
280 }
281 }
282 }
283
castlingKingSq(colorT color) const284 squareT Position::castlingKingSq(colorT color) const {
285 return square_Relative(color, E1);
286 }
287
castlingRookSq(colorT color) const288 template <bool king_side> squareT Position::castlingRookSq(colorT color) const {
289 return king_side ? square_Relative(color, H1)
290 : square_Relative(color, A1);
291 }
292
validCastling(bool king_side,bool check_legal) const293 bool Position::validCastling(bool king_side, bool check_legal) const {
294 const squareT kingFrom = castlingKingSq(ToMove);
295 const squareT rookFrom = king_side ? castlingRookSq<true>(ToMove)
296 : castlingRookSq<false>(ToMove);
297 const squareT rookTo = king_side ? square_Relative(ToMove, F1)
298 : square_Relative(ToMove, D1);
299 const squareT kingTo = king_side ? square_Relative(ToMove, G1)
300 : square_Relative(ToMove, C1);
301 if (Board[kingFrom] != piece_Make(ToMove, KING) ||
302 Board[rookFrom] != piece_Make(ToMove, ROOK))
303 return false;
304
305 const int stepRook = rookFrom < rookTo ? -1 : 1;
306 for (int sq = rookTo; sq != rookFrom; sq += stepRook) {
307 if (Board[sq] != EMPTY && sq != kingFrom)
308 return false;
309
310 if (!check_legal)
311 break;
312 }
313
314 const int stepKing = kingFrom < kingTo ? -1 : 1;
315 for (int sq = kingTo; sq != kingFrom; sq += stepKing) {
316 if (Board[sq] != EMPTY && sq != rookFrom)
317 return false;
318
319 if (!check_legal)
320 break;
321
322 if (CalcNumChecks(sq) > 0)
323 return false;
324 }
325 return true;
326 }
327
328 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
329 // Position::GenCastling():
330 // Generate the legal castling moves.
331 // Assumes the side to move is NOT in check, so the caller
332 // should verify this first.
333 //
GenCastling(MoveList * mlist)334 void Position::GenCastling(MoveList* mlist) {
335 const squareT from = square_Relative(ToMove, E1);
336
337 if (GetCastling(ToMove, KSIDE) && validCastling(true, true))
338 AddLegalMove(mlist, from, from + 2, EMPTY);
339
340 if (GetCastling(ToMove, QSIDE) && validCastling(false, true))
341 AddLegalMove(mlist, from, from - 2, EMPTY);
342 }
343
344 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
345 // Position::GenKingMoves():
346 // Generate the legal King moves. Castling is generated as well, if
347 // the specified flag is true.
348 //
349 void
GenKingMoves(MoveList * mlist,genMovesT genType,bool castling)350 Position::GenKingMoves (MoveList * mlist, genMovesT genType, bool castling)
351 {
352 squareT kingSq = GetKingSquare();
353 squareT enemyKingSq = GetEnemyKingSquare();
354 colorT enemy = color_Flip(ToMove);
355 const squareT * destPtr;
356 pieceT king = piece_Make (ToMove, KING);
357 bool genNonCaptures = (genType & GEN_NON_CAPS);
358
359 ASSERT (Board[kingSq] == king);
360
361 destPtr = kingAttacks[kingSq];
362 while (*destPtr != NULL_SQUARE) {
363 // Try this move and see if it legal:
364
365 squareT destSq = *destPtr;
366 bool addThisMove = false;
367
368 // Only try this move if the target square has an enemy piece,
369 // or if it is empty and noncaptures are to be generated:
370 if ( (genNonCaptures && Board[destSq] == EMPTY)
371 || piece_Color (Board[destSq]) == enemy) {
372
373 // Empty or enemy piece there, so try the move:
374 pieceT captured = Board[destSq];
375 Board[destSq] = king;
376 Board[kingSq] = EMPTY;
377
378 // It is legal if the two kings will not be adjacent and the
379 // moving king will not be in check on its new square:
380 if (! square_Adjacent (destSq, enemyKingSq)) {
381 if (CalcNumChecks (destSq) == 0) {
382 addThisMove = true;
383 }
384 }
385 Board[kingSq] = king;
386 Board[destSq] = captured;
387 }
388 if (addThisMove) { AddLegalMove (mlist, kingSq, destSq, EMPTY); }
389 destPtr++;
390 }
391 // Now generate castling moves, if possible:
392 if (genNonCaptures && castling) { GenCastling (mlist); }
393 }
394
395 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
396 // Position::AddPromotions():
397 // Add promotion moves.
398 // Called by GenPawnMoves() when a pawn can be promoted.
399 //
400 inline void
AddPromotions(MoveList * mlist,squareT from,squareT dest)401 Position::AddPromotions (MoveList * mlist, squareT from, squareT dest)
402 {
403 ASSERT (piece_Type (Board[from]) == PAWN);
404 ASSERT (square_Rank (dest) == RANK_1 || square_Rank (dest) == RANK_8);
405
406 AddLegalMove (mlist, from, dest, QUEEN);
407 AddLegalMove (mlist, from, dest, ROOK);
408 AddLegalMove (mlist, from, dest, BISHOP);
409 AddLegalMove (mlist, from, dest, KNIGHT);
410 }
411
412 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
413 // Position::IsValidEnPassant
414 // Used to verify that an en passant pawn capture is valid.
415 // This is needed because illegal en passant captures can appear
416 // legal according to calculations of pinned pieces. For example,
417 // consider WK d5, WP e5, BP f5 (just moved there), BR h5 and
418 // the en passant capture exf6 would be illegal.
419 inline bool
IsValidEnPassant(squareT from,squareT to)420 Position::IsValidEnPassant (squareT from, squareT to)
421 {
422 ASSERT (from <= H8 && to <= H8);
423 ASSERT (to == EPTarget);
424
425 // Check that this en passant capture is legal:
426 pieceT ownPawn = piece_Make(ToMove, PAWN);
427 pieceT enemyPawn = piece_Make (color_Flip(ToMove), PAWN);
428 squareT enemyPawnSq = (ToMove == WHITE) ? to - 8 : to + 8;
429 ASSERT (Board[from] == ownPawn);
430 ASSERT (Board[enemyPawnSq] == enemyPawn);
431 Board[from] = EMPTY;
432
433 // PG
434 Board[to] = ownPawn;
435
436 Board[enemyPawnSq] = EMPTY;
437 bool isValid = ! IsKingInCheck();
438
439 //PG
440 Board[to] = EMPTY;
441
442 Board[from] = ownPawn;
443 Board[enemyPawnSq] = enemyPawn;
444 return isValid;
445 }
446
447 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
448 // Position::GenPawnMoves():
449 // Generate legal pawn moves.
450 // If dir != NULL_DIR, pawn MUST move in direction dir or its opposite.
451 // If sqset != NULL, pawn MUST move to a square in sqset.
452 // The dir and sq parameters are for pinned pawns and check evasions.
453 void
GenPawnMoves(MoveList * mlist,squareT from,directionT dir,SquareSet * sqset,genMovesT genType)454 Position::GenPawnMoves (MoveList * mlist, squareT from,
455 directionT dir, SquareSet * sqset, genMovesT genType)
456 {
457 bool genNonCaptures = (genType & GEN_NON_CAPS);
458 directionT oppdir = direction_Opposite(dir);
459 directionT forward;
460 rankT promoRank;
461 rankT secondRank;
462 if (ToMove == WHITE) {
463 forward = UP; promoRank = RANK_8; secondRank = RANK_2;
464 } else {
465 forward = DOWN; promoRank = RANK_1; secondRank = RANK_7;
466 }
467 squareT dest;
468
469 ASSERT (Board[from] == piece_Make (ToMove, PAWN));
470
471 if (genNonCaptures
472 && (dir == NULL_DIR || dir == forward || oppdir == forward)) {
473 dest = square_Move (from, forward);
474 if (Board[dest]==EMPTY && (sqset==NULL || sqset->Contains(dest))) {
475 if (square_Rank(dest) == promoRank) {
476 AddPromotions (mlist, from, dest);
477 } else {
478 AddLegalMove (mlist, from, dest, EMPTY);
479 }
480 }
481 if (square_Rank(from) == secondRank && Board[dest] == EMPTY) {
482 dest = square_Move (dest, forward);
483 if (Board[dest]==EMPTY && (sqset==NULL || sqset->Contains(dest))) {
484 AddLegalMove (mlist, from, dest, EMPTY);
485 }
486 }
487 }
488
489 // Now do captures: left, then right
490 // To be a possible capture, dest square must be EPTarget or hold
491 // an enemy piece.
492 #define POSSIBLE_CAPTURE(d) ((d != NULL_SQUARE) \
493 && ((piece_Color (Board[d]) == (color_Flip(ToMove))) \
494 || (d == EPTarget && IsValidEnPassant(from,d))))
495
496 directionT capdir = forward | LEFT;
497 if (dir == NULL_DIR || dir == capdir || oppdir == capdir) {
498 dest = square_Move (from, capdir);
499 if (POSSIBLE_CAPTURE(dest) && (sqset==NULL || sqset->Contains(dest))) {
500 if (square_Rank(dest) == promoRank) {
501 AddPromotions (mlist, from, dest);
502 } else {
503 AddLegalMove (mlist, from, dest, EMPTY);
504 }
505 }
506 }
507 capdir = forward | RIGHT;
508 if (dir == NULL_DIR || dir == capdir || oppdir == capdir) {
509 dest = square_Move (from, capdir);
510 if (POSSIBLE_CAPTURE(dest) && (sqset==NULL || sqset->Contains(dest))) {
511 if (square_Rank(dest) == promoRank) {
512 AddPromotions (mlist, from, dest);
513 } else {
514 AddLegalMove (mlist, from, dest, EMPTY);
515 }
516 }
517 }
518 return;
519 }
520
521
522 //////////////////////////////////////////////////////////////////////
523 // PUBLIC FUNCTIONS
524
525
526 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
527 // Position::GetHPSig():
528 // Return the position's home pawn signature.
529 //
530 uint
GetHPSig(void)531 Position::GetHPSig (void)
532 {
533 uint hpSig = 0;
534 pieceT * b = &(Board[A2]);
535 if (*b == WP) { hpSig |= 0x8000; } b++; /* a2 */
536 if (*b == WP) { hpSig |= 0x4000; } b++; /* b2 */
537 if (*b == WP) { hpSig |= 0x2000; } b++; /* c2 */
538 if (*b == WP) { hpSig |= 0x1000; } b++; /* d2 */
539 if (*b == WP) { hpSig |= 0x0800; } b++; /* e2 */
540 if (*b == WP) { hpSig |= 0x0400; } b++; /* f2 */
541 if (*b == WP) { hpSig |= 0x0200; } b++; /* g2 */
542 if (*b == WP) { hpSig |= 0x0100; } /* h2 */
543 b = &(Board[A7]);
544 if (*b == BP) { hpSig |= 0x0080; } b++; /* a7 */
545 if (*b == BP) { hpSig |= 0x0040; } b++; /* b7 */
546 if (*b == BP) { hpSig |= 0x0020; } b++; /* c7 */
547 if (*b == BP) { hpSig |= 0x0010; } b++; /* d7 */
548 if (*b == BP) { hpSig |= 0x0008; } b++; /* e7 */
549 if (*b == BP) { hpSig |= 0x0004; } b++; /* f7 */
550 if (*b == BP) { hpSig |= 0x0002; } b++; /* g7 */
551 if (*b == BP) { hpSig |= 0x0001; } /* h7 */
552 return hpSig;
553 }
554
Position()555 Position::Position() {
556 // Setting up a valid board is left to StdStart() or Clear().
557 Board [COLOR_SQUARE] = EMPTY;
558 Board [NULL_SQUARE] = END_OF_BOARD;
559
560 // Make sure all tables used for move generation, hashing,
561 // square tests, etc have been computed:
562 initHashValues();
563 }
564
565
566 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
567 // Position::Clear():
568 // Clear the board and associated structures.
569 //
570 void
Clear(void)571 Position::Clear (void)
572 {
573 int i;
574 for (i=A1; i <= H8; i++) { Board[i] = EMPTY; }
575 for (i=WK; i <= BP; i++) {
576 Material[i] = 0;
577 for (uint j=0; j < 8; j++) {
578 NumOnRank[i][j] = NumOnFyle[i][j] = 0;
579 }
580 for (uint d=0; d < 15; d++) {
581 NumOnLeftDiag[i][d] = NumOnRightDiag[i][d] = 0;
582 }
583 NumOnSquareColor[i][WHITE] = NumOnSquareColor[i][BLACK] = 0;
584 }
585 Count[WHITE] = Count[BLACK] = 0;
586 EPTarget = NULL_SQUARE;
587 Castling = 0;
588 Board [NULL_SQUARE] = END_OF_BOARD;
589 PlyCounter = 0;
590 HalfMoveClock = 0;
591 Hash = 0;
592 PawnHash = 0;
593 return;
594 }
595
596
597 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
598 // Position::StdStart():
599 // Set up the standard chess starting position. For performance the data is copied from a
600 // template.
601 //
getStdStart()602 const Position& Position::getStdStart()
603 {
604 static Position startPositionTemplate;
605 static bool init = true;
606
607 if (init){
608 init = false;
609 Position* p = &startPositionTemplate;
610 p->Clear();
611 p->Material[WK] = p->Material[BK] = 1;
612 p->Material[WQ] = p->Material[BQ] = 1;
613 p->Material[WR] = p->Material[BR] = 2;
614 p->Material[WB] = p->Material[BB] = 2;
615 p->Material[WN] = p->Material[BN] = 2;
616 p->Material[WP] = p->Material[BP] = 8;
617 p->Count[WHITE] = p->Count[BLACK] = 16;
618
619 p->AddToBoard(WK, E1); p->List[WHITE][0] = E1; p->ListPos[E1] = 0;
620 p->AddToBoard(BK, E8); p->List[BLACK][0] = E8; p->ListPos[E8] = 0;
621 p->AddToBoard(WR, A1); p->List[WHITE][1] = A1; p->ListPos[A1] = 1;
622 p->AddToBoard(BR, A8); p->List[BLACK][1] = A8; p->ListPos[A8] = 1;
623 p->AddToBoard(WN, B1); p->List[WHITE][2] = B1; p->ListPos[B1] = 2;
624 p->AddToBoard(BN, B8); p->List[BLACK][2] = B8; p->ListPos[B8] = 2;
625 p->AddToBoard(WB, C1); p->List[WHITE][3] = C1; p->ListPos[C1] = 3;
626 p->AddToBoard(BB, C8); p->List[BLACK][3] = C8; p->ListPos[C8] = 3;
627 p->AddToBoard(WQ, D1); p->List[WHITE][4] = D1; p->ListPos[D1] = 4;
628 p->AddToBoard(BQ, D8); p->List[BLACK][4] = D8; p->ListPos[D8] = 4;
629 p->AddToBoard(WB, F1); p->List[WHITE][5] = F1; p->ListPos[F1] = 5;
630 p->AddToBoard(BB, F8); p->List[BLACK][5] = F8; p->ListPos[F8] = 5;
631 p->AddToBoard(WN, G1); p->List[WHITE][6] = G1; p->ListPos[G1] = 6;
632 p->AddToBoard(BN, G8); p->List[BLACK][6] = G8; p->ListPos[G8] = 6;
633 p->AddToBoard(WR, H1); p->List[WHITE][7] = H1; p->ListPos[H1] = 7;
634 p->AddToBoard(BR, H8); p->List[BLACK][7] = H8; p->ListPos[H8] = 7;
635
636 for (uint i=0; i < 8; i++) {
637 p->AddToBoard(WP, A2+i); p->List[WHITE][i+8] = A2+i; p->ListPos[A2+i] = i+8;
638 p->AddToBoard(BP, A7+i); p->List[BLACK][i+8] = A7+i; p->ListPos[A7+i] = i+8;
639 }
640
641 p->Castling = 0;
642 p->SetCastling (WHITE, QSIDE, true); p->SetCastling (WHITE, KSIDE, true);
643 p->SetCastling (BLACK, QSIDE, true); p->SetCastling (BLACK, KSIDE, true);
644 p->EPTarget = NULL_SQUARE;
645 p->ToMove = WHITE;
646 p->PlyCounter = 0;
647 p->HalfMoveClock = 0;
648 p->Board [NULL_SQUARE] = END_OF_BOARD;
649 p->Hash = stdStartHash;
650 p->PawnHash = stdStartPawnHash;
651 }
652 return startPositionTemplate;
653 }
654
655 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
656 // Position::IsStdStart
657 // Returns true if the position is the standard starting position.
IsStdStart() const658 bool Position::IsStdStart() const {
659 if (ToMove != WHITE
660 || Hash != stdStartHash || PawnHash != stdStartPawnHash
661 || GetCount(WHITE) != 16 || GetCount(BLACK) != 16
662 || RankCount(WP,RANK_2) != 8 || RankCount(BP,RANK_7) != 8
663 || RankCount(WN,RANK_1) != 2 || RankCount(BN,RANK_8) != 2
664 || !GetCastling(WHITE,KSIDE) || !GetCastling(WHITE,QSIDE)
665 || !GetCastling(BLACK,KSIDE) || !GetCastling(BLACK,QSIDE)) {
666 return false;
667 }
668 return true;
669 }
670
671 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
672 // Position::AddPiece():
673 // Add a piece to the board and piecelist.
674 // Checks that a side cannot have more than 16 pieces or more
675 // than one king.
676 //
677 errorT
AddPiece(pieceT p,squareT sq)678 Position::AddPiece (pieceT p, squareT sq)
679 {
680 ASSERT (p != EMPTY);
681 colorT c = piece_Color(p);
682 if ((c != WHITE && c != BLACK) || Count[c] > 15)
683 return ERROR_PieceCount;
684
685 if (piece_Type(p) == KING) {
686 // Check there is not already a King:
687 if (Material[p] > 0) { return ERROR_PieceCount; }
688
689 // King is always at the start of the piecelist, so move the piece
690 // already at location 0 if there is one:
691 if (Count[c] > 0) {
692 squareT oldsq = List[c][0];
693 List[c][Count[c]] = oldsq;
694 ListPos[oldsq] = Count[c];
695 }
696 List[c][0] = sq;
697 ListPos[sq] = 0;
698 } else {
699 ListPos[sq] = Count[c];
700 List[c][Count[c]] = sq;
701 }
702 Count[c]++;
703 Material[p]++;
704 AddToBoard (p, sq);
705 return OK;
706 }
707
708
709 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
710 // Position::CalcPins():
711 // Calculate the pieces for the side to move that are
712 // pinned to their king. The array Pinned[] stores, for
713 // each piece, the direction in which it is pinned.
714 //
715 // For example WK on e1, WQ on e2, BQ on e7 on the e-fyle
716 // means the WQ is Pinned in the direction UP.
717 //
718 void
CalcPins(void)719 Position::CalcPins (void)
720 {
721 Pinned[ 0] = Pinned[ 1] = Pinned[ 2] = Pinned[ 3] = Pinned[ 4] =
722 Pinned[ 5] = Pinned[ 6] = Pinned[ 7] = Pinned[ 8] = Pinned[ 9] =
723 Pinned[10] = Pinned[11] = Pinned[12] = Pinned[13] = Pinned[14] =
724 Pinned[15] = NULL_DIR;
725
726 squareT kingSq = GetKingSquare (ToMove);
727 colorT enemy = color_Flip (ToMove);
728 pieceT enemyQueen = piece_Make (enemy, QUEEN);
729 pieceT enemyRook = piece_Make (enemy, ROOK);
730 pieceT enemyBishop = piece_Make (enemy, BISHOP);
731
732 // Pins and checks from Bishops/Queens/Rooks:
733 fyleT fyle = square_Fyle (kingSq);
734 if (FyleCount(enemyQueen,fyle) + FyleCount(enemyRook,fyle) > 0) {
735 CalcPinsDir (UP, ROOK);
736 CalcPinsDir (DOWN, ROOK);
737 }
738 rankT rank = square_Rank (kingSq);
739 if (RankCount(enemyQueen,rank) + RankCount(enemyRook,rank) > 0) {
740 CalcPinsDir (LEFT, ROOK);
741 CalcPinsDir (RIGHT, ROOK);
742 }
743 leftDiagT ld = square_LeftDiag (kingSq);
744 if (LeftDiagCount(enemyQueen,ld) + LeftDiagCount(enemyBishop,ld) > 0) {
745 CalcPinsDir (UP_LEFT, BISHOP);
746 CalcPinsDir (DOWN_RIGHT, BISHOP);
747 }
748 rightDiagT rd = square_RightDiag (kingSq);
749 if (RightDiagCount(enemyQueen,rd) + RightDiagCount(enemyBishop,rd) > 0) {
750 CalcPinsDir (UP_RIGHT, BISHOP);
751 CalcPinsDir (DOWN_LEFT, BISHOP);
752 }
753 }
754
755 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
756 // Position::GenPieceMoves():
757 // Generates moves for a nonpawn, nonking piece.
758 // If sqset != NULL, moves must be to a square in sqset.<
759 void
GenPieceMoves(MoveList * mlist,squareT fromSq,SquareSet * sqset,bool capturesOnly)760 Position::GenPieceMoves (MoveList * mlist, squareT fromSq,
761 SquareSet * sqset, bool capturesOnly)
762 {
763 colorT c = ToMove;
764 pieceT p = Board[fromSq];
765 pieceT ptype = piece_Type(p);
766 ASSERT (p != EMPTY && ptype != KING && ptype != PAWN);
767
768 if (ptype == KNIGHT) {
769 GenKnightMoves (mlist, c, fromSq, sqset, capturesOnly);
770 return;
771 }
772 if (ptype != BISHOP) {
773 GenSliderMoves (mlist, c, fromSq, UP, sqset, capturesOnly);
774 GenSliderMoves (mlist, c, fromSq, DOWN, sqset, capturesOnly);
775 GenSliderMoves (mlist, c, fromSq, LEFT, sqset, capturesOnly);
776 GenSliderMoves (mlist, c, fromSq, RIGHT, sqset, capturesOnly);
777 }
778 if (ptype != ROOK) {
779 GenSliderMoves (mlist, c, fromSq, UP_LEFT, sqset, capturesOnly);
780 GenSliderMoves (mlist, c, fromSq, DOWN_LEFT, sqset, capturesOnly);
781 GenSliderMoves (mlist, c, fromSq, UP_RIGHT, sqset, capturesOnly);
782 GenSliderMoves (mlist, c, fromSq, DOWN_RIGHT, sqset, capturesOnly);
783 }
784 }
785
786 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
787 // Position::GenerateMoves
788 // Generate the legal moves list.
789 // If the specified pieceType is not EMPTY, then only legal
790 // moves for that type of piece are generated.
791 void
GenerateMoves(MoveList * mlist,pieceT pieceType,genMovesT genType,bool maybeInCheck)792 Position::GenerateMoves (MoveList* mlist, pieceT pieceType,
793 genMovesT genType, bool maybeInCheck)
794 {
795 ASSERT(mlist != NULL);
796
797 bool genNonCaptures = (genType & GEN_NON_CAPS);
798 bool capturesOnly = !genNonCaptures;
799
800 uint mask = 0;
801 if (pieceType != EMPTY) {
802 mask = 1 << pieceType;
803 } else {
804 mask = (1 << KING) | (1 << QUEEN) | (1 << ROOK)
805 | (1 << BISHOP) | (1 << KNIGHT) | (1 << PAWN);
806 }
807
808 // Use the objects own move list if none was provided:
809 mlist->Clear();
810
811 // Compute which pieces of the side to move are pinned to the king:
812 CalcPins();
813
814 // Determine if the side to move is in check and find where the
815 // checking pieces are, unless the caller has passed maybeInCheck=false
816 // indicating it is CERTAIN the side to move is not in check here.
817
818 uint numChecks = 0;
819 if (maybeInCheck) {
820 SquareList checkSquares;
821 numChecks = CalcNumChecks (GetKingSquare(ToMove), &checkSquares);
822 if (numChecks > 0) {
823 // The side to move IS in check:
824 GenCheckEvasions (mlist, pieceType, genType, &checkSquares);
825 return;
826 }
827 }
828
829 // The side to move is NOT in check. Iterate over each non-king
830 // piece, and then generate King moves last of all:
831
832 uint npieces = Count[ToMove];
833 for (uint x = 1; x < npieces; x++) {
834 squareT sq = List[ToMove][x];
835 pieceT p = Board[sq];
836 pieceT ptype = piece_Type(p);
837 if (! (mask & (1 << ptype))) { continue; }
838 directionT pinned = Pinned[x];
839
840 // If Pinned[x] == dir (not NULL_DIR), x can ONLY move along
841 // that direction or its opposite.
842
843 if (pinned != NULL_DIR) { // piece x is pinned to king
844 if (ptype == PAWN) {
845 GenPawnMoves (mlist, sq, pinned, NULL, genType);
846 } else if (ptype == KNIGHT) {
847 // do nothing -- pinned knights cannot move
848 } else {
849 // Piece is a pinned Queen/Rook/Bishop. Only generate
850 // moves along the pinned direction and its opposite:
851 if (ptype == QUEEN
852 || (ptype == ROOK && !direction_IsDiagonal(pinned))
853 || (ptype == BISHOP && direction_IsDiagonal(pinned))) {
854 GenSliderMoves (mlist, ToMove, sq, pinned, NULL, capturesOnly);
855 GenSliderMoves (mlist, ToMove, sq, dirOpposite[pinned],
856 NULL, capturesOnly);
857 }
858 }
859 } else {
860 // This piece is free to move anywhere
861 if (ptype == PAWN) {
862 GenPawnMoves (mlist, sq, NULL_DIR, NULL, genType);
863 } else {
864 // Knight/Queen/Bishop/Rook:
865 GenPieceMoves (mlist, sq, NULL, capturesOnly);
866 }
867 }
868 }
869
870 // Lastly, king moves...
871 if (mask & (1 << KING)) {
872 bool castling = !numChecks;
873 GenKingMoves (mlist, genType, castling);
874 }
875 }
876
877 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
878 // Position::IsLegalMove
879 // Determines whether the specified move is legal in this position,
880 // without requiring move generation (except for castling moves).
881 bool
IsLegalMove(simpleMoveT * sm)882 Position::IsLegalMove (simpleMoveT * sm) {
883 squareT from = sm->from;
884 squareT to = sm->to;
885 if (from > H8 || to > H8) { return false; }
886 if (from == to) { return false; }
887 pieceT mover = Board[from];
888 pieceT captured = Board[to];
889 if (piece_Color(mover) != ToMove) { return false; }
890 if (piece_Color(captured) == ToMove) { return false; }
891 if (sm->movingPiece != mover) { return false; }
892 mover = piece_Type (mover);
893 if (sm->promote != EMPTY && mover != PAWN) { return false; }
894
895 if (mover == PAWN) {
896 rankT rfrom = square_Rank(from);
897 rankT rto = square_Rank(to);
898 if (ToMove == BLACK) { rfrom = RANK_8 - rfrom; rto = RANK_8 - rto; }
899 int rdiff = (int)rto - (int)rfrom;
900 int fdiff = (int)square_Fyle(to) - (int)square_Fyle(from);
901 if (rdiff < 1 || rdiff > 2) { return false; }
902 if (fdiff < -1 || fdiff > 1) { return false; }
903 if (fdiff == 0) { // Pawn push:
904 if (captured != EMPTY) { return false; }
905 if (rdiff == 2) { // Two-square push:
906 if (rfrom != RANK_2) { return false; }
907 // Make sure the square in between is empty:
908 squareT midsquare = from + ((to - from) / 2);
909 if (Board[midsquare] != EMPTY) { return false; }
910 }
911 } else { // Pawn capture:
912 if (rdiff != 1) { return false; }
913 if (captured == EMPTY) {
914 // It must be en passant, or illegal
915 if (to != EPTarget) { return false; }
916 }
917 }
918 // Check the promotion piece:
919 if (rto == RANK_8) {
920 pieceT p = sm->promote;
921 if (p != QUEEN && p != ROOK && p != BISHOP && p != KNIGHT) {
922 return false;
923 }
924 } else {
925 if (sm->promote != EMPTY) { return false; }
926 }
927
928 } else if (piece_IsSlider(mover)) {
929 // Make sure the direction is valid:
930 directionT dir = sqDir[from][to];
931 if (dir == NULL_DIR) { return false; }
932 if (mover == ROOK && direction_IsDiagonal(dir)) { return false; }
933 if (mover == BISHOP && !direction_IsDiagonal(dir)) { return false; }
934 int delta = direction_Delta (dir);
935 // Make sure all the in-between squares are empty:
936 squareT dest = from + delta;
937 while (dest != to) {
938 if (Board[dest] != EMPTY) { return false; }
939 dest += delta;
940 }
941
942 } else if (mover == KNIGHT) {
943 if (! square_IsKnightHop (from, to)) { return false; }
944
945 } else /* (mover == KING) */ {
946 colorT enemy = color_Flip(ToMove);
947 if (! square_Adjacent (from, to)) {
948 // The move must be castling, or illegal.
949 if (IsKingInCheck()) { return false; }
950 MoveList mlist;
951 GenCastling (&mlist);
952 return std::find(mlist.begin(), mlist.end(), cmpMove(*sm)) != mlist.end();
953 }
954 if (square_Adjacent (to, GetKingSquare(enemy))) { return false; }
955 }
956
957 // The move looks good, but does it leave the king in check?
958 squareT kingSq = (mover == KING) ? to : GetKingSquare(ToMove);
959 colorT enemy = color_Flip(ToMove);
960 DoSimpleMove (sm);
961 uint nchecks = CalcAttacks (enemy, kingSq, NULL);
962 UndoSimpleMove (sm);
963 return (nchecks == 0);
964 }
965
966 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
967 // Position::MatchPawnMove():
968 // Sets the LegalMoves list to contain the matching pawn move,
969 // if there is one.
970 //
971 errorT
MatchPawnMove(MoveList * mlist,fyleT fromFyle,squareT to,pieceT promote)972 Position::MatchPawnMove (MoveList * mlist, fyleT fromFyle, squareT to, pieceT promote)
973 {
974 ASSERT(mlist != NULL);
975
976 mlist->Clear();
977
978 sint diff = (int)square_Fyle(to) - (int)fromFyle;
979 if (diff < -1 || diff > 1) { return ERROR_InvalidMove; }
980 pieceT pawn;
981 rankT toRank = square_Rank(to);
982 fyleT toFyle = square_Fyle(to);
983 rankT promoteRank = (ToMove == WHITE ? RANK_8 : RANK_1);
984
985 // from is the from square; backup is the alternative from square
986 // for a pawn move two squares forward.
987
988 squareT from, backup = NS;
989
990 if (ToMove == WHITE) {
991 pawn = WP;
992 if (toRank < RANK_3) { return ERROR_InvalidMove; }
993 from = square_Make(fromFyle, toRank - 1);
994 if (toRank == RANK_4 && fromFyle == toFyle) { backup = to - 16; }
995 } else {
996 pawn = BP;
997 if (toRank > RANK_6) { return ERROR_InvalidMove; }
998 from = square_Make(fromFyle, toRank + 1);
999 if (toRank == RANK_5 && fromFyle == toFyle) { backup = to + 16; }
1000 }
1001
1002 // See if the promotion piece is valid:
1003
1004 if (toRank == promoteRank) {
1005 // if (promote == EMPTY) { return ERROR_InvalidMove; }
1006 if (promote == EMPTY) {
1007 // autopromote to queen
1008 promote = QUEEN;
1009 }
1010 } else {
1011 if (promote != EMPTY) { return ERROR_InvalidMove; }
1012 }
1013
1014 if (Board[from] != pawn) {
1015 // No match; but it could be a foward-two-squares move:
1016 if (backup == NS || Board[from] != EMPTY || Board[backup] != pawn) {
1017 // A forward-two-squares move is impossible.
1018 return ERROR_InvalidMove;
1019 }
1020 from = backup;
1021 }
1022
1023 // OK, now 'from' is the only possible from-square. Is the move legal?
1024 // We make the move on the board and see if the King is in check.
1025
1026 uint legal = 0;
1027 if (fromFyle == toFyle) {
1028 // Not a capture:
1029
1030 if (Board[to] != EMPTY) { return ERROR_InvalidMove; }
1031 Board[to] = pawn; Board[from] = EMPTY;
1032 if (CalcNumChecks (GetKingSquare()) == 0) {
1033 legal = 1;
1034 }
1035 Board[to] = EMPTY; Board[from] = pawn;
1036
1037 } else {
1038 // It is a capture -- is it legal?
1039
1040 pieceT captured = Board[to];
1041 if (captured == EMPTY) {
1042 // Must be an en passant or illegal move.
1043 if (to != EPTarget) { return ERROR_InvalidMove; }
1044 squareT epSquare = square_Make(toFyle, square_Rank(from));
1045
1046 pieceT enemyPawn = piece_Make (color_Flip(ToMove), PAWN);
1047 // If following assert fails, eptarget was corrupt
1048 ASSERT (Board[epSquare] == enemyPawn);
1049
1050 Board[to] = pawn; Board[from] = EMPTY;
1051 Board[epSquare] = EMPTY;
1052 Material[enemyPawn] --;
1053 if (CalcNumChecks (GetKingSquare()) == 0) { legal = 1; }
1054 Board[epSquare] = enemyPawn;
1055 Board[to] = EMPTY;
1056 Board[from] = pawn;
1057 Material[enemyPawn]++;
1058
1059 } else {
1060 if (piece_Color(captured) == ToMove) {
1061 // Capturing a friendly!
1062 return ERROR_InvalidMove;
1063 } else {
1064 // A regular capture. See if it leaves King in check:
1065 Board[to] = pawn; Board[from] = EMPTY;
1066 Material[captured]--;
1067 if (CalcNumChecks (GetKingSquare()) == 0) {
1068 legal = 1;
1069 }
1070 Material[captured]++;
1071 Board[to] = captured; Board[from] = pawn;
1072 }
1073 }
1074 }
1075
1076 if (legal == 1) {
1077 AddLegalMove (mlist, from, to, promote);
1078 return OK;
1079 }
1080 return ERROR_InvalidMove;
1081 }
1082
1083 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1084 // Position::GenCheckEvasions():
1085 // Generate legal moves for the side to move when the
1086 // King is in check.
1087 //
1088 void
GenCheckEvasions(MoveList * mlist,pieceT mask,genMovesT genType,SquareList * checkSquares)1089 Position::GenCheckEvasions (MoveList * mlist, pieceT mask, genMovesT genType,
1090 SquareList * checkSquares)
1091 {
1092 ASSERT(mlist != NULL);
1093 uint numChecks = checkSquares->Size();
1094
1095 // Assert that king IS actually in check:
1096 ASSERT (numChecks > 0);
1097
1098 bool genNonCaptures = (genType & GEN_NON_CAPS);
1099 bool capturesOnly = !genNonCaptures;
1100 mlist->Clear();
1101
1102 squareT king = GetKingSquare (ToMove);
1103
1104 // if it's double check, we can ONLY move the king
1105 if (numChecks == 1) {
1106 // OK, it is NOT a double check
1107 // Try to block piece/capture piece. Remember en passant!
1108 // First, generate a list of targets: squares between the king
1109 // and attacker to block, and the attacker's square.
1110
1111 squareT attackSq = checkSquares->Get(0);
1112 directionT dir = sqDir[king][attackSq];
1113 SquareSet targets; // Set of blocking/capturing squares.
1114 targets.Add(attackSq);
1115
1116 // Now add squares we can might be able to block on.
1117 if (dir != NULL_DIR) {
1118 squareT sq = square_Move (king, dir);
1119 while (sq != attackSq) {
1120 if (Board[sq] == EMPTY) { targets.Add(sq); }
1121 sq = square_Move (sq, dir);
1122 }
1123 }
1124
1125 // Try each non-King piece in turn. If a piece is pinned to
1126 // the king, don't bother since it cannot possibly block or
1127 // capture the piece that is giving check!
1128
1129 uint numPieces = Count[ToMove];
1130 for (uint p2 = 1; p2 < numPieces; p2++) {
1131 squareT from = List[ToMove][p2];
1132 pieceT p2piece = Board[from];
1133 if (Pinned[p2] != NULL_DIR) { continue; }
1134 if (mask == EMPTY || mask == piece_Type(p2piece)) {
1135 if (piece_Type(p2piece) == PAWN) {
1136 GenPawnMoves (mlist, from, NULL_DIR, &targets, genType);
1137 // Capturing a pawn en passant will only get out
1138 // of check if the pawn that moved two squares
1139 // is doing the checking. If it is not, that means
1140 // a discovered check with the last pawn move so
1141 // taking en passant cannot get out of check.
1142 if (EPTarget != NULL_SQUARE) {
1143 squareT pawnSq = (ToMove == WHITE ? EPTarget - 8 : EPTarget + 8);
1144 if (pawnSq == attackSq) {
1145 SquareSet epset;
1146 epset.Add(EPTarget);
1147 GenPawnMoves (mlist, from, NULL_DIR, &epset, genType);
1148 }
1149 }
1150 } else {
1151 GenPieceMoves (mlist, from, &targets, capturesOnly);
1152 }
1153 }
1154 } // end of search for captures/blocks
1155 }
1156
1157 // Now king moves -- just compute them normally:
1158 if (mask == EMPTY || mask == KING) { GenKingMoves(mlist, genType, false); }
1159
1160 return;
1161 }
1162
1163 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1164 // Position::TreeCalcAttacks():
1165 // Calculate attack score for a side on a square,
1166 // using a recursive tree search.
1167 int
TreeCalcAttacks(colorT side,squareT target)1168 Position::TreeCalcAttacks(colorT side, squareT target)
1169 {
1170 int maxScore = -2;
1171 uint moveCount = 0, zeroCount = 0;
1172 MoveList moveList;
1173 GenerateCaptures(&moveList);
1174 for (uint i=0; i < moveList.Size(); i++) {
1175 simpleMoveT *smPtr = moveList.Get(i);
1176 if (smPtr->to == target) {
1177 if (piece_IsKing(Board[target])) return -1;
1178 moveCount++;
1179 DoSimpleMove(smPtr);
1180 int score = TreeCalcAttacks(color_Flip(side), target);
1181 UndoSimpleMove(smPtr);
1182 if (!score && ++zeroCount > 1) return -2;
1183 if (score > maxScore) maxScore = score;
1184 }
1185 }
1186
1187 if (!moveCount) return 0;
1188 if (!maxScore) return -1;
1189 return -maxScore;
1190 }
1191
1192 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1193 // Position::CalcAttacks():
1194 // Calculate the number of attacks by a side on a square.
1195 // This function also puts a list of the attacking piece squares
1196 // in the fromSqs parameter if it is non-NULL.
1197 //
1198 // It ONLY uses the Board[] and Material[] lists of the Position, and
1199 // ASSUMES they are correct with respect to each other, but it does
1200 // NOT use the List[] or ListPos[] information.
1201 // This allows us to move pieces quickly (altering only Board[] and
1202 // Material[]) and detect whether they leave the king in check,
1203 // without having to update other information.
1204 uint
CalcAttacks(colorT side,squareT target,SquareList * fromSquares) const1205 Position::CalcAttacks (colorT side, squareT target, SquareList * fromSquares) const
1206 {
1207 // If squares is NULL, caller doesn't want a list of the squares of
1208 // attacking pieces. To avoid comparing fromSquares with NULL every time
1209 // we find a check, we set up a local array to use instead if fromSquares
1210 // is NULL.
1211 SquareList fromSqs;
1212 if (fromSquares == NULL) { fromSquares = &fromSqs; }
1213
1214 fromSquares->Clear();
1215 squareT sq;
1216
1217 // Bishop/Queen/Rook attacks: look at each of the 8 directions
1218 pieceT king, queen, rook, bishop, knight;
1219 if (side == WHITE) {
1220 king = WK; queen = WQ; rook = WR; bishop = WB; knight = WN;
1221 } else {
1222 king = BK; queen = BQ; rook = BR; bishop = BB; knight = BN;
1223 }
1224
1225 uint numQueensRooks = Material[queen] + Material[rook];
1226 uint numQueensBishops = Material[queen] + Material[bishop];
1227
1228 // We only bother if there are any sliding pieces of each type:
1229 if (numQueensRooks > 0) {
1230 fyleT fyle = square_Fyle (target);
1231 rankT rank = square_Rank (target);
1232 directionT dirs[4];
1233 uint ndirs = 0;
1234 if (FyleCount(queen,fyle) + FyleCount(rook,fyle) > 0) {
1235 dirs[ndirs++] = UP; dirs[ndirs++] = DOWN;
1236 }
1237 if (RankCount(queen,rank) + RankCount(rook,rank) > 0) {
1238 dirs[ndirs++] = LEFT; dirs[ndirs++] = RIGHT;
1239 }
1240 for (uint i = 0; i < ndirs; i++) {
1241 directionT dir = dirs[i];
1242 int delta = direction_Delta (dir);
1243 squareT dest = target;
1244 squareT last = square_Last (target, dir);
1245
1246 while (dest != last) {
1247 dest += delta;
1248 pieceT p = Board[dest];
1249 if (p == EMPTY) {
1250 // empty square: keep searching
1251 } else if (p == queen || p == rook) {
1252 // Found an attacking piece
1253 fromSquares->Add(dest);
1254 break;
1255 } else {
1256 // Found a piece, but not a queen or rook
1257 break;
1258 }
1259 }
1260 }
1261 }
1262
1263 // Now diagonal sliders: Queens/Bishops:
1264 if (numQueensBishops > 0) {
1265 leftDiagT left = square_LeftDiag (target);
1266 rightDiagT right = square_RightDiag (target);
1267 directionT dirs[4];
1268 uint ndirs = 0;
1269 if (LeftDiagCount(queen,left) + LeftDiagCount(bishop,left) > 0) {
1270 dirs[ndirs++] = UP_LEFT; dirs[ndirs++] = DOWN_RIGHT;
1271 }
1272 if (RightDiagCount(queen,right) + RightDiagCount(bishop,right) > 0) {
1273 dirs[ndirs++] = UP_RIGHT; dirs[ndirs++] = DOWN_LEFT;
1274 }
1275 for (uint i = 0; i < ndirs; i++) {
1276 directionT dir = dirs[i];
1277 int delta = direction_Delta (dir);
1278 squareT dest = target;
1279 squareT last = square_Last (target, dir);
1280
1281 while (dest != last) {
1282 dest += delta;
1283 pieceT p = Board[dest];
1284 if (p == EMPTY) {
1285 // empty square: keep searching
1286 } else if (p == queen || p == bishop) {
1287 // Found an attacking piece
1288 fromSquares->Add(dest);
1289 break;
1290 } else {
1291 // Found a piece, but not an enemy queen or bishop
1292 break;
1293 }
1294 }
1295 }
1296 }
1297
1298 // Now knight checks: we only bother if there is a knight on the
1299 // opposite square color of the target square color.
1300 if (Material[knight] > 0
1301 && SquareColorCount(knight, color_Flip(square_Color(target))) > 0) {
1302 const squareT * destPtr = knightAttacks[target];
1303 while (true) {
1304 squareT dest = *destPtr;
1305 if (dest == NULL_SQUARE) { break; }
1306 if (Board[dest] == knight) {
1307 fromSquares->Add(dest);
1308 }
1309 destPtr++;
1310 }
1311 }
1312
1313 // Now pawn attacks:
1314 if (side == WHITE) {
1315 if (square_Rank(target) != RANK_1) { //if (Material[WP] > 0) {
1316 sq = square_Move (target, DOWN_LEFT);
1317 if (Board[sq] == WP) {
1318 fromSquares->Add(sq);
1319 }
1320 sq = square_Move (target, DOWN_RIGHT);
1321 if (Board[sq] == WP) {
1322 fromSquares->Add(sq);
1323 }
1324 }
1325 } else {
1326 if (square_Rank(target) != RANK_8) { //if (Material[BP] > 0) {
1327 sq = square_Move (target, UP_LEFT);
1328 if (Board[sq] == BP) {
1329 fromSquares->Add(sq);
1330 }
1331 sq = square_Move (target, UP_RIGHT);
1332 if (Board[sq] == BP) {
1333 fromSquares->Add(sq);
1334 }
1335 }
1336 }
1337
1338 // King attacks:
1339 const squareT *destPtr = kingAttacks[target];
1340 do if (Board[*destPtr] == king) fromSquares->Add(*destPtr);
1341 while (*++destPtr != NULL_SQUARE);
1342
1343 return fromSquares->Size();
1344 }
1345
1346 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1347 // Position::IsKingInCheckDir
1348 // Returns true if the King of the side to move is attacked
1349 // by an enemy sliding piece (Queen/Rook/Bishop) from the
1350 // specified direction.
1351 bool
IsKingInCheckDir(directionT dir)1352 Position::IsKingInCheckDir (directionT dir)
1353 {
1354 ASSERT (dir != NULL_DIR);
1355 squareT kingSq = GetKingSquare(ToMove);
1356 colorT enemy = color_Flip(ToMove);
1357 bool isDiagonal = direction_IsDiagonal(dir);
1358 pieceT queen = piece_Make (enemy, QUEEN);
1359 pieceT slider = piece_Make (enemy, (isDiagonal ? BISHOP : ROOK));
1360
1361 // First, make sure the enemy has sliding pieces that could give check:
1362 uint nSliders = PieceCount(queen) + PieceCount(slider);
1363 if (nSliders == 0) { return false; }
1364
1365 // Now make sure the enemy has a sliding piece on the appropriate
1366 // rank, file or diagonal:
1367 fyleT fyle = square_Fyle (kingSq);
1368 rankT rank = square_Rank (kingSq);
1369 leftDiagT ldiag = square_LeftDiag (kingSq);
1370 rightDiagT rdiag = square_RightDiag (kingSq);
1371
1372 switch (dir) {
1373 case UP:
1374 case DOWN:
1375 nSliders = FyleCount(queen,fyle) + FyleCount(slider,fyle);
1376 break;
1377 case LEFT:
1378 case RIGHT:
1379 nSliders = RankCount(queen,rank) + RankCount(slider,rank);
1380 break;
1381 case UP_LEFT:
1382 case DOWN_RIGHT:
1383 nSliders = LeftDiagCount(queen,ldiag) + LeftDiagCount(slider,ldiag);
1384 break;
1385 case UP_RIGHT:
1386 case DOWN_LEFT:
1387 nSliders = RightDiagCount(queen,rdiag) + RightDiagCount(slider,rdiag);
1388 break;
1389 }
1390 if (nSliders == 0) { return false; }
1391
1392 // Now move along the specified direction looking for a checking piece:
1393 squareT dest = kingSq;
1394 squareT last = square_Last (kingSq, dir);
1395 int delta = direction_Delta (dir);
1396
1397 while (dest != last) {
1398 dest += delta;
1399 pieceT p = Board[dest];
1400 if (p == EMPTY) {
1401 // empty square: keep searching
1402 } else if (p == queen || p == slider) {
1403 // Found an checking slider piece
1404 return true;
1405 } else {
1406 // Found a piece, but not an enemy queen or rook/bishop
1407 break;
1408 }
1409 }
1410
1411 return false;
1412 }
1413
1414 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1415 // Position::IsKingInCheck
1416 // Returns true if the king of the side to move is in check.
1417 // If the specified move is not NULL, it must be the legal move
1418 // that the opponent played to reach this position. This will
1419 // be used as a speed optimization, by skipping cases where the
1420 // move could not have left the king in check.
1421 //
1422 bool
IsKingInCheck(simpleMoveT * sm)1423 Position::IsKingInCheck (simpleMoveT * sm)
1424 {
1425 if (sm == NULL) { return IsKingInCheck(); }
1426
1427 squareT kingSq = GetKingSquare(ToMove);
1428 pieceT p = piece_Type (sm->movingPiece);
1429 if (sm->promote != EMPTY) { p = piece_Type(sm->promote); }
1430
1431 // No optimization of the last move was castling:
1432 if (p == KING && square_Fyle(sm->from) == E_FYLE) {
1433 fyleT toFyle = square_Fyle(sm->to);
1434 if (toFyle == C_FYLE || toFyle == G_FYLE) {
1435 return IsKingInCheck();
1436 }
1437 }
1438 // No optimization for en passant capture:
1439 if (p == PAWN && piece_Type(sm->capturedPiece) == PAWN) {
1440 rankT fromRank = square_Rank(sm->from);
1441 rankT capturedRank = square_Rank(sm->capturedSquare);
1442 if (fromRank == capturedRank) { return IsKingInCheck(); }
1443 }
1444
1445 if (p == PAWN) {
1446 if (ToMove == WHITE) {
1447 if (Material[BP] > 0) {
1448 squareT sq = square_Move (kingSq, UP_LEFT);
1449 if (Board[sq] == BP) { return true; }
1450 sq = square_Move (kingSq, UP_RIGHT);
1451 if (Board[sq] == BP) { return true; }
1452 }
1453 } else {
1454 if (Material[WP] > 0) {
1455 squareT sq = square_Move (kingSq, DOWN_LEFT);
1456 if (Board[sq] == WP) { return true; }
1457 sq = square_Move (kingSq, DOWN_RIGHT);
1458 if (Board[sq] == WP) { return true; }
1459 }
1460 }
1461 } else if (p == KNIGHT) {
1462 if (square_IsKnightHop (kingSq, sm->to)) { return true; }
1463 } else if (p == KING) {
1464 // A king cannot directly check its adversary.
1465 } else {
1466 // A sliding piece:
1467 directionT toDir = sqDir[kingSq][sm->to];
1468 if (toDir != NULL_DIR && IsKingInCheckDir(toDir)) { return true; }
1469 }
1470
1471 // Now look for a discovered check from a sliding piece:
1472 directionT dir = sqDir[kingSq][sm->from];
1473 if (dir != NULL_DIR && IsKingInCheckDir(dir)) { return true; }
1474
1475 ASSERT (IsKingInCheck() == false);
1476 return false;
1477 }
1478
1479 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1480 // Position::Mobility
1481 // Returns the number of squares a rook or bishop of the specified
1482 // color would attack from the specified square.
1483 uint
Mobility(pieceT p,colorT color,squareT from)1484 Position::Mobility (pieceT p, colorT color, squareT from)
1485 {
1486 ASSERT (p == ROOK || p == BISHOP);
1487 uint mobility = 0;
1488 directionT rookDirs[4] = { UP, DOWN, LEFT, RIGHT };
1489 directionT bishopDirs[4]
1490 = { UP_LEFT, UP_RIGHT, DOWN_LEFT, DOWN_RIGHT };
1491 directionT * dirPtr = (p == ROOK ? rookDirs : bishopDirs);
1492
1493 for (uint i=0; i < 4; i++) {
1494 directionT dir = dirPtr[i];
1495 int delta = direction_Delta (dir);
1496 squareT dest = from;
1497 squareT last = square_Last (from, dir);
1498
1499 while (dest != last) {
1500 dest += delta;
1501 pieceT p = Board[dest];
1502 if (p == EMPTY) { // Empty square
1503 mobility++;
1504 } else if (piece_Color(p) == color) { // Friendly piece
1505 break; // Finished with this direction.
1506 } else { // Enemy piece
1507 mobility++;
1508 break; // Finished with this direction.
1509 }
1510 }
1511 }
1512 return mobility;
1513 }
1514
1515 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1516 // Position::IsKingInMate():
1517 // Quick check if king is in mate.
1518 //
1519 bool
IsKingInMate(void)1520 Position::IsKingInMate (void)
1521 {
1522 SquareList checkSquares;
1523 uint numChecks = CalcNumChecks (GetKingSquare(ToMove), &checkSquares);
1524 if (numChecks == 0) { return false; }
1525 CalcPins ();
1526 MoveList mlist;
1527 GenCheckEvasions (&mlist, EMPTY, GEN_ALL_MOVES, &checkSquares);
1528 if (mlist.Size() == 0) { return true; }
1529 return false;
1530 }
1531
1532 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1533 // Position::IsLegal()
1534 // Verifies the position as being legal.
1535 // Returns false for any of the following:
1536 // - if the two kings are adjacent;
1537 // - if there are any pawns on the 1st/8th rank;
1538 // - if the side to move is already checking the enemy king.
1539 bool
IsLegal(void)1540 Position::IsLegal (void)
1541 {
1542 squareT stmKing = GetKingSquare();
1543 squareT enemyKing = GetEnemyKingSquare();
1544 if (square_Adjacent (stmKing, enemyKing)) { return false; }
1545 if (RankCount (WP, RANK_1) != 0) { return false; }
1546 if (RankCount (WP, RANK_8) != 0) { return false; }
1547 if (RankCount (BP, RANK_1) != 0) { return false; }
1548 if (RankCount (BP, RANK_8) != 0) { return false; }
1549 if (CalcAttacks (ToMove, enemyKing, NULL) > 0) {
1550 return false;
1551 }
1552 return true;
1553 }
1554
1555
1556 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1557 // Position::IsPromoMove():
1558 // Returns true if the move is a promotion move.
1559 // NOTE that the move may not actually be legal!
1560 // The arguments 'from' and 'to' can be in either order.
1561 bool
IsPromoMove(squareT from,squareT to)1562 Position::IsPromoMove (squareT from, squareT to)
1563 {
1564 rankT seventh, eighth;
1565 pieceT pawn;
1566 if (ToMove == WHITE) { seventh = RANK_7; eighth = RANK_8; pawn = WP; }
1567 else { seventh = RANK_2; eighth = RANK_1; pawn = BP; }
1568 rankT fromR, toR;
1569 fromR = square_Rank(from);
1570 toR = square_Rank(to);
1571 if ( (fromR == seventh && toR == eighth && Board[from] == pawn) ||
1572 (toR == seventh && fromR == eighth && Board[to] == pawn) ) {
1573 return 1;
1574 }
1575 return 0;
1576 }
1577
1578
1579 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1580 // Position::DoSimpleMove():
1581 // Make the move on the board and update all the necessary
1582 // fields in the simpleMove structure so it can be undone.
1583 //
1584 void
DoSimpleMove(simpleMoveT * sm)1585 Position::DoSimpleMove (simpleMoveT * sm)
1586 {
1587 ASSERT (sm != NULL);
1588 // The caller must have set the first 4 members of sm
1589 const squareT from = sm->from;
1590 const squareT to = sm->to;
1591 const auto promo = sm->promote;
1592 const auto ptype = piece_Type(sm->movingPiece);
1593 const auto pieceNum = ListPos[from];
1594
1595 // update move fields that (maybe) have not yet been set:
1596 sm->pieceNum = pieceNum;
1597 sm->capturedPiece = Board[to];
1598 sm->capturedSquare = to;
1599 sm->castleFlags = Castling;
1600 sm->epSquare = EPTarget;
1601 sm->oldHalfMoveClock = HalfMoveClock;
1602
1603 HalfMoveClock++;
1604 PlyCounter++;
1605
1606 auto finalUpdate = [&](auto enPassantSq) {
1607 EPTarget = enPassantSq;
1608 ToMove = color_Flip(ToMove);
1609 };
1610
1611 auto addPiece = [&](auto idx, auto pieceType, squareT destSq) {
1612 List[ToMove][idx] = destSq;
1613 ListPos[destSq] = idx;
1614 AddToBoard(piece_Make(ToMove, pieceType), destSq);
1615 };
1616
1617 if (sm->isNullMove())
1618 return finalUpdate(NULL_SQUARE);
1619
1620 if (ptype == KING) {
1621 ClearCastlingFlags(ToMove);
1622 if (auto castleSide = sm->isCastle()) {
1623 squareT rookfrom, rookto;
1624 if (castleSide == 1) {
1625 rookfrom = castlingRookSq<true>(ToMove);
1626 rookto = to - 1;
1627 } else {
1628 rookfrom = castlingRookSq<false>(ToMove);
1629 rookto = to + 1;
1630 }
1631 const int kingIdx = 0;
1632 const int rookIdx = ListPos[rookfrom];
1633 RemoveFromBoard(piece_Make(ToMove, ROOK), rookfrom);
1634 RemoveFromBoard(piece_Make(ToMove, KING), GetKingSquare(ToMove));
1635 addPiece(kingIdx, KING, to);
1636 addPiece(rookIdx, ROOK, rookto);
1637
1638 sm->pieceNum = kingIdx;
1639 sm->capturedPiece = EMPTY;
1640 return finalUpdate(NULL_SQUARE);
1641 }
1642 }
1643
1644 colorT enemy = color_Flip(ToMove);
1645 ASSERT(ptype == piece_Type(Board[from]));
1646
1647 // Handle en passant capture:
1648 if (ptype == PAWN && sm->capturedPiece == EMPTY
1649 && square_Fyle(from) != square_Fyle(to)) {
1650 // This was an EP capture. We do not need to check it was a capture
1651 // since if a pawn lands on EPTarget it must capture to get there.
1652 sm->capturedSquare = (ToMove == WHITE ? (to - 8) : (to + 8));
1653 ASSERT (Board[sm->capturedSquare] == piece_Make(enemy, PAWN));
1654 sm->capturedPiece = Board[sm->capturedSquare];
1655 }
1656
1657 // handle captures:
1658 if (sm->capturedPiece != EMPTY) {
1659 ASSERT (piece_Type(sm->capturedPiece) != KING);
1660 sm->capturedNum = ListPos[sm->capturedSquare];
1661 // update opponents List of pieces
1662 Count[enemy]--;
1663 ListPos[List[enemy][Count[enemy]]] = sm->capturedNum;
1664 List[enemy][sm->capturedNum] = List[enemy][Count[enemy]];
1665 Material[sm->capturedPiece]--;
1666 HalfMoveClock = 0;
1667 RemoveFromBoard (sm->capturedPiece, sm->capturedSquare);
1668 }
1669
1670 // now make the move:
1671 ASSERT(sm->movingPiece == Board[from]);
1672 const pieceT movingPiece = Board[from];
1673 RemoveFromBoard(movingPiece, from);
1674 if (promo != EMPTY) {
1675 ASSERT(movingPiece == piece_Make(ToMove, PAWN));
1676 Material[movingPiece]--;
1677 Material[piece_Make(ToMove, promo)]++;
1678 addPiece(pieceNum, promo, to);
1679 } else {
1680 addPiece(pieceNum, ptype, to);
1681 }
1682
1683 // Handle clearing of castling flags:
1684 if (Castling) {
1685 // See if a rook moved or was captured:
1686 if (from == castlingRookSq<false>(ToMove))
1687 SetCastling(ToMove, QSIDE, false);
1688 if (from == castlingRookSq<true>(ToMove))
1689 SetCastling(ToMove, KSIDE, false);
1690 if (to == castlingRookSq<false>(enemy))
1691 SetCastling(enemy, QSIDE, false);
1692 if (to == castlingRookSq<true>(enemy))
1693 SetCastling(enemy, KSIDE, false);
1694 }
1695
1696 // Set the EPTarget square, if a pawn advanced two squares and an
1697 // enemy pawn is on a square where en passant may be possible.
1698 EPTarget = NULL_SQUARE;
1699 if (ptype == PAWN) {
1700 rankT fromRank = square_Rank(from);
1701 rankT toRank = square_Rank(to);
1702 if (fromRank == RANK_2 && toRank == RANK_4
1703 && (Board[square_Move(to,LEFT)] == BP
1704 || Board[square_Move(to,RIGHT)] == BP)) {
1705 EPTarget = square_Move(from, UP);
1706 }
1707 if (fromRank == RANK_7 && toRank == RANK_5
1708 && (Board[square_Move(to,LEFT)] == WP
1709 || Board[square_Move(to,RIGHT)] == WP)) {
1710 EPTarget = square_Move(from, DOWN);
1711 }
1712 HalfMoveClock = 0; // 50-move clock resets on pawn moves.
1713 }
1714
1715 ToMove = enemy;
1716 return;
1717 }
1718
1719
1720 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1721 // Position::UndoSimpleMove():
1722 // Take back a simple move that has been made with DoSimpleMove().
1723 //
1724 void
UndoSimpleMove(simpleMoveT const * m)1725 Position::UndoSimpleMove (simpleMoveT const* m)
1726 {
1727 ASSERT (m != NULL);
1728 const squareT from = m->from;
1729 const squareT to = m->to;
1730 const auto pieceNum = ListPos[to];
1731 pieceT p = Board[to];
1732 EPTarget = m->epSquare;
1733 Castling = m->castleFlags;
1734 HalfMoveClock = m->oldHalfMoveClock;
1735 PlyCounter--;
1736 ToMove = color_Flip(ToMove);
1737
1738 // Check for a null move:
1739 if (m->isNullMove()) {
1740 return;
1741 }
1742
1743 auto addPiece = [&](auto idx, auto pieceType, squareT destSq) {
1744 List[ToMove][idx] = destSq;
1745 ListPos[destSq] = idx;
1746 AddToBoard(piece_Make(ToMove, pieceType), destSq);
1747 };
1748
1749 // handle Castling:
1750 if (piece_Type(p) == KING) {
1751 if (auto castleSide = m->isCastle()) {
1752 squareT rookfrom, rookto;
1753 if (castleSide == 1) {
1754 rookfrom = to - 1;
1755 rookto = castlingRookSq<true>(ToMove);
1756 } else {
1757 rookfrom = to + 1;
1758 rookto = castlingRookSq<false>(ToMove);
1759 }
1760 const int kingIdx = 0;
1761 const int rookIdx = ListPos[rookfrom];
1762 RemoveFromBoard(piece_Make(ToMove, KING), GetKingSquare(ToMove));
1763 RemoveFromBoard(piece_Make(ToMove, ROOK), rookfrom);
1764 addPiece(rookIdx, ROOK, rookto);
1765 addPiece(kingIdx, KING, castlingKingSq(ToMove));
1766 return;
1767 }
1768 }
1769
1770 // Handle a capture: insert piece back into piecelist.
1771 // This works for EP captures too, since the square of the captured
1772 // piece is in the "capturedSquare" field rather than assuming the
1773 // value of the "to" field. The only time these two fields are
1774 // different is for an en passant move.
1775 if (m->capturedPiece != EMPTY) {
1776 colorT c = color_Flip(ToMove);
1777 ListPos[List[c][m->capturedNum]] = Count[c];
1778 ListPos[m->capturedSquare] = m->capturedNum;
1779 List[c][Count[c]] = List[c][m->capturedNum];
1780 List[c][m->capturedNum] = m->capturedSquare;
1781 Material[m->capturedPiece]++;
1782 Count[c]++;
1783 }
1784
1785 // handle promotion:
1786 if (m->promote != EMPTY) {
1787 Material[p]--;
1788 RemoveFromBoard (p, to);
1789 p = piece_Make(ToMove, PAWN);
1790 Material[p]++;
1791 AddToBoard (p, to);
1792 }
1793
1794 // now make the move:
1795 List[ToMove][pieceNum] = from;
1796 ListPos[from] = pieceNum;
1797 RemoveFromBoard (p, to);
1798 AddToBoard (p, from);
1799 if (m->capturedPiece != EMPTY) {
1800 AddToBoard (m->capturedPiece, m->capturedSquare);
1801 }
1802 }
1803
1804
1805 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1806 // Position::RelocatePiece():
1807 // Given a from-square and to-square, modifies the position so
1808 // the piece on the from-square is relocated to the to-square.
1809 // Returns an error if the from square is empty, or the target
1810 // square is not empty, or the relocation would otherwise
1811 // produce an illegal position (e.g. pawn on the 1st or 8th rank
1812 // or a King in check).
1813 //
1814 errorT
RelocatePiece(squareT fromSq,squareT toSq)1815 Position::RelocatePiece (squareT fromSq, squareT toSq)
1816 {
1817 // Must have on-board squares:
1818 if (fromSq == NS || toSq == NS) { return ERROR; }
1819
1820 // If squares are identical, just return success:
1821 if (fromSq == toSq) { return OK; }
1822
1823 pieceT piece = Board[fromSq];
1824 pieceT ptype = piece_Type(piece);
1825 colorT pcolor = piece_Color(piece);
1826
1827 // Must be relocating a nonempty piece to an empty square:
1828 if (piece == EMPTY || Board[toSq] != EMPTY) { return ERROR; }
1829
1830 // Pawns cannot relocate to the first or last rank:
1831 if (ptype == PAWN) {
1832 rankT toRank = square_Rank(toSq);
1833 if (toRank == RANK_1 || toRank == RANK_8) { return ERROR; }
1834 }
1835
1836 // Locate the piece index in the appropriate list of pieces:
1837 uint index = ListPos[fromSq];
1838 ASSERT(List[pcolor][index] == fromSq);
1839
1840 // Relocate the piece:
1841 List[pcolor][index] = toSq;
1842 ListPos[toSq] = index;
1843 RemoveFromBoard (piece, fromSq);
1844 AddToBoard (piece, toSq);
1845
1846 // Check for adjacent kings or side to move giving check:
1847 if (! IsLegal()) {
1848 // Undo the relocation and return error:
1849 List[pcolor][index] = fromSq;
1850 RemoveFromBoard (piece, toSq);
1851 AddToBoard (piece, fromSq);
1852 return ERROR;
1853 }
1854
1855 // Relocation successful:
1856 return OK;
1857 }
1858
1859
1860 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1861 // Position::MaterialValue():
1862 // Returns the sum value of material for a particular side,
1863 // where piece values are:
1864 // King: 0 (since both sides always have one)
1865 // Queen: 9
1866 // Rook: 5
1867 // Bishop, Knight: 3 each
1868 // Pawn: 1
1869 uint
MaterialValue(colorT c)1870 Position::MaterialValue (colorT c)
1871 {
1872 ASSERT (c == WHITE || c == BLACK);
1873 uint value = 0;
1874 if (c == WHITE) {
1875 value += 9 * PieceCount(WQ);
1876 value += 5 * PieceCount(WR);
1877 value += 3 * PieceCount(WB);
1878 value += 3 * PieceCount(WN);
1879 value += 1 * PieceCount(WP);
1880 } else {
1881 value += 9 * PieceCount(BQ);
1882 value += 5 * PieceCount(BR);
1883 value += 3 * PieceCount(BB);
1884 value += 3 * PieceCount(BN);
1885 value += 1 * PieceCount(BP);
1886 }
1887 return value;
1888 }
1889
1890
1891 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1892 // Position::MakeSANString():
1893 // Make the SAN string for a simpleMove.
1894 // The parameter 'sanFlag' indicates whether '+' and '#' symbols
1895 // should be added to checking or mating moves.
1896 //
1897 void
MakeSANString(simpleMoveT * m,char * s,sanFlagT flag)1898 Position::MakeSANString (simpleMoveT * m, char * s, sanFlagT flag)
1899 {
1900 ASSERT (m != NULL && s != NULL);
1901
1902 auto isOccupied = [this](auto square) { return Board[square] != EMPTY; };
1903
1904 ASSERT(m->from == List[ToMove][ListPos[m->from]]);
1905 const squareT from = m->from;
1906 const squareT to = m->to;
1907 char * c = s;
1908 pieceT piece = Board[from];
1909 pieceT p = piece_Type(piece);
1910
1911 if (p == PAWN) {
1912 if (square_Fyle(from) != square_Fyle(to)) { // pawn capture
1913 *c++ = square_FyleChar(from);
1914 *c++ = 'x';
1915 }
1916 *c++ = square_FyleChar(to);
1917 *c++ = square_RankChar(to);
1918 if ((square_Rank(to)==RANK_1) || (square_Rank(to)==RANK_8)) {
1919 *c++ = '=';
1920 *c++ = piece_Char(m->promote);
1921 p = piece_Type(m->promote);
1922 }
1923
1924 } else if (p == KING) {
1925 if (m->isNullMove()) {
1926 //*c++ = 'n'; *c++ = 'u'; *c++ = 'l'; *c++ = 'l';
1927 *c++ = '-'; *c++ = '-';
1928 } else {
1929 switch (m->isCastle()) {
1930 case 0:
1931 *c++ = 'K';
1932 if (Board[to] != EMPTY)
1933 *c++ = 'x';
1934 *c++ = square_FyleChar(to);
1935 *c++ = square_RankChar(to);
1936 break;
1937 case 1:
1938 *c++ = 'O';
1939 *c++ = '-';
1940 *c++ = 'O';
1941 break;
1942 case 2:
1943 *c++ = 'O';
1944 *c++ = '-';
1945 *c++ = 'O';
1946 *c++ = '-';
1947 *c++ = 'O';
1948 break;
1949 }
1950 }
1951
1952 } else { // Queen/Rook/Bishop/Knight
1953 *c++ = piece_Char(p);
1954
1955 // We only need to calculate legal moves to disambiguate if there
1956 // are more than one of this type of piece.
1957 if (Material[piece] > 1) {
1958 int ambiguity = 0;
1959 for (uint i = 1, n = Count[ToMove]; i < n; i++) {
1960 squareT sq = List[ToMove][i];
1961 if (sq == from || Board[sq] != piece)
1962 continue;
1963
1964 if (!movegen::pseudo(sq, to, ToMove, p, isOccupied))
1965 continue; // Skip illegal move
1966
1967 const auto pin = movegen::opens_ray(sq, to, GetKingSquare(),
1968 isOccupied);
1969 if (pin.first != INVALID_PIECE &&
1970 piece_Color_NotEmpty(Board[pin.second]) != ToMove) {
1971 pieceT pt = piece_Type(Board[pin.second]);
1972 if (pt == QUEEN || pt == pin.first)
1973 continue; // Skip pinned piece
1974 }
1975
1976 // Ambiguity:
1977 // 1 (0001) --> need from-file (preferred) or from-rank
1978 // 3 (0011) --> need from-file
1979 // 5 (0101) --> need from-rank
1980 // 7 (0111) --> need both from-file and from-rank
1981 ambiguity |= 1;
1982 if (square_Rank(from) == square_Rank(sq)) {
1983 ambiguity |= 2; // 0b0010
1984 } else if (square_Fyle(from) == square_Fyle(sq)) {
1985 ambiguity |= 4; // 0b0100
1986 }
1987 }
1988 if (ambiguity) {
1989 if (ambiguity != 5)
1990 *c++ = square_FyleChar(from); // print from-fyle
1991 if (ambiguity >= 5)
1992 *c++ = square_RankChar(from); // print from-rank
1993 }
1994 }
1995 if (Board[to] != EMPTY)
1996 *c++ = 'x';
1997 *c++ = square_FyleChar(to);
1998 *c++ = square_RankChar(to);
1999 }
2000
2001 bool check;
2002 if (flag != SAN_NO_CHECKTEST) {
2003 squareT oldTo = Board[to];
2004 Board[to] = Board[from];
2005 Board[from] = EMPTY;
2006 squareT enemyKingSq = GetEnemyKingSquare();
2007 check = (p != KING) &&
2008 movegen::attack(to, enemyKingSq, ToMove, p, isOccupied);
2009 if (!check) {
2010 bool enpassant = (p == PAWN && oldTo == EMPTY &&
2011 square_Fyle(from) != square_Fyle(to));
2012 if (!enpassant && (p != KING || !m->isCastle()) &&
2013 !movegen::attack_slider(from, enemyKingSq, QUEEN, isOccupied)) {
2014 flag = SAN_NO_CHECKTEST;
2015 }
2016
2017 } else if (flag != SAN_MATETEST) {
2018 *c++ = '+';
2019 flag = SAN_NO_CHECKTEST;
2020 }
2021 Board[from] = Board[to];
2022 Board[to] = oldTo;
2023 }
2024
2025 // Now do the check or mate symbol:
2026 if (flag != SAN_NO_CHECKTEST) {
2027 // Now we make the move to test for check:
2028 DoSimpleMove (m);
2029 if (check || CalcNumChecks(GetKingSquare()) > 0) {
2030 char ch = '+';
2031 if (flag == SAN_MATETEST) {
2032 MoveList mlist;
2033 GenerateMoves (&mlist);
2034 if (mlist.Size() == 0) { ch = '#'; }
2035 }
2036 *c++ = ch;
2037 }
2038 UndoSimpleMove (m);
2039 }
2040 *c = 0;
2041 }
2042
2043 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2044 // Position::ReadCoordMove():
2045 // Given a move in coordinate notation,
2046 // e.g. "e2e4" or "g1f3", generates the legal move it represents.
2047 // Returns: OK or ERROR_InvalidMove.
2048 // If "reverse" is true, coordinates in reverse order are acceptable,
2049 // e.g. "f3g1" for 1.Nf3.
2050 //
ReadCoordMove(simpleMoveT * m,const char * str,int slen,bool reverse)2051 errorT Position::ReadCoordMove(simpleMoveT* m, const char* str, int slen,
2052 bool reverse) {
2053 ASSERT (m != NULL && str != NULL);
2054 fyleT fromFyle, toFyle;
2055 rankT fromRank, toRank;
2056 squareT from, to;
2057 pieceT promo = EMPTY;
2058
2059 if (slen == 5) {
2060 promo = piece_FromChar(toupper(str[4]));
2061 } else if (slen != 4) { return ERROR_InvalidMove; }
2062
2063 fromFyle = fyle_FromChar (str[0]);
2064 fromRank = rank_FromChar (str[1]);
2065 from = square_Make (fromFyle, fromRank);
2066 if (from == NS) { return ERROR_InvalidMove; }
2067
2068 toFyle = fyle_FromChar (str[2]);
2069 toRank = rank_FromChar (str[3]);
2070 to = square_Make (toFyle, toRank);
2071 if (to == NS) { return ERROR_InvalidMove; }
2072
2073 MoveList mlist;
2074 GenerateMoves(&mlist);
2075 for (size_t i = 0, n = mlist.Size(); i < n; i++) {
2076 simpleMoveT* sm = mlist.Get(i);
2077 if (sm->promote == promo) {
2078 if (sm->from == from && sm->to == to) {
2079 *m = *sm;
2080 return OK;
2081 }
2082 if (reverse && sm->to == from && sm->from == to) {
2083 *m = *sm;
2084 return OK;
2085 }
2086 }
2087 }
2088 return ERROR_InvalidMove;
2089 }
2090
trimCheck(const char * str,int slen)2091 static int trimCheck(const char* str, int slen) {
2092 while (slen > 0) { // trim mate '#' or check '+'
2093 --slen;
2094 if (str[slen] != '#' && str[slen] != '+') {
2095 ++slen;
2096 break;
2097 }
2098 }
2099 return slen;
2100 }
2101
ReadMovePawn(simpleMoveT * sm,const char * str,int slen,fyleT frFyle)2102 errorT Position::ReadMovePawn(simpleMoveT* sm, const char* str, int slen,
2103 fyleT frFyle) {
2104 ASSERT(sm != NULL && str != NULL && frFyle <= H_FYLE);
2105
2106 slen = trimCheck(str, slen);
2107 if (slen < 2)
2108 return ERROR_InvalidMove;
2109
2110 auto is_digit = [](char ch) {
2111 return isdigit(static_cast<unsigned char>(ch));
2112 };
2113 auto is_lower = [](char ch) {
2114 return islower(static_cast<unsigned char>(ch));
2115 };
2116
2117 if (slen >= 4 && // Check if it is a coordinates-style move ("e2e4")
2118 is_digit(str[1]) && is_lower(str[2]) && is_digit(str[3])) {
2119 return ReadCoordMove(sm, str, slen, false);
2120 }
2121
2122 MoveList mlist;
2123 pieceT promo = EMPTY;
2124 auto last_ch = static_cast<unsigned char>(str[slen - 1]);
2125 if (!is_digit(last_ch)) {
2126 // Promotion, last char must be Q/R/B/N.
2127 promo = piece_FromChar(toupper(last_ch));
2128 if (promo != QUEEN && promo != ROOK && promo != KNIGHT &&
2129 promo != BISHOP) {
2130 return ERROR_InvalidMove;
2131 }
2132 slen--;
2133 // Accept the move even if it is of the form "a8Q" not "a8=Q":
2134 if (str[slen - 1] == '=') {
2135 slen--;
2136 }
2137 }
2138 if (slen < 2)
2139 return ERROR_InvalidMove;
2140
2141 // Check for the compact form of capture with no rank,
2142 // e.g. "ed" or "de=Q":
2143 if (slen == 2 && (str[1] >= 'a' && str[1] <= 'h')) {
2144 auto toFyle = fyle_FromChar(str[1]);
2145 // Check each rank in turn, looking for the capture:
2146 for (rankT r = RANK_1; r <= RANK_8; r++) {
2147 auto to = square_Make(toFyle, r);
2148 if (MatchPawnMove(&mlist, frFyle, to, promo) == OK) {
2149 *sm = *(mlist.Get(0));
2150 return OK;
2151 }
2152 }
2153 // It is NOT a valid capture with no rank:
2154 return ERROR_InvalidMove;
2155 }
2156
2157 auto toFyle = fyle_FromChar(str[slen - 2]);
2158 auto toRank = rank_FromChar(str[slen - 1]);
2159 if (toRank == NO_RANK || toFyle == NO_FYLE)
2160 return ERROR_InvalidMove;
2161
2162 auto to = square_Make(toFyle, toRank);
2163 if (MatchPawnMove(&mlist, frFyle, to, promo) != OK)
2164 return ERROR_InvalidMove;
2165
2166 *sm = *(mlist.Get(0));
2167 return OK;
2168 }
2169
ReadMoveKing(simpleMoveT * sm,const char * str,int slen)2170 errorT Position::ReadMoveKing(simpleMoveT* sm, const char* str, int slen) {
2171 ASSERT(sm != NULL && str != NULL);
2172
2173 slen = trimCheck(str, slen);
2174 if (slen < 3 || slen > 6)
2175 return ERROR_InvalidMove;
2176
2177 auto toRank = rank_FromChar(str[slen - 1]);
2178 auto toFyle = fyle_FromChar(str[slen - 2]);
2179 if (toRank == NO_RANK || toFyle == NO_FYLE)
2180 return ERROR_InvalidMove;
2181
2182 auto target = square_Make(toFyle, toRank);
2183 squareT kingSq = GetKingSquare(ToMove);
2184 if (!movegen::valid_king(kingSq, target))
2185 return ERROR_InvalidMove;
2186
2187 pieceT captured = Board[target];
2188 if (captured != EMPTY && (piece_Color_NotEmpty(captured) == ToMove ||
2189 piece_Type(captured) == KING)) {
2190 return ERROR_InvalidMove;
2191 }
2192
2193 // XXX We should also check for adjacency to enemy King!!
2194 if (movegen::valid_king(GetKingSquare(color_Flip(ToMove)), target))
2195 return ERROR_InvalidMove;
2196
2197 // Now make the move on the Board and Material lists, and see if it
2198 // leaves the King in check:
2199 auto movingPiece = piece_Make(ToMove, KING);
2200 Board[target] = movingPiece;
2201 Board[kingSq] = EMPTY;
2202 if (captured != EMPTY) {
2203 Material[captured]--;
2204 }
2205 auto nChecks = CalcNumChecks(target);
2206 if (captured != EMPTY) {
2207 Material[captured]++;
2208 }
2209 Board[target] = captured;
2210 Board[kingSq] = movingPiece;
2211 if (nChecks)
2212 return ERROR_InvalidMove;
2213
2214 sm->from = kingSq;
2215 sm->to = target;
2216 sm->promote = EMPTY;
2217 sm->movingPiece = movingPiece;
2218 return OK;
2219 }
2220
2221 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2222 // Position::ReadMove():
2223 // Given a move in (possibly sloppy) PGN notation,
2224 // generates the legal move it corresponds to.
2225 // Returns: OK or ERROR_InvalidMove.
2226 //
ReadMove(simpleMoveT * sm,const char * str,int slen,pieceT piece)2227 errorT Position::ReadMove(simpleMoveT* sm, const char* str, int slen,
2228 pieceT piece) {
2229 ASSERT(sm != NULL && str != NULL);
2230 ASSERT(piece == QUEEN || piece == ROOK || piece == BISHOP ||
2231 piece == KNIGHT);
2232
2233 slen = trimCheck(str, slen);
2234 if (slen < 3 || slen > 6)
2235 return ERROR_InvalidMove;
2236
2237 auto toRank = rank_FromChar(str[slen - 1]);
2238 auto toFyle = fyle_FromChar(str[slen - 2]);
2239 if (toRank == NO_RANK || toFyle == NO_FYLE)
2240 return ERROR_InvalidMove;
2241 auto to = square_Make(toFyle, toRank);
2242
2243 pieceT captured = Board[to];
2244 if (captured != EMPTY && (piece_Color_NotEmpty(captured) == ToMove ||
2245 piece_Type(captured) == KING)) {
2246 return ERROR_InvalidMove;
2247 }
2248
2249 auto frFyle = NO_FYLE;
2250 auto frRank = NO_RANK;
2251 if (slen > 3) { // There is some ambiguity information in the input string.
2252 frFyle = fyle_FromChar(str[1]);
2253 frRank = rank_FromChar(str[1]);
2254 if (frRank == NO_RANK && slen > 4) {
2255 frRank = rank_FromChar(str[2]);
2256 }
2257 }
2258
2259 // Loop through looking for pieces of the corresponding type. We start at 1
2260 // since the King is always the piece at position 0 in the list.
2261 int matchCount = 0;
2262 auto movingPiece = piece_Make(ToMove, piece);
2263 int nPieces = Material[movingPiece];
2264 squareT kingSq = GetKingSquare(ToMove);
2265 for (unsigned i = 1, n = Count[ToMove]; i < n && nPieces; i++) {
2266 auto from = List[ToMove][i];
2267 if (Board[from] != movingPiece)
2268 continue;
2269
2270 --nPieces;
2271 if ((frFyle != NO_FYLE && frFyle != square_Fyle(from)) ||
2272 (frRank != NO_RANK && frRank != square_Rank(from)))
2273 continue;
2274
2275 auto isOccupied = [this](auto sq) { return Board[sq] != EMPTY; };
2276 if (!movegen::pseudo(from, to, ToMove, piece, isOccupied))
2277 continue;
2278
2279 const auto pin = movegen::opens_ray(from, to, kingSq, isOccupied);
2280 if (pin.first != INVALID_PIECE) {
2281 auto p = Board[pin.second];
2282 if (piece_Color_NotEmpty(p) != ToMove &&
2283 (piece_Type(p) == QUEEN || piece_Type(p) == pin.first))
2284 continue;
2285 }
2286
2287 ++matchCount;
2288 sm->from = from;
2289 sm->to = to;
2290 sm->promote = EMPTY;
2291 sm->movingPiece = movingPiece;
2292 }
2293 return (matchCount == 1) ? OK // ok.
2294 : ERROR_InvalidMove; // No match, or too many
2295 // (ambiguous) moves match.
2296 }
2297
ReadMoveCastle(simpleMoveT * sm,const char * str,int slen)2298 errorT Position::ReadMoveCastle(simpleMoveT* sm, const char* str, int slen) {
2299 slen = trimCheck(str, slen);
2300
2301 auto str_equal = [&](const char* const_str, const int len) {
2302 return slen == len && std::equal(str, str + len, const_str);
2303 };
2304
2305 sm->from = square_Relative(ToMove, E1);
2306 sm->promote = EMPTY;
2307 sm->movingPiece = piece_Make(ToMove, KING);
2308 sm->capturedPiece = EMPTY;
2309
2310 if (str_equal("O-O", 3) || str_equal("OO", 2)) {
2311 sm->to = sm->from + 2;
2312 if (!IsKingInCheck() && validCastling(true, true)) // short castle
2313 return GetCastling(ToMove, KSIDE) ? OK : ERROR_CastlingAvailability;
2314
2315 return validCastling(true, false) ? ERROR_CastlingAvailability
2316 : ERROR_InvalidMove;
2317 }
2318 if (str_equal("O-O-O", 5) || str_equal("OOO", 3)) {
2319 sm->to = sm->from - 2;
2320 if (!IsKingInCheck() && validCastling(false, true)) // long castle
2321 return GetCastling(ToMove, QSIDE) ? OK : ERROR_CastlingAvailability;
2322
2323 return validCastling(false, false) ? ERROR_CastlingAvailability
2324 : ERROR_InvalidMove;
2325 }
2326 return ERROR_InvalidMove;
2327 }
2328
ParseMove(simpleMoveT * sm,const char * str)2329 errorT Position::ParseMove(simpleMoveT* sm, const char* str) {
2330 while (!isalpha(static_cast<unsigned char>(*str)) && *str != '\0') {
2331 str++; // trim left
2332 }
2333 const char* begin = str;
2334 while (!isspace(static_cast<unsigned char>(*str)) && *str != '\0') {
2335 str++; // trim right
2336 }
2337 return ParseMove(sm, begin, str);
2338 }
2339
2340 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2341 // Position::ParseMove():
2342 // Parse a single move from SAN-style notation.
2343 //
ParseMove(simpleMoveT * sm,const char * str,const char * strEnd)2344 errorT Position::ParseMove(simpleMoveT* sm, const char* str,
2345 const char* strEnd) {
2346 ASSERT(str != NULL);
2347
2348 int length = static_cast<int>(std::distance(str, strEnd));
2349 if (length < 2 || length > 9)
2350 return ERROR_InvalidMove;
2351
2352 switch (str[0]) {
2353 case 'a':
2354 return ReadMovePawn(sm, str, length, A_FYLE);
2355 case 'b':
2356 return ReadMovePawn(sm, str, length, B_FYLE);
2357 case 'c':
2358 return ReadMovePawn(sm, str, length, C_FYLE);
2359 case 'd':
2360 return ReadMovePawn(sm, str, length, D_FYLE);
2361 case 'e':
2362 return ReadMovePawn(sm, str, length, E_FYLE);
2363 case 'f':
2364 return ReadMovePawn(sm, str, length, F_FYLE);
2365 case 'g':
2366 return ReadMovePawn(sm, str, length, G_FYLE);
2367 case 'h':
2368 return ReadMovePawn(sm, str, length, H_FYLE);
2369 case 'K':
2370 return ReadMoveKing(sm, str, length);
2371 case 'Q':
2372 return ReadMove(sm, str, length, QUEEN);
2373 case 'R':
2374 return ReadMove(sm, str, length, ROOK);
2375 case 'B':
2376 return ReadMove(sm, str, length, BISHOP);
2377 case 'N':
2378 return ReadMove(sm, str, length, KNIGHT);
2379 case 'O':
2380 return ReadMoveCastle(sm, str, length);
2381 }
2382
2383 // Check for a null move:
2384 if ((length == 2 && std::equal(str, str + 2, "--")) ||
2385 (length == 2 && std::equal(str, str + 2, "Z0")) ||
2386 (length == 4 && std::equal(str, str + 4, "null"))) {
2387 sm->from = GetKingSquare(ToMove);
2388 sm->to = sm->from;
2389 sm->movingPiece = Board[sm->from];
2390 sm->promote = EMPTY;
2391 return OK;
2392 }
2393
2394 // Invalid move, check for a misspelled first char:
2395 switch (str[0]) {
2396 case 'A':
2397 return ReadMovePawn(sm, str, length, A_FYLE);
2398 case 'C':
2399 return ReadMovePawn(sm, str, length, C_FYLE);
2400 case 'D':
2401 return ReadMovePawn(sm, str, length, D_FYLE);
2402 case 'E':
2403 return ReadMovePawn(sm, str, length, E_FYLE);
2404 case 'F':
2405 return ReadMovePawn(sm, str, length, F_FYLE);
2406 case 'G':
2407 return ReadMovePawn(sm, str, length, G_FYLE);
2408 case 'H':
2409 return ReadMovePawn(sm, str, length, H_FYLE);
2410 case 'P':
2411 return ParseMove(sm, str + 1, strEnd);
2412 case 'k':
2413 return ReadMoveKing(sm, str, length);
2414 case 'q':
2415 return ReadMove(sm, str, length, QUEEN);
2416 case 'r':
2417 return ReadMove(sm, str, length, ROOK);
2418 case 'n':
2419 return ReadMove(sm, str, length, KNIGHT);
2420 }
2421 return ERROR_InvalidMove;
2422 }
2423
2424 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2425 // Position::CalcSANStrings():
2426 // Calculate the SAN string for each move in the legal moves list.
2427 //
2428 void
CalcSANStrings(sanListT * sanList,sanFlagT flag)2429 Position::CalcSANStrings (sanListT *sanList, sanFlagT flag)
2430 {
2431 MoveList mlist;
2432 GenerateMoves(&mlist);
2433 for (size_t i = 0, n = mlist.Size(); i < n; i++) {
2434 MakeSANString(mlist.Get(i), sanList->list[i], flag);
2435 }
2436 sanList->num = mlist.Size();
2437 sanList->current = true;
2438 }
2439
2440 errorT
ReadFromLongStr(const char * str)2441 Position::ReadFromLongStr (const char * str)
2442 {
2443 pieceT pieceFromByte [256] = {EMPTY};
2444 pieceFromByte [(int) 'K'] = WK; pieceFromByte [(int) 'k'] = BK;
2445 pieceFromByte [(int) 'Q'] = WQ; pieceFromByte [(int) 'q'] = BQ;
2446 pieceFromByte [(int) 'R'] = WR; pieceFromByte [(int) 'r'] = BR;
2447 pieceFromByte [(int) 'B'] = WB; pieceFromByte [(int) 'b'] = BB;
2448 pieceFromByte [(int) 'N'] = WN; pieceFromByte [(int) 'n'] = BN;
2449 pieceFromByte [(int) 'P'] = WP; pieceFromByte [(int) 'p'] = BP;
2450
2451 Clear();
2452 for (squareT sq=A1; sq <= H8; sq++) {
2453 if (str[sq] == '.') { continue; }
2454 pieceT p = pieceFromByte [(byte) str[sq]];
2455 if (p == EMPTY) { return ERROR_Corrupt; }
2456 if (AddPiece (p,sq) != OK) { return ERROR_Corrupt; }
2457 }
2458 switch (str[65]) {
2459 case 'w':
2460 SetToMove (WHITE);
2461 break;
2462 case 'b':
2463 SetToMove (BLACK);
2464 break;
2465 default:
2466 return ERROR_Corrupt;
2467 }
2468 return OK;
2469 }
2470
2471 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2472 // Position::MakeLongStr():
2473 // Make a string representing the board. It will be 66 characters
2474 // long, encoding the 64 squares (in the order a1,b1,...,g8,h8
2475 // with white pieces in upper case, black pieces in lower case,
2476 // and empty squares as dots) then a space, and finally "w" or "b"
2477 // indicating the side to move. Example for the starting position:
2478 // "RNBQKBNRPPPPPPPP................................pppppppprbnqkbnr w"
2479 //
2480 void
MakeLongStr(char * str)2481 Position::MakeLongStr (char * str)
2482 {
2483 ASSERT (str != NULL);
2484 char * s = str;
2485 for (squareT sq = A1; sq <= H8; sq++) {
2486 *s++ = PIECE_CHAR[Board[sq]];
2487 }
2488 *s++ = ' ';
2489 *s++ = (ToMove == WHITE ? 'w' : 'b');
2490 *s = 0;
2491 }
2492
2493 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2494 // Position::ReadFromCompactStr():
2495 // Sets the position from the provided Null-terminated 33-byte
2496 // compact string.
2497 // The first 32 bytes contain the square valued, 4 bits per value,
2498 // for the square order A1, B1, ...., G8, H8.
2499 // The next byte contains the side to move, 1 for White or 2 for Black.
2500 // The final two bytes contain castling and en passant rights.
2501 // To ensure no bytes within the staring are zero-valued (so it
2502 // can be used as a regular null-terminated string), the value 1
2503 // is added to the color, castling and en passant fields.
2504 errorT
ReadFromCompactStr(const byte * str)2505 Position::ReadFromCompactStr (const byte * str)
2506 {
2507 Clear();
2508 for (uint i=0; i < 32; i++) {
2509 pieceT p = str[i] >> 4;
2510 if (p != EMPTY) {
2511 if (AddPiece (p, i * 2) != OK) {
2512 return ERROR_Corrupt;
2513 }
2514 }
2515 p = str[i] & 15;
2516 if (p != EMPTY) {
2517 if (AddPiece (p, i * 2 + 1) != OK) {
2518 return ERROR_Corrupt;
2519 }
2520 }
2521 }
2522 colorT toMove = str[32] - 1;
2523 if (toMove != WHITE && toMove != BLACK) {
2524 return ERROR_Corrupt;
2525 }
2526 ToMove = toMove;
2527 Castling = str[33] - 1;
2528 EPTarget = str[34] - 1;
2529 return OK;
2530 }
2531
2532 void
PrintCompactStr(char * cboard)2533 Position::PrintCompactStr (char * cboard)
2534 {
2535 for (uint i=0; i < 32; i++) {
2536 uint i2 = i << 1;
2537 cboard[i] = (byte)(Board[i2] << 4) | Board[i2+1];
2538 }
2539 cboard[32] = 1 + ToMove;
2540 cboard[33] = 1 + Castling;
2541
2542 // Check that there really is an enemy pawn that might
2543 // be able to capture to the en passant square. For example,
2544 // if the EP square is c6 but there is no white pawn on
2545 // b5 or d5, then en passant should be ignored.
2546
2547 squareT ep = EPTarget;
2548 if (ToMove == WHITE) {
2549 if (Board[square_Move (ep, DOWN_LEFT)] != WP &&
2550 Board[square_Move (ep, DOWN_RIGHT)] != WP) { ep = NULL_SQUARE; }
2551
2552 } else {
2553 if (Board[square_Move (ep, UP_LEFT)] != BP &&
2554 Board[square_Move (ep, UP_RIGHT)] != BP) { ep = NULL_SQUARE; }
2555
2556 }
2557 cboard[34] = 1 + ep;
2558 cboard[35] = 0;
2559 }
2560
2561 void
PrintCompactStrFlipped(char * cboard)2562 Position::PrintCompactStrFlipped (char * cboard)
2563 {
2564 for (uint i=0; i < 32; i++) {
2565 uint i2 = i << 1;
2566 // Flip 1st rank to 8th, etc:
2567 i2 = ((7 - (i2)/8) * 8 + ((i2) % 8));
2568 cboard[i] = (byte)(PIECE_FLIP[Board[i2]] << 4) |
2569 (byte)(PIECE_FLIP[Board[i2+1]]);
2570 }
2571 cboard[32] = 1 + color_Flip(ToMove);
2572 cboard[33] = 1 + Castling;
2573 cboard[34] = 1 + EPTarget;
2574 cboard[35] = 0;
2575 }
2576
2577 /// Setup the position from a FEN string.
2578 /// Note: the slashes usually found in Fen strings to mark the start
2579 /// of a new row do not need to be present, but if they are, they must
2580 /// appear at the actual start of a new row or the string will be
2581 /// considered corrupt.
2582 ///
2583 /// IMPORTANT: the shortcut of having a two-digit number to represent
2584 /// a number of empty rows (e.g. "/24/" instead of "/8/8/8/") is NOT
2585 /// accepted by this function.
2586 ///
2587 /// It is not considered an error for the halfmove clock or fullmove
2588 /// counter to be invalid, so this routine can also read positions
2589 /// from EPD lines (which only share the first four fields with FEN).
ReadFromFEN(const char * str)2590 errorT Position::ReadFromFEN(const char* str) {
2591 ASSERT (str != NULL);
2592
2593 auto is_space = [](char ch) {
2594 return isspace(static_cast<unsigned char>(ch));
2595 };
2596 auto skip_spaces = [&]() {
2597 while (isspace(*str)) {
2598 str++;
2599 }
2600 };
2601
2602 // pieceFromByte[] converts a character to its piece, e.g. 'k' -> BK.
2603 static pieceT pieceFromByte [256];
2604
2605 // Note the first Call to set up the static arrays only once:
2606 static int firstCall = 1;
2607 if (firstCall) {
2608 firstCall = 0;
2609
2610 // Set up pieceFromByte[]:
2611 for (int i=0; i < 256; i++) { pieceFromByte[i] = EMPTY; }
2612 pieceFromByte [(int) 'K'] = WK; pieceFromByte [(int) 'k'] = BK;
2613 pieceFromByte [(int) 'Q'] = WQ; pieceFromByte [(int) 'q'] = BQ;
2614 pieceFromByte [(int) 'R'] = WR; pieceFromByte [(int) 'r'] = BR;
2615 pieceFromByte [(int) 'B'] = WB; pieceFromByte [(int) 'b'] = BB;
2616 pieceFromByte [(int) 'N'] = WN; pieceFromByte [(int) 'n'] = BN;
2617 pieceFromByte [(int) 'P'] = WP; pieceFromByte [(int) 'p'] = BP;
2618 }
2619
2620 Clear();
2621
2622 // Piece placement
2623 skip_spaces();
2624 for (int row = 7; row >= 0; --row) {
2625 for (int col = 0; col < 8;) {
2626 const auto ch = *str++;
2627 if (ch == '/') {
2628 // A FEN string does not have to contain '/'s but if one
2629 // appears anywhere except the start of a row, it is an error:
2630 if (col != 0)
2631 return ERROR_InvalidFEN;
2632
2633 } else if (ch > '0' && ch < '9') {
2634 col += (ch - '0');
2635 if (col > 8)
2636 return ERROR_InvalidFEN;
2637
2638 } else {
2639 auto piece = pieceFromByte[static_cast<unsigned char>(ch)];
2640 if (piece == EMPTY)
2641 return ERROR_InvalidFEN;
2642
2643 if (AddPiece(piece, static_cast<squareT>(row * 8 + col)) != OK)
2644 return ERROR_InvalidFEN;
2645
2646 col++;
2647 }
2648 }
2649 }
2650 if (Material[WK] != 1 || Material[BK] != 1) { return ERROR_InvalidFEN; }
2651
2652 // Now the side to move:
2653 skip_spaces();
2654 switch (*str++) {
2655 case 'w':
2656 SetToMove (WHITE);
2657 break;
2658 case 'b':
2659 SetToMove (BLACK);
2660 break;
2661 default:
2662 return ERROR_InvalidFEN;
2663 }
2664
2665 if (! IsLegal()) { return ERROR_InvalidFEN; }
2666
2667 // Now the castling flags:
2668 skip_spaces();
2669 if (*str == '-') {
2670 str++; // do nothing
2671 } else if (*str == 0) {
2672 // The FEN has no castling field, so just guess that
2673 // castling is possible whenever a king and rook are
2674 // still on their starting squares:
2675 if (Board[E1] == WK) {
2676 if (Board[A1] == WR) { SetCastling (WHITE, QSIDE, true); }
2677 if (Board[H1] == WR) { SetCastling (WHITE, KSIDE, true); }
2678 }
2679 if (Board[E8] == BK) {
2680 if (Board[A8] == BR) { SetCastling (BLACK, QSIDE, true); }
2681 if (Board[H8] == BR) { SetCastling (BLACK, KSIDE, true); }
2682 }
2683 } else {
2684 while (!is_space(*str) && *str != 0) {
2685 switch (*str++) {
2686 case 'Q':
2687 SetCastling (WHITE, QSIDE, true);
2688 break;
2689 case 'q':
2690 SetCastling (BLACK, QSIDE, true);
2691 break;
2692 case 'K':
2693 SetCastling (WHITE, KSIDE, true);
2694 break;
2695 case 'k':
2696 SetCastling (BLACK, KSIDE, true);
2697 break;
2698 default:
2699 return ERROR_InvalidFEN;
2700 }
2701 }
2702 }
2703
2704 // Now the EP target:
2705 skip_spaces();
2706 if (*str == '-') {
2707 EPTarget = NULL_SQUARE;
2708 str++; // No EP target
2709 } else if (*str) {
2710 char fylec = *str++;
2711 if (fylec < 'a' || fylec > 'h') {
2712 return ERROR_InvalidFEN;
2713 }
2714 char rankc = *str++;
2715 if (rankc != '3' && rankc != '6') {
2716 return ERROR_InvalidFEN;
2717 }
2718 EPTarget = square_Make(fyle_FromChar(fylec), rank_FromChar(rankc));
2719 }
2720
2721 // Now the capture/pawn halfmove clock:
2722 skip_spaces();
2723 if (*str) {
2724 char* end;
2725 HalfMoveClock = (ushort)std::max(0l, strtol(str, &end, 10));
2726 str = end;
2727 }
2728
2729 // Finally, the fullmove counter:
2730 skip_spaces();
2731 if (*str) {
2732 int i = atoi(str);
2733 if (i >= 1) {
2734 PlyCounter = (i - 1) * 2;
2735 }
2736 }
2737 if (ToMove == BLACK) { PlyCounter++; }
2738 return OK;
2739 }
2740
2741
2742 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2743 // Position::PrintFEN():
2744 // Print the FEN representation of the position.
2745 // If flags == FEN_COMPACT, only the board and side-to-move fields
2746 // are printed, in compact form (no slashes between rows).
2747 // If flags == FEN_BOARD, only the board and side-to-move fields
2748 // are printed.
2749 // If flags == FEN_CASTLING_EP, the castling and en passant fields
2750 // are also printed.
2751 // If flags == FEN_ALL_FIELDS, all fields are printed including
2752 // the halfmove clock and ply counter.
2753 //
PrintFEN(char * str,uint flags) const2754 void Position::PrintFEN(char* str, uint flags) const {
2755 ASSERT (str != NULL);
2756 uint emptyRun, iRank, iFyle;
2757 for (iRank = 0; iRank < 8; iRank++) {
2758 const pieceT* pBoard = &(Board[(7 - iRank) * 8]);
2759 emptyRun = 0;
2760 if (iRank > 0 && flags > FEN_COMPACT) { *str++ = '/'; }
2761 for (iFyle = 0; iFyle < 8; iFyle++, pBoard++) {
2762 if (*pBoard != EMPTY) {
2763 if (emptyRun) { *str++ = (byte) emptyRun + '0'; }
2764 emptyRun = 0;
2765 *str++ = PIECE_CHAR[*pBoard];
2766 } else {
2767 emptyRun++;
2768 }
2769 }
2770 if (emptyRun) { *str++ = (byte) emptyRun + '0'; }
2771 }
2772
2773 if (flags > FEN_COMPACT) { *str++ = ' '; }
2774 *str++ = (ToMove == WHITE ? 'w' : 'b');
2775 *str = 0;
2776
2777 if (flags >= FEN_CASTLING_EP) {
2778 // Add the castling flags and EP flag as well:
2779 *str++ = ' ';
2780 if (Castling == 0) {
2781 *str++ = '-';
2782 } else {
2783 if (GetCastling (WHITE, KSIDE)) { *str++ = 'K'; }
2784 if (GetCastling (WHITE, QSIDE)) { *str++ = 'Q'; }
2785 if (GetCastling (BLACK, KSIDE)) { *str++ = 'k'; }
2786 if (GetCastling (BLACK, QSIDE)) { *str++ = 'q'; }
2787 }
2788 *str++ = ' ';
2789
2790 // Now the EP target square:
2791 if (EPTarget == NULL_SQUARE) {
2792 *str++ = '-';
2793 } else {
2794 *str++ = square_FyleChar (EPTarget);
2795 *str++ = square_RankChar (EPTarget);
2796 }
2797 *str = 0;
2798
2799 if (flags >= FEN_ALL_FIELDS) {
2800 // Also print the Halfmove and ply counters:
2801 *str++ = ' ';
2802 sprintf (str, "%d %d", HalfMoveClock, (PlyCounter / 2) + 1);
2803 }
2804 }
2805 return;
2806 }
2807
2808 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2809 // Position::DumpHtmlBoard():
2810 // Prints the board in a format for use in HTML documents.
2811 // Assumes that the HTML document will be in a directory that
2812 // has a subdirectory bitmapsDir with files "bwr.gif", etc.
2813 // The numeric arguments are the pixel width and height for each
2814 // square -- if zero, then the bitmaps are not scaled.
2815
2816 // The following values define the available HTML styles.
2817 // Style 0 has 40x40 non-transparent images in the "bitmaps" directory.
2818 // Style 1 has 36x35 non-transparent images in the "bitmaps2" directory.
2819
2820 struct htmlStyleT {
2821 const char * dir; // directory containing images.
2822 uint width; // width value specified in <img> tag.
2823 uint height; // height value specified in <img> tag.
2824 bool transparent; // True if the style uses transparent images,
2825 // with square colors set by "bgcolor".
2826 };
2827
2828 void
DumpHtmlBoard(DString * dstr,uint style,const char * dir,bool flip)2829 Position::DumpHtmlBoard (DString * dstr, uint style, const char * dir, bool flip)
2830 {
2831 const uint HTML_DIAG_STYLES = 2;
2832 htmlStyleT hs [HTML_DIAG_STYLES];
2833 hs[0].dir = "bitmaps"; hs[0].width = 40; hs[0].height = 40;
2834 hs[1].dir = "bitmaps2"; hs[1].width = 36; hs[1].height = 35;
2835 if (style >= HTML_DIAG_STYLES) { style = 0; }
2836
2837 uint width = hs[style].width;
2838 uint height = hs[style].height;
2839 uint iRank, iFyle;
2840 pieceT * pBoard;
2841 if (dir == NULL) { dir = hs[style].dir; }
2842
2843 dstr->Append ("<br><br><center>\n");
2844 dstr->Append ("<table Border=1 CellSpacing=0 CellPadding=0>\n");
2845 for (iRank = 0; iRank < 8; iRank++) {
2846 dstr->Append ("<tr>\n");
2847 pBoard = &(Board[(7 - iRank) * 8]);
2848 for (iFyle = 0; iFyle < 8; iFyle++, pBoard++) {
2849 pieceT piece = *pBoard;
2850 if (flip) { piece = Board[iRank * 8 + (7 - iFyle)]; }
2851 dstr->Append (" <td><img border=0 ");
2852 if (width > 0) {
2853 char temp[40];
2854 sprintf (temp, "width=%u ", width);
2855 dstr->Append (temp);
2856 }
2857 if (height > 0) {
2858 char temp[40];
2859 sprintf (temp, "height=%u ", height);
2860 dstr->Append (temp);
2861 }
2862 dstr->Append ("src=\"");
2863 dstr->Append (dir);
2864 dstr->AddChar ('/');
2865 bool lightSq = ((iRank % 2) == (iFyle % 2));
2866 if (lightSq) {
2867 dstr->AddChar ('w');
2868 } else {
2869 dstr->AddChar ('b');
2870 }
2871 if (piece == EMPTY) {
2872 dstr->Append ("sq.gif");
2873 } else {
2874 colorT c = piece_Color(piece);
2875 dstr->AddChar (c == WHITE ? 'w' : 'b');
2876 dstr->AddChar (tolower (PIECE_CHAR[piece]));
2877 dstr->Append (".gif");
2878 }
2879 dstr->Append ("\" alt=\"");
2880 if (piece == EMPTY) {
2881 if (! lightSq) { dstr->Append ("::"); }
2882 } else {
2883 colorT c = piece_Color(piece);
2884 dstr->AddChar (c == WHITE ? 'W' : 'B');
2885 dstr->AddChar (toupper (PIECE_CHAR[piece]));
2886 }
2887 dstr->Append ("\"></td>\n");
2888 }
2889 dstr->Append ("</tr>\n");
2890 }
2891 dstr->Append ("</table>\n");
2892 //if (ToMove == WHITE) {
2893 // dstr->Append ("<br><b>White to move.</b>\n");
2894 //} else {
2895 // dstr->Append ("<br><b>Black to move.</b>\n");
2896 //}
2897 dstr->Append("</center><br>");
2898 }
2899
2900 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2901 // Position::DumpLatexBoard():
2902 // Prints the board in a format used by a chess package that is
2903 // available for the LaTeX or TeX typesetting language.
2904 void
DumpLatexBoard(DString * dstr,bool flip)2905 Position::DumpLatexBoard (DString * dstr, bool flip)
2906 {
2907 uint iRank, iFyle;
2908 pieceT * pBoard;
2909 dstr->Append ("\\board{");
2910 for (iRank = 0; iRank < 8; iRank++) {
2911 pBoard = &(Board[(7 - iRank) * 8]);
2912 for (iFyle = 0; iFyle < 8; iFyle++, pBoard++) {
2913 pieceT piece = *pBoard;
2914 if (flip) { piece = Board[iRank * 8 + (7 - iFyle)]; }
2915 if (piece != EMPTY) {
2916 dstr->AddChar (PIECE_CHAR[piece]);
2917 } else { // put a space or a '*':
2918 dstr->AddChar (((iRank % 2) == (iFyle % 2)) ? ' ' : '*');
2919 }
2920 }
2921 if (iRank < 7) {
2922 dstr->Append ("}\n {");
2923 } else { dstr->AddChar ('}'); }
2924 }
2925 }
2926
2927 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2928 // Position::Compare():
2929 // Compare another position with this one.
2930 //
2931 sint
Compare(Position * p)2932 Position::Compare (Position * p)
2933 {
2934 int i = 32;
2935 byte *p1, *p2;
2936 p1 = Board;
2937 p2 = p->Board;
2938 while (i && *p1 == *p2) {
2939 i--; p1++; p2++;
2940 }
2941 if (p1 < p2) { return -1; }
2942 if (p1 > p2) { return 1; }
2943 return (ToMove - p->GetToMove());
2944 }
2945
2946 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2947 // Position::Random
2948 // Given a string such as "KRPKR" or "KRP-kr", sets up a
2949 // random position with that material configuration.
2950 inline squareT
randomSquare(void)2951 randomSquare (void) { return rand() % 64; }
2952
2953 inline squareT
randomPawnSquare(void)2954 randomPawnSquare (void) { return (rand() % 48) + A2; }
2955
2956 errorT
Random(const char * material)2957 Position::Random (const char * material)
2958 {
2959 pieceT pieces [32]; // List of pieces excluding kings
2960 uint nPieces[2] = {0, 0}; // Number of pieces per side excluding kings.
2961 uint total = 0; // Total number of pieces excluding kings.
2962
2963 colorT side = WHITE;
2964
2965 // The material string must start with a king:
2966 if (toupper(*material) != 'K') { return ERROR_Corrupt; }
2967 material++;
2968
2969 // Read the material string:
2970 while (1) {
2971 char ch = toupper(*material);
2972 if (ch == 0) { break; }
2973 switch (ch) {
2974 case 'K':
2975 if (side == BLACK) { return ERROR_Corrupt; } // Seen third king!
2976 side = BLACK;
2977 break;
2978 case 'Q': case 'R': case 'B': case 'N': case 'P':
2979 if (nPieces[side] >= 15) { return ERROR_Corrupt; }
2980 nPieces[side]++;
2981 if (ch == 'P') {
2982 pieces[total] = piece_Make (side, PAWN);
2983 } else {
2984 pieces[total] = piece_Make (side, piece_FromChar(ch));
2985 }
2986 total++;
2987 break;
2988 case ' ': case '-': case '.': case ',': case ':':
2989 // Ignore spaces, commas, etc:
2990 break;
2991 default:
2992 return ERROR_Corrupt;
2993 }
2994 material++;
2995 }
2996 if (side != BLACK) { return ERROR_Corrupt; } // Never saw Black king!
2997
2998 // Generate two non-adjacent king squares:
2999 squareT wk = randomSquare();
3000 squareT bk = randomSquare();
3001 while (wk == bk || square_Adjacent (wk, bk)) { bk = randomSquare(); }
3002
3003 // Now add all other pieces to empty squares, looping until a legal
3004 // position is found:
3005 while (1) {
3006 Clear();
3007 ToMove = (rand() % 2) ? WHITE : BLACK;
3008 AddPiece (WK, wk);
3009 AddPiece (BK, bk);
3010
3011 for (uint i=0; i < total; i++) {
3012 squareT sq;
3013 pieceT p = pieces[i];
3014 bool isPawn = (piece_Type(p) == PAWN);
3015 while (1) {
3016 sq = isPawn ? randomPawnSquare() : randomSquare();
3017 if (Board[sq] == EMPTY) { break; }
3018 }
3019 // Add this piece on the random empty square:
3020 AddPiece (p, sq);
3021 }
3022 // Generated a random position with kings not adjacent and
3023 // every piece on its own square. We can stop at this
3024 // attempt if the enemy king is not in check:
3025 squareT enemyKing = (ToMove == WHITE) ? bk : wk;
3026 if (CalcAttacks (ToMove, enemyKing, NULL) == 0) { break; }
3027 }
3028 return OK;
3029 }
3030
3031 //////////////////////////////////////////////////////////////////////
3032 // EOF: position.cpp
3033 //////////////////////////////////////////////////////////////////////
3034