gomoku/gomoku.h

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