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 gen_next_quies( tree_t * restrict ptree, int alpha, int turn,
  15                            int ply, int qui_ply );
  16
  17 int
  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;
  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   value = evaluate( ptree, ply, turn );
  49
  50
  51   if ( alpha < value )
  52     {
  53       if ( beta <= value )
  54         {
  55           DOut( ", cut by stand-pat\n" );
  56           MOVE_CURR = MOVE_PASS;
  57           return value;
  58         }
  59       alpha = value;
  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 value;
  67     }
  68
  69
  70   if ( ( qui_ply == 1 && ! ( ply == 2 && InCheck( turn ) ) )
  71        || ( 1 < qui_ply && qui_ply < QUIES_PLY_LIMIT && ! InCheck( turn ) ) )
  72     {
  73       MOVE_CURR = IsMateIn1Ply( turn );
  74       if ( MOVE_CURR )
  75         {
  76           value = score_mate1ply + 1 - ply;
  77
  78           if ( alpha < value
  79                && value < beta ) { pv_close( ptree, ply, mate_search ); }
  80
  81           DOut( "mate found\n" );
  82
  83           assert( is_move_valid( ptree, MOVE_CURR, turn ) );
  84           return value;
  85         }
  86     }
  87
  88
  89   ptree->anext_move[ply].next_phase = next_quies_gencap;
  90   while ( gen_next_quies( ptree, alpha, turn, ply, qui_ply ) )
  91     {
  92       DOut( "\nexpand %s (%" PRIu64 ")",
  93             str_CSA_move(MOVE_CURR), ptree->node_searched );
  94
  95       MakeMove( turn, MOVE_CURR, ply );
  96       if ( InCheck(turn) )
  97         {
  98           UnMakeMove( turn, MOVE_CURR, ply );
  99           continue;
 100         }
 101
 102       value = -search_quies( ptree, -beta, -alpha, Flip(turn), ply+1,
 103                              qui_ply+1 );
 104
 105       UnMakeMove( turn, MOVE_CURR, ply );
 106
 107       if ( alpha < value )
 108         {
 109           check_futile_score_quies( ptree, MOVE_CURR, ptree->stand_pat[ply],
 110                                     -ptree->stand_pat[ply+1], turn );
 111           if ( beta <= value )
 112             {
 113               DOut( ", beta cut (%" PRIu64 ")\n", ptree->node_searched );
 114
 115               assert( ! IsMove(MOVE_CURR)
 116                       || is_move_valid( ptree, MOVE_CURR, turn ) );
 117               return value;
 118             }
 119
 120           DOut( ", renew alpha=%d (%" PRIu64 ")\n",
 121                 value, ptree->node_searched );
 122           alpha = value;
 123         }
 124     }
 125
 126   DOut( "\nall searched (%" PRIu64 ")\n", ptree->node_searched );
 127
 128   if ( qui_ply < QUIES_PLY_LIMIT && is_mate_in3ply( ptree, turn, ply ) )
 129     {
 130       value = score_mate1ply + 1 - ply;
 131
 132       if ( alpha < value
 133            && value < beta ) { pv_close( ptree, ply, mate_search ); }
 134
 135       assert( is_move_valid( ptree, MOVE_CURR, turn ) );
 136       return value;
 137     }
 138
 139   if ( alpha_old != alpha )
 140     {
 141       if ( alpha == ptree->stand_pat[ply] ) { pv_close( ptree, ply, no_rep ); }
 142       else { pv_copy( ptree, ply ); }
 143     }
 144
 145   return alpha;
 146 }
 147
 148
 149 static int
 150 gen_next_quies( tree_t * restrict ptree, int alpha, int turn, int ply,
 151                 int qui_ply )
 152 {
 153   switch ( ptree->anext_move[ply].next_phase )
 154     {
 155     case next_quies_gencap:
 156       {
 157         unsigned int * restrict pmove;
 158         int * restrict psortv;
 159         int i, j, n, nqmove, value, min_score, diff;
 160         unsigned int move;
 161
 162         ptree->move_last[ply] = GenCaptures( turn, ptree->move_last[ply-1] );
 163
 164         /* set sort values */
 165         pmove  = ptree->move_last[ply-1];
 166         psortv = ptree->sort_value;
 167         nqmove = 0;
 168         n      = (int)( ptree->move_last[ply] - pmove );
 169
 170         for ( i = 0; i < n; i++ )
 171           {
 172             move = pmove[i];
 173
 174             if ( qui_ply >= QUIES_PLY_LIMIT
 175                  && ( ( UToCap(move) == pawn && ! I2IsPromote(move) )
 176                       || ( ! UToCap(move) && I2PieceMove(move) != pawn ) ) )
 177               {
 178                 continue;
 179               }
 180
 181             diff      = estimate_score_diff( ptree, move, turn );
 182             min_score = eval_max_score( ptree, move, ptree->stand_pat[ply],
 183                                         turn, diff );
 184
 185             if ( alpha < min_score )
 186               {
 187                 value = swap( ptree, move, -1, MT_CAP_SILVER, turn );
 188                 if ( -1 < value )
 189                   {
 190                     psortv[nqmove]  = value + diff;
 191                     pmove[nqmove++] = move;
 192                   }
 193               }
 194           }
 195
 196         /* insertion sort */
 197         psortv[nqmove] = INT_MIN;
 198         for ( i = nqmove-2; i >= 0; i-- )
 199           {
 200             value = psortv[i];  move = pmove[i];
 201             for ( j = i+1; psortv[j] > value; j++ )
 202               {
 203                 psortv[j-1] = psortv[j];  pmove[j-1] = pmove[j];
 204               }
 205             psortv[j-1] = value;  pmove[j-1] = move;
 206           }
 207
 208         ptree->move_last[ply]             = ptree->move_last[ply-1] + nqmove;
 209         ptree->anext_move[ply].move_last  = pmove;
 210         ptree->anext_move[ply].next_phase = next_quies_captures;
 211       }
 212
 213     case next_quies_captures:
 214       if ( ptree->anext_move[ply].move_last != ptree->move_last[ply] )
 215         {
 216           MOVE_CURR = *ptree->anext_move[ply].move_last++;
 217           return 1;
 218         }
 219     }
 220
 221   return 0;
 222 }