games/gomoku/gomoku.h

   1 /*      $NetBSD: gomoku.h,v 1.16 2009/07/13 19:05:40 roy 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 <sys/endian.h>
  39 #include <stdio.h>
  40
  41 /* board dimensions */
  42 #define BSZ     19
  43 #define BSZ1    (BSZ+1)
  44 #define BSZ2    (BSZ+2)
  45 #define BAREA   (BSZ2*BSZ1+1)
  46
  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)
  51
  52 #define MUP     (BSZ1)
  53 #define MDOWN   (-BSZ1)
  54 #define MLEFT   (-1)
  55 #define MRIGHT  (1)
  56
  57 /* values for s_occ */
  58 #define BLACK   0
  59 #define WHITE   1
  60 #define EMPTY   2
  61 #define BORDER  3
  62
  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
  70
  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
  90
  91 #define PT(x,y)         ((x) + BSZ1 * (y))
  92
  93 /*
  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
 100  *
 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
 114  *
 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.
 126  *
 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).
 137  */
 138
 139 #define MAXA            6
 140 #define MAXB            2
 141 #define MAXCOMBO        0x600
 142
 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;
 155 };
 156
 157 /*
 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.
 168  */
 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 */
 184 };
 185
 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 */
 191
 192 /*
 193  * This structure is used for recording the completion points of
 194  * multi frame combos.
 195  */
 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 */
 204 };
 205
 206 /*
 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.
 210  */
 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 */
 223 };
 224
 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 */
 236
 237 /*
 238  * This structure is used to store overlap information between frames.
 239  */
 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 */
 246 };
 247
 248 extern  const char      *letters;
 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(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);