next.c

   1 #include <stdlib.h>
   2 #include <assert.h>
   3 #include <limits.h>
   4 #include "shogi.h"
   5
   6 int CONV
   7 gen_next_move( tree_t * restrict ptree, int ply, int turn )
   8 {
   9   switch ( ptree->anext_move[ply].next_phase )
  10     {
  11     case next_move_hash:
  12       {
  13         unsigned int * restrict pmove;
  14         int * restrict psortv = ptree->sort_value;
  15         unsigned int move, killer1, killer2, move_hash, move_best, move_second;
  16         int i, j, sortv, n, value_best, value_second, value, remaining;
  17
  18         ptree->anext_move[ply].phase_done = 0;
  19         ptree->anext_move[ply].next_phase = next_move_capture;
  20         ptree->anext_move[ply].move_last  = pmove = ptree->move_last[ply];
  21         ptree->move_last[ply] = GenCaptures( turn, pmove );
  22
  23         move_hash  = ptree->amove_hash[ply];
  24         killer1    = ptree->amove_killer[ply].no1;
  25         killer2    = ptree->amove_killer[ply].no2;
  26         remaining  = 0;
  27         move_best  = move_second  = 0;
  28         value_best = value_second = 0;
  29         n = (int)( ptree->move_last[ply] - pmove );
  30         for ( i = 0; i < n; i++ )
  31           {
  32             move = pmove[i];
  33             sortv = swap( ptree, move, -1, INT_MAX, turn );
  34             if ( sortv > value_best )
  35               {
  36                 move_second  = move_best;
  37                 value_second = value_best;
  38                 value_best = sortv;
  39                 move_best  = move;
  40               }
  41             else if ( sortv > value_second )
  42               {
  43                 move_second  = move;
  44                 value_second = sortv;
  45               }
  46             if ( move == move_hash ) { sortv = INT_MIN; }
  47             else if ( UToFromToPromo(move) == killer1 )
  48               {
  49                 killer1 = 0;
  50                 value = ptree->amove_killer[ply].no1_value
  51                   + p_value_ex[15U+UToCap(move)];
  52                 if ( sortv < value ) { sortv = value; }
  53                 if ( sortv > -1 ) { remaining++; }
  54               }
  55             else if ( UToFromToPromo(move) == killer2 )
  56               {
  57                 killer2 = 0;
  58                 value = ptree->amove_killer[ply].no2_value
  59                   + p_value_ex[15U+UToCap(move)];
  60                 if ( sortv < value ) { sortv = value; }
  61                 if ( sortv > -1 ) { remaining++; }
  62               }
  63             else if ( sortv > -1 ) { remaining++; }
  64             psortv[i] = sortv;
  65           }
  66
  67         if ( killer1
  68              && killer1 != move_hash
  69              && ptree->amove_killer[ply].no1_value > -1
  70              && is_move_valid( ptree, killer1, turn ) )
  71           {
  72             *( ptree->move_last[ply]++ ) = killer1;
  73             psortv[n++] = ptree->amove_killer[ply].no1_value;
  74             remaining++;
  75           }
  76
  77         if ( killer2
  78              && killer2 != move_hash
  79              && ptree->amove_killer[ply].no2_value > -1
  80              && is_move_valid( ptree, killer2, turn ) )
  81           {
  82             *( ptree->move_last[ply]++ ) = killer2;
  83             psortv[n++] = ptree->amove_killer[ply].no2_value;
  84             remaining++;
  85           }
  86
  87         ptree->anext_move[ply].value_cap1 = value_best;
  88         ptree->anext_move[ply].move_cap1  = move_best;
  89         ptree->anext_move[ply].value_cap2 = value_second;
  90         ptree->anext_move[ply].move_cap2  = move_second;
  91         ptree->anext_move[ply].remaining  = remaining;
  92
  93         /* insertion sort */
  94         psortv[n] = INT_MIN;
  95         for ( i = n-2; i >= 0; i-- )
  96           {
  97             sortv = psortv[i];  move = pmove[i];
  98             for ( j = i+1; psortv[j] > sortv; j++ )
  99               {
 100                 psortv[j-1] = psortv[j];  pmove[j-1] = pmove[j];
 101               }
 102             psortv[j-1] = sortv;  pmove[j-1] = move;
 103           }
 104         if ( psortv[n-1] == INT_MIN ) { ptree->move_last[ply]--; }
 105
 106 #if ! defined(MINIMUM)
 107         if ( move_hash && ! is_move_valid( ptree, move_hash, turn ) )
 108           {
 109             out_warning( "An invalid hash move is found!!" );
 110             ptree->amove_hash[ply] = move_hash = 0U;
 111           }
 112 #endif
 113
 114         if ( move_hash )
 115           {
 116             if ( move_hash == move_best )
 117               {
 118                 ptree->anext_move[ply].phase_done |= phase_cap1;
 119               }
 120
 121             if ( UToFromToPromo(move_hash) == killer1 )
 122               {
 123                 ptree->anext_move[ply].phase_done |= phase_killer1;
 124               }
 125             else if ( UToFromToPromo(move_hash) == killer2 )
 126               {
 127                 ptree->anext_move[ply].phase_done |= phase_killer2;
 128               }
 129             ptree->anext_move[ply].phase_done |= phase_hash;
 130             MOVE_CURR = move_hash;
 131             return 1;
 132           }
 133       }
 134
 135     case next_move_capture:
 136       if ( ptree->anext_move[ply].remaining-- )
 137         {
 138           unsigned int move;
 139
 140           MOVE_CURR = move = *(ptree->anext_move[ply].move_last++);
 141           if ( move == ptree->anext_move[ply].move_cap1 )
 142             {
 143               ptree->anext_move[ply].phase_done |= phase_cap1;
 144             }
 145
 146           if ( UToFromToPromo(move) == ptree->amove_killer[ply].no1 )
 147             {
 148               ptree->anext_move[ply].phase_done |= phase_killer1;
 149             }
 150           else if ( UToFromToPromo(move) == ptree->amove_killer[ply].no2 )
 151             {
 152               ptree->anext_move[ply].phase_done |= phase_killer2;
 153             }
 154           return 1;
 155         }
 156
 157       {
 158         unsigned int * restrict pmove;
 159         unsigned int value_best, value, key, good, tried;
 160         int i, n, ibest;
 161
 162         value_best =  0;
 163         ibest      = -1;
 164         ptree->move_last[ply] = GenNoCaptures( turn, ptree->move_last[ply] );
 165         ptree->move_last[ply] = GenDrop( turn, ptree->move_last[ply] );
 166
 167         n = (int)( ptree->move_last[ply] - ptree->anext_move[ply].move_last );
 168         pmove = ptree->anext_move[ply].move_last;
 169         for ( i = 0; i < n; i++ )
 170           {
 171             if ( pmove[i] == ptree->amove_hash[ply]
 172                  || ( pmove[i] == ptree->amove_killer[ply].no1
 173                       && ( ptree->anext_move[ply].phase_done
 174                            & phase_killer1 ) )
 175                  || ( pmove[i] == ptree->amove_killer[ply].no2
 176                       && ( ptree->anext_move[ply].phase_done
 177                            & phase_killer2 ) ) )
 178               {
 179                 pmove[i] = 0;
 180                 continue;
 181               }
 182
 183             if ( UToCap(pmove[i]) ) { continue; }
 184             if ( I2IsPromote(pmove[i])
 185                  && I2PieceMove(pmove[i]) != silver ) { continue; }
 186
 187
 188             key   = phash( pmove[i], turn );
 189             good  = ptree->hist_good[key]  + 1;
 190             tried = ptree->hist_tried[key] + 2;
 191             value = ( good * 8192U ) / tried;
 192             if ( value > value_best )
 193               {
 194                 value_best = value;
 195                 ibest      = i;
 196               }
 197           }
 198
 199         if ( ibest >= 0 )
 200           {
 201             ptree->anext_move[ply].phase_done |= phase_history1;
 202             ptree->anext_move[ply].next_phase  = next_move_history2;
 203             MOVE_CURR  = pmove[ibest];
 204             pmove[ibest] = 0;
 205             return 1;
 206           }
 207       }
 208
 209     case next_move_history2:
 210       {
 211         unsigned int * restrict pmove;
 212         unsigned int value_best, value, key, good, tried;
 213         int ibest, i, n;
 214
 215         ptree->anext_move[ply].next_phase = next_move_misc;
 216         value_best = 0;
 217         ibest      = -1;
 218         n = (int)( ptree->move_last[ply] - ptree->anext_move[ply].move_last );
 219         pmove = ptree->anext_move[ply].move_last;
 220
 221         for ( i = 0; i < n; i++ )
 222           {
 223             if ( UToCap(pmove[i]) ) { continue; }
 224             if ( I2IsPromote(pmove[i])
 225                  && I2PieceMove(pmove[i]) != silver ) { continue; }
 226
 227             key   = phash( pmove[i], turn );
 228             good  = ptree->hist_good[key]  + 1;
 229             tried = ptree->hist_tried[key] + 2;
 230             value = ( good * 8192U ) / tried;
 231             if ( value > value_best && pmove[i] )
 232               {
 233                 value_best = value;
 234                 ibest      = i;
 235               }
 236           }
 237
 238         if ( ibest >= 0 )
 239           {
 240             ptree->anext_move[ply].phase_done |= phase_history2;
 241             MOVE_CURR  = pmove[ibest];
 242             pmove[ibest] = 0;
 243             return 1;
 244           }
 245       }
 246
 247     default:
 248       assert( ptree->anext_move[ply].next_phase == next_move_misc );
 249       while ( ptree->anext_move[ply].move_last < ptree->move_last[ply] )
 250         {
 251           if ( *( ptree->anext_move[ply].move_last ) )
 252             {
 253               MOVE_CURR = *(ptree->anext_move[ply].move_last++);
 254               ptree->anext_move[ply].phase_done |= phase_misc;
 255               return 1;
 256             }
 257           ptree->anext_move[ply].move_last++;
 258         }
 259     }
 260   return 0;
 261 }
 262
 263
 264 int CONV
 265 gen_next_evasion( tree_t * restrict ptree, int ply, int turn )
 266 {
 267   switch ( ptree->anext_move[ply].next_phase )
 268     {
 269     case next_evasion_hash:
 270       ptree->move_last[ply] = GenEvasion( turn, ptree->move_last[ply] );
 271
 272       if ( ptree->amove_hash[ply] )
 273         {
 274 #if ! defined(MINIMUM)
 275           unsigned int * restrict p;
 276
 277           for ( p = ptree->move_last[ply-1]; p < ptree->move_last[ply]; p++ )
 278             if ( *p == ptree->amove_hash[ply] ) { break; }
 279
 280           if ( *p != ptree->amove_hash[ply] )
 281             {
 282               out_warning( "An invalid hash evasion-move is found!!" );
 283               out_board( ptree, stdout, 0, 0 );
 284               Out( "%c%s\n", ach_turn[turn],
 285                    str_CSA_move(ptree->amove_hash[ply]) );
 286               Out( "hash key = %" PRIu64 ", hand = %u, turn = %d\n",
 287                    HASH_KEY, HAND_B, turn );
 288               ptree->amove_hash[ply] = 0U;
 289             }
 290           else
 291 #endif
 292             {
 293               ptree->anext_move[ply].next_phase = next_evasion_genall;
 294               ptree->current_move[ply]          = ptree->amove_hash[ply];
 295               return 1;
 296             }
 297         }
 298
 299     case next_evasion_genall:
 300       {
 301         unsigned int * restrict pmove;
 302         int * restrict psortv;
 303         unsigned int move;
 304         int n, i, j, sortv;
 305
 306         ptree->anext_move[ply].next_phase = next_evasion_misc;
 307         ptree->anext_move[ply].move_last = pmove = ptree->move_last[ply-1];
 308         n = (int)( ptree->move_last[ply] - pmove );
 309         psortv = ptree->sort_value;
 310
 311         for ( i = n-1; i >= 0; i-- )
 312           {
 313             move = pmove[i];
 314             if ( move == ptree->amove_hash[ply] )
 315               {
 316                 sortv    = INT_MIN;
 317                 pmove[i] = 0;
 318               }
 319             else if ( I2PieceMove(move) == king )
 320               {
 321                 sortv = p_value_ex[UToCap(move)+15] * 2;
 322               }
 323             else {
 324               sortv  = swap( ptree, move, INT_MIN, INT_MAX, turn );
 325               sortv += estimate_score_diff( ptree, move, turn );
 326             }
 327             psortv[i] = sortv;
 328           }
 329
 330         /* insertion sort */
 331         psortv[n] = INT_MIN;
 332         for ( i = n-2; i >= 0; i-- )
 333           {
 334             sortv = psortv[i];  move = pmove[i];
 335             for ( j = i+1; psortv[j] > sortv; j++ )
 336               {
 337                 psortv[j-1] = psortv[j];  pmove[j-1] = pmove[j];
 338               }
 339             psortv[j-1] = sortv;  pmove[j-1] = move;
 340           }
 341       }
 342
 343     default:
 344       assert( ptree->anext_move[ply].next_phase == next_evasion_misc );
 345       while ( ptree->anext_move[ply].move_last < ptree->move_last[ply] )
 346         {
 347           if ( *( ptree->anext_move[ply].move_last ) )
 348             {
 349               MOVE_CURR = *(ptree->anext_move[ply].move_last++);
 350               return 1;
 351             }
 352           ptree->anext_move[ply].move_last++;
 353         }
 354     }
 355   return 0;
 356 }