gomoku/gomoku.h

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