| 1 |
|
| /* xq_mate.c - how a game ended, and the fixed-depth mate search. |
| 2 |
|
| * |
| 3 |
|
| * PERL-FREE, as the rest of the engine is. Phase 04 of plan_xiangqi. |
| 4 |
|
| * |
| 5 |
|
| * TWO FUNCTIONS, AND THE FIRST ONE IS THE RULE EVERYBODY GETS WRONG. |
| 6 |
|
| */ |
| 7 |
|
| |
| 8 |
|
| #include "xq_abi.h" |
| 9 |
|
| |
| 10 |
1275850 |
| static const struct xq_abi *E(void) { return xq_abi_table(); } |
| 11 |
|
| |
| 12 |
|
| /* ---- the ending --------------------------------------------------------------- |
| 13 |
|
| * |
| 14 |
|
| * "Unlike in chess, in which stalemate is a draw, in xiangqi, it is a loss |
| 15 |
|
| * for the player who has no legal move." |
| 16 |
|
| * |
| 17 |
|
| * ONE BRANCH, TWO REASONS, AND NO DRAW ANYWHERE IN IT. A chess engine's |
| 18 |
|
| * structure is |
| 19 |
|
| * |
| 20 |
|
| * if (no moves) return in_check ? MATE : DRAW; |
| 21 |
|
| * |
| 22 |
|
| * and a port of that ships a bug which appears only in endgames. There is |
| 23 |
|
| * deliberately no `draw` value in this function at all: the draws this game has |
| 24 |
|
| * are the Asian Rules' repetition rulings and the three house counters, and |
| 25 |
|
| * every one of them is phase 06's. A position on its own can never be a draw. |
| 26 |
|
| */ |
| 27 |
355679 |
| static int xq_outcome(struct xq_board *b, int *reason) |
| 28 |
|
| { |
| 29 |
|
| int moves[XQ_MAX_MOVES]; |
| 30 |
355679 |
| int side = (E())->side(b); |
| 31 |
|
| |
| 32 |
355679 |
▶ | if (reason) *reason = XQ_ONGOING; |
Branch: 1 branch
| Branch | True | False | Total |
| if (reason) *reason = XQ_ONGOING; |
355679 |
0 |
355679 |
|
| 33 |
355679 |
▶ | if ((E())->gen_legal(b, moves) > 0) return XQ_ONGOING; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((E())->gen_legal(b, moves) > 0) return XQ_ONGOING; |
354795 |
884 |
355679 |
|
| 34 |
|
| |
| 35 |
884 |
▶ | if (reason) |
Branch: 1 branch
| Branch | True | False | Total |
| if (reason) |
884 |
0 |
884 |
|
| 36 |
884 |
▶ | *reason = (E())->in_check(b, side) ? XQ_BY_CHECKMATE : XQ_BY_STALEMATE; |
Branch: 1 branch
| Branch | True | False | Total |
| *reason = (E())->in_check(b, side) ? XQ_BY_CHECKMATE : XQ_BY_STALEMATE; |
797 |
87 |
884 |
|
| 37 |
884 |
▶ | return XQ_OTHER(side); |
Branch: 1 branch
| Branch | True | False | Total |
| return XQ_OTHER(side); |
62 |
822 |
884 |
|
| 38 |
|
| } |
| 39 |
|
| |
| 40 |
|
| /* ---- the mate search ----------------------------------------------------------- |
| 41 |
|
| * |
| 42 |
|
| * A fixed-depth, alpha-beta-free recursion. The mover needs ONE move that works; |
| 43 |
|
| * the defender needs EVERY reply to fail. Getting that quantifier backwards is |
| 44 |
|
| * the whole bug surface of this function, and it is why t/08 has a position |
| 45 |
|
| * where a mate in two does not exist: a version with `any` where `all` belongs |
| 46 |
|
| * finds a mate in almost every checking position and passes every test built |
| 47 |
|
| * from positions that really are mates. |
| 48 |
|
| * |
| 49 |
|
| * CHECKMATE SPECIFICALLY. A forced stalemate is also a win in this game and this |
| 50 |
|
| * function ignores it, because its caller is the Asian Rules' "threatening to |
| 51 |
|
| * checkmate" and a referee means mate when they say mate. Phase 09's search uses |
| 52 |
|
| * `outcome`, which counts both. |
| 53 |
|
| * |
| 54 |
|
| * BOUNDED BY `plies` AND BY NOTHING ELSE: no clock, no node budget, no table. |
| 55 |
|
| * Phase 05 calls it with 3. It is not the bot and must never become the bot, or |
| 56 |
|
| * the judge's rulings would depend on how loaded the box is. |
| 57 |
|
| */ |
| 58 |
8259 |
| static int mate_within(struct xq_board *b, int plies) |
| 59 |
|
| { |
| 60 |
|
| int moves[XQ_MAX_MOVES]; |
| 61 |
|
| int n, i; |
| 62 |
|
| |
| 63 |
8259 |
▶ | if (plies < 1) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (plies < 1) return 0; |
1 |
8258 |
8259 |
|
| 64 |
8258 |
| n = (E())->gen_legal(b, moves); |
| 65 |
8258 |
▶ | if (n == 0) return 0; /* the mover is itself finished */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (n == 0) return 0; /* the mover is itself finished */ |
129 |
8129 |
8258 |
|
| 66 |
|
| |
| 67 |
281295 |
▶ | for (i = 0; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < n; i++) { |
273657 |
7638 |
281295 |
|
| 68 |
|
| struct xq_undo u; |
| 69 |
273657 |
| int reason = XQ_ONGOING; |
| 70 |
|
| int over; |
| 71 |
|
| |
| 72 |
273657 |
| (E())->do_move(b, moves[i], &u); |
| 73 |
273657 |
| over = xq_outcome(b, &reason); |
| 74 |
|
| |
| 75 |
273657 |
▶ | if (over && reason == XQ_BY_CHECKMATE) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (over && reason == XQ_BY_CHECKMATE) { |
564 |
273093 |
273657 |
| if (over && reason == XQ_BY_CHECKMATE) { |
483 |
81 |
564 |
|
| 76 |
483 |
| (E())->undo_move(b, &u); |
| 77 |
491 |
| return 1; /* mate on this move */ |
| 78 |
|
| } |
| 79 |
|
| |
| 80 |
273174 |
▶ | if (!over && plies >= 3) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (!over && plies >= 3) { |
273093 |
81 |
273174 |
| if (!over && plies >= 3) { |
2490 |
270603 |
273093 |
|
| 81 |
|
| int replies[XQ_MAX_MOVES]; |
| 82 |
2490 |
| int m = (E())->gen_legal(b, replies); |
| 83 |
2490 |
| int j, all = 1; |
| 84 |
|
| /* EVERY reply must fail to save the defender */ |
| 85 |
2781 |
▶ | for (j = 0; j < m; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (j = 0; j < m; j++) { |
2773 |
8 |
2781 |
|
| 86 |
|
| struct xq_undo v; |
| 87 |
2773 |
| (E())->do_move(b, replies[j], &v); |
| 88 |
2773 |
▶ | if (!mate_within(b, plies - 2)) all = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!mate_within(b, plies - 2)) all = 0; |
2482 |
291 |
2773 |
|
| 89 |
2773 |
| (E())->undo_move(b, &v); |
| 90 |
2773 |
▶ | if (!all) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!all) break; |
2482 |
291 |
2773 |
|
| 91 |
|
| } |
| 92 |
2490 |
▶ | if (m > 0 && all) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (m > 0 && all) { |
2490 |
0 |
2490 |
| if (m > 0 && all) { |
8 |
2482 |
2490 |
|
| 93 |
8 |
| (E())->undo_move(b, &u); |
| 94 |
8 |
| return 1; |
| 95 |
|
| } |
| 96 |
|
| } |
| 97 |
273166 |
| (E())->undo_move(b, &u); |
| 98 |
|
| } |
| 99 |
7638 |
| return 0; |
| 100 |
|
| } |
| 101 |
|
| |
| 102 |
5486 |
| static int xq_mate_in(struct xq_board *b, int plies) |
| 103 |
|
| { |
| 104 |
5486 |
| return mate_within(b, plies); |
| 105 |
|
| } |
| 106 |
|
| |
| 107 |
|
| /* ---- installed into the table by xq_engine.c ----------------------------------- */ |
| 108 |
|
| |
| 109 |
|
| void xq_mate_install(struct xq_abi *t); |
| 110 |
|
| |
| 111 |
24 |
| void xq_mate_install(struct xq_abi *t) |
| 112 |
|
| { |
| 113 |
24 |
| t->outcome = xq_outcome; |
| 114 |
24 |
| t->mate_in = xq_mate_in; |
| 115 |
24 |
| } |