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