1 /* board.cpp
2 
3    GNU Chess engine
4 
5    Copyright (C) 2001-2011 Free Software Foundation, Inc.
6 
7    This program is free software: you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation, either version 3 of the License, or
10    (at your option) any later version.
11 
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16 
17    You should have received a copy of the GNU General Public License
18    along with this program.  If not, see <http://www.gnu.org/licenses/>.
19 */
20 
21 
22 // board.cpp
23 
24 // includes
25 
26 #include "attack.h"
27 #include "board.h"
28 #include "colour.h"
29 #include "fen.h"
30 #include "hash.h"
31 #include "list.h"
32 #include "move.h"
33 #include "move_do.h"
34 #include "move_evasion.h"
35 #include "move_gen.h"
36 #include "move_legal.h"
37 #include "pawn.h" // TODO: bit.h
38 #include "piece.h"
39 #include "pst.h"
40 #include "util.h"
41 #include "value.h"
42 
43 namespace engine {
44 
45 // constants
46 
47 static const bool UseSlowDebug = false;
48 
49 // functions
50 
51 // board_is_ok()
52 
board_is_ok(const board_t * board)53 bool board_is_ok(const board_t * board) {
54 
55    int sq, piece, colour;
56    int size, pos;
57 
58    if (board == NULL) return false;
59 
60    // optional heavy DEBUG mode
61 
62    if (!UseSlowDebug) return true;
63 
64    // squares
65 
66    for (sq = 0; sq < SquareNb; sq++) {
67 
68       piece = board->square[sq];
69       pos = board->pos[sq];
70 
71       if (SQUARE_IS_OK(sq)) {
72 
73          // inside square
74 
75          if (piece == Empty) {
76 
77             if (pos != -1) return false;
78 
79          } else {
80 
81             if (!piece_is_ok(piece)) return false;
82 
83             if (!PIECE_IS_PAWN(piece)) {
84 
85                colour = PIECE_COLOUR(piece);
86                if (pos < 0 || pos >= board->piece_size[colour]) return false;
87                if (board->piece[colour][pos] != sq) return false;
88 
89             } else { // pawn
90 
91                if (SQUARE_IS_PROMOTE(sq)) return false;
92 
93                colour = PIECE_COLOUR(piece);
94                if (pos < 0 || pos >= board->pawn_size[colour]) return false;
95                if (board->pawn[colour][pos] != sq) return false;
96             }
97          }
98 
99       } else {
100 
101          // edge square
102 
103          if (piece != Edge) return false;
104          if (pos != -1) return false;
105       }
106    }
107 
108    // piece lists
109 
110    for (colour = 0; colour < ColourNb; colour++) {
111 
112       // piece list
113 
114       size = board->piece_size[colour];
115       if (size < 1 || size > 16) return false;
116 
117       for (pos = 0; pos < size; pos++) {
118 
119          sq = board->piece[colour][pos];
120          if (!SQUARE_IS_OK(sq)) return false;
121 
122          if (board->pos[sq] != pos) return false;
123 
124          piece = board->square[sq];
125          if (!COLOUR_IS(piece,colour)) return false;
126          if (pos == 0 && !PIECE_IS_KING(piece)) return false;
127          if (pos != 0 && PIECE_IS_KING(piece)) return false;
128 
129          if (pos != 0 && PIECE_ORDER(piece) > PIECE_ORDER(board->square[board->piece[colour][pos-1]])) {
130             return false;
131          }
132       }
133 
134       sq = board->piece[colour][size];
135       if (sq != SquareNone) return false;
136 
137       // pawn list
138 
139       size = board->pawn_size[colour];
140       if (size < 0 || size > 8) return false;
141 
142       for (pos = 0; pos < size; pos++) {
143 
144          sq = board->pawn[colour][pos];
145          if (!SQUARE_IS_OK(sq)) return false;
146          if (SQUARE_IS_PROMOTE(sq)) return false;
147 
148          if (board->pos[sq] != pos) return false;
149 
150          piece = board->square[sq];
151          if (!COLOUR_IS(piece,colour)) return false;
152          if (!PIECE_IS_PAWN(piece)) return false;
153       }
154 
155       sq = board->pawn[colour][size];
156       if (sq != SquareNone) return false;
157 
158       // piece total
159 
160       if (board->piece_size[colour] + board->pawn_size[colour] > 16) return false;
161    }
162 
163    // material
164 
165    if (board->piece_nb != board->piece_size[White] + board->pawn_size[White]
166                         + board->piece_size[Black] + board->pawn_size[Black]) {
167       return false;
168    }
169 
170    if (board->number[WhitePawn12] != board->pawn_size[White]) return false;
171    if (board->number[BlackPawn12] != board->pawn_size[Black]) return false;
172    if (board->number[WhiteKing12] != 1) return false;
173    if (board->number[BlackKing12] != 1) return false;
174 
175    // misc
176 
177    if (!COLOUR_IS_OK(board->turn)) return false;
178 
179    if (board->ply_nb < 0) return false;
180    if (board->sp < board->ply_nb) return false;
181 
182    if (board->cap_sq != SquareNone && !SQUARE_IS_OK(board->cap_sq)) return false;
183 
184    if (board->opening != board_opening(board)) return false;
185    if (board->endgame != board_endgame(board)) return false;
186    if (board->key != hash_key(board)) return false;
187    if (board->pawn_key != hash_pawn_key(board)) return false;
188    if (board->material_key != hash_material_key(board)) return false;
189 
190    return true;
191 }
192 
193 // board_clear()
194 
board_clear(board_t * board)195 void board_clear(board_t * board) {
196 
197    int sq, sq_64;
198 
199    ASSERT(board!=NULL);
200 
201    // edge squares
202 
203    for (sq = 0; sq < SquareNb; sq++) {
204       board->square[sq] = Edge;
205    }
206 
207    // empty squares
208 
209    for (sq_64 = 0; sq_64 < 64; sq_64++) {
210       sq = SQUARE_FROM_64(sq_64);
211       board->square[sq] = Empty;
212    }
213 
214    // misc
215 
216    board->turn = ColourNone;
217    board->flags = FlagsNone;
218    board->ep_square = SquareNone;
219    board->ply_nb = 0;
220 }
221 
222 // board_copy()
223 
board_copy(board_t * dst,const board_t * src)224 void board_copy(board_t * dst, const board_t * src) {
225 
226    ASSERT(dst!=NULL);
227    ASSERT(board_is_ok(src));
228 
229    *dst = *src;
230 }
231 
232 // board_init_list()
233 
board_init_list(board_t * board)234 void board_init_list(board_t * board) {
235 
236    int sq_64, sq, piece;
237    int colour, pos;
238    int i, size;
239    int square;
240    int order;
241    int file;
242 
243    ASSERT(board!=NULL);
244 
245    // init
246 
247    for (sq = 0; sq < SquareNb; sq++) {
248       board->pos[sq] = -1;
249    }
250 
251    board->piece_nb = 0;
252    for (piece = 0; piece < 12; piece++) board->number[piece] = 0;
253 
254    // piece lists
255 
256    for (colour = 0; colour < ColourNb; colour++) {
257 
258       // piece list
259 
260       pos = 0;
261 
262       for (sq_64 = 0; sq_64 < 64; sq_64++) {
263 
264          sq = SQUARE_FROM_64(sq_64);
265          piece = board->square[sq];
266          if (piece != Empty && !piece_is_ok(piece)) my_fatal("board_init_list(): illegal position\n");
267 
268          if (COLOUR_IS(piece,colour) && !PIECE_IS_PAWN(piece)) {
269 
270             if (pos >= 16) my_fatal("board_init_list(): illegal position\n");
271             ASSERT(pos>=0&&pos<16);
272 
273             board->pos[sq] = pos;
274             board->piece[colour][pos] = sq;
275             pos++;
276 
277             board->piece_nb++;
278             board->number[PIECE_TO_12(piece)]++;
279          }
280       }
281 
282       if (board->number[COLOUR_IS_WHITE(colour)?WhiteKing12:BlackKing12] != 1) my_fatal("board_init_list(): illegal position\n");
283 
284       ASSERT(pos>=1&&pos<=16);
285       board->piece[colour][pos] = SquareNone;
286       board->piece_size[colour] = pos;
287 
288       // MV sort
289 
290       size = board->piece_size[colour];
291 
292       for (i = 1; i < size; i++) {
293 
294          square = board->piece[colour][i];
295          piece = board->square[square];
296          order = PIECE_ORDER(piece);
297 
298          for (pos = i; pos > 0 && order > PIECE_ORDER(board->square[(sq=board->piece[colour][pos-1])]); pos--) {
299             ASSERT(pos>0&&pos<size);
300             board->piece[colour][pos] = sq;
301             ASSERT(board->pos[sq]==pos-1);
302             board->pos[sq] = pos;
303          }
304 
305          ASSERT(pos>=0&&pos<size);
306          board->piece[colour][pos] = square;
307          ASSERT(board->pos[square]==i);
308          board->pos[square] = pos;
309       }
310 
311       // debug
312 
313       if (DEBUG) {
314 
315          for (i = 0; i < board->piece_size[colour]; i++) {
316 
317             sq = board->piece[colour][i];
318             ASSERT(board->pos[sq]==i);
319 
320             if (i == 0) { // king
321                ASSERT(PIECE_IS_KING(board->square[sq]));
322             } else {
323                ASSERT(!PIECE_IS_KING(board->square[sq]));
324                ASSERT(PIECE_ORDER(board->square[board->piece[colour][i]])<=PIECE_ORDER(board->square[board->piece[colour][i-1]]));
325             }
326          }
327       }
328 
329       // pawn list
330 
331       for (file = 0; file < FileNb; file++) {
332          board->pawn_file[colour][file] = 0;
333       }
334 
335       pos = 0;
336 
337       for (sq_64 = 0; sq_64 < 64; sq_64++) {
338 
339          sq = SQUARE_FROM_64(sq_64);
340          piece = board->square[sq];
341 
342          if (COLOUR_IS(piece,colour) && PIECE_IS_PAWN(piece)) {
343 
344             if (pos >= 8 || SQUARE_IS_PROMOTE(sq)) my_fatal("board_init_list(): illegal position\n");
345             ASSERT(pos>=0&&pos<8);
346 
347             board->pos[sq] = pos;
348             board->pawn[colour][pos] = sq;
349             pos++;
350 
351             board->piece_nb++;
352             board->number[PIECE_TO_12(piece)]++;
353             board->pawn_file[colour][SQUARE_FILE(sq)] |= BIT(PAWN_RANK(sq,colour));
354          }
355       }
356 
357       ASSERT(pos>=0&&pos<=8);
358       board->pawn[colour][pos] = SquareNone;
359       board->pawn_size[colour] = pos;
360 
361       if (board->piece_size[colour] + board->pawn_size[colour] > 16) my_fatal("board_init_list(): illegal position\n");
362    }
363 
364    // last square
365 
366    board->cap_sq = SquareNone;
367 
368    // PST
369 
370    board->opening = board_opening(board);
371    board->endgame = board_endgame(board);
372 
373    // hash key
374 
375    for (i = 0; i < board->ply_nb; i++) board->stack[i] = 0; // HACK
376    board->sp = board->ply_nb;
377 
378    board->key = hash_key(board);
379    board->pawn_key = hash_pawn_key(board);
380    board->material_key = hash_material_key(board);
381 
382    // legality
383 
384    if (!board_is_legal(board)) my_fatal("board_init_list(): illegal position\n");
385 
386    // debug
387 
388    ASSERT(board_is_ok(board));
389 }
390 
391 // board_is_legal()
392 
board_is_legal(const board_t * board)393 bool board_is_legal(const board_t * board) {
394 
395    ASSERT(board!=NULL);
396 
397    return !IS_IN_CHECK(board,COLOUR_OPP(board->turn));
398 }
399 
400 // board_is_check()
401 
board_is_check(const board_t * board)402 bool board_is_check(const board_t * board) {
403 
404    ASSERT(board!=NULL);
405 
406    return IS_IN_CHECK(board,board->turn);
407 }
408 
409 // board_is_mate()
410 
board_is_mate(const board_t * board)411 bool board_is_mate(const board_t * board) {
412 
413    attack_t attack[1];
414 
415    ASSERT(board!=NULL);
416 
417    attack_set(attack,board);
418 
419    if (!ATTACK_IN_CHECK(attack)) return false; // not in check => not mate
420    if (legal_evasion_exist(board,attack)) return false; // legal move => not mate
421 
422    return true; // in check and no legal move => mate
423 }
424 
425 // board_is_stalemate()
426 
board_is_stalemate(board_t * board)427 bool board_is_stalemate(board_t * board) {
428 
429    list_t list[1];
430    int i, move;
431 
432    ASSERT(board!=NULL);
433 
434    // init
435 
436    if (IS_IN_CHECK(board,board->turn)) return false; // in check => not stalemate
437 
438    // move loop
439 
440    gen_moves(list,board);
441 
442    for (i = 0; i < LIST_SIZE(list); i++) {
443       move = LIST_MOVE(list,i);
444       if (pseudo_is_legal(move,board)) return false; // legal move => not stalemate
445    }
446 
447    return true; // in check and no legal move => mate
448 }
449 
450 // board_is_repetition()
451 
board_is_repetition(const board_t * board)452 bool board_is_repetition(const board_t * board) {
453 
454    int i;
455 
456    ASSERT(board!=NULL);
457 
458    // 50-move rule
459 
460    if (board->ply_nb >= 100) { // potential draw
461 
462       if (board->ply_nb > 100) return true;
463 
464       ASSERT(board->ply_nb==100);
465       return !board_is_mate(board);
466    }
467 
468    // position repetition
469 
470    ASSERT(board->sp>=board->ply_nb);
471 
472    for (i = 4; i <= board->ply_nb; i += 2) {
473       if (board->stack[board->sp-i] == board->key) return true;
474    }
475 
476    return false;
477 }
478 
479 // board_opening()
480 
board_opening(const board_t * board)481 int board_opening(const board_t * board) {
482 
483    int opening;
484    int colour;
485    const sq_t * ptr;
486    int sq, piece;
487 
488    ASSERT(board!=NULL);
489 
490    opening = 0;
491 
492    for (colour = 0; colour < ColourNb; colour++) {
493 
494       for (ptr = &board->piece[colour][0]; (sq=*ptr) != SquareNone; ptr++) {
495          piece = board->square[sq];
496          opening += PST(PIECE_TO_12(piece),SQUARE_TO_64(sq),Opening);
497       }
498 
499       for (ptr = &board->pawn[colour][0]; (sq=*ptr) != SquareNone; ptr++) {
500          piece = board->square[sq];
501          opening += PST(PIECE_TO_12(piece),SQUARE_TO_64(sq),Opening);
502       }
503    }
504 
505    return opening;
506 }
507 
508 // board_endgame()
509 
board_endgame(const board_t * board)510 int board_endgame(const board_t * board) {
511 
512    int endgame;
513    int colour;
514    const sq_t * ptr;
515    int sq, piece;
516 
517    ASSERT(board!=NULL);
518 
519    endgame = 0;
520 
521    for (colour = 0; colour < ColourNb; colour++) {
522 
523       for (ptr = &board->piece[colour][0]; (sq=*ptr) != SquareNone; ptr++) {
524          piece = board->square[sq];
525          endgame += PST(PIECE_TO_12(piece),SQUARE_TO_64(sq),Endgame);
526       }
527 
528       for (ptr = &board->pawn[colour][0]; (sq=*ptr) != SquareNone; ptr++) {
529          piece = board->square[sq];
530          endgame += PST(PIECE_TO_12(piece),SQUARE_TO_64(sq),Endgame);
531       }
532    }
533 
534    return endgame;
535 }
536 
537 }  // namespace engine
538 
539 // end of board.cpp
540 
541