6 enum { mate_king_cap_checker = 0,
13 mate_intercept_move_gen,
15 mate_intercept_weak_move,
16 mate_intercept_drop_sup };
18 static int CONV mate3_and( tree_t * restrict ptree, int turn, int ply,
20 static void CONV checker( const tree_t * restrict ptree, char *psq, int turn );
21 static unsigned int CONV gen_king_cap_checker( const tree_t * restrict ptree,
23 static int CONV mate_weak_or( tree_t * restrict ptree, int turn, int ply,
25 static unsigned int * CONV gen_move_to( const tree_t * restrict ptree, int sq,
27 unsigned int * restrict pmove );
28 static unsigned int * CONV gen_king_move( const tree_t * restrict ptree,
29 const char *psq, int turn,
31 unsigned int * restrict pmove );
32 static unsigned int * CONV gen_intercept( tree_t * restrict __ptree__,
33 int sq_checker, int ply, int turn,
34 int * restrict premaining,
35 unsigned int * restrict pmove,
37 static int CONV gen_next_evasion_mate( tree_t * restrict ptree,
38 const char *psq, int ply, int turn,
41 static uint64_t mate3_hash_tbl[ MATE3_MASK + 1 ] = {0};
44 mhash_probe( tree_t * restrict ptree, int turn, int ply )
46 uint64_t key_current, key, word;
49 word = mate3_hash_tbl[ (unsigned int)HASH_KEY & MATE3_MASK ];
50 #if ! defined(__x86_64__)
54 key = word & ~(uint64_t)0x7ffffU;
55 key_current = HASH_KEY & ~(uint64_t)0x7ffffU;
56 key_current ^= (uint64_t)HAND_B << 42;
57 key_current ^= (uint64_t)turn << 63;
59 if ( key != key_current ) { return 0; }
61 move = (unsigned int)word & 0x7ffffU;
62 if ( move != MOVE_NA )
64 move |= turn ? Cap2Move( BOARD[I2To(move)])
65 : Cap2Move(-BOARD[I2To(move)]);
75 mhash_store( const tree_t * restrict ptree, int turn, unsigned int move )
79 word = HASH_KEY & ~(uint64_t)0x7ffffU;
80 word |= (uint64_t)( move & 0x7ffffU );
81 word ^= (uint64_t)HAND_B << 42;
82 word ^= (uint64_t)turn << 63;
84 #if ! defined(__x86_64__)
87 mate3_hash_tbl[ (unsigned int)HASH_KEY & MATE3_MASK ] = word;
92 is_mate_in3ply( tree_t * restrict ptree, int turn, int ply )
96 if ( mhash_probe( ptree, turn, ply ) )
98 if ( MOVE_CURR == MOVE_NA ) { return 0; }
102 if ( ply >= PLY_MAX-2 ) { return 0; }
106 ptree->anext_move[ply].move_last = ptree->move_last[ply-1];
107 ptree->move_last[ply] = GenCheck( turn, ptree->move_last[ply-1] );
109 while ( ptree->anext_move[ply].move_last != ptree->move_last[ply] )
111 MOVE_CURR = *ptree->anext_move[ply].move_last++;
113 if ( MOVE_CURR & MOVE_CHK_CLEAR ) { flag_skip = 0; }
114 if ( flag_skip ) { continue; }
116 assert( is_move_valid( ptree, MOVE_CURR, turn ) );
117 MakeMove( turn, MOVE_CURR, ply );
120 UnMakeMove( turn, MOVE_CURR, ply );
124 value = mate3_and( ptree, Flip(turn), ply+1, 0 );
126 UnMakeMove( turn, MOVE_CURR, ply );
130 mhash_store( ptree, turn, MOVE_CURR );
134 if ( ( MOVE_CURR & MOVE_CHK_SET )
135 && I2To(MOVE_CURR) != I2To(ptree->current_move[ply+1]) )
141 mhash_store( ptree, turn, MOVE_NA );
147 mate3_and( tree_t * restrict ptree, int turn, int ply, int flag )
152 assert( InCheck(turn) );
154 ptree->anext_move[ply].next_phase = mate_king_cap_checker;
155 checker( ptree, asq, turn );
157 while ( gen_next_evasion_mate( ptree, asq, ply, turn, flag ) ) {
159 if ( ptree->anext_move[ply].next_phase == mate_intercept_drop_sup )
164 MakeMove( turn, MOVE_CURR, ply );
165 assert( ! InCheck(turn) );
167 if ( InCheck( Flip(turn) ) ) { move = 0; }
168 else { move = IsMateIn1Ply( Flip(turn) ); }
171 && ptree->anext_move[ply].next_phase == mate_intercept_weak_move )
173 assert( asq[1] == nsquare );
174 move = (unsigned int)mate_weak_or( ptree, Flip(turn), ply+1, asq[0],
178 UnMakeMove( turn, MOVE_CURR, ply );
180 if ( ! move ) { return 0; }
188 mate_weak_or( tree_t * restrict ptree, int turn, int ply, int from,
191 int idirec, pc, pc_cap, value, flag;
193 if ( ply >= PLY_MAX-2 ) { return 0; }
197 if ( IsDiscoverWK( from, to ) ) { return 0; }
201 MOVE_CURR = ( To2Move(to) | From2Move(from)
202 | Piece2Move(pc) | Cap2Move(pc_cap) );
203 if ( ( pc == bishop || pc == rook )
204 && ( to > I4 || from > I4 ) ) { MOVE_CURR |= FLAG_PROMO; }
207 if ( IsDiscoverBK( from, to ) ) { return 0; }
211 MOVE_CURR = ( To2Move(to) | From2Move(from) | Piece2Move(pc)
212 | Cap2Move(pc_cap) );
213 if ( ( pc == bishop || pc == rook )
214 && ( to < A6 || from < A6 ) ) { MOVE_CURR |= FLAG_PROMO; }
217 MakeMove( turn, MOVE_CURR, ply );
218 if ( I2From(MOVE_LAST) < nsquare )
222 UnMakeMove( turn, MOVE_CURR, ply );
228 assert( ! InCheck(turn) );
232 ptree->move_last[ply] = ptree->move_last[ply-1];
233 value = mate3_and( ptree, Flip(turn), ply+1, flag );
235 UnMakeMove( turn, MOVE_CURR, ply );
242 gen_next_evasion_mate( tree_t * restrict ptree, const char *psq, int ply,
245 switch ( ptree->anext_move[ply].next_phase )
247 case mate_king_cap_checker:
248 ptree->anext_move[ply].next_phase = mate_cap_checker_gen;
249 MOVE_CURR = gen_king_cap_checker( ptree, psq[0], turn );
250 if ( MOVE_CURR ) { return 1; }
252 case mate_cap_checker_gen:
253 ptree->anext_move[ply].next_phase = mate_cap_checker;
254 ptree->anext_move[ply].move_last = ptree->move_last[ply-1];
255 ptree->move_last[ply] = ptree->move_last[ply-1];
256 if ( psq[1] == nsquare )
258 ptree->move_last[ply]
259 = gen_move_to( ptree, psq[0], turn, ptree->move_last[ply-1] );
262 case mate_cap_checker:
263 if ( ptree->anext_move[ply].move_last != ptree->move_last[ply] )
265 MOVE_CURR = *(ptree->anext_move[ply].move_last++);
269 case mate_king_cap_gen:
270 ptree->anext_move[ply].next_phase = mate_king_cap;
271 ptree->anext_move[ply].move_last = ptree->move_last[ply-1];
272 ptree->move_last[ply]
273 = gen_king_move( ptree, psq, turn, 1, ptree->move_last[ply-1] );
276 if ( ptree->anext_move[ply].move_last != ptree->move_last[ply] )
278 MOVE_CURR = *(ptree->anext_move[ply].move_last++);
282 case mate_king_move_gen:
283 ptree->anext_move[ply].next_phase = mate_king_move;
284 ptree->anext_move[ply].move_last = ptree->move_last[ply-1];
285 ptree->move_last[ply]
286 = gen_king_move( ptree, psq, turn, 0, ptree->move_last[ply-1] );
289 if ( ptree->anext_move[ply].move_last != ptree->move_last[ply] )
291 MOVE_CURR = *(ptree->anext_move[ply].move_last++);
295 case mate_intercept_move_gen:
296 ptree->anext_move[ply].remaining = 0;
297 ptree->anext_move[ply].next_phase = mate_intercept_move;
298 ptree->anext_move[ply].move_last = ptree->move_last[ply-1];
299 ptree->move_last[ply] = ptree->move_last[ply-1];
300 if ( psq[1] == nsquare && abs(BOARD[(int)psq[0]]) != knight )
303 ptree->move_last[ply] = gen_intercept( ptree, psq[0], ply, turn, &n,
304 ptree->move_last[ply-1],
308 ptree->anext_move[ply].next_phase = mate_intercept_drop_sup;
309 ptree->anext_move[ply].remaining = 0;
310 MOVE_CURR = *(ptree->anext_move[ply].move_last++);
314 ptree->anext_move[ply].remaining = n;
317 case mate_intercept_move:
318 if ( ptree->anext_move[ply].remaining-- )
320 MOVE_CURR = *(ptree->anext_move[ply].move_last++);
323 ptree->anext_move[ply].next_phase = mate_intercept_weak_move;
325 case mate_intercept_weak_move:
326 if ( ptree->anext_move[ply].move_last != ptree->move_last[ply] )
328 MOVE_CURR = *(ptree->anext_move[ply].move_last++);
342 checker( const tree_t * restrict ptree, char *psq, int turn )
345 int n, sq0, sq1, sq_king;
350 bb = b_attacks_to_piece( ptree, sq_king );
354 bb = w_attacks_to_piece( ptree, sq_king );
358 assert( BBTest(bb) );
366 if ( BBContract( abb_king_attacks[sq_king], abb_mask[sq1] ) )
379 static unsigned int CONV
380 gen_king_cap_checker( const tree_t * restrict ptree, int to, int turn )
388 if ( ! BBContract( abb_king_attacks[from],
389 abb_mask[to] ) ) { return 0;}
390 if ( is_white_attacked( ptree, to ) ) { return 0; }
391 move = Cap2Move(BOARD[to]);
395 if ( ! BBContract( abb_king_attacks[from],
396 abb_mask[to] ) ) { return 0;}
397 if ( is_black_attacked( ptree, to ) ) { return 0; }
398 move = Cap2Move(-BOARD[to]);
400 move |= To2Move(to) | From2Move(from) | Piece2Move(king);
406 static unsigned int * CONV
407 gen_move_to( const tree_t * restrict ptree, int to, int turn,
408 unsigned int * restrict pmove )
411 int direc, from, pc, flag_promo, flag_unpromo;
415 bb = w_attacks_to_piece( ptree, to );
416 BBNotAnd( bb, bb, abb_mask[SQ_WKING] );
419 from = LastOne( bb );
422 direc = (int)adirec[SQ_WKING][from];
423 if ( direc && is_pinned_on_white_king( ptree, from, direc ) )
434 if ( to > I4 ) { flag_promo = 1; flag_unpromo = 0; }
437 case lance: case knight:
438 if ( to > I3 ) { flag_promo = 1; flag_unpromo = 0; }
439 else if ( to > I4 ) { flag_promo = 1; }
443 if ( to > I4 || from > I4 ) { flag_promo = 1; }
446 case bishop: case rook:
448 || from > I4 ) { flag_promo = 1; flag_unpromo = 0; }
454 assert( flag_promo || flag_unpromo );
457 *pmove++ = ( From2Move(from) | To2Move(to) | FLAG_PROMO
458 | Piece2Move(pc) | Cap2Move(BOARD[to]) );
462 *pmove++ = ( From2Move(from) | To2Move(to)
463 | Piece2Move(pc) | Cap2Move(BOARD[to]) );
468 bb = b_attacks_to_piece( ptree, to );
469 BBNotAnd( bb, bb, abb_mask[SQ_BKING] );
472 from = FirstOne( bb );
475 direc = (int)adirec[SQ_BKING][from];
476 if ( direc && is_pinned_on_black_king( ptree, from, direc ) )
487 if ( to < A6 ) { flag_promo = 1; flag_unpromo = 0; }
490 case lance: case knight:
491 if ( to < A7 ) { flag_promo = 1; flag_unpromo = 0; }
492 else if ( to < A6 ) { flag_promo = 1; }
496 if ( to < A6 || from < A6 ) { flag_promo = 1; }
499 case bishop: case rook:
501 || from < A6 ) { flag_promo = 1; flag_unpromo = 0; }
507 assert( flag_promo || flag_unpromo );
510 *pmove++ = ( From2Move(from) | To2Move(to) | FLAG_PROMO
511 | Piece2Move(pc) | Cap2Move(-BOARD[to]) );
515 *pmove++ = ( From2Move(from) | To2Move(to)
516 | Piece2Move(pc) | Cap2Move(-BOARD[to]) );
525 static unsigned int * CONV
526 gen_king_move( const tree_t * restrict ptree, const char *psq, int turn,
527 int is_capture, unsigned int * restrict pmove )
535 bb = abb_king_attacks[from];
538 BBAnd( bb, bb, BB_BOCCUPY );
539 BBNotAnd( bb, bb, abb_mask[(int)psq[0]] );
541 else { BBNotAnd( bb, bb, BB_BOCCUPY ); }
542 BBNotAnd( bb, bb, BB_WOCCUPY );
546 bb = abb_king_attacks[from];
549 BBAnd( bb, bb, BB_WOCCUPY );
550 BBNotAnd( bb, bb, abb_mask[(int)psq[0]] );
552 else { BBNotAnd( bb, bb, BB_WOCCUPY ); }
553 BBNotAnd( bb, bb, BB_BOCCUPY );
561 if ( psq[1] != nsquare
562 && ( adirec[from][(int)psq[1]]
563 == adirec[from][to] ) ) { continue; }
566 && adirec[from][(int)psq[0]] == adirec[from][to] ) {
567 if ( adirec[from][(int)psq[0]] & flag_cross )
569 if ( abs(BOARD[(int)psq[0]]) == lance
570 || abs(BOARD[(int)psq[0]]) == rook
571 || abs(BOARD[(int)psq[0]]) == dragon ) { continue; }
573 else if ( ( adirec[from][(int)psq[0]] & flag_diag )
574 && ( abs(BOARD[(int)psq[0]]) == bishop
575 || abs(BOARD[(int)psq[0]]) == horse ) ){ continue; }
580 if ( is_white_attacked( ptree, to ) ) { continue; }
582 *pmove++ = ( From2Move(from) | To2Move(to)
583 | Piece2Move(king) | Cap2Move(BOARD[to]) );
586 if ( is_black_attacked( ptree, to ) ) { continue; }
588 *pmove++ = ( From2Move(from) | To2Move(to)
589 | Piece2Move(king) | Cap2Move(-BOARD[to]) );
597 static unsigned int * CONV
598 gen_intercept( tree_t * restrict __ptree__, int sq_checker, int ply, int turn,
599 int * restrict premaining, unsigned int * restrict pmove,
602 #define Drop(pc) ( To2Move(to) | Drop2Move(pc) )
604 const tree_t * restrict ptree = __ptree__;
605 bitboard_t bb_atk, bb_defender, bb;
606 unsigned int amove[16];
608 int n0, n1, inc, pc, sq_k, to, from, direc, nmove, nsup, i, min_chuai, itemp;
609 int dist, flag_promo, flag_unpromo;
615 bb_defender = BB_WOCCUPY;
616 BBNotAnd( bb_defender, bb_defender, abb_mask[sq_k] );
620 bb_defender = BB_BOCCUPY;
621 BBNotAnd( bb_defender, bb_defender, abb_mask[sq_k] );
624 switch ( adirec[sq_k][sq_checker] )
627 min_chuai = ( sq_k < A8 || I2 < sq_k ) ? 2 : 4;
637 itemp = (int)aifile[sq_k];
638 min_chuai = ( itemp == file1 || itemp == file9 ) ? 2 : 4;
643 assert( (int)adirec[sq_k][sq_checker] == direc_diag2 );
647 if ( sq_k > sq_checker ) { inc = -inc; }
649 for ( dist = 1, to = sq_k + inc;
651 dist += 1, to += inc ) {
653 assert( 0 <= to && to < nsquare && BOARD[to] == empty );
656 bb_atk = attacks_to_piece( ptree, to );
657 BBAnd( bb, bb_defender, bb_atk );
660 from = LastOne( bb );
663 direc = (int)adirec[sq_k][from];
668 if ( direc && is_pinned_on_white_king( ptree, from, direc ) )
676 if ( to > I4 ) { flag_promo = 1; flag_unpromo = 0; }
679 case lance: case knight:
680 if ( to > I3 ) { flag_promo = 1; flag_unpromo = 0; }
681 else if ( to > I4 ) { flag_promo = 1; }
685 if ( to > I4 || from > I4 ) { flag_promo = 1; }
688 case bishop: case rook:
690 || from > I4 ) { flag_promo = 1; flag_unpromo = 0; }
698 if ( direc && is_pinned_on_black_king( ptree, from, direc ) )
706 if ( to < A6 ) { flag_promo = 1; flag_unpromo = 0; }
709 case lance: case knight:
710 if ( to < A7 ) { flag_promo = 1; flag_unpromo = 0; }
711 else if ( to < A6 ) { flag_promo = 1; }
715 if ( to < A6 || from < A6 ) { flag_promo = 1; }
718 case bishop: case rook:
720 || from < A6 ) { flag_promo = 1; flag_unpromo = 0; }
727 assert( flag_promo || flag_unpromo );
730 amove[nmove++] = ( From2Move(from) | To2Move(to)
731 | FLAG_PROMO | Piece2Move(pc) );
735 amove[nmove++] = ( From2Move(from) | To2Move(to)
740 nsup = ( to == sq_k + inc ) ? nmove + 1 : nmove;
743 for ( i = n0 + n1 - 1; i >= n0; i-- ) { pmove[i+nmove] = pmove[i]; }
744 for ( i = 0; i < nmove; i++ ) { pmove[n0++] = amove[i]; }
746 else if ( nmove ) { pmove[n0 + n1++] = amove[0]; }
750 /* - tentative assumption - */
751 /* no recursive drops at non-supported square. */
752 if ( flag == 2 ) { continue; }
754 /* -tentative assumption- */
755 /* no intercept-drop at non-supported square. */
756 if ( (int)I2To(MOVE_LAST) == sq_checker
757 && dist > min_chuai ) { continue; }
768 if ( IsHandRook(hand) ) { amove[nmove++] = Drop(rook); }
769 else if ( IsHandLance(hand) && to < A1 )
771 amove[nmove++] = Drop(lance);
773 else if ( IsHandPawn(hand)
775 && ! ( BBToU(BB_WPAWN) & ( mask_file1 >> aifile[to] ) )
776 && ! IsMateWPawnDrop( __ptree__, to ) )
778 amove[nmove++] = Drop(pawn);
783 if ( IsHandPawn(hand)
785 && ! ( BBToU(BB_WPAWN) & ( mask_file1 >> aifile[to] ) )
786 && ! IsMateWPawnDrop( __ptree__, to ) )
788 amove[nmove++] = Drop(pawn);
790 if ( IsHandLance(hand) && to < A1 ) { amove[nmove++] = Drop(lance); }
791 if ( IsHandRook(hand) ) { amove[nmove++] = Drop(rook); }
794 if ( IsHandKnight(hand) && to < A2 ) { amove[nmove++] = Drop(knight); }
802 if ( IsHandRook(hand) ) { amove[nmove++] = Drop(rook); }
803 else if ( IsHandLance(hand) && to > I9 )
805 amove[nmove++] = Drop(lance);
807 else if ( IsHandPawn(hand)
809 && ! ( BBToU(BB_BPAWN) & ( mask_file1 >> aifile[to] ) )
810 && ! IsMateBPawnDrop( __ptree__, to ) )
812 amove[nmove++] = Drop(pawn);
817 if ( IsHandPawn(hand)
819 && ! ( BBToU(BB_BPAWN) & ( mask_file1 >> aifile[to] ) )
820 && ! IsMateBPawnDrop( __ptree__, to ) )
822 amove[nmove++] = Drop(pawn);
824 if ( IsHandLance(hand) && to > I9 ) { amove[nmove++] = Drop(lance); }
825 if ( IsHandRook(hand) ) { amove[nmove++] = Drop(rook); }
828 if ( IsHandKnight(hand) && to > I8 ) { amove[nmove++] = Drop(knight); }
831 if ( IsHandSilver(hand) ) { amove[nmove++] = Drop(silver); }
832 if ( IsHandGold(hand) ) { amove[nmove++] = Drop(gold); }
833 if ( IsHandBishop(hand) ) { amove[nmove++] = Drop(bishop); }
837 /* - tentative assumption - */
838 /* a supported intercepter saves the king for two plies at least. */
839 if ( nmove && flag == 0 && dist > min_chuai
840 && I2From(MOVE_LAST) >= nsquare )
847 for ( i = n0 + n1 - 1; i >= n0; i-- ) { pmove[i+nmove] = pmove[i]; }
848 for ( i = 0; i < nmove; i++ ) { pmove[n0++] = amove[i]; }
850 else for ( i = 0; i < nmove; i++ ) { pmove[n0 + n1++] = amove[i]; }
854 return pmove + n0 + n1;