1 /* $NetBSD: makemove.c,v 1.11 2009/08/12 06:19:17 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 35 #include <sys/cdefs.h> 36 #ifndef lint 37 #if 0 38 static char sccsid[] = "@(#)makemove.c 8.2 (Berkeley) 5/3/95"; 39 #else 40 __RCSID("$NetBSD: makemove.c,v 1.11 2009/08/12 06:19:17 dholland Exp $"); 41 #endif 42 #endif /* not lint */ 43 44 #include "gomoku.h" 45 46 /* direction deltas */ 47 const int dd[4] = { 48 MRIGHT, MRIGHT+MDOWN, MDOWN, MDOWN+MLEFT 49 }; 50 51 static const int weight[5] = { 0, 1, 7, 22, 100 }; 52 53 static void update_overlap(struct spotstr *); 54 55 /* 56 * Return values: 57 * MOVEOK everything is OK. 58 * RESIGN Player resigned. 59 * ILLEGAL Illegal move. 60 * WIN The winning move was just played. 61 * TIE The game is a tie. 62 */ 63 int 64 makemove(int us, int mv) 65 { 66 struct spotstr *sp, *fsp; 67 union comboval *cp; 68 struct spotstr *osp; 69 struct combostr *cbp, *cbp1; 70 union comboval *cp1; 71 int i, f, r, d, n; 72 int space, val, bmask; 73 74 /* check for end of game */ 75 if (mv == RESIGN) 76 return(RESIGN); 77 78 /* check for illegal move */ 79 sp = &board[mv]; 80 if (sp->s_occ != EMPTY) 81 return(ILLEGAL); 82 83 /* make move */ 84 sp->s_occ = us; 85 movelog[movenum - 1] = mv; 86 if (++movenum == BSZ * BSZ) 87 return(TIE); 88 89 /* compute new frame values */ 90 sp->s_wval = 0; 91 osp = sp; 92 for (r = 4; --r >= 0; ) { /* for each direction */ 93 d = dd[r]; 94 fsp = osp; 95 bmask = BFLAG << r; 96 for (f = 5; --f >= 0; fsp -= d) { /* for each frame */ 97 if (fsp->s_occ == BORDER) 98 goto nextr; 99 if (fsp->s_flags & bmask) 100 continue; 101 102 /* remove this frame from the sorted list of frames */ 103 cbp = fsp->s_frame[r]; 104 if (cbp->c_next) { 105 if (sortframes[BLACK] == cbp) 106 sortframes[BLACK] = cbp->c_next; 107 if (sortframes[WHITE] == cbp) 108 sortframes[WHITE] = cbp->c_next; 109 cbp->c_next->c_prev = cbp->c_prev; 110 cbp->c_prev->c_next = cbp->c_next; 111 } 112 113 /* compute old weight value for this frame */ 114 cp = &fsp->s_fval[BLACK][r]; 115 if (cp->s <= 0x500) 116 val = weight[5 - cp->c.a - cp->c.b]; 117 else 118 val = 0; 119 cp = &fsp->s_fval[WHITE][r]; 120 if (cp->s <= 0x500) 121 val += weight[5 - cp->c.a - cp->c.b]; 122 123 /* compute new combo value for this frame */ 124 sp = fsp; 125 space = sp->s_occ == EMPTY; 126 n = 0; 127 for (i = 5; --i >= 0; sp += d) { /* for each spot */ 128 if (sp->s_occ == us) 129 n++; 130 else if (sp->s_occ == EMPTY) 131 sp->s_wval -= val; 132 else { 133 /* this frame is now blocked, adjust values */ 134 fsp->s_flags |= bmask; 135 fsp->s_fval[BLACK][r].s = MAXCOMBO; 136 fsp->s_fval[WHITE][r].s = MAXCOMBO; 137 while (--i >= 0) { 138 sp += d; 139 if (sp->s_occ == EMPTY) 140 sp->s_wval -= val; 141 } 142 goto nextf; 143 } 144 } 145 146 /* check for game over */ 147 if (n == 5) 148 return(WIN); 149 150 /* compute new value & combo number for this frame & color */ 151 fsp->s_fval[!us][r].s = MAXCOMBO; 152 cp = &fsp->s_fval[us][r]; 153 /* both ends open? */ 154 if (space && sp->s_occ == EMPTY) { 155 cp->c.a = 4 - n; 156 cp->c.b = 1; 157 } else { 158 cp->c.a = 5 - n; 159 cp->c.b = 0; 160 } 161 val = weight[n]; 162 sp = fsp; 163 for (i = 5; --i >= 0; sp += d) /* for each spot */ 164 if (sp->s_occ == EMPTY) 165 sp->s_wval += val; 166 167 /* add this frame to the sorted list of frames by combo value */ 168 cbp1 = sortframes[us]; 169 if (!cbp1) 170 sortframes[us] = cbp->c_next = cbp->c_prev = cbp; 171 else { 172 cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir]; 173 if (cp->s <= cp1->s) { 174 /* insert at the head of the list */ 175 sortframes[us] = cbp; 176 } else { 177 do { 178 cbp1 = cbp1->c_next; 179 cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir]; 180 if (cp->s <= cp1->s) 181 break; 182 } while (cbp1 != sortframes[us]); 183 } 184 cbp->c_next = cbp1; 185 cbp->c_prev = cbp1->c_prev; 186 cbp1->c_prev->c_next = cbp; 187 cbp1->c_prev = cbp; 188 } 189 190 nextf: 191 ; 192 } 193 194 /* both ends open? */ 195 if (fsp->s_occ == EMPTY) { 196 cp = &fsp->s_fval[BLACK][r]; 197 if (cp->c.b) { 198 cp->c.a += 1; 199 cp->c.b = 0; 200 } 201 cp = &fsp->s_fval[WHITE][r]; 202 if (cp->c.b) { 203 cp->c.a += 1; 204 cp->c.b = 0; 205 } 206 } 207 208 nextr: 209 ; 210 } 211 212 update_overlap(osp); 213 214 return(MOVEOK); 215 } 216 217 /* 218 * fix up the overlap array due to updating spot osp. 219 */ 220 static void 221 update_overlap(struct spotstr *osp) 222 { 223 struct spotstr *sp, *sp1, *sp2; 224 int i, f, r, r1, d, d1, n; 225 int a, b, bmask, bmask1; 226 struct spotstr *esp; 227 u_char *str; 228 229 esp = NULL; 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_flags & 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_flags & 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_flags & 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 } 308