Expand PMF_FN_* macros.
[netbsd-mini2440.git] / games / gomoku / gomoku.h
blobfeb3cef5d1f67843f3bb2c5ed1b75981b6ab64b0
1 /* $NetBSD: gomoku.h,v 1.16 2009/07/13 19:05:40 roy Exp $ */
3 /*
4 * Copyright (c) 1994
5 * The Regents of the University of California. All rights reserved.
7 * This code is derived from software contributed to Berkeley by
8 * Ralph Campbell.
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.
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.
34 * @(#)gomoku.h 8.2 (Berkeley) 5/3/95
37 #include <sys/types.h>
38 #include <sys/endian.h>
39 #include <stdio.h>
41 /* board dimensions */
42 #define BSZ 19
43 #define BSZ1 (BSZ+1)
44 #define BSZ2 (BSZ+2)
45 #define BAREA (BSZ2*BSZ1+1)
47 /* frame dimentions (based on 5 in a row) */
48 #define FSZ1 BSZ
49 #define FSZ2 (BSZ-4)
50 #define FAREA (FSZ1*FSZ2 + FSZ2*FSZ2 + FSZ1*FSZ2 + FSZ2*FSZ2)
52 #define MUP (BSZ1)
53 #define MDOWN (-BSZ1)
54 #define MLEFT (-1)
55 #define MRIGHT (1)
57 /* values for s_occ */
58 #define BLACK 0
59 #define WHITE 1
60 #define EMPTY 2
61 #define BORDER 3
63 /* return values for makemove() */
64 #define MOVEOK 0
65 #define RESIGN 1
66 #define ILLEGAL 2
67 #define WIN 3
68 #define TIE 4
69 #define SAVE 5
71 #define A 1
72 #define B 2
73 #define C 3
74 #define D 4
75 #define E 5
76 #define F 6
77 #define G 7
78 #define H 8
79 #define J 9
80 #define K 10
81 #define L 11
82 #define M 12
83 #define N 13
84 #define O 14
85 #define P 15
86 #define Q 16
87 #define R 17
88 #define S 18
89 #define T 19
91 #define PT(x,y) ((x) + BSZ1 * (y))
94 * A 'frame' is a group of five or six contiguous board locations.
95 * An open ended frame is one with spaces on both ends; otherwise, its closed.
96 * A 'combo' is a group of intersecting frames and consists of two numbers:
97 * 'A' is the number of moves to make the combo non-blockable.
98 * 'B' is the minimum number of moves needed to win once it can't be blocked.
99 * A 'force' is a combo that is one move away from being non-blockable
101 * Single frame combo values:
102 * <A,B> board values
103 * 5,0 . . . . . O
104 * 4,1 . . . . . .
105 * 4,0 . . . . X O
106 * 3,1 . . . . X .
107 * 3,0 . . . X X O
108 * 2,1 . . . X X .
109 * 2,0 . . X X X O
110 * 1,1 . . X X X .
111 * 1,0 . X X X X O
112 * 0,1 . X X X X .
113 * 0,0 X X X X X O
115 * The rule for combining two combos (<A1,B1> <A2,B2>)
116 * with V valid intersection points, is:
117 * A' = A1 + A2 - 2 - V
118 * B' = MIN(A1 + B1 - 1, A2 + B2 - 1)
119 * Each time a frame is added to the combo, the number of moves to complete
120 * the force is the number of moves needed to 'fill' the frame plus one at
121 * the intersection point. The number of moves to win is the number of moves
122 * to complete the best frame minus the last move to complete the force.
123 * Note that it doesn't make sense to combine a <1,x> with anything since
124 * it is already a force. Also, the frames have to be independent so a
125 * single move doesn't affect more than one frame making up the combo.
127 * Rules for comparing which of two combos (<A1,B1> <A2,B2>) is better:
128 * Both the same color:
129 * <A',B'> = (A1 < A2 || A1 == A2 && B1 <= B2) ? <A1,B1> : <A2,B2>
130 * We want to complete the force first, then the combo with the
131 * fewest moves to win.
132 * Different colors, <A1,B1> is the combo for the player with the next move:
133 * <A',B'> = A2 <= 1 && (A1 > 1 || A2 + B2 < A1 + B1) ? <A2,B2> : <A1,B1>
134 * We want to block only if we have to (i.e., if they are one move away
135 * from completing a force and we don't have a force that we can
136 * complete which takes fewer or the same number of moves to win).
139 #define MAXA 6
140 #define MAXB 2
141 #define MAXCOMBO 0x600
143 union comboval {
144 struct {
145 #if BYTE_ORDER == BIG_ENDIAN
146 u_char a; /* # moves to complete force */
147 u_char b; /* # moves to win */
148 #endif
149 #if BYTE_ORDER == LITTLE_ENDIAN
150 u_char b; /* # moves to win */
151 u_char a; /* # moves to complete force */
152 #endif
153 } c;
154 u_short s;
158 * This structure is used to record information about single frames (F) and
159 * combinations of two more frames (C).
160 * For combinations of two or more frames, there is an additional
161 * array of pointers to the frames of the combination which is sorted
162 * by the index into the frames[] array. This is used to prevent duplication
163 * since frame A combined with B is the same as B with A.
164 * struct combostr *c_sort[size c_nframes];
165 * The leaves of the tree (frames) are numbered 0 (bottom, leftmost)
166 * to c_nframes - 1 (top, right). This is stored in c_frameindex and
167 * c_dir if C_LOOP is set.
169 struct combostr {
170 struct combostr *c_next; /* list of combos at the same level */
171 struct combostr *c_prev; /* list of combos at the same level */
172 struct combostr *c_link[2]; /* C:previous level or F:NULL */
173 union comboval c_linkv[2]; /* C:combo value for link[0,1] */
174 union comboval c_combo; /* C:combo value for this level */
175 u_short c_vertex; /* C:intersection or F:frame head */
176 u_char c_nframes; /* number of frames in the combo */
177 u_char c_dir; /* C:loop frame or F:frame direction */
178 u_char c_flags; /* C:combo flags */
179 u_char c_frameindex; /* C:intersection frame index */
180 u_char c_framecnt[2]; /* number of frames left to attach */
181 u_char c_emask[2]; /* C:bit mask of completion spots for
182 * link[0] and link[1] */
183 u_char c_voff[2]; /* C:vertex offset within frame */
186 /* flag values for c_flags */
187 #define C_OPEN_0 0x01 /* link[0] is an open ended frame */
188 #define C_OPEN_1 0x02 /* link[1] is an open ended frame */
189 #define C_LOOP 0x04 /* link[1] intersects previous frame */
190 #define C_MARK 0x08 /* indicates combo processed */
193 * This structure is used for recording the completion points of
194 * multi frame combos.
196 struct elist {
197 struct elist *e_next; /* list of completion points */
198 struct combostr *e_combo; /* the whole combo */
199 u_char e_off; /* offset in frame of this empty spot */
200 u_char e_frameindex; /* intersection frame index */
201 u_char e_framecnt; /* number of frames left to attach */
202 u_char e_emask; /* real value of the frame's emask */
203 union comboval e_fval; /* frame combo value */
207 * One spot structure for each location on the board.
208 * A frame consists of the combination for the current spot plus the five spots
209 * 0: right, 1: right & down, 2: down, 3: down & left.
211 struct spotstr {
212 short s_occ; /* color of occupant */
213 short s_wval; /* weighted value */
214 int s_flags; /* flags for graph walks */
215 struct combostr *s_frame[4]; /* level 1 combo for frame[dir] */
216 union comboval s_fval[2][4]; /* combo value for [color][frame] */
217 union comboval s_combo[2]; /* minimum combo value for BLK & WHT */
218 u_char s_level[2]; /* number of frames in the min combo */
219 u_char s_nforce[2]; /* number of <1,x> combos */
220 struct elist *s_empty; /* level n combo completion spots */
221 struct elist *s_nempty; /* level n+1 combo completion spots */
222 int dummy[2]; /* XXX */
225 /* flag values for s_flags */
226 #define CFLAG 0x000001 /* frame is part of a combo */
227 #define CFLAGALL 0x00000F /* all frame directions marked */
228 #define IFLAG 0x000010 /* legal intersection point */
229 #define IFLAGALL 0x0000F0 /* any intersection points? */
230 #define FFLAG 0x000100 /* frame is part of a <1,x> combo */
231 #define FFLAGALL 0x000F00 /* all force frames */
232 #define MFLAG 0x001000 /* frame has already been seen */
233 #define MFLAGALL 0x00F000 /* all frames seen */
234 #define BFLAG 0x010000 /* frame intersects border or dead */
235 #define BFLAGALL 0x0F0000 /* all frames dead */
238 * This structure is used to store overlap information between frames.
240 struct overlap_info {
241 int o_intersect; /* intersection spot */
242 struct combostr *o_fcombo; /* the connecting combo */
243 u_char o_link; /* which link to update (0 or 1) */
244 u_char o_off; /* offset in frame of intersection */
245 u_char o_frameindex; /* intersection frame index */
248 extern const char *letters;
249 extern const char pdir[];
251 extern const int dd[4];
252 extern struct spotstr board[BAREA]; /* info for board */
253 extern struct combostr frames[FAREA]; /* storage for single frames */
254 extern struct combostr *sortframes[2]; /* sorted, non-empty frames */
255 extern u_char overlap[FAREA * FAREA]; /* frame [a][b] overlap */
256 extern short intersect[FAREA * FAREA]; /* frame [a][b] intersection */
257 extern int movelog[BSZ * BSZ]; /* history of moves */
258 extern int movenum;
259 extern int debug;
261 #define ASSERT(x)
263 void bdinit(struct spotstr *);
264 int get_line(char *, int);
265 void ask(const char *);
266 void dislog(const char *);
267 void bdump(FILE *);
268 void bdisp(void);
269 void bdisp_init(void);
270 void cursfini(void);
271 void cursinit(void);
272 void bdwho(int);
273 void panic(const char *, ...) __printflike(1, 2) __dead;
274 void debuglog(const char *, ...) __printflike(1, 2);
275 void whatsup(int);
276 const char *stoc(int);
277 int ctos(const char *);
278 int makemove(int, int);
279 int list_eq(struct combostr **, struct combostr **, int);
280 void clearcombo(struct combostr *, int);
281 void markcombo(struct combostr *);
282 int pickmove(int);