7 gen_next_move( tree_t * restrict ptree, int ply, int turn )
9 switch ( ptree->anext_move[ply].next_phase )
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;
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 );
23 move_hash = ptree->amove_hash[ply];
24 killer1 = ptree->amove_killer[ply].no1;
25 killer2 = ptree->amove_killer[ply].no2;
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++ )
33 sortv = swap( ptree, move, -1, INT_MAX, turn );
34 if ( sortv > value_best )
36 move_second = move_best;
37 value_second = value_best;
41 else if ( sortv > value_second )
46 if ( move == move_hash ) { sortv = INT_MIN; }
47 else if ( UToFromToPromo(move) == killer1 )
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++; }
55 else if ( UToFromToPromo(move) == killer2 )
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++; }
63 else if ( sortv > -1 ) { remaining++; }
68 && killer1 != move_hash
69 && ptree->amove_killer[ply].no1_value > -1
70 && is_move_valid( ptree, killer1, turn ) )
72 *( ptree->move_last[ply]++ ) = killer1;
73 psortv[n++] = ptree->amove_killer[ply].no1_value;
78 && killer2 != move_hash
79 && ptree->amove_killer[ply].no2_value > -1
80 && is_move_valid( ptree, killer2, turn ) )
82 *( ptree->move_last[ply]++ ) = killer2;
83 psortv[n++] = ptree->amove_killer[ply].no2_value;
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;
95 for ( i = n-2; i >= 0; i-- )
97 sortv = psortv[i]; move = pmove[i];
98 for ( j = i+1; psortv[j] > sortv; j++ )
100 psortv[j-1] = psortv[j]; pmove[j-1] = pmove[j];
102 psortv[j-1] = sortv; pmove[j-1] = move;
104 if ( psortv[n-1] == INT_MIN ) { ptree->move_last[ply]--; }
106 #if ! defined(MINIMUM)
107 if ( move_hash && ! is_move_valid( ptree, move_hash, turn ) )
109 out_warning( "An invalid hash move is found!!" );
110 ptree->amove_hash[ply] = move_hash = 0U;
116 if ( move_hash == move_best )
118 ptree->anext_move[ply].phase_done |= phase_cap1;
121 if ( UToFromToPromo(move_hash) == killer1 )
123 ptree->anext_move[ply].phase_done |= phase_killer1;
125 else if ( UToFromToPromo(move_hash) == killer2 )
127 ptree->anext_move[ply].phase_done |= phase_killer2;
129 ptree->anext_move[ply].phase_done |= phase_hash;
130 MOVE_CURR = move_hash;
135 case next_move_capture:
136 if ( ptree->anext_move[ply].remaining-- )
140 MOVE_CURR = move = *(ptree->anext_move[ply].move_last++);
141 if ( move == ptree->anext_move[ply].move_cap1 )
143 ptree->anext_move[ply].phase_done |= phase_cap1;
146 if ( UToFromToPromo(move) == ptree->amove_killer[ply].no1 )
148 ptree->anext_move[ply].phase_done |= phase_killer1;
150 else if ( UToFromToPromo(move) == ptree->amove_killer[ply].no2 )
152 ptree->anext_move[ply].phase_done |= phase_killer2;
158 unsigned int * restrict pmove;
159 unsigned int value_best, value, key, good, tried;
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++ )
170 if ( pmove[i] == ptree->amove_hash[ply]
171 || ( pmove[i] == ptree->amove_killer[ply].no1
172 && ( ptree->anext_move[ply].phase_done
174 || ( pmove[i] == ptree->amove_killer[ply].no2
175 && ( ptree->anext_move[ply].phase_done
176 & phase_killer2 ) ) )
182 if ( UToCap(pmove[i]) ) { continue; }
183 if ( I2IsPromote(pmove[i])
184 && I2PieceMove(pmove[i]) != silver ) { continue; }
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 )
200 ptree->anext_move[ply].phase_done |= phase_history1;
201 ptree->anext_move[ply].next_phase = next_move_history2;
202 MOVE_CURR = pmove[ibest];
208 case next_move_history2:
210 unsigned int * restrict pmove;
211 unsigned int value_best, value, key, good, tried;
214 ptree->anext_move[ply].next_phase = next_move_misc;
217 n = (int)( ptree->move_last[ply] - ptree->anext_move[ply].move_last );
218 pmove = ptree->anext_move[ply].move_last;
220 for ( i = 0; i < n; i++ )
222 if ( UToCap(pmove[i]) ) { continue; }
223 if ( I2IsPromote(pmove[i])
224 && I2PieceMove(pmove[i]) != silver ) { continue; }
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] )
239 ptree->anext_move[ply].phase_done |= phase_history2;
240 MOVE_CURR = pmove[ibest];
247 assert( ptree->anext_move[ply].next_phase == next_move_misc );
248 while ( ptree->anext_move[ply].move_last < ptree->move_last[ply] )
250 if ( *( ptree->anext_move[ply].move_last ) )
252 MOVE_CURR = *(ptree->anext_move[ply].move_last++);
253 ptree->anext_move[ply].phase_done |= phase_misc;
256 ptree->anext_move[ply].move_last++;
264 gen_next_evasion( tree_t * restrict ptree, int ply, int turn )
266 switch ( ptree->anext_move[ply].next_phase )
268 case next_evasion_hash:
269 ptree->move_last[ply] = GenEvasion( turn, ptree->move_last[ply] );
271 if ( ptree->amove_hash[ply] )
273 #if ! defined(MINIMUM)
274 unsigned int * restrict p;
276 for ( p = ptree->move_last[ply-1]; p < ptree->move_last[ply]; p++ )
277 if ( *p == ptree->amove_hash[ply] ) { break; }
279 if ( *p != ptree->amove_hash[ply] )
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;
292 ptree->anext_move[ply].next_phase = next_evasion_genall;
293 ptree->current_move[ply] = ptree->amove_hash[ply];
298 case next_evasion_genall:
300 unsigned int * restrict pmove;
301 int * restrict psortv;
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;
310 for ( i = n-1; i >= 0; i-- )
313 if ( move == ptree->amove_hash[ply] )
318 else if ( I2PieceMove(move) == king )
320 sortv = p_value_ex[UToCap(move)+15] * 2;
323 sortv = swap( ptree, move, INT_MIN, INT_MAX, turn );
324 sortv += estimate_score_diff( ptree, move, turn );
331 for ( i = n-2; i >= 0; i-- )
333 sortv = psortv[i]; move = pmove[i];
334 for ( j = i+1; psortv[j] > sortv; j++ )
336 psortv[j-1] = psortv[j]; pmove[j-1] = pmove[j];
338 psortv[j-1] = sortv; pmove[j-1] = move;
343 assert( ptree->anext_move[ply].next_phase == next_evasion_misc );
344 while ( ptree->anext_move[ply].move_last < ptree->move_last[ply] )
346 if ( *( ptree->anext_move[ply].move_last ) )
348 ptree->current_move[ply] = *(ptree->anext_move[ply].move_last++);
351 ptree->anext_move[ply].move_last++;