next.c

   1 #include <stdlib.h>
   2 #include <assert.h>
   3 #include <limits.h>
   4 #include "shogi.h"
   5
   6 int
   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         n = (int)( ptree->move_last[ply] - ptree->anext_move[ply].move_last );
 167         pmove = ptree->anext_move[ply].move_last;
 168         for ( i = 0; i < n; i++ )
 169           {
 170             if ( pmove[i] == ptree->amove_hash[ply]
 171                  || ( pmove[i] == ptree->amove_killer[ply].no1
 172                       && ( ptree->anext_move[ply].phase_done
 173                            & phase_killer1 ) )
 174                  || ( pmove[i] == ptree->amove_killer[ply].no2
 175                       && ( ptree->anext_move[ply].phase_done
 176                            & phase_killer2 ) ) )
 177               {
 178                 pmove[i] = 0;
 179                 continue;
 180               }
 181
 182             if ( UToCap(pmove[i]) ) { continue; }
 183             if ( I2IsPromote(pmove[i])
 184                  && I2PieceMove(pmove[i]) != silver ) { continue; }
 185
 186
 187             key   = phash( pmove[i], turn );
 188             good  = ptree->hist_good[key]  + 1;
 189             tried = ptree->hist_tried[key] + 2;
 190             value = ( good * 8192U ) / tried;
 191             if ( value > value_best )
 192               {
 193                 value_best = value;
 194                 ibest      = i;
 195               }
 196           }
 197
 198         if ( ibest >= 0 )
 199           {
 200             ptree->anext_move[ply].phase_done |= phase_history1;
 201             ptree->anext_move[ply].next_phase  = next_move_history2;
 202             MOVE_CURR  = pmove[ibest];
 203             pmove[ibest] = 0;
 204             return 1;
 205           }
 206       }
 207
 208     case next_move_history2:
 209       {
 210         unsigned int * restrict pmove;
 211         unsigned int value_best, value, key, good, tried;
 212         int ibest, i, n;
 213
 214         ptree->anext_move[ply].next_phase = next_move_misc;
 215         value_best = 0;
 216         ibest      = -1;
 217         n = (int)( ptree->move_last[ply] - ptree->anext_move[ply].move_last );
 218         pmove = ptree->anext_move[ply].move_last;
 219
 220         for ( i = 0; i < n; i++ )
 221           {
 222             if ( UToCap(pmove[i]) ) { continue; }
 223             if ( I2IsPromote(pmove[i])
 224                  && I2PieceMove(pmove[i]) != silver ) { continue; }
 225
 226             key   = phash( pmove[i], turn );
 227             good  = ptree->hist_good[key]  + 1;
 228             tried = ptree->hist_tried[key] + 2;
 229             value = ( good * 8192U ) / tried;
 230             if ( value > value_best && pmove[i] )
 231               {
 232                 value_best = value;
 233                 ibest      = i;
 234               }
 235           }
 236
 237         if ( ibest >= 0 )
 238           {
 239             ptree->anext_move[ply].phase_done |= phase_history2;
 240             MOVE_CURR  = pmove[ibest];
 241             pmove[ibest] = 0;
 242             return 1;
 243           }
 244       }
 245
 246     default:
 247       assert( ptree->anext_move[ply].next_phase == next_move_misc );
 248       while ( ptree->anext_move[ply].move_last < ptree->move_last[ply] )
 249         {
 250           if ( *( ptree->anext_move[ply].move_last ) )
 251             {
 252               MOVE_CURR = *(ptree->anext_move[ply].move_last++);
 253               ptree->anext_move[ply].phase_done |= phase_misc;
 254               return 1;
 255             }
 256           ptree->anext_move[ply].move_last++;
 257         }
 258     }
 259   return 0;
 260 }
 261
 262
 263 int
 264 gen_next_evasion( tree_t * restrict ptree, int ply, int turn )
 265 {
 266   switch ( ptree->anext_move[ply].next_phase )
 267     {
 268     case next_evasion_hash:
 269       ptree->move_last[ply] = GenEvasion( turn, ptree->move_last[ply] );
 270
 271       if ( ptree->amove_hash[ply] )
 272         {
 273 #if ! defined(MINIMUM)
 274           unsigned int * restrict p;
 275
 276           for ( p = ptree->move_last[ply-1]; p < ptree->move_last[ply]; p++ )
 277             if ( *p == ptree->amove_hash[ply] ) { break; }
 278
 279           if ( *p != ptree->amove_hash[ply] )
 280             {
 281               out_warning( "An invalid hash evasion-move is found!!" );
 282               out_board( ptree, stdout, 0, 0 );
 283               Out( "%c%s\n", ach_turn[turn],
 284                    str_CSA_move(ptree->amove_hash[ply]) );
 285               Out( "hash key = %" PRIu64 ", hand = %u, turn = %d\n",
 286                    HASH_KEY, HAND_B, turn );
 287               ptree->amove_hash[ply] = 0U;
 288             }
 289           else
 290 #endif
 291             {
 292               ptree->anext_move[ply].next_phase = next_evasion_genall;
 293               ptree->current_move[ply]          = ptree->amove_hash[ply];
 294               return 1;
 295             }
 296         }
 297
 298     case next_evasion_genall:
 299       {
 300         unsigned int * restrict pmove;
 301         int * restrict psortv;
 302         unsigned int move;
 303         int n, i, j, sortv;
 304
 305         ptree->anext_move[ply].next_phase = next_evasion_misc;
 306         ptree->anext_move[ply].move_last = pmove = ptree->move_last[ply-1];
 307         n = (int)( ptree->move_last[ply] - pmove );
 308         psortv = ptree->sort_value;
 309
 310         for ( i = n-1; i >= 0; i-- )
 311           {
 312             move = pmove[i];
 313             if ( move == ptree->amove_hash[ply] )
 314               {
 315                 sortv    = INT_MIN;
 316                 pmove[i] = 0;
 317               }
 318             else if ( I2PieceMove(move) == king )
 319               {
 320                 sortv = p_value_ex[UToCap(move)+15] * 2;
 321               }
 322             else {
 323               sortv  = swap( ptree, move, INT_MIN, INT_MAX, turn );
 324               sortv += estimate_score_diff( ptree, move, turn );
 325             }
 326             psortv[i] = sortv;
 327           }
 328
 329         /* insertion sort */
 330         psortv[n] = INT_MIN;
 331         for ( i = n-2; i >= 0; i-- )
 332           {
 333             sortv = psortv[i];  move = pmove[i];
 334             for ( j = i+1; psortv[j] > sortv; j++ )
 335               {
 336                 psortv[j-1] = psortv[j];  pmove[j-1] = pmove[j];
 337               }
 338             psortv[j-1] = sortv;  pmove[j-1] = move;
 339           }
 340       }
 341
 342     default:
 343       assert( ptree->anext_move[ply].next_phase == next_evasion_misc );
 344       while ( ptree->anext_move[ply].move_last < ptree->move_last[ply] )
 345         {
 346           if ( *( ptree->anext_move[ply].move_last ) )
 347             {
 348               ptree->current_move[ply] = *(ptree->anext_move[ply].move_last++);
 349               return 1;
 350             }
 351           ptree->anext_move[ply].move_last++;
 352         }
 353     }
 354   return 0;
 355 }