xq_mate.c

filter: Statementstmt 100% 38 / 38 Branchbran 91.1% 31 / 34 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 95.8% 69 / 72 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xq_search.c ↑ Summary
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
BranchTrueFalseTotal
if (reason) *reason = XQ_ONGOING; 355679 0 355679
33 355679 ▶ if ((E())->gen_legal(b, moves) > 0) return XQ_ONGOING;
Branch: 1 branch
BranchTrueFalseTotal
if ((E())->gen_legal(b, moves) > 0) return XQ_ONGOING; 354795 884 355679
34  
35 884 ▶ if (reason)
Branch: 1 branch
BranchTrueFalseTotal
if (reason) 884 0 884
36 884 ▶ *reason = (E())->in_check(b, side) ? XQ_BY_CHECKMATE : XQ_BY_STALEMATE;
Branch: 1 branch
BranchTrueFalseTotal
*reason = (E())->in_check(b, side) ? XQ_BY_CHECKMATE : XQ_BY_STALEMATE; 797 87 884
37 884 ▶ return XQ_OTHER(side);
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!all) break; 2482 291 2773
91 }
92 2490 ▶ if (m > 0 && all) {
Branch: 2 branches
BranchTrueFalseTotal
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 }
« xq_search.c ↑ Summary