Allow setting up position from scratch
[bonanza.git] / 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 }