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