From 13b5b0009082f9bc2c991c326ca650178761bdff Mon Sep 17 00:00:00 2001 From: tls Date: Sat, 28 Dec 1996 18:44:55 +0000 Subject: Import of 4.4BSD-Lite2 source --- gomoku/gomoku.h | 266 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 266 insertions(+) create mode 100644 gomoku/gomoku.h (limited to 'gomoku/gomoku.h') diff --git a/gomoku/gomoku.h b/gomoku/gomoku.h new file mode 100644 index 00000000..173e329f --- /dev/null +++ b/gomoku/gomoku.h @@ -0,0 +1,266 @@ +/* + * Copyright (c) 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Ralph Campbell. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)gomoku.h 8.2 (Berkeley) 5/3/95 + */ + +#include + +/* board dimensions */ +#define BSZ 19 +#define BSZ1 (BSZ+1) +#define BSZ2 (BSZ+2) +#define BAREA (BSZ2*BSZ1+1) + +/* frame dimentions (based on 5 in a row) */ +#define FSZ1 BSZ +#define FSZ2 (BSZ-4) +#define FAREA (FSZ1*FSZ2 + FSZ2*FSZ2 + FSZ1*FSZ2 + FSZ2*FSZ2) + +#define MUP (BSZ1) +#define MDOWN (-BSZ1) +#define MLEFT (-1) +#define MRIGHT (1) + +/* values for s_occ */ +#define BLACK 0 +#define WHITE 1 +#define EMPTY 2 +#define BORDER 3 + +/* return values for makemove() */ +#define MOVEOK 0 +#define RESIGN 1 +#define ILLEGAL 2 +#define WIN 3 +#define TIE 4 +#define SAVE 5 + +#define A 1 +#define B 2 +#define C 3 +#define D 4 +#define E 5 +#define F 6 +#define G 7 +#define H 8 +#define J 9 +#define K 10 +#define L 11 +#define M 12 +#define N 13 +#define O 14 +#define P 15 +#define Q 16 +#define R 17 +#define S 18 +#define T 19 + +#define PT(x,y) ((x) + BSZ1 * (y)) + +/* + * A 'frame' is a group of five or six contiguous board locations. + * An open ended frame is one with spaces on both ends; otherwise, its closed. + * A 'combo' is a group of intersecting frames and consists of two numbers: + * 'A' is the number of moves to make the combo non-blockable. + * 'B' is the minimum number of moves needed to win once it can't be blocked. + * A 'force' is a combo that is one move away from being non-blockable + * + * Single frame combo values: + * board values + * 5,0 . . . . . O + * 4,1 . . . . . . + * 4,0 . . . . X O + * 3,1 . . . . X . + * 3,0 . . . X X O + * 2,1 . . . X X . + * 2,0 . . X X X O + * 1,1 . . X X X . + * 1,0 . X X X X O + * 0,1 . X X X X . + * 0,0 X X X X X O + * + * The rule for combining two combos ( ) + * with V valid intersection points, is: + * A' = A1 + A2 - 2 - V + * B' = MIN(A1 + B1 - 1, A2 + B2 - 1) + * Each time a frame is added to the combo, the number of moves to complete + * the force is the number of moves needed to 'fill' the frame plus one at + * the intersection point. The number of moves to win is the number of moves + * to complete the best frame minus the last move to complete the force. + * Note that it doesn't make sense to combine a <1,x> with anything since + * it is already a force. Also, the frames have to be independent so a + * single move doesn't affect more than one frame making up the combo. + * + * Rules for comparing which of two combos ( ) is better: + * Both the same color: + * = (A1 < A2 || A1 == A2 && B1 <= B2) ? : + * We want to complete the force first, then the combo with the + * fewest moves to win. + * Different colors, is the combo for the player with the next move: + * = A2 <= 1 && (A1 > 1 || A2 + B2 < A1 + B1) ? : + * We want to block only if we have to (i.e., if they are one move away + * from completing a force and we don't have a force that we can + * complete which takes fewer or the same number of moves to win). + */ + +#define MAXA 6 +#define MAXB 2 +#define MAXCOMBO 0x600 + +union comboval { + struct { +#if BYTE_ORDER == BIG_ENDIAN + u_char a; /* # moves to complete force */ + u_char b; /* # moves to win */ +#endif +#if BYTE_ORDER == LITTLE_ENDIAN + u_char b; /* # moves to win */ + u_char a; /* # moves to complete force */ +#endif + } c; + u_short s; +}; + +/* + * This structure is used to record information about single frames (F) and + * combinations of two more frames (C). + * For combinations of two or more frames, there is an additional + * array of pointers to the frames of the combination which is sorted + * by the index into the frames[] array. This is used to prevent duplication + * since frame A combined with B is the same as B with A. + * struct combostr *c_sort[size c_nframes]; + * The leaves of the tree (frames) are numbered 0 (bottom, leftmost) + * to c_nframes - 1 (top, right). This is stored in c_frameindex and + * c_dir if C_LOOP is set. + */ +struct combostr { + struct combostr *c_next; /* list of combos at the same level */ + struct combostr *c_prev; /* list of combos at the same level */ + struct combostr *c_link[2]; /* C:previous level or F:NULL */ + union comboval c_linkv[2]; /* C:combo value for link[0,1] */ + union comboval c_combo; /* C:combo value for this level */ + u_short c_vertex; /* C:intersection or F:frame head */ + u_char c_nframes; /* number of frames in the combo */ + u_char c_dir; /* C:loop frame or F:frame direction */ + u_char c_flg; /* C:combo flags */ + u_char c_frameindex; /* C:intersection frame index */ + u_char c_framecnt[2]; /* number of frames left to attach */ + u_char c_emask[2]; /* C:bit mask of completion spots for + * link[0] and link[1] */ + u_char c_voff[2]; /* C:vertex offset within frame */ +}; + +/* flag values for c_flg */ +#define C_OPEN_0 0x01 /* link[0] is an open ended frame */ +#define C_OPEN_1 0x02 /* link[1] is an open ended frame */ +#define C_LOOP 0x04 /* link[1] intersects previous frame */ +#define C_MARK 0x08 /* indicates combo processed */ + +/* + * This structure is used for recording the completion points of + * multi frame combos. + */ +struct elist { + struct elist *e_next; /* list of completion points */ + struct combostr *e_combo; /* the whole combo */ + u_char e_off; /* offset in frame of this empty spot */ + u_char e_frameindex; /* intersection frame index */ + u_char e_framecnt; /* number of frames left to attach */ + u_char e_emask; /* real value of the frame's emask */ + union comboval e_fval; /* frame combo value */ +}; + +/* + * One spot structure for each location on the board. + * A frame consists of the combination for the current spot plus the five spots + * 0: right, 1: right & down, 2: down, 3: down & left. + */ +struct spotstr { + short s_occ; /* color of occupant */ + short s_wval; /* weighted value */ + int s_flg; /* flags for graph walks */ + struct combostr *s_frame[4]; /* level 1 combo for frame[dir] */ + union comboval s_fval[2][4]; /* combo value for [color][frame] */ + union comboval s_combo[2]; /* minimum combo value for BLK & WHT */ + u_char s_level[2]; /* number of frames in the min combo */ + u_char s_nforce[2]; /* number of <1,x> combos */ + struct elist *s_empty; /* level n combo completion spots */ + struct elist *s_nempty; /* level n+1 combo completion spots */ + int dummy[2]; /* XXX */ +}; + +/* flag values for s_flg */ +#define CFLAG 0x000001 /* frame is part of a combo */ +#define CFLAGALL 0x00000F /* all frame directions marked */ +#define IFLAG 0x000010 /* legal intersection point */ +#define IFLAGALL 0x0000F0 /* any intersection points? */ +#define FFLAG 0x000100 /* frame is part of a <1,x> combo */ +#define FFLAGALL 0x000F00 /* all force frames */ +#define MFLAG 0x001000 /* frame has already been seen */ +#define MFLAGALL 0x00F000 /* all frames seen */ +#define BFLAG 0x010000 /* frame intersects border or dead */ +#define BFLAGALL 0x0F0000 /* all frames dead */ + +/* + * This structure is used to store overlap information between frames. + */ +struct ovlp_info { + int o_intersect; /* intersection spot */ + struct combostr *o_fcombo; /* the connecting combo */ + u_char o_link; /* which link to update (0 or 1) */ + u_char o_off; /* offset in frame of intersection */ + u_char o_frameindex; /* intersection frame index */ +}; + +extern char *letters; +extern char fmtbuf[]; +extern char pdir[]; + +extern int dd[4]; +extern struct spotstr board[BAREA]; /* info for board */ +extern struct combostr frames[FAREA]; /* storage for single frames */ +extern struct combostr *sortframes[2]; /* sorted, non-empty frames */ +extern u_char overlap[FAREA * FAREA]; /* frame [a][b] overlap */ +extern short intersect[FAREA * FAREA]; /* frame [a][b] intersection */ +extern int movelog[BSZ * BSZ]; /* history of moves */ +extern int movenum; +extern int debug; + +extern char *copy(); +extern char *stoc(); +extern char *tail(); + +#define ASSERT(x) -- cgit v1.2.3-56-ge451