gomoku.h revision 1.52 1 1.52 rillig /* $NetBSD: gomoku.h,v 1.52 2022/05/29 14:50:37 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.52 rillig /* A spot on the board, or one of the special values below. */
67 1.48 rillig typedef unsigned short spot_index;
68 1.52 rillig #define PT(x, y) ((x) + (BSZ + 1) * (y))
69 1.34 rillig /* return values for makemove, readinput */
70 1.1 tls #define MOVEOK 0
71 1.1 tls #define RESIGN 1
72 1.1 tls #define ILLEGAL 2
73 1.1 tls #define WIN 3
74 1.1 tls #define TIE 4
75 1.1 tls #define SAVE 5
76 1.46 rillig #define END_OF_INPUT 6
77 1.1 tls
78 1.1 tls /*
79 1.52 rillig * A 'combo' is a group of intersecting or overlapping frames and consists of
80 1.52 rillig * two numbers:
81 1.52 rillig * 'F' is the number of moves still needed to make the combo non-blockable.
82 1.37 rillig * 'W' is the minimum number of moves needed to win once it can't be blocked.
83 1.1 tls *
84 1.36 rillig * A 'force' is a combo that is one move away from being non-blockable.
85 1.1 tls *
86 1.1 tls * Each time a frame is added to the combo, the number of moves to complete
87 1.1 tls * the force is the number of moves needed to 'fill' the frame plus one at
88 1.1 tls * the intersection point. The number of moves to win is the number of moves
89 1.1 tls * to complete the best frame minus the last move to complete the force.
90 1.1 tls * Note that it doesn't make sense to combine a <1,x> with anything since
91 1.1 tls * it is already a force. Also, the frames have to be independent so a
92 1.1 tls * single move doesn't affect more than one frame making up the combo.
93 1.1 tls *
94 1.37 rillig * Rules for comparing which of two combos (<F1,W1> <F2,W2>) is better:
95 1.1 tls * Both the same color:
96 1.37 rillig * <F',W'> = (F1 < F2 || F1 == F2 && W1 <= W2) ? <F1,W1> : <F2,W2>
97 1.1 tls * We want to complete the force first, then the combo with the
98 1.1 tls * fewest moves to win.
99 1.37 rillig * Different colors, <F1,W1> is the combo for the player with the next move:
100 1.37 rillig * <F',W'> = F2 <= 1 && (F1 > 1 || F2 + W2 < F1 + W1) ? <F2,W2> : <F1,W1>
101 1.1 tls * We want to block only if we have to (i.e., if they are one move away
102 1.31 rillig * from completing a force, and we don't have a force that we can
103 1.1 tls * complete which takes fewer or the same number of moves to win).
104 1.1 tls */
105 1.1 tls
106 1.36 rillig /*
107 1.36 rillig * Single frame combo values:
108 1.37 rillig * <F,W> board values
109 1.36 rillig * 5,0 . . . . . O
110 1.36 rillig * 4,1 . . . . . .
111 1.36 rillig * 4,0 . . . . X O
112 1.36 rillig * 3,1 . . . . X .
113 1.36 rillig * 3,0 . . . X X O
114 1.36 rillig * 2,1 . . . X X .
115 1.36 rillig * 2,0 . . X X X O
116 1.36 rillig * 1,1 . . X X X .
117 1.36 rillig * 1,0 . X X X X O
118 1.36 rillig * 0,1 . X X X X .
119 1.36 rillig * 0,0 X X X X X O
120 1.36 rillig *
121 1.37 rillig * The rule for combining two combos (<F1,W1> <F2,W2>) with V valid
122 1.36 rillig * intersection points is:
123 1.37 rillig * F' = F1 + F2 - 2 - V
124 1.37 rillig * W' = MIN(F1 + W1 - 1, F2 + W2 - 1)
125 1.36 rillig */
126 1.22 rillig union comboval {
127 1.1 tls struct {
128 1.1 tls #if BYTE_ORDER == BIG_ENDIAN
129 1.37 rillig u_char a;
130 1.37 rillig u_char b;
131 1.1 tls #endif
132 1.1 tls #if BYTE_ORDER == LITTLE_ENDIAN
133 1.37 rillig u_char b;
134 1.37 rillig u_char a;
135 1.1 tls #endif
136 1.1 tls } c;
137 1.1 tls u_short s;
138 1.1 tls };
139 1.37 rillig #define cv_force c.a /* # moves to complete force */
140 1.37 rillig #define cv_win c.b /* # moves to win */
141 1.1 tls
142 1.1 tls /*
143 1.1 tls * This structure is used to record information about single frames (F) and
144 1.1 tls * combinations of two more frames (C).
145 1.1 tls * For combinations of two or more frames, there is an additional
146 1.1 tls * array of pointers to the frames of the combination which is sorted
147 1.1 tls * by the index into the frames[] array. This is used to prevent duplication
148 1.1 tls * since frame A combined with B is the same as B with A.
149 1.1 tls * struct combostr *c_sort[size c_nframes];
150 1.1 tls * The leaves of the tree (frames) are numbered 0 (bottom, leftmost)
151 1.1 tls * to c_nframes - 1 (top, right). This is stored in c_frameindex and
152 1.1 tls * c_dir if C_LOOP is set.
153 1.1 tls */
154 1.1 tls struct combostr {
155 1.1 tls struct combostr *c_next; /* list of combos at the same level */
156 1.1 tls struct combostr *c_prev; /* list of combos at the same level */
157 1.39 rillig struct combostr *c_link[2]; /* F: NULL,
158 1.39 rillig * C: previous level */
159 1.39 rillig union comboval c_linkv[2]; /* C: combo value for link[0, 1] */
160 1.39 rillig union comboval c_combo; /* F: initial combo value (read-only),
161 1.39 rillig * C: combo value for this level */
162 1.49 rillig spot_index c_vertex; /* F: frame head,
163 1.39 rillig * C: intersection */
164 1.39 rillig u_char c_nframes; /* F: 1,
165 1.39 rillig * C: number of frames in the combo */
166 1.39 rillig u_char c_dir; /* F: frame direction,
167 1.39 rillig * C: loop frame */
168 1.39 rillig u_char c_flags; /* C: combo flags */
169 1.39 rillig u_char c_frameindex; /* C: intersection frame index */
170 1.1 tls u_char c_framecnt[2]; /* number of frames left to attach */
171 1.39 rillig u_char c_emask[2]; /* C: bit mask of completion spots for
172 1.1 tls * link[0] and link[1] */
173 1.39 rillig u_char c_voff[2]; /* C: vertex offset within frame */
174 1.1 tls };
175 1.1 tls
176 1.11 dholland /* flag values for c_flags */
177 1.31 rillig #define C_OPEN_0 0x01 /* link[0] is an open-ended frame */
178 1.31 rillig #define C_OPEN_1 0x02 /* link[1] is an open-ended frame */
179 1.1 tls #define C_LOOP 0x04 /* link[1] intersects previous frame */
180 1.1 tls
181 1.1 tls /*
182 1.1 tls * This structure is used for recording the completion points of
183 1.1 tls * multi frame combos.
184 1.1 tls */
185 1.1 tls struct elist {
186 1.1 tls struct elist *e_next; /* list of completion points */
187 1.1 tls struct combostr *e_combo; /* the whole combo */
188 1.1 tls u_char e_off; /* offset in frame of this empty spot */
189 1.1 tls u_char e_frameindex; /* intersection frame index */
190 1.1 tls u_char e_framecnt; /* number of frames left to attach */
191 1.1 tls u_char e_emask; /* real value of the frame's emask */
192 1.1 tls union comboval e_fval; /* frame combo value */
193 1.1 tls };
194 1.1 tls
195 1.49 rillig /* The index of a frame in the global 'frames'. */
196 1.49 rillig typedef unsigned short frame_index;
197 1.49 rillig
198 1.50 rillig /* 0 = right, 1 = down right, 2 = down, 3 = down left. */
199 1.50 rillig typedef unsigned char direction;
200 1.50 rillig
201 1.1 tls /*
202 1.1 tls * One spot structure for each location on the board.
203 1.50 rillig * A frame consists of the combination for the current spot plus the next
204 1.50 rillig * five spots in the direction.
205 1.1 tls */
206 1.1 tls struct spotstr {
207 1.1 tls short s_occ; /* color of occupant */
208 1.1 tls short s_wval; /* weighted value */
209 1.11 dholland int s_flags; /* flags for graph walks */
210 1.49 rillig frame_index s_frame[4]; /* level 1 combo for [dir] */
211 1.50 rillig union comboval s_fval[2][4]; /* combo value for [color][dir] */
212 1.50 rillig union comboval s_combo[2]; /* minimum combo value for [color] */
213 1.1 tls u_char s_level[2]; /* number of frames in the min combo */
214 1.1 tls u_char s_nforce[2]; /* number of <1,x> combos */
215 1.1 tls struct elist *s_empty; /* level n combo completion spots */
216 1.1 tls struct elist *s_nempty; /* level n+1 combo completion spots */
217 1.1 tls };
218 1.1 tls
219 1.11 dholland /* flag values for s_flags */
220 1.1 tls #define CFLAG 0x000001 /* frame is part of a combo */
221 1.1 tls #define CFLAGALL 0x00000F /* all frame directions marked */
222 1.1 tls #define IFLAG 0x000010 /* legal intersection point */
223 1.1 tls #define IFLAGALL 0x0000F0 /* any intersection points? */
224 1.1 tls #define FFLAG 0x000100 /* frame is part of a <1,x> combo */
225 1.1 tls #define FFLAGALL 0x000F00 /* all force frames */
226 1.1 tls #define MFLAG 0x001000 /* frame has already been seen */
227 1.1 tls #define MFLAGALL 0x00F000 /* all frames seen */
228 1.1 tls #define BFLAG 0x010000 /* frame intersects border or dead */
229 1.1 tls #define BFLAGALL 0x0F0000 /* all frames dead */
230 1.1 tls
231 1.43 rillig struct game {
232 1.50 rillig unsigned int nmoves; /* number of played moves */
233 1.50 rillig spot_index moves[BSZ * BSZ]; /* log of all played moves */
234 1.51 rillig spot_index win_spot; /* the winning move, or 0 */
235 1.51 rillig direction win_dir;
236 1.43 rillig };
237 1.43 rillig
238 1.38 rillig extern const char letters[];
239 1.6 jsm extern const char pdir[];
240 1.1 tls
241 1.6 jsm extern const int dd[4];
242 1.1 tls extern struct spotstr board[BAREA]; /* info for board */
243 1.1 tls extern struct combostr frames[FAREA]; /* storage for single frames */
244 1.1 tls extern struct combostr *sortframes[2]; /* sorted, non-empty frames */
245 1.42 rillig extern u_char overlap[FAREA * FAREA];
246 1.48 rillig extern spot_index intersect[FAREA * FAREA]; /* frame [a][b] intersection */
247 1.43 rillig extern struct game game;
248 1.1 tls extern int debug;
249 1.1 tls
250 1.28 rillig extern bool interactive;
251 1.20 dholland extern const char *plyr[];
252 1.20 dholland
253 1.45 rillig void init_board(void);
254 1.18 dholland int get_coord(void);
255 1.28 rillig int get_key(const char *);
256 1.33 rillig bool get_line(char *, int, void (*)(const char *));
257 1.10 jsm void ask(const char *);
258 1.10 jsm void dislog(const char *);
259 1.10 jsm void bdump(FILE *);
260 1.10 jsm void bdisp(void);
261 1.10 jsm void bdisp_init(void);
262 1.10 jsm void cursfini(void);
263 1.10 jsm void cursinit(void);
264 1.32 rillig void bdwho(void);
265 1.13 dholland void panic(const char *, ...) __printflike(1, 2) __dead;
266 1.13 dholland void debuglog(const char *, ...) __printflike(1, 2);
267 1.10 jsm void whatsup(int);
268 1.47 rillig const char *stoc(spot_index);
269 1.47 rillig spot_index ctos(const char *);
270 1.48 rillig int makemove(int, spot_index);
271 1.10 jsm void clearcombo(struct combostr *, int);
272 1.10 jsm void markcombo(struct combostr *);
273 1.10 jsm int pickmove(int);
274 1.27 rillig #if defined(DEBUG)
275 1.27 rillig void printcombo(struct combostr *, char *, size_t);
276 1.27 rillig #endif
277