17 #include "evaluator.h"
21 unsigned total_nodes, min_depth;
24 struct killer_move killer_moves[64][2]; // two for each depth
25 unsigned killer_currdepth; // easier to have as a global :-/
26 unsigned max_depth, max_selective_depth; // my oh my
29 int find_best_move(const struct position * const pos, unsigned long long phash, unsigned *ret_from, unsigned *ret_to, unsigned depth, unsigned seldepth, int alpha, int beta, bool search_castling);
31 void uciprintf(const char *format, ...)
37 vsnprintf(buf, 4096, format, ap);
48 int estimate_score(struct position *pos, unsigned depth)
50 unsigned long long phash, bucket;
51 struct hash_entry *he;
53 // hack -- looking up the hash table is too expensive just to get
54 // a good estimate, so we don't do it except at a certain level
56 bool found_any = false;
57 unsigned best_depth = 10000;
60 // see if we have something in the hash -- we don't really care at what
61 // depth, _anything_ is better than the static evaluation, really
62 phash = hash_position(pos);
63 bucket = phash % HASH_BUCKETS;
64 he = transposition_table[bucket];
67 if (he->phash == phash)
70 if (he->phash == phash && he->depth < best_depth) {
72 best_depth = he->depth;
73 best_depth_score = he->score;
79 return best_depth_score;
82 return (pos->white_to_move) ? evaluate(pos) : -evaluate(pos);
85 #define ADD_MOVE(newsquare) \
87 assert(IS_WHITE(pos->board[square]) == pos->white_to_move); \
88 moves[num_moves].pos = *pos; \
89 moves[num_moves].from = square; \
90 moves[num_moves].to = newsquare; \
91 if (pos->white_to_move) \
92 real_make_move(&moves[num_moves].pos, square, newsquare, &moves[num_moves].pos.white_pieces[i], moves[num_moves].pos.black_pieces); \
94 real_make_move(&moves[num_moves].pos, square, newsquare, &moves[num_moves].pos.black_pieces[i], moves[num_moves].pos.white_pieces); \
95 moves[num_moves].estimate_score = -estimate_score(&moves[num_moves].pos, depth); \
96 indexes[num_moves] = num_moves; \
97 heapify(moves, indexes, num_moves); \
101 struct binheap_node {
104 unsigned char from, to;
107 bool bh_greaterthan(struct binheap_node *moves, unsigned *indexes, unsigned i1, unsigned i2)
109 bool killer1 = (killer_moves[killer_currdepth][0].from == moves[indexes[i1]].from &&
110 killer_moves[killer_currdepth][0].to == moves[indexes[i1]].to) ||
111 (killer_moves[killer_currdepth][1].from == moves[indexes[i1]].from &&
112 killer_moves[killer_currdepth][1].to == moves[indexes[i1]].to);
113 bool killer2 = (killer_moves[killer_currdepth][0].from == moves[indexes[i2]].from &&
114 killer_moves[killer_currdepth][0].to == moves[indexes[i2]].to) ||
115 (killer_moves[killer_currdepth][1].from == moves[indexes[i2]].from &&
116 killer_moves[killer_currdepth][1].to == moves[indexes[i2]].to);
118 if (killer1 && !killer2)
120 if (killer2 && !killer1)
123 return (moves[indexes[i1]].estimate_score > moves[indexes[i2]].estimate_score);
126 void heapify(struct binheap_node *moves, unsigned *indexes, unsigned i)
134 if (bh_greaterthan(moves, indexes, i, parent)) {
135 unsigned tmp = indexes[i];
136 indexes[i] = indexes[parent];
137 indexes[parent] = tmp;
139 heapify(moves, indexes, parent);
143 void downheapify(struct binheap_node *moves, unsigned *indexes, unsigned i, unsigned num_elem)
145 unsigned child1 = 2 * i + 1;
146 unsigned child2 = 2 * i + 2;
147 unsigned compare_ind;
150 if (child1 >= num_elem)
153 if (child2 >= num_elem) {
155 compare_ind = child1;
157 // two children -- find the largest one
158 if (bh_greaterthan(moves, indexes, child1, child2)) {
159 compare_ind = child1;
161 compare_ind = child2;
165 // see if we should swap
166 if (bh_greaterthan(moves, indexes, compare_ind, i)) {
167 unsigned tmp = indexes[i];
168 indexes[i] = indexes[compare_ind];
169 indexes[compare_ind] = tmp;
171 downheapify(moves, indexes, compare_ind, num_elem);
175 // generate all possible moves, stick them in a binary heap based on estimated score, and then try
176 // them in the estimated order
177 int find_best_move(const struct position * const pos, unsigned long long phash, unsigned *ret_from, unsigned *ret_to, unsigned depth, unsigned seldepth, int alpha, int beta, bool search_castling)
180 const struct piece * const ptr = (pos->white_to_move) ? pos->white_pieces : pos->black_pieces;
182 unsigned best_from = 21, best_to = 21; // a1-a1 (easy to pick out visually)
184 struct binheap_node moves[128]; // should be plenty?
185 unsigned indexes[128]; // much cheaper to move around
186 unsigned num_moves = 0;
192 if (depth + seldepth < min_depth)
193 min_depth = depth + seldepth;
195 // see if we can find this position in our hash tables
196 if (lookup_hash(pos, phash, depth, seldepth, ret_from, ret_to, &score)) {
200 killer_currdepth = depth + seldepth;
202 for (i = 0; i < 16; ++i) {
203 unsigned piece, type, square;
205 type = ptr[i].type; // without color
206 if (type == PIECE_EMPTY)
209 square = ptr[i].square;
210 piece = pos->board[square]; // with color
212 if (type == PIECE_PAWN) {
213 int pawn_step = IS_WHITE(piece) ? 10 : -10;
215 // could it move forwards one step?
216 if (pos->board[ptr[i].square + pawn_step] == PIECE_EMPTY) {
217 ADD_MOVE(square + pawn_step);
219 // so that's OK, what about two?
220 if (pos->board[square + pawn_step * 2] == PIECE_EMPTY &&
221 ((IS_WHITE(piece) && NUM_TO_RANK(square) == 1) ||
222 (IS_BLACK(piece) && NUM_TO_RANK(square) == 6))) {
223 ADD_MOVE(square + pawn_step * 2);
227 // could it capture left?
228 if ((pos->board[square + pawn_step - 1] == PIECE_EMPTY && (square + pawn_step - 1 == pos->ep_square)) ||
229 (pos->board[square + pawn_step - 1] != PIECE_EMPTY && NUM_TO_FILE(square) != 0 && OPPOSITE_COLOR(piece, pos->board[square + pawn_step - 1]))) {
230 ADD_MOVE(square + pawn_step - 1);
233 // could it capture right?
234 if ((pos->board[square + pawn_step + 1] == PIECE_EMPTY && (square + pawn_step + 1 == pos->ep_square)) ||
235 (pos->board[square + pawn_step + 1] != PIECE_EMPTY && NUM_TO_FILE(square) != 7 && OPPOSITE_COLOR(piece, pos->board[square + pawn_step + 1]))) {
236 ADD_MOVE(square + pawn_step + 1);
242 if (type == PIECE_KNIGHT) {
243 // these are all the possible knight moves
244 if (CAN_GOTO(piece, pos->board[square + 12]))
245 ADD_MOVE(square + 12);
246 if (CAN_GOTO(piece, pos->board[square - 12]))
247 ADD_MOVE(square - 12);
248 if (CAN_GOTO(piece, pos->board[square - 21]))
249 ADD_MOVE(square - 21);
250 if (CAN_GOTO(piece, pos->board[square + 21]))
251 ADD_MOVE(square + 21);
252 if (CAN_GOTO(piece, pos->board[square + 19]))
253 ADD_MOVE(square + 19);
254 if (CAN_GOTO(piece, pos->board[square - 19]))
255 ADD_MOVE(square - 19);
256 if (CAN_GOTO(piece, pos->board[square + 8]))
257 ADD_MOVE(square + 8);
258 if (CAN_GOTO(piece, pos->board[square - 8]))
259 ADD_MOVE(square - 8);
264 if (type == PIECE_KING) {
265 // these are all the possible king moves
266 if (CAN_GOTO(piece, pos->board[square + 1]))
267 ADD_MOVE(square + 1);
268 if (CAN_GOTO(piece, pos->board[square - 1]))
269 ADD_MOVE(square - 1);
270 if (CAN_GOTO(piece, pos->board[square + 11]))
271 ADD_MOVE(square + 11);
272 if (CAN_GOTO(piece, pos->board[square - 11]))
273 ADD_MOVE(square - 11);
274 if (CAN_GOTO(piece, pos->board[square + 10]))
275 ADD_MOVE(square + 10);
276 if (CAN_GOTO(piece, pos->board[square - 10]))
277 ADD_MOVE(square - 10);
278 if (CAN_GOTO(piece, pos->board[square + 9]))
279 ADD_MOVE(square + 9);
280 if (CAN_GOTO(piece, pos->board[square - 9]))
281 ADD_MOVE(square - 9);
283 // evaluate if white can castle or not; quite ugly, but OK
284 if (search_castling) {
285 bool c_short, c_long;
286 if (pos->white_to_move) {
287 c_short = pos->wc_short;
288 c_long = pos->wc_long;
290 c_short = pos->bc_short;
291 c_long = pos->bc_long;
294 if (pos->board[square + 1] != PIECE_EMPTY ||
295 pos->board[square + 2] != PIECE_EMPTY)
297 if (pos->board[square - 1] != PIECE_EMPTY ||
298 pos->board[square - 2] != PIECE_EMPTY ||
299 pos->board[square - 3] != PIECE_EMPTY ||
300 pos->board[square - 4] != PIECE_EMPTY)
303 if (c_short || c_long) {
304 struct position npos = *pos;
305 npos.white_to_move = !npos.white_to_move;
308 // score -20000 => our king is in check
309 score = find_best_move(&npos, hash_position(&npos), NULL, NULL, 1, 0, -40000, 40000, false);
315 // check if the middle square is in check
317 if (pos->white_to_move)
318 real_make_move(&npos, square, square + 1, &npos.white_pieces[i], npos.black_pieces);
320 real_make_move(&npos, square, square + 1, &npos.black_pieces[i], npos.white_pieces);
321 score = find_best_move(&npos, hash_position(&npos), NULL, NULL, 1, 0, -40000, 40000, false);
324 ADD_MOVE(square + 2);
327 // check if the middle square is in check
329 if (pos->white_to_move)
330 real_make_move(&npos, square, square - 1, &npos.white_pieces[i], npos.black_pieces);
332 real_make_move(&npos, square, square - 1, &npos.black_pieces[i], npos.white_pieces);
333 score = find_best_move(&npos, hash_position(&npos), NULL, NULL, 1, 0, -40000, 40000, false);
336 ADD_MOVE(square - 2);
344 if (SLIDES_STRAIGHT(type)) {
345 // slide to the right for as long we can
346 int nsq = square + 1;
348 if (CAN_GOTO(piece, pos->board[nsq]))
350 if (pos->board[nsq] != PIECE_EMPTY)
358 if (CAN_GOTO(piece, pos->board[nsq]))
360 if (pos->board[nsq] != PIECE_EMPTY)
368 if (CAN_GOTO(piece, pos->board[nsq]))
370 if (pos->board[nsq] != PIECE_EMPTY)
378 if (CAN_GOTO(piece, pos->board[nsq]))
380 if (pos->board[nsq] != PIECE_EMPTY)
386 if (SLIDES_DIAGONALLY(type)) {
387 // slide to the upper-right for as long as we can
388 int nsq = square + 11;
390 if (CAN_GOTO(piece, pos->board[nsq]))
392 if (pos->board[nsq] != PIECE_EMPTY)
400 if (CAN_GOTO(piece, pos->board[nsq]))
402 if (pos->board[nsq] != PIECE_EMPTY)
410 if (CAN_GOTO(piece, pos->board[nsq]))
412 if (pos->board[nsq] != PIECE_EMPTY)
420 if (CAN_GOTO(piece, pos->board[nsq]))
422 if (pos->board[nsq] != PIECE_EMPTY)
429 // null-move heuristic
431 struct position npos = *pos;
432 unsigned long long nphash;
433 npos.white_to_move = !npos.white_to_move;
436 nphash = hash_position(&npos);
437 score = -find_best_move(&npos, nphash, NULL, NULL, depth - 1, seldepth, alpha, beta, true);
441 best_from = moves[indexes[0]].from;
442 best_to = moves[indexes[0]].to;
449 // now go through all the moves
450 while (num_moves > 0) {
452 const struct position * const npos = &moves[indexes[0]].pos;
453 unsigned long long nphash;
456 * If this move estimated way too good score, it means we just captured
457 * the king, and this position is definitely not legal. Stop the search,
458 * since there's no point of searching illegal positions.
460 if (moves[indexes[0]].estimate_score < -15000) {
461 alpha = -15000 + (max_depth + max_selective_depth - depth - seldepth);
462 best_from = moves[indexes[0]].from;
463 best_to = moves[indexes[0]].to;
465 killer_moves[depth][phash & 1].from = best_from;
466 killer_moves[depth][phash & 1].to = best_to;
470 if (moves[indexes[0]].estimate_score > 15000) {
471 alpha = 15000 - (max_depth + max_selective_depth - depth - seldepth);
472 best_from = moves[indexes[0]].from;
473 best_to = moves[indexes[0]].to;
475 killer_moves[depth][phash & 1].from = best_from;
476 killer_moves[depth][phash & 1].to = best_to;
481 nphash = hash_position(&moves[indexes[0]].pos);
482 if (lookup_record(nphash) >= 1) {
483 // ouch, move repetition, it's going to be a draw
485 } else if (depth == 1) {
486 // terminal node: static evaluation
487 score = (pos->white_to_move) ? evaluate(npos) : -evaluate(npos);
489 // non-terminal node: consider the opponent's best move
491 // if we're close to the end, and this is a capture, make a move extension
492 if (depth <= 1 && seldepth > 0 && pos->board[moves[indexes[0]].to] != PIECE_EMPTY)
493 score = -find_best_move(npos, nphash, NULL, NULL, depth, seldepth - 1, -beta, -alpha, true);
495 score = -find_best_move(npos, nphash, NULL, NULL, depth - 1, seldepth, -beta, -alpha, true);
500 best_from = moves[indexes[0]].from;
501 best_to = moves[indexes[0]].to;
504 // replace a random killer move
505 killer_moves[depth][phash & 1].from = best_from;
506 killer_moves[depth][phash & 1].to = best_to;
512 // swap this element with the last one
513 tmp = indexes[num_moves - 1];
514 indexes[num_moves - 1] = indexes[0];
518 downheapify(moves, indexes, 0, num_moves);
521 if ((best_from != 21 || best_to != 21) && search_castling)
522 insert_hash(pos, phash, depth, seldepth, best_from, best_to, alpha);
526 *ret_from = best_from;
532 void alarm_sounded(int signal)
535 fprintf(ucilog, "Aborting search due to signal %u\n", signal);
538 void ai_move(struct position *pos, unsigned think_time)
540 unsigned from, to, best_from, best_to;
541 int score, depth, seldepth;
542 struct timeval think_start, now;
545 gettimeofday(&think_start, NULL);
551 signal(SIGALRM, alarm_sounded);
553 abort_search = false;
556 struct position npos;
562 max_selective_depth = seldepth;
564 //fprintf(stderr, "\n\n\nThinking at depth %u:\n\n", depth);
565 min_depth = depth + seldepth;
566 score = find_best_move(pos, hash_position(pos), &from, &to, depth, seldepth, -40000, 40000, true);
574 gettimeofday(&now, NULL);
575 time_spent = (now.tv_sec - think_start.tv_sec) +
576 1e-6 * (now.tv_usec - think_start.tv_usec);
578 uciprintf("info depth %u seldepth %u score cp %d time %u hashfull %u nodes %u nps %u pv",
579 depth, depth + seldepth - min_depth + 1, score,
580 (unsigned)(time_spent * 1000.0),
581 100 * hash_used / HASH_MAX_ELEMS,
582 total_nodes, (unsigned)(total_nodes / time_spent + 0.5));
583 uciprintf(" %c%u%c%u",
584 "abcdefgh"[NUM_TO_FILE(from)], NUM_TO_RANK(from) + 1,
585 "abcdefgh"[NUM_TO_FILE(to)], NUM_TO_RANK(to) + 1);
587 // reconstruct the pv (hopefully from the hash table!)
589 make_move(&npos, from, to);
595 find_best_move(&npos, hash_position(&npos), &pvf, &pvt, pdepth, seldepth, -40000, 40000, true);
597 uciprintf(" %c%u%c%u",
598 "abcdefgh"[NUM_TO_FILE(pvf)], NUM_TO_RANK(pvf) + 1,
599 "abcdefgh"[NUM_TO_FILE(pvt)], NUM_TO_RANK(pvt) + 1);
601 //print_position(&npos);
602 make_move(&npos, pvf, pvt);
608 // this was a much better idea before we had selective search :-)
610 if (score > 15000 || score < -15000)
614 if (seldepth < depth * 2)
615 seldepth += (depth+1)/2;
622 make_move(pos, best_from, best_to);
624 uciprintf("bestmove %c%u%c%u\n",
625 "abcdefgh"[NUM_TO_FILE(best_from)], NUM_TO_RANK(best_from) + 1,
626 "abcdefgh"[NUM_TO_FILE(best_to)], NUM_TO_RANK(best_to) + 1);
632 struct position curr_pos;
633 ucilog = fopen("ucilog.txt", "w");
641 char buf[4096], *ptr;
642 fgets(buf, 4096, stdin);
645 ptr = strchr(buf, '\n');
649 ptr = strchr(buf, '\r');
653 fprintf(ucilog, "<= %s\n", buf);
656 if (strcmp(buf, "uci") == 0) {
657 uciprintf("id name stupid\n");
658 uciprintf("id author Steinar H. Gunderson\n");
659 uciprintf("uciok\n");
663 if (strcmp(buf, "isready") == 0) {
664 uciprintf("readyok\n");
668 if (strcmp(buf, "ucinewgame") == 0) {
669 // TODO: clear history and possibly pawn structure stuff?
672 if (strncmp(buf, "position", 8) == 0) {
674 if (strncmp(ptr, "startpos", 8) == 0) {
675 init_position(&curr_pos);
678 if (strncmp(ptr, "fen", 3) == 0) {
679 // no fen handling yet
680 ptr = strchr(ptr, ' ') + 1;
682 if (strncmp(ptr, "moves", 5) == 0) {
683 ptr = strchr(ptr, ' ');
684 while (ptr != NULL) {
685 unsigned from_file, from_rank, to_file, to_rank;
686 from_file = tolower(ptr[1]) - 'a';
687 from_rank = ptr[2] - '1';
688 to_file = tolower(ptr[3]) - 'a';
689 to_rank = ptr[4] - '1';
691 make_move(&curr_pos, SQUARE_TO_NUM(from_file, from_rank), SQUARE_TO_NUM(to_file, to_rank));
692 record_move(&curr_pos);
694 ptr = strchr(ptr + 1, ' ');
699 if (strncmp(buf, "go", 2) == 0) {
700 // see if there's a clock for us -- if not, use ten seconds
701 unsigned thinking_time = 10;
703 if (curr_pos.white_to_move)
704 ptr = strstr(buf, "wtime ");
706 ptr = strstr(buf, "btime ");
709 unsigned total_ms = atoi(ptr + 6);
711 ptr = strstr(buf, "movestogo ");
713 moves = atoi(ptr + 10);
715 thinking_time = ((total_ms - 5000) / (moves + 2) + 500) / 1000;
717 // also allocate 90% of the increment, if there's any
718 if (curr_pos.white_to_move)
719 ptr = strstr(buf, "winc ");
721 ptr = strstr(buf, "binc ");
723 thinking_time += atoi(ptr + 5) * 9 / 10000;
725 if (thinking_time < 1)
728 fprintf(ucilog, "Allocating %u seconds to think for this move.\n", thinking_time);
731 ai_move(&curr_pos, thinking_time);
732 record_move(&curr_pos);
737 fprintf(ucilog, "Unknown UCI command '%s'!\n", buf);