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