search.cpp-old

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