quiesrch.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include <limits.h>
   4 #include <assert.h>
   5 #include "shogi.h"
   6
   7 /* #define DBG_QSEARCH */
   8 #if defined(DBG_QSEARCH)
   9 #  define DOut( ... )  if ( dbg_flag ) { out( __VA_ARGS__ ); }
  10 #else
  11 #  define DOut( ... )
  12 #endif
  13
  14 static int CONV gen_next_quies( tree_t * restrict ptree, int alpha, int turn,
  15                                 int ply, int qui_ply );
  16
  17 int CONV
  18 search_quies( tree_t * restrict ptree, int alpha, int beta, int turn, int ply,
  19               int qui_ply )
  20 {
  21   int value, alpha_old, stand_pat;
  22
  23 #if defined(DBG_QSEARCH)
  24   int dbg_flag = 0;
  25
  26   if ( iteration_depth == 2 && ply == 4
  27        && ! strcmp( str_CSA_move(ptree->current_move[1]), "7776FU" )
  28        && ! strcmp( str_CSA_move(ptree->current_move[2]), "3334FU" )
  29        && ! strcmp( str_CSA_move(ptree->current_move[3]), "8822UM" ) )
  30     {
  31       dbg_flag = 1;
  32       Out( "qsearch start (alpha=%d beta=%d sp=%d %" PRIu64 ")",
  33            alpha, beta, value, ptree->node_searched );
  34     }
  35 #endif
  36
  37
  38 #if defined(TLP)
  39   if ( ! ptree->tlp_id )
  40 #endif
  41     {
  42       node_last_check += 1;
  43     }
  44   ptree->node_searched += 1;
  45   ptree->nquies_called += 1;
  46   alpha_old             = alpha;
  47
  48   stand_pat = evaluate( ptree, ply, turn );
  49
  50
  51   if ( alpha < stand_pat )
  52     {
  53       if ( beta <= stand_pat )
  54         {
  55           DOut( ", cut by stand-pat\n" );
  56           MOVE_CURR = MOVE_PASS;
  57           return stand_pat;
  58         }
  59       alpha = stand_pat;
  60     }
  61
  62   if ( ply >= PLY_MAX-1 )
  63     {
  64       if ( alpha_old != alpha ) { pv_close( ptree, ply, no_rep ); }
  65       MOVE_CURR = MOVE_NA;
  66       return stand_pat;
  67     }
  68
  69
  70   if ( is_mate_in3ply( ptree, turn, ply ) )
  71     {
  72       value = score_mate1ply + 1 - ply;
  73
  74       if ( alpha < value
  75            && value < beta ) { pv_close( ptree, ply, mate_search ); }
  76
  77       assert( is_move_valid( ptree, MOVE_CURR, turn ) );
  78       return value;
  79     }
  80
  81
  82   ptree->anext_move[ply].next_phase = next_quies_gencap;
  83   while ( gen_next_quies( ptree, alpha, turn, ply, qui_ply ) )
  84     {
  85       DOut( "\nexpand %s (%" PRIu64 ")",
  86             str_CSA_move(MOVE_CURR), ptree->node_searched );
  87
  88       MakeMove( turn, MOVE_CURR, ply );
  89       if ( InCheck(turn) )
  90         {
  91           UnMakeMove( turn, MOVE_CURR, ply );
  92           continue;
  93         }
  94
  95       value = -search_quies( ptree, -beta, -alpha, Flip(turn), ply+1,
  96                              qui_ply+1 );
  97
  98       UnMakeMove( turn, MOVE_CURR, ply );
  99
 100       if ( alpha < value )
 101         {
 102           check_futile_score_quies( ptree, MOVE_CURR, ptree->save_eval[ply],
 103                                     -ptree->save_eval[ply+1], turn );
 104           if ( beta <= value )
 105             {
 106               DOut( ", beta cut (%" PRIu64 ")\n", ptree->node_searched );
 107
 108               assert( ! IsMove(MOVE_CURR)
 109                       || is_move_valid( ptree, MOVE_CURR, turn ) );
 110               return value;
 111             }
 112
 113           DOut( ", renew alpha=%d (%" PRIu64 ")\n",
 114                 value, ptree->node_searched );
 115           alpha = value;
 116         }
 117     }
 118
 119   DOut( "\nall searched (%" PRIu64 ")\n", ptree->node_searched );
 120
 121   if ( alpha_old != alpha )
 122     {
 123       if ( alpha == stand_pat ) { pv_close( ptree, ply, no_rep ); }
 124       else                      { pv_copy( ptree, ply ); }
 125     }
 126
 127   return alpha;
 128 }
 129
 130
 131 static int CONV
 132 gen_next_quies( tree_t * restrict ptree, int alpha, int turn, int ply,
 133                 int qui_ply )
 134 {
 135   switch ( ptree->anext_move[ply].next_phase )
 136     {
 137     case next_quies_gencap:
 138       {
 139         unsigned int * restrict pmove;
 140         int * restrict psortv;
 141         int i, j, n, nqmove, value, min_score, diff;
 142         unsigned int move;
 143
 144         ptree->move_last[ply] = GenCaptures( turn, ptree->move_last[ply-1] );
 145
 146         /* set sort values */
 147         pmove  = ptree->move_last[ply-1];
 148         psortv = ptree->sort_value;
 149         nqmove = 0;
 150         n      = (int)( ptree->move_last[ply] - pmove );
 151
 152         for ( i = 0; i < n; i++ )
 153           {
 154             move = pmove[i];
 155
 156             if ( qui_ply >= QUIES_PLY_LIMIT
 157                  && ( ( UToCap(move) == pawn && ! I2IsPromote(move) )
 158                       || ( ! UToCap(move) && I2PieceMove(move) != pawn ) ) )
 159               {
 160                 continue;
 161               }
 162
 163             diff      = estimate_score_diff( ptree, move, turn );
 164             min_score = eval_max_score( ptree, move, ptree->save_eval[ply],
 165                                         turn, diff );
 166
 167             if ( alpha < min_score )
 168               {
 169                 value = swap( ptree, move, -1, MT_CAP_SILVER, turn );
 170                 if ( -1 < value )
 171                   {
 172                     psortv[nqmove]  = value + diff;
 173                     pmove[nqmove++] = move;
 174                   }
 175               }
 176           }
 177
 178         /* insertion sort */
 179         psortv[nqmove] = INT_MIN;
 180         for ( i = nqmove-2; i >= 0; i-- )
 181           {
 182             value = psortv[i];  move = pmove[i];
 183             for ( j = i+1; psortv[j] > value; j++ )
 184               {
 185                 psortv[j-1] = psortv[j];  pmove[j-1] = pmove[j];
 186               }
 187             psortv[j-1] = value;  pmove[j-1] = move;
 188           }
 189
 190         ptree->move_last[ply]             = ptree->move_last[ply-1] + nqmove;
 191         ptree->anext_move[ply].move_last  = pmove;
 192         ptree->anext_move[ply].next_phase = next_quies_captures;
 193       }
 194
 195     case next_quies_captures:
 196       if ( ptree->anext_move[ply].move_last != ptree->move_last[ply] )
 197         {
 198           MOVE_CURR = *ptree->anext_move[ply].move_last++;
 199           return 1;
 200         }
 201     }
 202
 203   return 0;
 204 }