gomoku/makemove.c

   1 /*      $NetBSD: makemove.c,v 1.3 1997/01/03 01:35:29 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
  39 #ifndef lint
  40 #if 0
  41 static char sccsid[] = "@(#)makemove.c  8.2 (Berkeley) 5/3/95";
  42 #else
  43 static char rcsid[] = "$NetBSD: makemove.c,v 1.3 1997/01/03 01:35:29 cgd Exp $";
  44 #endif
  45 #endif /* not lint */
  46
  47 #include "gomoku.h"
  48
  49                 /* direction deltas */
  50 int     dd[4] = {
  51         MRIGHT, MRIGHT+MDOWN, MDOWN, MDOWN+MLEFT
  52 };
  53
  54 int     weight[5] = { 0, 1, 7, 22, 100 };
  55
  56 /*
  57  * Return values:
  58  *      MOVEOK  everything is OK.
  59  *      RESIGN  Player resigned.
  60  *      ILLEGAL Illegal move.
  61  *      WIN     The the winning move was just played.
  62  *      TIE     The game is a tie.
  63  */
  64 makemove(us, mv)
  65         int us, mv;
  66 {
  67         register struct spotstr *sp, *fsp;
  68         register union comboval *cp;
  69         struct spotstr *osp;
  70         struct combostr *cbp, *cbp1;
  71         union comboval *cp1;
  72         register int i, f, r, d, n;
  73         int space, val, bmask;
  74
  75         /* check for end of game */
  76         if (mv == RESIGN)
  77                 return(RESIGN);
  78
  79         /* check for illegal move */
  80         sp = &board[mv];
  81         if (sp->s_occ != EMPTY)
  82                 return(ILLEGAL);
  83
  84         /* make move */
  85         sp->s_occ = us;
  86         movelog[movenum - 1] = mv;
  87         if (++movenum == BSZ * BSZ)
  88                 return(TIE);
  89
  90         /* compute new frame values */
  91         sp->s_wval = 0;
  92         osp = sp;
  93         for (r = 4; --r >= 0; ) {                       /* for each direction */
  94             d = dd[r];
  95             fsp = osp;
  96             bmask = BFLAG << r;
  97             for (f = 5; --f >= 0; fsp -= d) {           /* for each frame */
  98                 if (fsp->s_occ == BORDER)
  99                     goto nextr;
 100                 if (fsp->s_flg & bmask)
 101                     continue;
 102
 103                 /* remove this frame from the sorted list of frames */
 104                 cbp = fsp->s_frame[r];
 105                 if (cbp->c_next) {
 106                         if (sortframes[BLACK] == cbp)
 107                             sortframes[BLACK] = cbp->c_next;
 108                         if (sortframes[WHITE] == cbp)
 109                             sortframes[WHITE] = cbp->c_next;
 110                         cbp->c_next->c_prev = cbp->c_prev;
 111                         cbp->c_prev->c_next = cbp->c_next;
 112                 }
 113
 114                 /* compute old weight value for this frame */
 115                 cp = &fsp->s_fval[BLACK][r];
 116                 if (cp->s <= 0x500)
 117                     val = weight[5 - cp->c.a - cp->c.b];
 118                 else
 119                     val = 0;
 120                 cp = &fsp->s_fval[WHITE][r];
 121                 if (cp->s <= 0x500)
 122                     val += weight[5 - cp->c.a - cp->c.b];
 123
 124                 /* compute new combo value for this frame */
 125                 sp = fsp;
 126                 space = sp->s_occ == EMPTY;
 127                 n = 0;
 128                 for (i = 5; --i >= 0; sp += d) {        /* for each spot */
 129                     if (sp->s_occ == us)
 130                         n++;
 131                     else if (sp->s_occ == EMPTY)
 132                         sp->s_wval -= val;
 133                     else {
 134                         /* this frame is now blocked, adjust values */
 135                         fsp->s_flg |= bmask;
 136                         fsp->s_fval[BLACK][r].s = MAXCOMBO;
 137                         fsp->s_fval[WHITE][r].s = MAXCOMBO;
 138                         while (--i >= 0) {
 139                             sp += d;
 140                             if (sp->s_occ == EMPTY)
 141                                 sp->s_wval -= val;
 142                         }
 143                         goto nextf;
 144                     }
 145                 }
 146
 147                 /* check for game over */
 148                 if (n == 5)
 149                     return(WIN);
 150
 151                 /* compute new value & combo number for this frame & color */
 152                 fsp->s_fval[!us][r].s = MAXCOMBO;
 153                 cp = &fsp->s_fval[us][r];
 154                 /* both ends open? */
 155                 if (space && sp->s_occ == EMPTY) {
 156                     cp->c.a = 4 - n;
 157                     cp->c.b = 1;
 158                 } else {
 159                     cp->c.a = 5 - n;
 160                     cp->c.b = 0;
 161                 }
 162                 val = weight[n];
 163                 sp = fsp;
 164                 for (i = 5; --i >= 0; sp += d)          /* for each spot */
 165                     if (sp->s_occ == EMPTY)
 166                         sp->s_wval += val;
 167
 168                 /* add this frame to the sorted list of frames by combo value */
 169                 cbp1 = sortframes[us];
 170                 if (!cbp1)
 171                     sortframes[us] = cbp->c_next = cbp->c_prev = cbp;
 172                 else {
 173                     cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir];
 174                     if (cp->s <= cp1->s) {
 175                         /* insert at the head of the list */
 176                         sortframes[us] = cbp;
 177                     } else {
 178                         do {
 179                             cbp1 = cbp1->c_next;
 180                             cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir];
 181                             if (cp->s <= cp1->s)
 182                                 break;
 183                         } while (cbp1 != sortframes[us]);
 184                     }
 185                     cbp->c_next = cbp1;
 186                     cbp->c_prev = cbp1->c_prev;
 187                     cbp1->c_prev->c_next = cbp;
 188                     cbp1->c_prev = cbp;
 189                 }
 190
 191             nextf:
 192                 ;
 193             }
 194
 195             /* both ends open? */
 196             if (fsp->s_occ == EMPTY) {
 197                 cp = &fsp->s_fval[BLACK][r];
 198                 if (cp->c.b) {
 199                     cp->c.a += 1;
 200                     cp->c.b = 0;
 201                 }
 202                 cp = &fsp->s_fval[WHITE][r];
 203                 if (cp->c.b) {
 204                     cp->c.a += 1;
 205                     cp->c.b = 0;
 206                 }
 207             }
 208
 209         nextr:
 210             ;
 211         }
 212
 213         update_overlap(osp);
 214
 215         return(MOVEOK);
 216 }
 217
 218 /*
 219  * fix up the overlap array due to updating spot osp.
 220  */
 221 update_overlap(osp)
 222         struct spotstr *osp;
 223 {
 224         register struct spotstr *sp, *sp1, *sp2;
 225         register int i, f, r, r1, d, d1, n;
 226         int a, b, bmask, bmask1;
 227         struct spotstr *esp;
 228         char *str;
 229
 230         for (r = 4; --r >= 0; ) {                       /* for each direction */
 231             d = dd[r];
 232             sp1 = osp;
 233             bmask = BFLAG << r;
 234             for (f = 0; f < 6; f++, sp1 -= d) {         /* for each frame */
 235                 if (sp1->s_occ == BORDER)
 236                     break;
 237                 if (sp1->s_flg & bmask)
 238                     continue;
 239                 /*
 240                  * Update all other frames that intersect the current one
 241                  * to indicate whether they still overlap or not.
 242                  * Since F1 overlap F2 == F2 overlap F1, we only need to
 243                  * do the rows 0 <= r1 <= r. The r1 == r case is special
 244                  * since the two frames can overlap at more than one point.
 245                  */
 246                 str = &overlap[(a = sp1->s_frame[r] - frames) * FAREA];
 247                 sp2 = sp1 - d;
 248                 for (i = f + 1; i < 6; i++, sp2 -= d) {
 249                     if (sp2->s_occ == BORDER)
 250                         break;
 251                     if (sp2->s_flg & bmask)
 252                         continue;
 253                     /*
 254                      * count the number of empty spots to see if there is
 255                      * still an overlap.
 256                      */
 257                     n = 0;
 258                     sp = sp1;
 259                     for (b = i - f; b < 5; b++, sp += d) {
 260                         if (sp->s_occ == EMPTY) {
 261                             esp = sp;   /* save the intersection point */
 262                             n++;
 263                         }
 264                     }
 265                     b = sp2->s_frame[r] - frames;
 266                     if (n == 0) {
 267                         if (sp->s_occ == EMPTY) {
 268                             str[b] &= 0xA;
 269                             overlap[b * FAREA + a] &= 0xC;
 270                             intersect[a * FAREA + b] = n = sp - board;
 271                             intersect[b * FAREA + a] = n;
 272                         } else {
 273                             str[b] = 0;
 274                             overlap[b * FAREA + a] = 0;
 275                         }
 276                     } else if (n == 1) {
 277                         if (sp->s_occ == EMPTY) {
 278                             str[b] &= 0xAF;
 279                             overlap[b * FAREA + a] &= 0xCF;
 280                         } else {
 281                             str[b] &= 0xF;
 282                             overlap[b * FAREA + a] &= 0xF;
 283                         }
 284                         intersect[a * FAREA + b] = n = esp - board;
 285                         intersect[b * FAREA + a] = n;
 286                     }
 287                     /* else no change, still multiple overlap */
 288                 }
 289
 290                 /* the other directions can only intersect at spot osp */
 291                 for (r1 = r; --r1 >= 0; ) {
 292                     d1 = dd[r1];
 293                     bmask1 = BFLAG << r1;
 294                     sp = osp;
 295                     for (i = 6; --i >= 0; sp -= d1) {   /* for each spot */
 296                         if (sp->s_occ == BORDER)
 297                             break;
 298                         if (sp->s_flg & bmask1)
 299                             continue;
 300                         b = sp->s_frame[r1] - frames;
 301                         str[b] = 0;
 302                         overlap[b * FAREA + a] = 0;
 303                     }
 304                 }
 305             }
 306         }
 307 }