search.cpp

   1 /***************************************************************************
   2                           search.cpp  -  description
   3                              -------------------
   4     begin                : Wed Mar 13 2002
   5     copyright            : (C) 2002-2005 by Monge Maurizio
   6     email                : monge@linuz.sns.it
   7  ***************************************************************************/
   8
   9 /***************************************************************************
  10  *                                                                         *
  11  *   This program is free software; you can redistribute it and/or modify  *
  12  *   it under the terms of the GNU General Public License as published by  *
  13  *   the Free Software Foundation; either version 2 of the License, or     *
  14  *   (at your option) any later version.                                   *
  15  *                                                                         *
  16  ***************************************************************************/
  17
  18 #include "engine.h"
  19 #include "utils.h"
  20 #include <string.h>
  21 #include <stdlib.h>
  22 #include <math.h>
  23
  24 #define MAX_PV 80
  25 #define PLY    100
  26
  27
  28 // uint16_t killers[MAX_PV][64*64];
  29 //
  30 // #define HISTORY_INDEX(m) (SQUARE_TO_64(m.from)*64 + SQUARE_TO_64(m.to))
  31
  32
  33
  34 /* enable the nega-scout pv-search */
  35 #define NEGA_SCOUT           0
  36
  37 /* enable the null move */
  38 #define NULL_MOVE            0
  39
  40 /* before doing the alpha beta search check if any of the following positions
  41    can give use an early cutoff thanks to the hashtable */
  42 #define EARLY_TRANSP_CUTOFF   0
  43
  44 /* when the hashtable provides no "best" move, do a depth-2 search */
  45 #define INTERNAL_ITERATIVE_DEEPENING  0
  46
  47 /* use the history sorting heuristic */
  48 #define HISTORY_HEURISTIC    1
  49
  50 /* improve the sorting heuristic for moves to the center */
  51 #define CENTER_HEURISTIC     0
  52
  53 class SearchStack
  54 {
  55 public:
  56     int   base_depth;     /* depth of the search at this ply */
  57     int   extensions;     /* global extensions at this node */
  58     Move *moves;       /* all generated moves */
  59     int   num_moves;   /* num of moves */
  60     int   curr_move;   /* the move being currently analyzed */
  61     int16_t  alpha;    /* alpha ans beta when the search started (not improved) */
  62     int16_t  beta;
  63     bool  under_check;
  64     Move  threat;
  65     int   best_move;
  66 };
  67
  68 Move mv_stack[200*MAX_PV];
  69 int mv_stack_top = 0;
  70 SearchStack stack[MAX_PV];
  71 int current_ply = 0;
  72
  73 #if 0
  74 #define STAT(x)
  75 #else
  76 #define STAT(x) stat_##x++;
  77
  78 #define S(x) uint64_t stat_##x;
  79     S(quiesce_nodes);
  80     S(quiesce_hash);
  81     S(quiesce_called);
  82     S(quiesce_best_can_be_first);
  83     S(quiesce_best_was_first);
  84     S(quiesce_cutoff);
  85     S(quiesce_cutoff_first);
  86     S(search_nodes);
  87     S(search_hash);
  88     S(search_best_can_be_first);
  89     S(search_best_was_first);
  90     S(search_cutoff);
  91     S(search_cutoff_first);
  92     S(null_tried);
  93     S(null_successful);
  94 #undef S
  95
  96 void reset_stats()
  97 {
  98 #define S(x) stat_##x = 0;
  99     S(quiesce_nodes);
 100     S(quiesce_hash);
 101     S(quiesce_called);
 102     S(quiesce_best_can_be_first);
 103     S(quiesce_best_was_first);
 104     S(quiesce_cutoff);
 105     S(quiesce_cutoff_first);
 106     S(search_nodes);
 107     S(search_hash);
 108     S(search_best_can_be_first);
 109     S(search_best_was_first);
 110     S(search_cutoff);
 111     S(search_cutoff_first);
 112     S(null_tried);
 113     S(null_successful);
 114 #undef S
 115 }
 116
 117 void print_stats()
 118 {
 119 #define S(x) printf("# " #x " = "U64F"\n", stat_##x);
 120     S(quiesce_nodes);
 121     S(quiesce_hash);
 122     S(quiesce_called);
 123     S(quiesce_best_can_be_first);
 124     S(quiesce_best_was_first);
 125     S(quiesce_cutoff);
 126     S(quiesce_cutoff_first);
 127     S(search_nodes);
 128     S(search_hash);
 129     S(search_best_can_be_first);
 130     S(search_best_was_first);
 131     S(search_cutoff);
 132     S(search_cutoff_first);
 133     S(null_tried);
 134     S(null_successful);
 135 #undef S
 136 }
 137
 138 #endif
 139
 140 void Engine::print_stat()
 141 {
 142     if(eng_status != ANALYZING)
 143     {
 144         printf("Thinking: ");
 145         for(int i=0; i<current_ply; i++)
 146         {
 147             if(stack[i].curr_move == -2)
 148             {
 149                 continue;
 150             } //Internal iterative deepening
 151             else if(stack[i].curr_move == -1)
 152             {
 153                 printf("<NULL>");
 154                 board.do_null_move();
 155             }
 156             else
 157             {
 158                 char buf[32];
 159                 printf("%s", move_to_alg(buf, &(stack[i].moves[stack[i].curr_move]) ) );
 160                 board.do_move(stack[i].moves[stack[i].curr_move]);
 161             }
 162             printf((i != current_ply-1) ? " " : "\n");
 163         }
 164         rewind_thinking();
 165         return;
 166     }
 167
 168     if(thinking)
 169     {
 170         char buf[32];
 171         output("stat01: %d "U64F" %d %d %d %s\n",
 172             current_time() - start_think_time,
 173             processed_nodes,
 174             stack[0].base_depth/100,
 175             stack[0].num_moves-1-stack[0].curr_move,
 176             stack[0].num_moves,
 177             move_to_alg(buf, &(stack[0].moves[stack[0].curr_move]) ) );
 178     }
 179     else
 180         output("stat01: 0 0 0 0 0\n");
 181 }
 182
 183 void Engine::rewind_thinking()
 184 {
 185     for(int i=current_ply-1; i>=0; i--)
 186     {
 187         if(stack[i].curr_move == -2)
 188         { } //Internal iterative deepening
 189         else if(stack[i].curr_move == -1)
 190             board.undo_null_move();
 191         else
 192             board.undo_move(stack[i].moves[stack[i].curr_move]);
 193     }
 194 }
 195
 196 void Engine::restore_thinking()
 197 {
 198     for(int i=0; i<current_ply; i++)
 199     {
 200         if(stack[i].curr_move == -2)
 201         { } //Internal iterative deepening
 202         else if(stack[i].curr_move == -1)
 203             board.do_null_move();
 204         else
 205             board.do_move(stack[i].moves[stack[i].curr_move]);
 206     }
 207
 208     /* regenerate pinning info and under_check var, just to be sure :) */
 209     Move mvs[250];
 210     board.find_moves(mvs);
 211 }
 212
 213 #if 0
 214 void
 215 Engine::moves_heuristic(Move *mv, int num_mv, int ply, int orig_depth,
 216                                     Move best_mv_hash, bool quiesce)
 217 {
 218     /*uint8_t up_right = Board::up_dir[IS_WHITE(board.color_to_move)] + RIGHT;
 219     uint8_t up_left = Board::up_dir[IS_WHITE(board.color_to_move)] + LEFT;*/
 220     int hash_move = -1;
 221
 222     for(int i=0;i<num_mv;i++)
 223     {
 224         mv[i].val = 0;
 225         mv[i].extend = 0;
 226
 227         /* give a high bonus to the move stored in the hash, if any.
 228            mark only which is, don't continue, because some extensions
 229            may be triggered ad added later (ie pawn strike, etc) */
 230         if(mv[i].as_int == best_mv_hash.as_int)
 231             hash_move = i;
 232
 233         if(board.move_is_check(mv[i]) )
 234         {
 235             int see = board.move_see_val(mv[i]);
 236             if(orig_depth>-5*PLY && see >= 0)
 237                 mv[i].val = 25000 + see*64;
 238             else
 239                 mv[i].val = 15000;
 240         }
 241         else if(mv[i].capture)
 242         {
 243             int see = board.move_see_val(mv[i]);
 244             if(see > 0 || (orig_depth>-5*PLY && see==0) )
 245                 mv[i].val = 20000 + see*64;
 246             else
 247                 mv[i].val = 10000;
 248         }
 249     }
 250
 251     if(hash_move!=-1)
 252         mv[hash_move].val = 30000;
 253 }
 254 #else
 255 void
 256 Engine::moves_heuristic(Move *mv, int num_mv, int ply, int orig_depth,
 257                                     Move best_mv_hash, bool quiesce)
 258 {
 259     /*uint8_t up_right = Board::up_dir[IS_WHITE(board.color_to_move)] + RIGHT;
 260     uint8_t up_left = Board::up_dir[IS_WHITE(board.color_to_move)] + LEFT;*/
 261     int hash_move = -1;
 262
 263     for(int i=0;i<num_mv;i++)
 264     {
 265         mv[i].val = 0;
 266         mv[i].extend = 0;
 267
 268         /* give a high bonus to the move stored in the hash, if any.
 269            mark only which is, don't continue, because some extensions
 270            may be triggered ad added later (ie pawn strike, etc) */
 271         if(mv[i].as_int == best_mv_hash.as_int)
 272             hash_move = i;
 273
 274         /* process strong pawn moves */
 275         if(PIECE_OF(board.data[mv[i].from])==PAWN)  /* pawn strike */
 276         {
 277             if( ROW_OF(mv[i].to) == board.seventh_rank[IS_WHITE(board.color_to_move)] )
 278             {
 279                 int x = board.move_see_val(mv[i]);
 280
 281                 if(x<0)
 282                 {
 283                     mv[i].val += -15000;
 284                     continue;
 285                 }
 286
 287                 mv[i].val += 29499; /* 7th push */
 288                 mv[i].extend = 1;   /* extend search */
 289                 continue;
 290             }
 291
 292             if( mv[i].flags == PROMOTEQUEEN )
 293             {
 294                 int x = board.move_see_val(mv[i]);
 295
 296                 if(x<0)
 297                 {
 298                     mv[i].val += -15000;
 299                     continue;
 300                 }
 301
 302                 mv[i].val += 29500; /* promote! */
 303                 mv[i].extend = 1;   /* extend search */
 304                 continue;
 305             }
 306
 307             #if 0
 308             /* pawn strike */
 309             uint8_t p1 = mv[i].to + up_right;
 310             uint8_t p2 = mv[i].to + up_left;
 311             uint8_t a = OUT_OF_BOARD(p1) ? 0 : board.data[p1];
 312             uint8_t b = OUT_OF_BOARD(p2) ? 0 : board.data[p2];
 313             if( (COLOR_OF(a)==board.other_color && PIECE_OF(a)!=PAWN)
 314                 || (COLOR_OF(b)==board.other_color && PIECE_OF(b)!=PAWN) )
 315             {
 316                 int x = board.move_see_val(mv[i]);
 317                 if(x<0)
 318                 {
 319                     mv[i].val += -15000;
 320                     continue;
 321                 }
 322
 323                 mv[i].val += 27000; /* pawn strike! */
 324                 mv[i].extend = 1;   /* extend search */
 325                 continue;
 326             }
 327             #endif
 328         }
 329
 330         if(mv[i].capture)
 331         {
 332             int x = board.move_see_val(mv[i]);
 333
 334             if(x>0)
 335             {
 336                 if(orig_depth>-7*PLY && board.move_is_check(mv[i]) )
 337                 {
 338                     mv[i].val += 29800+x;
 339                     //mv[i].extend = 1;
 340                 }
 341                 else
 342                     mv[i].val += 29000+x;
 343                 continue;
 344             }
 345             else if(x<0)
 346             {
 347                 mv[i].val += -15000+x;
 348                 continue;
 349             }
 350             else if(orig_depth>-7*PLY && board.move_is_check(mv[i]) )
 351             {
 352                 /* = capture but check */
 353                 mv[i].val += 29800;
 354                 continue;
 355             }
 356         }
 357         else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
 358         if(0 && orig_depth>-3*PLY && board.move_is_check(mv[i]) )
 359         {
 360             if(board.move_see_val(mv[i])>=0)
 361             {
 362                 mv[i].val += 28799;
 363                 continue;
 364             }
 365         }
 366
 367         if(quiesce)
 368             continue;
 369
 370 #if HISTORY_HEURISTIC
 371         /* add the value depending on the heuristic */
 372 //         mv[i].val += killers[ply][HISTORY_INDEX(mv[i])];
 373 //         if(ply>=2)
 374 //             mv[i].val += killers[ply-2][HISTORY_INDEX(mv[i])];
 375 #endif //HISTORY_HEURISTIC
 376
 377 #if CENTER_HEURISTIC
 378         static int bof[128] = {
 379             0,0,1,2,2,1,0,0,ENDL,
 380             0,1,2,3,3,2,1,0,ENDL,
 381             0,2,4,5,5,4,2,0,ENDL,
 382             1,2,5,6,6,5,2,1,ENDL,
 383             1,2,5,6,6,5,2,1,ENDL,
 384             0,2,4,5,5,4,2,0,ENDL,
 385             0,1,2,3,3,2,1,0,ENDL,
 386             0,0,1,2,2,1,0,0,ENDL
 387         };
 388
 389         /* add a bonus for moves towards the center */
 390         mv[i].val += (bof[mv[i].to] - bof[mv[i].from]);
 391 #endif //CENTER_HEURISTIC
 392     }
 393
 394     if(hash_move!=-1)
 395         mv[hash_move].val = 30000;
 396 }
 397 #endif
 398
 399
 400 void
 401 Engine::moves_quiescence_heuristic(Move *mv, int num_mv, const Move& best_mv_hash, int static_eval, int alpha, int beta)
 402 {
 403     for(int i=0;i<num_mv;i++)
 404     {
 405         mv[i].val = -30000;
 406         mv[i].cost = 0;
 407
 408         /* give a high bonus to the move stored in the hash, if any. */
 409         if(mv[i].as_int == best_mv_hash.as_int)
 410         {
 411             mv[i].val = 30000;
 412             continue;
 413         }
 414
 415         if( mv[i].flags == PROMOTEQUEEN )
 416         {
 417             mv[i].val = 20000;
 418             continue;
 419         }
 420
 421         if(mv[i].capture)
 422         {
 423             int x = board.move_see_val(mv[i]);
 424
 425             if((static_eval == -INF && x>0)
 426                 || (static_eval + x*100 + 100 > alpha))
 427             {
 428                 if( board.move_is_check(mv[i]) )
 429                     mv[i].val = 15000 + x*64;
 430                 else
 431                     mv[i].val = 10000 + x*64;
 432                 continue;
 433             }
 434             else
 435             {
 436                 if(board.move_is_check(mv[i]))
 437                 {
 438                     mv[i].val = 5000 + x*64;
 439                     mv[i].cost = 20 + MAX(0, -x*8);
 440                 }
 441                 else
 442                 {
 443                     mv[i].val = x*64;
 444                     mv[i].cost = 40 + MAX(0, -x*12);
 445                 }
 446                 continue;
 447             }
 448         }
 449
 450         if( board.move_is_check(mv[i]) )
 451         {
 452             A88 atk = IS_WHITE(board.other_color) ? board.w_attacks : board.b_attacks;
 453             A88 def = IS_WHITE(board.color_to_move) ? board.w_attacks : board.b_attacks;
 454
 455             if(atk[mv[i].to] && !def[mv[i].to])
 456             {
 457                 mv[i].val = -5000;
 458                 mv[i].cost = 50;
 459             }
 460             else
 461             {
 462                 mv[i].val = -2000;
 463                 mv[i].cost = 30;
 464             }
 465         }
 466     }
 467 }
 468
 469
 470
 471 int16_t
 472 Engine::quiesce(int ply, int depth, int16_t alpha, int16_t beta)
 473 {
 474     SearchStack *s = &stack[ply];
 475     int16_t static_eval = -INF;
 476     int16_t best = -INF;
 477     int16_t best_guessed = alpha;
 478     uint16_t cbest_mv_hash = 0;    /* the compressed move from the hash */
 479     Move best_mv_hash = Move::FromInt(0);   /* the move from the hash */
 480     int best_mv_found = -1;  /* the index of the best move AFTER searching */
 481     bool    dangerous_position = false;
 482
 483     STAT(quiesce_nodes);
 484
 485     s->base_depth = 0;
 486     s->extensions = 0;
 487     s->num_moves = 0;
 488     s->curr_move = -3;
 489     s->alpha = alpha;
 490     s->beta = beta;
 491     s->threat = Move::FromInt(0);
 492     s->best_move = -1;
 493
 494     prefetch_hash( board.hash );
 495
 496     /* check if time is running out */
 497     if(check_time())
 498         return 0;
 499
 500     /* check for a draw for repetition or 50mvs. Of course the draw for
 501         repetition must be checked BEFORE probing the hash :)*/
 502     if(check_draw())
 503         return (board.color_to_move == st_computer_color) ? v_eval_draw :
 504                ((board.other_color == st_computer_color) ? -v_eval_draw : 0); /* be aggressive! */
 505
 506
 507 /*******************************************************************************
 508     Probe the hashtable.
 509     If the probe is succesful the hashtable will return us value
 510     that can be exact, a lower bound or an upper bound, and if the
 511     depth of the hashed search is >= the current depth this value
 512     will be used to improve alpha and beta and possibly return immediatly.
 513     The hastable will also give us a "best" move that will be searched
 514     first.
 515     This is the move that caused the "final" cutoff when this position
 516     was searched previously. This best move is actually the index of the best
 517     move in the array of generated moves (it is supposed to be deterministic :)
 518 *******************************************************************************/
 519
 520     HashEntry *h = probe_hash( board.hash );
 521
 522     if(h)
 523     {
 524         int16_t l = h->lower();
 525         int16_t u = h->upper();
 526
 527         if(l>=beta || u==l)
 528         {
 529             STAT(quiesce_hash);
 530             return l;
 531         }
 532         if(u<=alpha)
 533         {
 534             STAT(quiesce_hash);
 535             return u;
 536         }
 537
 538         beta = MIN(beta, u);
 539         alpha = MAX(alpha, l);
 540
 541         cbest_mv_hash = h->best_mv;
 542         best_guessed = MAX(best_guessed, h->lower());
 543     }
 544
 545
 546 /*******************************************************************************
 547     Test if we are under check, and if so extend search
 548 *******************************************************************************/
 549
 550     s->under_check = board.under_attack(board.king_pos[IS_WHITE(board.color_to_move)],
 551                                                                 board.other_color);
 552
 553     if(s->under_check)
 554         dangerous_position = true;
 555 //     else
 556 //     {
 557 //         int d = 0;
 558 //         int num_mv;
 559 //         Move *mv = mv_stack + mv_stack_top;
 560 //         board.do_null_move();
 561 //         num_mv = board.find_moves(mv);
 562 //
 563 //         for(int i=0;i<num_mv;i++)
 564 //         {
 565 //             if(!mv[i].capture)
 566 //                 continue;
 567 //             if(board.move_see_val(mv[i])>0)
 568 //                 d++;
 569 //         }
 570 //
 571 //         board.undo_null_move();
 572 //         if(d >= 2)
 573 //             dangerous_position = true;
 574 //     }
 575
 576     if(ply > 40)
 577         dangerous_position = false;
 578
 579     if(!dangerous_position)
 580     {
 581         best = static_eval = board.evaluate(st_computer_color, alpha, beta);
 582
 583         alpha = MAX(alpha, best);
 584         if(best >= beta)
 585             goto qsearch_done;
 586
 587         if(ply>40)
 588             goto qsearch_done;
 589     }
 590
 591
 592 /*******************************************************************************
 593     Now generate the legal moves and look for a check/stalemate
 594 *******************************************************************************/
 595
 596     /* generate all the legal moves */
 597     s->moves = &mv_stack[mv_stack_top];
 598     s->num_moves = board.find_moves(s->moves);
 599     mv_stack_top += s->num_moves;
 600     s->under_check = board.under_check;
 601
 602     /* return now if the positon is terminal */
 603     if(!s->num_moves)
 604     {
 605         if(s->under_check)
 606             /* while mating, sacrify as much as possible :) */
 607             best = -INF + ply;//*50 + board.material[IS_WHITE(eng_color)]/50;
 608         else
 609             best = 0;
 610         goto qsearch_done;
 611     }
 612
 613
 614 /*******************************************************************************
 615     Sort the moves.
 616     First comes the move from the hashtable, if avalable.
 617     The remaining moves are sorted with a heuristic that keeps in account
 618     the history heuristic (ie the moves that previously caused an alpha
 619     cutoff), a MVV/LVA bonus value and a small bonus for moves that go
 620     toward the center.
 621 *******************************************************************************/
 622
 623     /* convert the move we got from the hash to the move structure */
 624     if(cbest_mv_hash)
 625     {
 626         best_mv_hash = board.uncompress_move(cbest_mv_hash);
 627         /* if it happened that the move we got from the hashtable
 628             is not valid, simply no move will get the high
 629             heuristic bonus value */
 630     }
 631
 632     /* for each move calculate the heuristic goodness value */
 633     moves_quiescence_heuristic(s->moves, s->num_moves, best_mv_hash, static_eval, alpha, beta);
 634
 635     /* if quiesce rip-off bad moves */
 636     if(!dangerous_position)
 637     {
 638         int n = 0;
 639         for(int i=0;i<s->num_moves;i++)
 640         if(s->moves[i].val>=10000 ||
 641             (s->moves[i].val>=-10000 && depth>s->moves[i].cost) )
 642             s->moves[n++] = s->moves[i];
 643         mv_stack_top -= s->num_moves-n;
 644         s->num_moves = n;
 645     }
 646
 647     /* sort the moves using the heuristic values */
 648     sort_moves( s->moves, s->num_moves );
 649
 650     /* set the current best move index (as will be saved in the hash) */
 651     best_mv_found = 0;
 652
 653 /*******************************************************************************
 654     It is now time to loop all the successor moves and search recursively.
 655 *******************************************************************************/
 656
 657     for(int i=0;i<s->num_moves;i++)
 658     {
 659         int16_t val;
 660
 661         /* sort moves incrementally, in the hope of a beta cut */
 662         //incremental_sort_moves(s->moves+i, s->num_moves-i);
 663
 664         s->curr_move = i;
 665         current_ply++;
 666         board.do_move(s->moves[i]);
 667         val = -quiesce( ply+1, depth - s->moves[i].cost, -beta, -alpha);
 668         board.undo_move(s->moves[i]);
 669         current_ply--;
 670
 671         /* update the current best value and check for and alpha cut */
 672         best = MAX(best, val);
 673         if(best > alpha)
 674         {
 675             best_mv_found = i;
 676             s->best_move = i;
 677
 678             /* alpha cut! */
 679             alpha = best;
 680         }
 681
 682         /* beta cut! */
 683         if(best >= beta)
 684         {
 685             STAT(quiesce_cutoff);
 686             if(i==0)
 687                 STAT(quiesce_cutoff_first);
 688             break;
 689         }
 690     }
 691
 692
 693 qsearch_done:
 694     mv_stack_top -= s->num_moves; /* free the moves we allocated */
 695
 696     /* if we found a best move searching, that move will be saved.
 697        if we did no search (ie quiescence), save the old hash value,
 698        or -1 if no hash entry had been found */
 699     int bestmv = cbest_mv_hash;
 700     if(best_mv_found >= 0)
 701     {
 702         bestmv = board.compress_move(s->moves[best_mv_found]);
 703         STAT(quiesce_best_can_be_first);
 704         if(best_mv_found == 0)
 705             STAT(quiesce_best_was_first);
 706     }
 707
 708     /* write the value in the hash, with the index of the best move */
 709     write_hash( best > s->alpha ? best : -INF,
 710                 best < beta ? best : +INF, 0, bestmv);
 711
 712     return best;
 713 }
 714
 715
 716 /*******************************************************************************
 717     The main alpha-beta recursive search function.
 718     It handles both normal search (with or without null move)
 719     and quiescence search, because i have having 2 almost identical
 720     function around.
 721 *******************************************************************************/
 722
 723 int16_t
 724 Engine::search(int ply, int depth, bool pv, int16_t alpha, int16_t beta, bool inner)
 725 {
 726     SearchStack *s = &stack[ply];
 727     int null_value = INF;
 728     int16_t best = -INF;
 729     int16_t best_guessed = alpha;
 730     uint16_t cbest_mv_hash = 0;    /* the compressed move from the hash */
 731     Move best_mv_hash = Move::FromInt(0);   /* the move from the hash */
 732     int best_mv_found = -1;  /* the index of the best move AFTER searching */
 733     bool    extended = false;
 734
 735     STAT(search_nodes);
 736
 737     s->base_depth = depth;
 738     s->extensions = 0;
 739     s->num_moves = 0;
 740     s->curr_move = -3;
 741     s->alpha = alpha;
 742     s->beta = beta;
 743     s->threat = Move::FromInt(0);
 744     s->best_move = -1;
 745
 746     prefetch_hash( board.hash );
 747
 748     /* check if time is running out */
 749     if(check_time())
 750         return 0;
 751
 752     /* check for a draw for repetition or 50mvs. Of course the draw for
 753         repetition must be checked BEFORE probing the hash :)*/
 754     if(check_draw())
 755         return (board.color_to_move == st_computer_color) ? v_eval_draw :
 756                ((board.other_color == st_computer_color) ? -v_eval_draw : 0); /* be aggressive! */
 757
 758 /*******************************************************************************
 759     Probe the hashtable.
 760     If the probe is succesful the hashtable will return us value
 761     that can be exact, a lower bound or an upper bound, and if the
 762     depth of the hashed search is >= the current depth this value
 763     will be used to improve alpha and beta and possibly return immediatly.
 764     The hastable will also give us a "best" move that will be searched
 765     first.
 766     This is the move that caused the "final" cutoff when this position
 767     was searched previously. This best move is actually the index of the best
 768     move in the array of generated moves (it is supposed to be deterministic :)
 769 *******************************************************************************/
 770     HashEntry *h = probe_hash( board.hash );
 771
 772     if(h && (h->depth >= s->base_depth))// || ABS(h->value)>INF-1000) )
 773     {
 774         int16_t l = h->lower();
 775         int16_t u = h->upper();
 776
 777
 778         if(l>=beta || u==l)
 779         {
 780             STAT(search_hash);
 781             return l;
 782         }
 783         if(u<=alpha)
 784         {
 785             STAT(search_hash);
 786             return u;
 787         }
 788
 789         beta = MIN(beta, u);
 790         alpha = MAX(alpha, l);
 791     }
 792
 793     if(h) {
 794         cbest_mv_hash = h->best_mv;
 795         best_guessed = MAX(best_guessed, h->lower());
 796     }
 797
 798
 799 /*******************************************************************************
 800     Test if we are under check, and if so extend search
 801 *******************************************************************************/
 802
 803     s->under_check = board.under_attack(board.king_pos[IS_WHITE(board.color_to_move)],
 804                                                                 board.other_color);
 805
 806 /*******************************************************************************
 807     If it is time to quiesce, evaluate and test if we can exit
 808     immediately with a beta cut-off (try first a rough eval - delta)
 809 *******************************************************************************/
 810 //s    quiesce = (!s->under_check) && (depth<=0);
 811 #if 0
 812     if(quiesce && depth>=-100)
 813     {
 814         int num_mv;
 815         Move *mv = mv_stack + mv_stack_top;
 816         board.do_null_move();
 817         num_mv = board.find_moves(mv);
 818
 819         for(int i=0;i<num_mv;i++)
 820         {
 821             if(!mv[i].capture)
 822                 continue;
 823             if(board.move_see_val(mv[i])>0)
 824             {
 825                 quiesce = false;
 826                 break;
 827             }
 828         }
 829
 830         board.undo_null_move();
 831     }
 832 #endif
 833
 834
 835 #if NULL_MOVE
 836 /*******************************************************************************
 837     Try the null move.
 838 *******************************************************************************/
 839     if(!s->under_check && (stack[ply-1].curr_move!=-1) && depth >= 2*PLY && beta<INF-1000)
 840     {
 841         s->curr_move = -1;
 842         current_ply++;
 843         board.do_null_move();
 844         null_value = -search( ply+1, depth-v_search_null_reduction, true, -beta, -beta+1);
 845         //null_value = -search( ply+1, depth-v_search_null_reduction, true, -beta, -INF);
 846         board.undo_null_move();
 847         current_ply--;
 848
 849         STAT(null_tried);
 850
 851         /* null move cut! */
 852         if(null_value >= beta)
 853         {
 854             STAT(null_successful);
 855             return null_value;
 856         }
 857
 858 //         if(val<alpha-100 &&  /* we are facing a threat*/
 859 //            stack[ply+1].best_move != -1) /* be sure we aren't reading random memory */
 860 //         {
 861 //             /* ok, officially the array stack[ply+1].moves has already
 862 //                 been deallocated, but who cares :) */
 863 //             s->threat = stack[ply+1].moves[stack[ply+1].best_move];
 864 //
 865 //             #if 0
 866 //             /* Botvinnik-Markoff extension!!! */
 867 //             if(!extended && ply>=3 && (s->threat == stack[ply-2].threat) )
 868 //             {
 869 //                 depth += 80;
 870 //                 extended = true;
 871 //             }
 872 //             #endif
 873 //         }
 874     }
 875 #endif
 876
 877
 878
 879 /*******************************************************************************
 880     Now generate the legal moves and look for a check/stalemate
 881 *******************************************************************************/
 882
 883     /* generate all the legal moves */
 884     s->moves = &mv_stack[mv_stack_top];
 885     s->num_moves = board.find_moves(s->moves);
 886     mv_stack_top += s->num_moves;
 887     s->under_check = board.under_check;
 888
 889     if(s->under_check==2) /* double check */
 890     {
 891         depth += 200;
 892         extended = true;
 893     }
 894     else if(s->under_check) /* simple check */
 895     {
 896         depth += 100;
 897         if(stack[ply-1].curr_move!=-1 &&
 898            !board.pins[stack[ply-1].moves[  /* last moved piece is not attacking the king */
 899              stack[ply-1].curr_move].to])   /* so this is a discover check */
 900         {
 901             depth += 50;
 902         }
 903         extended = true;
 904     }
 905
 906     /* return now if the positon is terminal */
 907     if(!s->num_moves)
 908     {
 909         if(s->under_check)
 910             /* while mating, sacrify as much as possible :) */
 911             best = -INF + ply;//*50 + board.material[IS_WHITE(eng_color)]/50;
 912         else
 913             best = 0;
 914         goto search_done;
 915     }
 916
 917     /* single-reply extension */
 918     if(s->num_moves == 1 && !extended)
 919     {
 920         depth += 100;
 921         extended = true;
 922     }
 923     else if(s->num_moves <= 3 && !extended)
 924     {
 925         depth += 50;
 926         extended = true;
 927     }
 928
 929
 930
 931 /*******************************************************************************
 932     Try to get an early beta cutoff using the hash table values
 933     of the following moves, and improve alpha too.
 934     Try only the first 6 value of the ordered moves (argh, looking into the
 935     hashtable is very expensive because of the cache!!!!!!!!)
 936 *******************************************************************************/
 937 #if EARLY_TRANSP_CUTOFF
 938     if(depth >= 2*PLY)
 939     {
 940         HashKey hk = board.move_hash(s->moves[0]);
 941         for(int i=1;i<s->num_moves;i++)
 942         {
 943             prefetch_hash(hk);
 944             HashKey newhk = board.move_hash(s->moves[i]);
 945             HashEntry *h2 = probe_hash( hk );
 946             hk = newhk;
 947
 948             if(h2 && h2->depth >= depth-100)
 949             {
 950                 if(-h2->up >= beta)
 951                 {
 952                     best = -h2->up;
 953                     goto search_done;
 954                 }
 955                 alpha = MAX(alpha, (int16_t)-h2->up);
 956             }
 957         }
 958
 959         HashEntry *h2 = probe_hash( hk );
 960         if(h2 && h2->depth >= depth-100)
 961         {
 962             if(-h2->up >= beta)
 963             {
 964                 best = -h2->up;
 965                 goto search_done;
 966             }
 967             alpha = MAX(alpha, (int16_t)-h2->up);
 968         }
 969     }
 970 #endif //EARLY_TRANSP_CUTOFF
 971
 972
 973 /*******************************************************************************
 974     Sort the moves.
 975     First comes the move from the hashtable, if avalable.
 976     The remaining moves are sorted with a heuristic that keeps in account
 977     the history heuristic (ie the moves that previously caused an alpha
 978     cutoff), a MVV/LVA bonus value and a small bonus for moves that go
 979     toward the center.
 980 *******************************************************************************/
 981
 982     /* convert the move we got from the hash to the move structure */
 983     if(cbest_mv_hash)
 984     {
 985         best_mv_hash = board.uncompress_move(cbest_mv_hash);
 986         /* if it happened that the move we got from the hashtable
 987             is not valid, simply no move will get the high
 988             heuristic bonus value */
 989     }
 990     #if INTERNAL_ITERATIVE_DEEPENING
 991     else if(s->base_depth>=3*PLY && pv) /* don't do it only on the pv, or it will be useless :) */
 992     {
 993         s->curr_move = -2;
 994         current_ply++;
 995         int val = search(ply+1, s->base_depth-2*PLY, true, alpha, beta);
 996         current_ply--;
 997
 998         HashEntry *h2 = probe_hash( board.hash );
 999         if(h2 && h2->best_mv)
1000         {
1001             cbest_mv_hash = h2->best_mv;
1002             best_mv_hash = board.uncompress_move(cbest_mv_hash);
1003
1004             best_guessed = MAX(best_guessed, h2->lower());
1005         }
1006     }
1007     #endif //INTERNAL_ITERATIVE_DEEPENING
1008
1009
1010     /* for each move calculate the heuristic goodness value */
1011     moves_heuristic( s->moves, s->num_moves, ply, s->base_depth,
1012                                     best_mv_hash, false );
1013
1014     /* sort the moves using the heuristic values */
1015     sort_moves( s->moves, s->num_moves );
1016
1017     /* mh threat extension, unluckily does not seam to work well */
1018 //      if(!extended && ply<7 && (null_value < best_guessed-v_search_threat_threshold))
1019 //      {
1020 //          extended = true;
1021 //          depth += v_search_threat_extension;
1022 //      }
1023
1024
1025     /* set the current best move index (as will be saved in the hash) */
1026     best_mv_found = 0;
1027
1028 /*******************************************************************************
1029     It is now time to loop all the successor moves and search recursively.
1030 *******************************************************************************/
1031
1032     for(int i=0;i<s->num_moves;i++)
1033     {
1034         int16_t val;
1035         int sdepth = depth-100;
1036
1037         /* sort moves incrementally, in the hope of a beta cut */
1038         //incremental_sort_moves(s->moves+i, s->num_moves-i);
1039
1040         s->curr_move = i;
1041         current_ply++;
1042         board.do_move(s->moves[i]);
1043
1044         if(sdepth > 0)
1045         {
1046 #ifdef NEGA_SCOUT
1047             if(i == 0)
1048                 val = -search( ply+1, sdepth, pv, -beta, -alpha);
1049             else
1050             {
1051                 val = -search( ply+1, sdepth, false, -alpha-1, -alpha );
1052                 if((val>alpha) && pv)
1053                     val = -search( ply+1, sdepth, true, -beta, -alpha );
1054             }
1055 #else //NEGA_SCOUT
1056             val = -search( ply+1, sdepth, pv, -beta, -alpha);
1057 #endif //NEGA_SCOUT
1058         }
1059         else
1060         {
1061             val = -quiesce( ply+1, 100, -beta, -alpha);
1062             STAT(quiesce_called);
1063         }
1064
1065         board.undo_move(s->moves[i]);
1066         current_ply--;
1067
1068         /* update the current best value and check for and alpha cut */
1069         best = MAX(best, val);
1070         if(best > alpha)
1071         {
1072             best_mv_found = i;
1073             s->best_move = i;
1074
1075             /* alpha cut! */
1076             alpha = best;
1077         }
1078
1079         /* beta cut! */
1080         if(best >= beta)
1081         {
1082             STAT(search_cutoff);
1083             if(i==0)
1084                 STAT(search_cutoff_first);
1085             break;
1086         }
1087     }
1088
1089
1090 //     for(int i=0;i<best_mv_found;i++)
1091 //     {
1092 //         uint16_t& val = killers[0][HISTORY_INDEX(s->moves[i])];
1093 //         val = MAX(val-1, 0);
1094 //     }
1095 //     {uint16_t& kval = killers[0][HISTORY_INDEX(s->moves[best_mv_found])];
1096 //     kval = MIN(kval+16, 29000);}
1097
1098
1099 search_done:
1100     mv_stack_top -= s->num_moves; /* free the moves we allocated */
1101
1102     /* if we found a best move searching, that move will be saved.
1103        if we did no search (ie quiescence), save the old hash value,
1104        or -1 if no hash entry had been found */
1105     int bestmv = cbest_mv_hash;
1106     if(best_mv_found >= 0)
1107     {
1108         bestmv = board.compress_move(s->moves[best_mv_found]);
1109         STAT(search_best_can_be_first);
1110         if(best_mv_found == 0)
1111             STAT(search_best_was_first);
1112     }
1113
1114     /* write the value in the hash, with the index of the best move */
1115     write_hash( best > s->alpha ? best : -INF,
1116                 best < beta ? best : +INF,
1117                 s->base_depth, bestmv);
1118
1119     return best;
1120 }
1121
1122
1123 Move
1124 Engine::find_best_move()
1125 {
1126     SearchStack *s = &stack[0];
1127     Move retv;
1128
1129     ASSERT(!thinking);
1130
1131     reset_stats();
1132
1133     /* initialize the root node */
1134     current_ply = 0;
1135     s->base_depth = 2*PLY;
1136     s->extensions = 0;
1137     s->curr_move = -1;
1138     s->alpha = -INF;
1139     s->beta = INF;
1140     s->threat = Move::FromInt(0);
1141     s->best_move = -1;
1142
1143     s->moves = mv_stack;
1144     s->num_moves = mv_stack_top = board.find_moves(s->moves);
1145
1146     /* to print the analysis */
1147     if(post)
1148         output("\tply\tscore\ttime\tnodes\tpv\n");
1149
1150     /* return immediatly if the move is forced. */
1151     if(s->num_moves==1)
1152         return s->moves[0];
1153
1154     /* probe the play lines */
1155     if( eng_status == PLAYING
1156         && st_computer_color == board.color_to_move
1157          && probe_lines( board.hash, &retv))
1158     {
1159         retv.val = 0;
1160         return retv;
1161     }
1162
1163     /* probe the book */
1164     if(probe_book( board.hash, &retv) ) {
1165         for(int i=0;i<s->num_moves++;i++)
1166         if(retv.as_int == s->moves[i].as_int)
1167         {
1168             retv.val = 0;
1169             return retv;
1170         }
1171         output("ERROR! Got an invalid move from the book!\n");
1172     }
1173
1174     /* calculate how much time we will think*/
1175     start_think_time = current_time();
1176     if( analysis_limit == TIME_LIMIT )
1177     {
1178         if(board.color_to_move == st_computer_color)
1179             calc_best_time();
1180         else /* pondering? analysing? */
1181             time_best_csec = 99999999;
1182         max_think_time = start_think_time + time_best_csec - 2;
1183     }
1184
1185     processed_nodes = 0;
1186     thinking = true;
1187     make_old_hash();
1188
1189     /* set the back jump for the quick thinking exit */
1190     if(setjmp(back))
1191         goto exit_thinking;
1192
1193     /* start with a guess of 0 */
1194     s->moves[0].val = 0;
1195     retv = s->moves[0];
1196
1197     /* do the iterative deepening thing. */
1198     while(1)
1199     {
1200         int16_t alpha = -INF;
1201         int i=0;
1202
1203 //         for(int i=0;i<40;i++)
1204 //             memset( &killers[i], 0, 64*64*sizeof(uint16_t));
1205
1206         /* for each move call the alpha-beta search function */
1207         int best_mv = 0;
1208
1209         for(i=0;i<s->num_moves;i++)
1210         {
1211             s->curr_move = i;
1212             current_ply++;
1213             board.do_move(s->moves[i]);
1214 #if NEGA_SCOUT
1215             if(i == 0)
1216             {
1217                 s->moves[i].val = -search( 1, s->base_depth-100, true,
1218                                                     -INF, -alpha );
1219             }
1220             else
1221             {
1222                 s->moves[i].val = -search( 1, s->base_depth-100, false,
1223                                                     -alpha-1, -alpha );
1224                 if(s->moves[i].val > alpha)
1225                     s->moves[i].val = -search( 1, s->base_depth-100, true,
1226                                                     -INF, -alpha );
1227             }
1228 #else //NEGA_SCOUT
1229             s->moves[i].val = -search( 1, s->base_depth-100, true, -INF, -alpha);
1230 #endif //NEGA_SCOUT
1231             board.undo_move(s->moves[i]);
1232             current_ply--;
1233
1234             /* cut alpha */
1235             if(s->moves[i].val > alpha)
1236             {
1237                 alpha = s->moves[i].val;
1238                 retv = s->moves[i];
1239                 best_mv = i;
1240                 s->best_move = i;
1241
1242                 /* this move caused an alpha cut, so print the new line */
1243                 if( post /*&& processed_nodes>100000*/)
1244                 {
1245                     output("\t%d\t%d\t%d\t"U64F"\t", s->base_depth/100,
1246                                 s->moves[i].val, current_time() - start_think_time, processed_nodes);
1247                     print_moves(&s->moves[i], 1, true);
1248                 }
1249             }
1250         }
1251
1252         /* the search is done, sort the moves so that best is searched first */
1253         if(i>1)
1254         {
1255             s->moves[best_mv].val++;
1256             sort_moves(s->moves, i);   /* sort i moves (those that we where able to search) */
1257             s->moves[0].val--;
1258         }
1259
1260         /* print the result of the analysis at this depth */
1261         if( post /*&& processed_nodes>100000*/)
1262         {
1263             output("\t%d\t%d\t%d\t"U64F"\t", s->base_depth/100,
1264                         s->moves[0].val, current_time() - start_think_time, processed_nodes);
1265             print_moves(&s->moves[0], 1, true);
1266         }
1267
1268         /* max depth */
1269         if( s->base_depth >= 40*PLY )
1270                 break;
1271
1272         /* return in case of fixed depth search */
1273         if( eng_status == PLAYING && st_computer_color == board.color_to_move &&
1274                 analysis_limit == DEPTH_LIMIT && s->base_depth == st_depth*PLY)
1275             break;
1276
1277         /* return if 3/5 of time is gone (we can't search another ply anyway) */
1278         if( eng_status == PLAYING && st_computer_color == board.color_to_move &&
1279                 analysis_limit == TIME_LIMIT &&
1280                 (current_time()-start_think_time) >= (time_best_csec*3/5) )
1281             break;
1282
1283         /* if a checkmate was detected return immediately */
1284         if( ABS(alpha) > INF-1000)
1285             break;
1286
1287         s->base_depth += PLY;
1288     }
1289
1290 exit_thinking:
1291
1292     if(post)
1293     {
1294         output("#nodes: "U64F" (~"U64F" nps)\n", processed_nodes, (processed_nodes*100)/
1295                                                 MAX(current_time()-start_think_time,1) );
1296         print_stats();
1297     }
1298
1299     thinking = false;
1300     return retv;
1301 }