gomoku/gomoku.h

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