gomoku/gomoku.h

   1 /*      $NetBSD: gomoku.h,v 1.3 1997/01/03 01:35:27 cgd 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. All advertising materials mentioning features or use of this software
  19  *    must display the following acknowledgement:
  20  *      This product includes software developed by the University of
  21  *      California, Berkeley and its contributors.
  22  * 4. Neither the name of the University nor the names of its contributors
  23  *    may be used to endorse or promote products derived from this software
  24  *    without specific prior written permission.
  25  *
  26  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36  * SUCH DAMAGE.
  37  *
  38  *      @(#)gomoku.h    8.2 (Berkeley) 5/3/95
  39  */
  40
  41 #include <sys/types.h>
  42
  43 /* board dimensions */
  44 #define BSZ     19
  45 #define BSZ1    (BSZ+1)
  46 #define BSZ2    (BSZ+2)
  47 #define BAREA   (BSZ2*BSZ1+1)
  48
  49 /* frame dimentions (based on 5 in a row) */
  50 #define FSZ1    BSZ
  51 #define FSZ2    (BSZ-4)
  52 #define FAREA   (FSZ1*FSZ2 + FSZ2*FSZ2 + FSZ1*FSZ2 + FSZ2*FSZ2)
  53
  54 #define MUP     (BSZ1)
  55 #define MDOWN   (-BSZ1)
  56 #define MLEFT   (-1)
  57 #define MRIGHT  (1)
  58
  59 /* values for s_occ */
  60 #define BLACK   0
  61 #define WHITE   1
  62 #define EMPTY   2
  63 #define BORDER  3
  64
  65 /* return values for makemove() */
  66 #define MOVEOK  0
  67 #define RESIGN  1
  68 #define ILLEGAL 2
  69 #define WIN     3
  70 #define TIE     4
  71 #define SAVE    5
  72
  73 #define A 1
  74 #define B 2
  75 #define C 3
  76 #define D 4
  77 #define E 5
  78 #define F 6
  79 #define G 7
  80 #define H 8
  81 #define J 9
  82 #define K 10
  83 #define L 11
  84 #define M 12
  85 #define N 13
  86 #define O 14
  87 #define P 15
  88 #define Q 16
  89 #define R 17
  90 #define S 18
  91 #define T 19
  92
  93 #define PT(x,y)         ((x) + BSZ1 * (y))
  94
  95 /*
  96  * A 'frame' is a group of five or six contiguous board locations.
  97  * An open ended frame is one with spaces on both ends; otherwise, its closed.
  98  * A 'combo' is a group of intersecting frames and consists of two numbers:
  99  * 'A' is the number of moves to make the combo non-blockable.
 100  * 'B' is the minimum number of moves needed to win once it can't be blocked.
 101  * A 'force' is a combo that is one move away from being non-blockable
 102  *
 103  * Single frame combo values:
 104  *     <A,B>    board values
 105  *      5,0     . . . . . O
 106  *      4,1     . . . . . .
 107  *      4,0     . . . . X O
 108  *      3,1     . . . . X .
 109  *      3,0     . . . X X O
 110  *      2,1     . . . X X .
 111  *      2,0     . . X X X O
 112  *      1,1     . . X X X .
 113  *      1,0     . X X X X O
 114  *      0,1     . X X X X .
 115  *      0,0     X X X X X O
 116  *
 117  * The rule for combining two combos (<A1,B1> <A2,B2>)
 118  * with V valid intersection points, is:
 119  *      A' = A1 + A2 - 2 - V
 120  *      B' = MIN(A1 + B1 - 1, A2 + B2 - 1)
 121  * Each time a frame is added to the combo, the number of moves to complete
 122  * the force is the number of moves needed to 'fill' the frame plus one at
 123  * the intersection point. The number of moves to win is the number of moves
 124  * to complete the best frame minus the last move to complete the force.
 125  * Note that it doesn't make sense to combine a <1,x> with anything since
 126  * it is already a force. Also, the frames have to be independent so a
 127  * single move doesn't affect more than one frame making up the combo.
 128  *
 129  * Rules for comparing which of two combos (<A1,B1> <A2,B2>) is better:
 130  * Both the same color:
 131  *      <A',B'> = (A1 < A2 || A1 == A2 && B1 <= B2) ? <A1,B1> : <A2,B2>
 132  *      We want to complete the force first, then the combo with the
 133  *      fewest moves to win.
 134  * Different colors, <A1,B1> is the combo for the player with the next move:
 135  *      <A',B'> = A2 <= 1 && (A1 > 1 || A2 + B2 < A1 + B1) ? <A2,B2> : <A1,B1>
 136  *      We want to block only if we have to (i.e., if they are one move away
 137  *      from completing a force and we don't have a force that we can
 138  *      complete which takes fewer or the same number of moves to win).
 139  */
 140
 141 #define MAXA            6
 142 #define MAXB            2
 143 #define MAXCOMBO        0x600
 144
 145 union   comboval {
 146         struct {
 147 #if BYTE_ORDER == BIG_ENDIAN
 148                 u_char  a;      /* # moves to complete force */
 149                 u_char  b;      /* # moves to win */
 150 #endif
 151 #if BYTE_ORDER == LITTLE_ENDIAN
 152                 u_char  b;      /* # moves to win */
 153                 u_char  a;      /* # moves to complete force */
 154 #endif
 155         } c;
 156         u_short s;
 157 };
 158
 159 /*
 160  * This structure is used to record information about single frames (F) and
 161  * combinations of two more frames (C).
 162  * For combinations of two or more frames, there is an additional
 163  * array of pointers to the frames of the combination which is sorted
 164  * by the index into the frames[] array. This is used to prevent duplication
 165  * since frame A combined with B is the same as B with A.
 166  *      struct combostr *c_sort[size c_nframes];
 167  * The leaves of the tree (frames) are numbered 0 (bottom, leftmost)
 168  * to c_nframes - 1 (top, right). This is stored in c_frameindex and
 169  * c_dir if C_LOOP is set.
 170  */
 171 struct combostr {
 172         struct combostr *c_next;        /* list of combos at the same level */
 173         struct combostr *c_prev;        /* list of combos at the same level */
 174         struct combostr *c_link[2];     /* C:previous level or F:NULL */
 175         union comboval  c_linkv[2];     /* C:combo value for link[0,1] */
 176         union comboval  c_combo;        /* C:combo value for this level */
 177         u_short         c_vertex;       /* C:intersection or F:frame head */
 178         u_char          c_nframes;      /* number of frames in the combo */
 179         u_char          c_dir;          /* C:loop frame or F:frame direction */
 180         u_char          c_flg;          /* C:combo flags */
 181         u_char          c_frameindex;   /* C:intersection frame index */
 182         u_char          c_framecnt[2];  /* number of frames left to attach */
 183         u_char          c_emask[2];     /* C:bit mask of completion spots for
 184                                          * link[0] and link[1] */
 185         u_char          c_voff[2];      /* C:vertex offset within frame */
 186 };
 187
 188 /* flag values for c_flg */
 189 #define C_OPEN_0        0x01            /* link[0] is an open ended frame */
 190 #define C_OPEN_1        0x02            /* link[1] is an open ended frame */
 191 #define C_LOOP          0x04            /* link[1] intersects previous frame */
 192 #define C_MARK          0x08            /* indicates combo processed */
 193
 194 /*
 195  * This structure is used for recording the completion points of
 196  * multi frame combos.
 197  */
 198 struct  elist {
 199         struct elist    *e_next;        /* list of completion points */
 200         struct combostr *e_combo;       /* the whole combo */
 201         u_char          e_off;          /* offset in frame of this empty spot */
 202         u_char          e_frameindex;   /* intersection frame index */
 203         u_char          e_framecnt;     /* number of frames left to attach */
 204         u_char          e_emask;        /* real value of the frame's emask */
 205         union comboval  e_fval;         /* frame combo value */
 206 };
 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 five spots
 211  * 0: right, 1: right & down, 2: down, 3: down & left.
 212  */
 213 struct  spotstr {
 214         short           s_occ;          /* color of occupant */
 215         short           s_wval;         /* weighted value */
 216         int             s_flg;          /* flags for graph walks */
 217         struct combostr *s_frame[4];    /* level 1 combo for frame[dir] */
 218         union comboval  s_fval[2][4];   /* combo value for [color][frame] */
 219         union comboval  s_combo[2];     /* minimum combo value for BLK & WHT */
 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         int             dummy[2];       /* XXX */
 225 };
 226
 227 /* flag values for s_flg */
 228 #define CFLAG           0x000001        /* frame is part of a combo */
 229 #define CFLAGALL        0x00000F        /* all frame directions marked */
 230 #define IFLAG           0x000010        /* legal intersection point */
 231 #define IFLAGALL        0x0000F0        /* any intersection points? */
 232 #define FFLAG           0x000100        /* frame is part of a <1,x> combo */
 233 #define FFLAGALL        0x000F00        /* all force frames */
 234 #define MFLAG           0x001000        /* frame has already been seen */
 235 #define MFLAGALL        0x00F000        /* all frames seen */
 236 #define BFLAG           0x010000        /* frame intersects border or dead */
 237 #define BFLAGALL        0x0F0000        /* all frames dead */
 238
 239 /*
 240  * This structure is used to store overlap information between frames.
 241  */
 242 struct  ovlp_info {
 243         int             o_intersect;    /* intersection spot */
 244         struct combostr *o_fcombo;      /* the connecting combo */
 245         u_char          o_link;         /* which link to update (0 or 1) */
 246         u_char          o_off;          /* offset in frame of intersection */
 247         u_char          o_frameindex;   /* intersection frame index */
 248 };
 249
 250 extern  char    *letters;
 251 extern  char    fmtbuf[];
 252 extern  char    pdir[];
 253
 254 extern  int     dd[4];
 255 extern  struct  spotstr board[BAREA];           /* info for board */
 256 extern  struct  combostr frames[FAREA];         /* storage for single frames */
 257 extern  struct  combostr *sortframes[2];        /* sorted, non-empty frames */
 258 extern  u_char  overlap[FAREA * FAREA];         /* frame [a][b] overlap */
 259 extern  short   intersect[FAREA * FAREA];       /* frame [a][b] intersection */
 260 extern  int     movelog[BSZ * BSZ];             /* history of moves */
 261 extern  int     movenum;
 262 extern  int     debug;
 263
 264 extern  char    *copy();
 265 extern  char    *stoc();
 266 extern  char    *tail();
 267
 268 #define ASSERT(x)