fn_rules.c

filter: Statementstmt 96.2% 177 / 184 Branchbran 76.7% 89 / 116 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 88.6% 266 / 300 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« Fanorona.xs ↑ Summary fn_moves.c »
1 /* fn_rules.c - a game: a board, the moves that made it, and how it ends.
2 *
3 * PERL-FREE, as the other two files are.
4 *
5 * THE RULES THIS FILE IMPLEMENTS, quoted from the sources the distribution
6 * names in its documentation:
7 *
8 * "The game ends when one player captures all stones of the opponent."
9 * "The game is a draw if no player is able to win. In practice this is
10 * achieved by repetition of the same position with the same player to
11 * move."
12 * "There does not exist any documentation stating what the outcome of the
13 * game would be if a player is not able to move. If this occurs during a
14 * game we define that a player who is not able to move forfeits the game."
15 *
16 * and three readings where the sources give no number:
17 *
18 * - REPETITION DRAWS AT THE THIRD OCCURRENCE, counted between moves only. A
19 * position in the middle of a chain is not a position.
20 * - A QUIET LIMIT. A game is drawn after a set number of moves running,
21 * both sides counted, that took nothing.
22 * - A PLY CAP far above anything a game reaches, as a guard.
23 *
24 * A MOVE IS COMPLETE WHEN THE TURN PASSES: after a paika, after a stop, and
25 * after a step that left nothing to follow. Only then is anything judged, the
26 * history written and the counts moved. A step in the middle of a chain
27 * changes the board and nothing else.
28 *
29 * THEY ARE ASKED IN THIS ORDER, because one move can satisfy two: no stones,
30 * no move, repetition, the quiet limit, the cap.
31 *
32 * REPETITION LOOKS BACK ONLY AS FAR AS THE LAST CAPTURE. A capture takes a
33 * stone off the board for good, so no position before it can come again; the
34 * quiet count is exactly how many positions are worth comparing.
35 */
36  
37 #include <stdlib.h>
38 #include <string.h>
39 #include "fn_abi.h"
40  
41 37701238 static const struct fn_abi *E(void) { return fn_abi_table(); }
42  
43 /* What one game_step or game_stop changed, so that game_undo restores it. */
44 struct played {
45 struct fn_undo undo;
46 int quiet;
47 int ply;
48 int outcome;
49 };
50  
51 struct fn_game {
52 struct fn_board *board;
53 struct fn_variant variant;
54 int outcome;
55 int ply; /* moves completed */
56 int quiet; /* of them, how many running took nothing */
57 int took; /* whether the move in progress has taken */
58 unsigned long long *key; /* key[i] is the position after i moves */
59 int key_room;
60 struct played *stack; /* one a step or stop */
61 int stack_n;
62 int stack_room;
63 unsigned char *took_at; /* took, as it was before each stack entry */
64 };
65  
66 static int FN_GAMES_LIVE = 0;
67  
68 464787 static void fn_variant_default(struct fn_variant *v)
69 {
70 464787 ▶ if (!v) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!v) return; 0 464787 464787
71 464787 memset(v, 0, sizeof(*v));
72 464787 v->quiet_limit = FN_QUIET_DEFAULT;
73 464787 v->repeat = FN_REPEAT_DEFAULT;
74 464787 v->ply_cap = FN_PLY_CAP_DEFAULT;
75 }
76  
77 /* A limit below zero means the default. Zero turns the quiet limit and
78 * repetition OFF, which a table of forced results needs; the cap cannot be
79 * turned off, because the history is an array as long as it. */
80 464786 static void variant_clamp(struct fn_variant *v)
81 {
82 464786 ▶ if (v->quiet_limit < 0) v->quiet_limit = FN_QUIET_DEFAULT;
Branch: 1 branch
BranchTrueFalseTotal
if (v->quiet_limit < 0) v->quiet_limit = FN_QUIET_DEFAULT; 188 464598 464786
83 464786 ▶ if (v->repeat < 0) v->repeat = FN_REPEAT_DEFAULT;
Branch: 1 branch
BranchTrueFalseTotal
if (v->repeat < 0) v->repeat = FN_REPEAT_DEFAULT; 188 464598 464786
84 464786 ▶ if (v->repeat == 1) v->repeat = 2;
Branch: 1 branch
BranchTrueFalseTotal
if (v->repeat == 1) v->repeat = 2; 1 464785 464786
85 464786 ▶ if (v->ply_cap <= 0 || v->ply_cap > FN_PLY_CAP_MAX) v->ply_cap = FN_PLY_CAP_DEFAULT;
Branch: 2 branches
BranchTrueFalseTotal
if (v->ply_cap <= 0 || v->ply_cap > FN_PLY_CAP_MAX) v->ply_cap = FN_PLY_CAP_DEFAULT; 464786 0 464786
if (v->ply_cap <= 0 || v->ply_cap > FN_PLY_CAP_MAX) v->ply_cap = FN_PLY_CAP_DEFAULT; 0 464786 464786
86 464786 }
87  
88  
89 589429 static int fn_repeats(const struct fn_game *g)
90 {
91 589429 unsigned long long now = g->key[g->ply];
92 589429 int n = 1, i;
93 854623 ▶ for (i = g->ply - 2; i >= 0 && i >= g->ply - g->quiet; i -= 2)
Branch: 2 branches
BranchTrueFalseTotal
for (i = g->ply - 2; i >= 0 && i >= g->ply - g->quiet; i -= 2) 807648 46975 854623
for (i = g->ply - 2; i >= 0 && i >= g->ply - g->quiet; i -= 2) 265194 542454 807648
94 265194 ▶ if (g->key[i] == now) n++;
Branch: 1 branch
BranchTrueFalseTotal
if (g->key[i] == now) n++; 726 264468 265194
95 589429 return n;
96 }
97  
98 /* Judges the position a completed move has left. */
99 7851391 static int judge(const struct fn_game *g)
100 {
101 7851391 const struct fn_abi *e = E();
102 7851391 const struct fn_board *b = g->board;
103 7851391 int side = e->side(b);
104 7851391 ▶ if (e->count(b, side) == 0 || e->count(b, FN_OTHER(side)) == 0) return FN_BY_STONES;
Branch: 2 branches
BranchTrueFalseTotal
if (e->count(b, side) == 0 || e->count(b, FN_OTHER(side)) == 0) return FN_BY_STONES; 7337050 514341 7851391
if (e->count(b, side) == 0 || e->count(b, FN_OTHER(side)) == 0) return FN_BY_STONES; 1 7337049 7337050
105 7337049 ▶ if (e->play_steps(b, NULL, 0) == 0) return FN_BY_NO_MOVES;
Branch: 1 branch
BranchTrueFalseTotal
if (e->play_steps(b, NULL, 0) == 0) return FN_BY_NO_MOVES; 33 7337016 7337049
106 7337016 ▶ if (g->variant.repeat && fn_repeats(g) >= g->variant.repeat) return FN_DRAW_REPETITION;
Branch: 2 branches
BranchTrueFalseTotal
if (g->variant.repeat && fn_repeats(g) >= g->variant.repeat) return FN_DRAW_REPETITION; 589422 6747594 7337016
if (g->variant.repeat && fn_repeats(g) >= g->variant.repeat) return FN_DRAW_REPETITION; 11 589411 589422
107 7337005 ▶ if (g->variant.quiet_limit && g->quiet >= g->variant.quiet_limit) return FN_DRAW_QUIET;
Branch: 2 branches
BranchTrueFalseTotal
if (g->variant.quiet_limit && g->quiet >= g->variant.quiet_limit) return FN_DRAW_QUIET; 589087 6747918 7337005
if (g->variant.quiet_limit && g->quiet >= g->variant.quiet_limit) return FN_DRAW_QUIET; 20 589067 589087
108 7336985 ▶ if (g->ply >= g->variant.ply_cap) return FN_DRAW_PLY_CAP;
Branch: 1 branch
BranchTrueFalseTotal
if (g->ply >= g->variant.ply_cap) return FN_DRAW_PLY_CAP; 904 7336081 7336985
109 7336081 return FN_ONGOING;
110 }
111  
112 464786 static struct fn_game *fn_game_new(const struct fn_board *b, const struct fn_variant *v)
113 {
114 464786 const struct fn_abi *e = E();
115 464786 struct fn_game *g = (struct fn_game *) calloc(1, sizeof(struct fn_game));
116 464786 ▶ if (!g) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!g) return NULL; 0 464786 464786
117 464786 ▶ if (v) g->variant = *v; else fn_variant_default(&g->variant);
Branch: 1 branch
BranchTrueFalseTotal
if (v) g->variant = *v; else fn_variant_default(&g->variant); 464786 0 464786
118 464786 variant_clamp(&g->variant);
119 464786 ▶ g->board = b ? e->board_copy(b) : e->board_new(FN_COLS_MAX, FN_ROWS_MAX);
Branch: 1 branch
BranchTrueFalseTotal
g->board = b ? e->board_copy(b) : e->board_new(FN_COLS_MAX, FN_ROWS_MAX); 464786 0 464786
120 464786 g->key_room = g->variant.ply_cap + 2;
121 464786 g->key = (unsigned long long *) calloc((size_t) g->key_room, sizeof(unsigned long long));
122 464786 ▶ if (!g->board || !g->key) {
Branch: 2 branches
BranchTrueFalseTotal
if (!g->board || !g->key) { 464786 0 464786
if (!g->board || !g->key) { 0 464786 464786
123 0 ▶ if (g->board) e->board_drop(g->board);
Branch: 1 branch
BranchTrueFalseTotal
if (g->board) e->board_drop(g->board); 0 0 0
124 0 free(g->key);
125 0 free(g);
126 0 return NULL;
127 }
128 /* a game begins between moves: a chain the board came with is dropped */
129 464786 e->chain_set(g->board, -1, -1, 0);
130 464786 g->key[0] = e->key(g->board);
131 464786 g->outcome = judge(g);
132 464786 FN_GAMES_LIVE++;
133 464786 return g;
134 }
135  
136 33562 static struct fn_game *fn_game_copy(const struct fn_game *g)
137 {
138 33562 const struct fn_abi *e = E();
139 struct fn_game *n;
140 33562 ▶ if (!g) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!g) return NULL; 0 33562 33562
141 33562 n = (struct fn_game *) malloc(sizeof(struct fn_game));
142 33562 ▶ if (!n) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return NULL; 0 33562 33562
143 33562 *n = *g;
144 33562 n->board = e->board_copy(g->board);
145 33562 n->key = (unsigned long long *) malloc((size_t) g->key_room * sizeof(unsigned long long));
146 33562 n->stack = NULL;
147 33562 n->took_at = NULL;
148 33562 ▶ if (g->stack_room) {
Branch: 1 branch
BranchTrueFalseTotal
if (g->stack_room) { 22904 10658 33562
149 22904 n->stack = (struct played *) malloc((size_t) g->stack_room * sizeof(struct played));
150 22904 n->took_at = (unsigned char *) malloc((size_t) g->stack_room);
151 }
152 33562 ▶ if (!n->board || !n->key || (g->stack_room && (!n->stack || !n->took_at))) {
Branch: 5 branches
BranchTrueFalseTotal
if (!n->board || !n->key || (g->stack_room && (!n->stack || !n->took_at))) { 33562 0 33562
if (!n->board || !n->key || (g->stack_room && (!n->stack || !n->took_at))) { 33562 0 33562
if (!n->board || !n->key || (g->stack_room && (!n->stack || !n->took_at))) { 22904 10658 33562
if (!n->board || !n->key || (g->stack_room && (!n->stack || !n->took_at))) { 22904 0 22904
if (!n->board || !n->key || (g->stack_room && (!n->stack || !n->took_at))) { 0 22904 22904
153 0 ▶ if (n->board) e->board_drop(n->board);
Branch: 1 branch
BranchTrueFalseTotal
if (n->board) e->board_drop(n->board); 0 0 0
154 0 free(n->key); free(n->stack); free(n->took_at); free(n);
155 0 return NULL;
156 }
157 33562 memcpy(n->key, g->key, (size_t) g->key_room * sizeof(unsigned long long));
158 33562 ▶ if (g->stack_n) {
Branch: 1 branch
BranchTrueFalseTotal
if (g->stack_n) { 22904 10658 33562
159 22904 memcpy(n->stack, g->stack, (size_t) g->stack_n * sizeof(struct played));
160 22904 memcpy(n->took_at, g->took_at, (size_t) g->stack_n);
161 }
162 33562 FN_GAMES_LIVE++;
163 33562 return n;
164 }
165  
166 498348 static void fn_game_drop(struct fn_game *g)
167 {
168 498348 ▶ if (!g) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!g) return; 0 498348 498348
169 498348 (E())->board_drop(g->board);
170 498348 free(g->key);
171 498348 free(g->stack);
172 498348 free(g->took_at);
173 498348 free(g);
174 498348 FN_GAMES_LIVE--;
175 }
176  
177 9 static int fn_games_live(void) { return FN_GAMES_LIVE; }
178  
179 23176128 static const struct fn_board *fn_game_board(const struct fn_game *g) { return g->board; }
180 417 ▶static void fn_game_variant(const struct fn_game *g, struct fn_variant *out) { if (out) *out = g->variant; }
Branch: 1 branch
BranchTrueFalseTotal
static void fn_game_variant(const struct fn_game *g, struct fn_variant *out) { if (out) *out = g->variant; } 417 0 417
181 4490250 static int fn_game_ply(const struct fn_game *g) { return g->ply; }
182 9785 static int fn_game_quiet(const struct fn_game *g) { return g->quiet; }
183 9763346 static int fn_game_outcome(const struct fn_game *g) { return g->outcome; }
184 4471012 static int fn_game_depth(const struct fn_game *g) { return g->stack_n; }
185  
186 /* The side that won, or 0. A game won on stones is won by the side that has
187 * some: after a move that is always the mover, but a game may be BEGUN from a
188 * position in which one side has none, and then it is whoever has. A game won
189 * because the side to move is stuck is won by the other side. */
190 431995 static int fn_game_winner(const struct fn_game *g)
191 {
192 431995 const struct fn_abi *e = E();
193 431995 int side = e->side(g->board);
194 431995 ▶ if (g->outcome == FN_BY_STONES)
Branch: 1 branch
BranchTrueFalseTotal
if (g->outcome == FN_BY_STONES) 431047 948 431995
195 431047 ▶ return e->count(g->board, side) == 0 ? FN_OTHER(side) : side;
Branch: 1 branch
BranchTrueFalseTotal
return e->count(g->board, side) == 0 ? FN_OTHER(side) : side; 431046 1 431047
196 948 ▶ if (g->outcome == FN_BY_NO_MOVES) return FN_OTHER(side);
Branch: 1 branch
BranchTrueFalseTotal
if (g->outcome == FN_BY_NO_MOVES) return FN_OTHER(side); 7 941 948
197 941 return 0;
198 }
199  
200 9 static unsigned long long fn_game_key_at(const struct fn_game *g, int ply)
201 {
202 9 ▶ if (ply < 0 || ply > g->ply) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (ply < 0 || ply > g->ply) return 0; 9 0 9
if (ply < 0 || ply > g->ply) return 0; 0 9 9
203 9 return g->key[ply];
204 }
205  
206 5492339 static int fn_game_steps(const struct fn_game *g, struct fn_step *out, int max)
207 {
208 5492339 ▶ if (g->outcome != FN_ONGOING) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (g->outcome != FN_ONGOING) return 0; 3 5492336 5492339
209 5492336 return (E())->play_steps(g->board, out, max);
210 }
211  
212 11722 static int fn_game_can_stop(const struct fn_game *g)
213 {
214 11722 ▶ if (g->outcome != FN_ONGOING) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (g->outcome != FN_ONGOING) return 0; 2 11720 11722
215 11720 return (E())->can_stop(g->board);
216 }
217  
218 /* Room for one more entry on the stack, or 0. */
219 7805639 static int stack_grow(struct fn_game *g)
220 {
221 struct played *s;
222 unsigned char *t;
223 int room;
224 7805639 ▶ if (g->stack_n < g->stack_room) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (g->stack_n < g->stack_room) return 1; 7339343 466296 7805639
225 466296 ▶ room = g->stack_room ? g->stack_room * 2 : 64;
Branch: 1 branch
BranchTrueFalseTotal
room = g->stack_room ? g->stack_room * 2 : 64; 204 466092 466296
226 466296 s = (struct played *) realloc(g->stack, (size_t) room * sizeof(struct played));
227 466296 ▶ if (!s) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!s) return 0; 0 466296 466296
228 466296 g->stack = s;
229 466296 t = (unsigned char *) realloc(g->took_at, (size_t) room);
230 466296 ▶ if (!t) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!t) return 0; 0 466296 466296
231 466296 g->took_at = t;
232 466296 g->stack_room = room;
233 466296 return 1;
234 }
235  
236 /* The turn has just passed: count the move, write the position, judge it. */
237 7386605 static void move_done(struct fn_game *g)
238 {
239 7386605 g->ply++;
240 7386605 ▶ g->quiet = g->took ? 0 : g->quiet + 1;
Branch: 1 branch
BranchTrueFalseTotal
g->quiet = g->took ? 0 : g->quiet + 1; 6194010 1192595 7386605
241 7386605 g->took = 0;
242 7386605 g->key[g->ply] = (E())->key(g->board);
243 7386605 g->outcome = judge(g);
244 7386605 }
245  
246 7805639 static void remember(struct fn_game *g, struct played *p)
247 {
248 7805639 p->quiet = g->quiet;
249 7805639 p->ply = g->ply;
250 7805639 p->outcome = g->outcome;
251 7805639 g->took_at[g->stack_n] = (unsigned char) g->took;
252 7805639 }
253  
254 /* THE ONE DOOR A STEP COMES THROUGH. Refuses and changes nothing, or plays. */
255 7742587 static int fn_game_step(struct fn_game *g, int from, int dir, int kind, int *why)
256 {
257 7742587 const struct fn_abi *e = E();
258 struct fn_step s;
259 struct played *p;
260 int reason, removed;
261 7742587 ▶ if (why) *why = FN_WHY_OK;
Branch: 1 branch
BranchTrueFalseTotal
if (why) *why = FN_WHY_OK; 6792978 949609 7742587
262 7742587 ▶ if (g->outcome != FN_ONGOING) return FN_PLAY_OVER;
Branch: 1 branch
BranchTrueFalseTotal
if (g->outcome != FN_ONGOING) return FN_PLAY_OVER; 1 7742586 7742587
263 7742586 reason = e->play_why(g->board, from, dir, kind, &s);
264 7742586 ▶ if (reason != FN_WHY_OK) {
Branch: 1 branch
BranchTrueFalseTotal
if (reason != FN_WHY_OK) { 30 7742556 7742586
265 30 ▶ if (why) *why = reason;
Branch: 1 branch
BranchTrueFalseTotal
if (why) *why = reason; 30 0 30
266 30 return FN_PLAY_ILLEGAL;
267 }
268 7742556 ▶ if (!stack_grow(g)) return FN_PLAY_ILLEGAL;
Branch: 1 branch
BranchTrueFalseTotal
if (!stack_grow(g)) return FN_PLAY_ILLEGAL; 0 7742556 7742556
269 7742556 p = &g->stack[g->stack_n];
270 7742556 remember(g, p);
271 7742556 removed = e->play_step(g->board, &s, &p->undo);
272 7742556 g->stack_n++;
273 7742556 ▶ if (removed > 0) g->took = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (removed > 0) g->took = 1; 1548546 6194010 7742556
274 7742556 ▶ if (e->chain_at(g->board) < 0) move_done(g);
Branch: 1 branch
BranchTrueFalseTotal
if (e->chain_at(g->board) < 0) move_done(g); 7323522 419034 7742556
275 7742556 return FN_PLAY_OK;
276 }
277  
278 63085 static int fn_game_stop(struct fn_game *g)
279 {
280 63085 const struct fn_abi *e = E();
281 struct played *p;
282 63085 ▶ if (g->outcome != FN_ONGOING) return FN_PLAY_OVER;
Branch: 1 branch
BranchTrueFalseTotal
if (g->outcome != FN_ONGOING) return FN_PLAY_OVER; 1 63084 63085
283 63084 ▶ if (!e->can_stop(g->board)) return FN_PLAY_ILLEGAL;
Branch: 1 branch
BranchTrueFalseTotal
if (!e->can_stop(g->board)) return FN_PLAY_ILLEGAL; 1 63083 63084
284 63083 ▶ if (!stack_grow(g)) return FN_PLAY_ILLEGAL;
Branch: 1 branch
BranchTrueFalseTotal
if (!stack_grow(g)) return FN_PLAY_ILLEGAL; 0 63083 63083
285 63083 p = &g->stack[g->stack_n];
286 63083 remember(g, p);
287 63083 e->play_stop(g->board, &p->undo);
288 63083 g->stack_n++;
289 63083 move_done(g);
290 63083 return FN_PLAY_OK;
291 }
292  
293 /* Takes back the last step or stop. 0 when there is none. */
294 7724994 static int fn_game_undo(struct fn_game *g)
295 {
296 struct played *p;
297 7724994 ▶ if (g->stack_n == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (g->stack_n == 0) return 0; 171 7724823 7724994
298 7724823 g->stack_n--;
299 7724823 p = &g->stack[g->stack_n];
300 7724823 (E())->play_undo(g->board, &p->undo);
301 7724823 g->quiet = p->quiet;
302 7724823 g->ply = p->ply;
303 7724823 g->outcome = p->outcome;
304 7724823 g->took = g->took_at[g->stack_n];
305 7724823 return 1;
306 }
307  
308 /* ---- installed into the table by fn_engine.c ---------------------------------- */
309  
310 void fn_rules_install(struct fn_abi *t);
311  
312 43 void fn_rules_install(struct fn_abi *t)
313 {
314 43 t->variant_default = fn_variant_default;
315 43 t->game_new = fn_game_new;
316 43 t->game_copy = fn_game_copy;
317 43 t->game_drop = fn_game_drop;
318 43 t->games_live = fn_games_live;
319 43 t->game_board = fn_game_board;
320 43 t->game_variant = fn_game_variant;
321 43 t->game_ply = fn_game_ply;
322 43 t->game_quiet = fn_game_quiet;
323 43 t->game_depth = fn_game_depth;
324 43 t->game_outcome = fn_game_outcome;
325 43 t->game_winner = fn_game_winner;
326 43 t->game_key_at = fn_game_key_at;
327 43 t->repeats = fn_repeats;
328 43 t->game_steps = fn_game_steps;
329 43 t->game_can_stop = fn_game_can_stop;
330 43 t->game_step = fn_game_step;
331 43 t->game_stop = fn_game_stop;
332 43 t->game_undo = fn_game_undo;
333 43 }
« Fanorona.xs ↑ Summary fn_moves.c »