gomoku.h revision 1.55 1 1.55 rillig /* $NetBSD: gomoku.h,v 1.55 2022/05/29 17:01:42 rillig Exp $ */
2 1.3 cgd
3 1.1 tls /*
4 1.1 tls * Copyright (c) 1994
5 1.1 tls * The Regents of the University of California. All rights reserved.
6 1.1 tls *
7 1.1 tls * This code is derived from software contributed to Berkeley by
8 1.1 tls * Ralph Campbell.
9 1.1 tls *
10 1.1 tls * Redistribution and use in source and binary forms, with or without
11 1.1 tls * modification, are permitted provided that the following conditions
12 1.1 tls * are met:
13 1.1 tls * 1. Redistributions of source code must retain the above copyright
14 1.1 tls * notice, this list of conditions and the following disclaimer.
15 1.1 tls * 2. Redistributions in binary form must reproduce the above copyright
16 1.1 tls * notice, this list of conditions and the following disclaimer in the
17 1.1 tls * documentation and/or other materials provided with the distribution.
18 1.8 agc * 3. Neither the name of the University nor the names of its contributors
19 1.1 tls * may be used to endorse or promote products derived from this software
20 1.1 tls * without specific prior written permission.
21 1.1 tls *
22 1.1 tls * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 1.1 tls * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 1.1 tls * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 1.1 tls * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 1.1 tls * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 1.1 tls * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 1.1 tls * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 1.1 tls * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 1.1 tls * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 1.1 tls * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 1.1 tls * SUCH DAMAGE.
33 1.1 tls *
34 1.1 tls * @(#)gomoku.h 8.2 (Berkeley) 5/3/95
35 1.1 tls */
36 1.1 tls
37 1.1 tls #include <sys/types.h>
38 1.9 jsm #include <sys/endian.h>
39 1.26 rillig #include <stdbool.h>
40 1.4 lukem #include <stdio.h>
41 1.1 tls
42 1.36 rillig /*
43 1.52 rillig * The gomoku 'board' mainly consists of the playing area of BSZ x BSZ spots.
44 1.52 rillig * The playing area uses 1-based coordinates. Around the playing area is a
45 1.52 rillig * rectangle of border spots, to avoid having to check the coordinates when
46 1.52 rillig * calculating spot coordinates. The left and right border overlap, to save a
47 1.52 rillig * few bytes.
48 1.36 rillig */
49 1.36 rillig
50 1.1 tls #define BSZ 19
51 1.25 rillig #define BAREA ((1 + BSZ + 1) * (BSZ + 1) + 1)
52 1.1 tls
53 1.36 rillig /*
54 1.52 rillig * A 'frame' is a group of five or six contiguous spots on the board. An
55 1.36 rillig * open-ended frame is one with spaces on both ends; otherwise, it is closed.
56 1.36 rillig */
57 1.29 rillig #define FAREA (2 * BSZ * (BSZ - 4) + 2 * (BSZ - 4) * (BSZ - 4))
58 1.1 tls
59 1.52 rillig
60 1.52 rillig /* The content of a spot on the board; used in s_occ. */
61 1.1 tls #define BLACK 0
62 1.1 tls #define WHITE 1
63 1.1 tls #define EMPTY 2
64 1.1 tls #define BORDER 3
65 1.1 tls
66 1.53 rillig /* Either BLACK or WHITE. */
67 1.53 rillig typedef unsigned char player_color;
68 1.53 rillig
69 1.52 rillig /* A spot on the board, or one of the special values below. */
70 1.48 rillig typedef unsigned short spot_index;
71 1.52 rillig #define PT(x, y) ((x) + (BSZ + 1) * (y))
72 1.34 rillig /* return values for makemove, readinput */
73 1.1 tls #define MOVEOK 0
74 1.1 tls #define RESIGN 1
75 1.1 tls #define ILLEGAL 2
76 1.1 tls #define WIN 3
77 1.1 tls #define TIE 4
78 1.1 tls #define SAVE 5
79 1.46 rillig #define END_OF_INPUT 6
80 1.1 tls
81 1.1 tls /*
82 1.52 rillig * A 'combo' is a group of intersecting or overlapping frames and consists of
83 1.52 rillig * two numbers:
84 1.52 rillig * 'F' is the number of moves still needed to make the combo non-blockable.
85 1.37 rillig * 'W' is the minimum number of moves needed to win once it can't be blocked.
86 1.1 tls *
87 1.36 rillig * A 'force' is a combo that is one move away from being non-blockable.
88 1.1 tls *
89 1.1 tls * Each time a frame is added to the combo, the number of moves to complete
90 1.1 tls * the force is the number of moves needed to 'fill' the frame plus one at
91 1.1 tls * the intersection point. The number of moves to win is the number of moves
92 1.1 tls * to complete the best frame minus the last move to complete the force.
93 1.1 tls * Note that it doesn't make sense to combine a <1,x> with anything since
94 1.1 tls * it is already a force. Also, the frames have to be independent so a
95 1.1 tls * single move doesn't affect more than one frame making up the combo.
96 1.1 tls *
97 1.37 rillig * Rules for comparing which of two combos (<F1,W1> <F2,W2>) is better:
98 1.1 tls * Both the same color:
99 1.37 rillig * <F',W'> = (F1 < F2 || F1 == F2 && W1 <= W2) ? <F1,W1> : <F2,W2>
100 1.1 tls * We want to complete the force first, then the combo with the
101 1.1 tls * fewest moves to win.
102 1.37 rillig * Different colors, <F1,W1> is the combo for the player with the next move:
103 1.37 rillig * <F',W'> = F2 <= 1 && (F1 > 1 || F2 + W2 < F1 + W1) ? <F2,W2> : <F1,W1>
104 1.1 tls * We want to block only if we have to (i.e., if they are one move away
105 1.31 rillig * from completing a force, and we don't have a force that we can
106 1.1 tls * complete which takes fewer or the same number of moves to win).
107 1.1 tls */
108 1.1 tls
109 1.36 rillig /*
110 1.36 rillig * Single frame combo values:
111 1.37 rillig * <F,W> board values
112 1.36 rillig * 5,0 . . . . . O
113 1.36 rillig * 4,1 . . . . . .
114 1.36 rillig * 4,0 . . . . X O
115 1.36 rillig * 3,1 . . . . X .
116 1.36 rillig * 3,0 . . . X X O
117 1.36 rillig * 2,1 . . . X X .
118 1.36 rillig * 2,0 . . X X X O
119 1.36 rillig * 1,1 . . X X X .
120 1.36 rillig * 1,0 . X X X X O
121 1.36 rillig * 0,1 . X X X X .
122 1.36 rillig * 0,0 X X X X X O
123 1.36 rillig *
124 1.37 rillig * The rule for combining two combos (<F1,W1> <F2,W2>) with V valid
125 1.36 rillig * intersection points is:
126 1.37 rillig * F' = F1 + F2 - 2 - V
127 1.37 rillig * W' = MIN(F1 + W1 - 1, F2 + W2 - 1)
128 1.36 rillig */
129 1.22 rillig union comboval {
130 1.1 tls struct {
131 1.1 tls #if BYTE_ORDER == BIG_ENDIAN
132 1.37 rillig u_char a;
133 1.37 rillig u_char b;
134 1.1 tls #endif
135 1.1 tls #if BYTE_ORDER == LITTLE_ENDIAN
136 1.37 rillig u_char b;
137 1.37 rillig u_char a;
138 1.1 tls #endif
139 1.1 tls } c;
140 1.1 tls u_short s;
141 1.1 tls };
142 1.37 rillig #define cv_force c.a /* # moves to complete force */
143 1.37 rillig #define cv_win c.b /* # moves to win */
144 1.1 tls
145 1.1 tls /*
146 1.1 tls * This structure is used to record information about single frames (F) and
147 1.1 tls * combinations of two more frames (C).
148 1.1 tls * For combinations of two or more frames, there is an additional
149 1.1 tls * array of pointers to the frames of the combination which is sorted
150 1.1 tls * by the index into the frames[] array. This is used to prevent duplication
151 1.1 tls * since frame A combined with B is the same as B with A.
152 1.1 tls * struct combostr *c_sort[size c_nframes];
153 1.1 tls * The leaves of the tree (frames) are numbered 0 (bottom, leftmost)
154 1.1 tls * to c_nframes - 1 (top, right). This is stored in c_frameindex and
155 1.1 tls * c_dir if C_LOOP is set.
156 1.1 tls */
157 1.1 tls struct combostr {
158 1.1 tls struct combostr *c_next; /* list of combos at the same level */
159 1.1 tls struct combostr *c_prev; /* list of combos at the same level */
160 1.39 rillig struct combostr *c_link[2]; /* F: NULL,
161 1.39 rillig * C: previous level */
162 1.39 rillig union comboval c_linkv[2]; /* C: combo value for link[0, 1] */
163 1.39 rillig union comboval c_combo; /* F: initial combo value (read-only),
164 1.39 rillig * C: combo value for this level */
165 1.49 rillig spot_index c_vertex; /* F: frame head,
166 1.39 rillig * C: intersection */
167 1.39 rillig u_char c_nframes; /* F: 1,
168 1.39 rillig * C: number of frames in the combo */
169 1.39 rillig u_char c_dir; /* F: frame direction,
170 1.39 rillig * C: loop frame */
171 1.39 rillig u_char c_flags; /* C: combo flags */
172 1.39 rillig u_char c_frameindex; /* C: intersection frame index */
173 1.1 tls u_char c_framecnt[2]; /* number of frames left to attach */
174 1.39 rillig u_char c_emask[2]; /* C: bit mask of completion spots for
175 1.1 tls * link[0] and link[1] */
176 1.39 rillig u_char c_voff[2]; /* C: vertex offset within frame */
177 1.1 tls };
178 1.1 tls
179 1.11 dholland /* flag values for c_flags */
180 1.31 rillig #define C_OPEN_0 0x01 /* link[0] is an open-ended frame */
181 1.31 rillig #define C_OPEN_1 0x02 /* link[1] is an open-ended frame */
182 1.1 tls #define C_LOOP 0x04 /* link[1] intersects previous frame */
183 1.1 tls
184 1.1 tls /*
185 1.1 tls * This structure is used for recording the completion points of
186 1.1 tls * multi frame combos.
187 1.1 tls */
188 1.1 tls struct elist {
189 1.1 tls struct elist *e_next; /* list of completion points */
190 1.1 tls struct combostr *e_combo; /* the whole combo */
191 1.1 tls u_char e_off; /* offset in frame of this empty spot */
192 1.1 tls u_char e_frameindex; /* intersection frame index */
193 1.1 tls u_char e_framecnt; /* number of frames left to attach */
194 1.1 tls u_char e_emask; /* real value of the frame's emask */
195 1.1 tls union comboval e_fval; /* frame combo value */
196 1.1 tls };
197 1.1 tls
198 1.49 rillig /* The index of a frame in the global 'frames'. */
199 1.49 rillig typedef unsigned short frame_index;
200 1.49 rillig
201 1.50 rillig /* 0 = right, 1 = down right, 2 = down, 3 = down left. */
202 1.50 rillig typedef unsigned char direction;
203 1.50 rillig
204 1.1 tls /*
205 1.1 tls * One spot structure for each location on the board.
206 1.50 rillig * A frame consists of the combination for the current spot plus the next
207 1.50 rillig * five spots in the direction.
208 1.1 tls */
209 1.1 tls struct spotstr {
210 1.1 tls short s_occ; /* color of occupant */
211 1.1 tls short s_wval; /* weighted value */
212 1.11 dholland int s_flags; /* flags for graph walks */
213 1.49 rillig frame_index s_frame[4]; /* level 1 combo for [dir] */
214 1.50 rillig union comboval s_fval[2][4]; /* combo value for [color][dir] */
215 1.50 rillig union comboval s_combo[2]; /* minimum combo value for [color] */
216 1.1 tls u_char s_level[2]; /* number of frames in the min combo */
217 1.1 tls u_char s_nforce[2]; /* number of <1,x> combos */
218 1.1 tls struct elist *s_empty; /* level n combo completion spots */
219 1.1 tls struct elist *s_nempty; /* level n+1 combo completion spots */
220 1.1 tls };
221 1.1 tls
222 1.11 dholland /* flag values for s_flags */
223 1.1 tls #define CFLAG 0x000001 /* frame is part of a combo */
224 1.1 tls #define CFLAGALL 0x00000F /* all frame directions marked */
225 1.1 tls #define IFLAG 0x000010 /* legal intersection point */
226 1.1 tls #define IFLAGALL 0x0000F0 /* any intersection points? */
227 1.1 tls #define FFLAG 0x000100 /* frame is part of a <1,x> combo */
228 1.1 tls #define FFLAGALL 0x000F00 /* all force frames */
229 1.1 tls #define MFLAG 0x001000 /* frame has already been seen */
230 1.1 tls #define MFLAGALL 0x00F000 /* all frames seen */
231 1.1 tls #define BFLAG 0x010000 /* frame intersects border or dead */
232 1.1 tls #define BFLAGALL 0x0F0000 /* all frames dead */
233 1.1 tls
234 1.43 rillig struct game {
235 1.50 rillig unsigned int nmoves; /* number of played moves */
236 1.50 rillig spot_index moves[BSZ * BSZ]; /* log of all played moves */
237 1.51 rillig spot_index win_spot; /* the winning move, or 0 */
238 1.51 rillig direction win_dir;
239 1.54 rillig int user_x;
240 1.54 rillig int user_y;
241 1.43 rillig };
242 1.43 rillig
243 1.38 rillig extern const char letters[];
244 1.6 jsm extern const char pdir[];
245 1.1 tls
246 1.6 jsm extern const int dd[4];
247 1.1 tls extern struct spotstr board[BAREA]; /* info for board */
248 1.1 tls extern struct combostr frames[FAREA]; /* storage for single frames */
249 1.1 tls extern struct combostr *sortframes[2]; /* sorted, non-empty frames */
250 1.42 rillig extern u_char overlap[FAREA * FAREA];
251 1.48 rillig extern spot_index intersect[FAREA * FAREA]; /* frame [a][b] intersection */
252 1.43 rillig extern struct game game;
253 1.1 tls extern int debug;
254 1.1 tls
255 1.28 rillig extern bool interactive;
256 1.20 dholland extern const char *plyr[];
257 1.20 dholland
258 1.45 rillig void init_board(void);
259 1.55 rillig spot_index get_coord(void);
260 1.28 rillig int get_key(const char *);
261 1.33 rillig bool get_line(char *, int, void (*)(const char *));
262 1.10 jsm void ask(const char *);
263 1.10 jsm void dislog(const char *);
264 1.10 jsm void bdump(FILE *);
265 1.10 jsm void bdisp(void);
266 1.10 jsm void bdisp_init(void);
267 1.10 jsm void cursfini(void);
268 1.10 jsm void cursinit(void);
269 1.32 rillig void bdwho(void);
270 1.13 dholland void panic(const char *, ...) __printflike(1, 2) __dead;
271 1.13 dholland void debuglog(const char *, ...) __printflike(1, 2);
272 1.10 jsm void whatsup(int);
273 1.47 rillig const char *stoc(spot_index);
274 1.47 rillig spot_index ctos(const char *);
275 1.53 rillig int makemove(player_color, spot_index);
276 1.10 jsm void clearcombo(struct combostr *, int);
277 1.10 jsm void markcombo(struct combostr *);
278 1.53 rillig spot_index pickmove(player_color);
279 1.27 rillig #if defined(DEBUG)
280 1.27 rillig void printcombo(struct combostr *, char *, size_t);
281 1.27 rillig #endif
282