1 /* $OpenBSD: makemove.c,v 1.6 2003/06/03 03:01:39 millert Exp $ */ 2 /* 3 * Copyright (c) 1994 4 * The Regents of the University of California. All rights reserved. 5 * 6 * This code is derived from software contributed to Berkeley by 7 * Ralph Campbell. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 3. Neither the name of the University nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 */ 33 34 #ifndef lint 35 #if 0 36 static char sccsid[] = "@(#)makemove.c 8.2 (Berkeley) 5/3/95"; 37 #else 38 static char rcsid[] = "$OpenBSD: makemove.c,v 1.6 2003/06/03 03:01:39 millert Exp $"; 39 #endif 40 #endif /* not lint */ 41 42 #include "gomoku.h" 43 44 /* direction deltas */ 45 int dd[4] = { 46 MRIGHT, MRIGHT+MDOWN, MDOWN, MDOWN+MLEFT 47 }; 48 49 int weight[5] = { 0, 1, 7, 22, 100 }; 50 51 /* 52 * Return values: 53 * MOVEOK everything is OK. 54 * RESIGN Player resigned. 55 * ILLEGAL Illegal move. 56 * WIN The winning move was just played. 57 * TIE The game is a tie. 58 */ 59 int 60 makemove(us, mv) 61 int us, mv; 62 { 63 struct spotstr *sp, *fsp; 64 union comboval *cp; 65 struct spotstr *osp; 66 struct combostr *cbp, *cbp1; 67 union comboval *cp1; 68 int i, f, r, d, n; 69 int space, val, bmask; 70 71 /* check for end of game */ 72 if (mv == RESIGN) 73 return(RESIGN); 74 75 /* check for illegal move */ 76 sp = &board[mv]; 77 if (sp->s_occ != EMPTY) 78 return(ILLEGAL); 79 80 /* make move */ 81 sp->s_occ = us; 82 movelog[movenum - 1] = mv; 83 if (++movenum == BSZ * BSZ) 84 return(TIE); 85 86 /* compute new frame values */ 87 sp->s_wval = 0; 88 osp = sp; 89 for (r = 4; --r >= 0; ) { /* for each direction */ 90 d = dd[r]; 91 fsp = osp; 92 bmask = BFLAG << r; 93 for (f = 5; --f >= 0; fsp -= d) { /* for each frame */ 94 if (fsp->s_occ == BORDER) 95 goto nextr; 96 if (fsp->s_flg & bmask) 97 continue; 98 99 /* remove this frame from the sorted list of frames */ 100 cbp = fsp->s_frame[r]; 101 if (cbp->c_next) { 102 if (sortframes[BLACK] == cbp) 103 sortframes[BLACK] = cbp->c_next; 104 if (sortframes[WHITE] == cbp) 105 sortframes[WHITE] = cbp->c_next; 106 cbp->c_next->c_prev = cbp->c_prev; 107 cbp->c_prev->c_next = cbp->c_next; 108 } 109 110 /* compute old weight value for this frame */ 111 cp = &fsp->s_fval[BLACK][r]; 112 if (cp->s <= 0x500) 113 val = weight[5 - cp->c.a - cp->c.b]; 114 else 115 val = 0; 116 cp = &fsp->s_fval[WHITE][r]; 117 if (cp->s <= 0x500) 118 val += weight[5 - cp->c.a - cp->c.b]; 119 120 /* compute new combo value for this frame */ 121 sp = fsp; 122 space = sp->s_occ == EMPTY; 123 n = 0; 124 for (i = 5; --i >= 0; sp += d) { /* for each spot */ 125 if (sp->s_occ == us) 126 n++; 127 else if (sp->s_occ == EMPTY) 128 sp->s_wval -= val; 129 else { 130 /* this frame is now blocked, adjust values */ 131 fsp->s_flg |= bmask; 132 fsp->s_fval[BLACK][r].s = MAXCOMBO; 133 fsp->s_fval[WHITE][r].s = MAXCOMBO; 134 while (--i >= 0) { 135 sp += d; 136 if (sp->s_occ == EMPTY) 137 sp->s_wval -= val; 138 } 139 goto nextf; 140 } 141 } 142 143 /* check for game over */ 144 if (n == 5) 145 return(WIN); 146 147 /* compute new value & combo number for this frame & color */ 148 fsp->s_fval[!us][r].s = MAXCOMBO; 149 cp = &fsp->s_fval[us][r]; 150 /* both ends open? */ 151 if (space && sp->s_occ == EMPTY) { 152 cp->c.a = 4 - n; 153 cp->c.b = 1; 154 } else { 155 cp->c.a = 5 - n; 156 cp->c.b = 0; 157 } 158 val = weight[n]; 159 sp = fsp; 160 for (i = 5; --i >= 0; sp += d) /* for each spot */ 161 if (sp->s_occ == EMPTY) 162 sp->s_wval += val; 163 164 /* add this frame to the sorted list of frames by combo value */ 165 cbp1 = sortframes[us]; 166 if (!cbp1) 167 sortframes[us] = cbp->c_next = cbp->c_prev = cbp; 168 else { 169 cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir]; 170 if (cp->s <= cp1->s) { 171 /* insert at the head of the list */ 172 sortframes[us] = cbp; 173 } else { 174 do { 175 cbp1 = cbp1->c_next; 176 cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir]; 177 if (cp->s <= cp1->s) 178 break; 179 } while (cbp1 != sortframes[us]); 180 } 181 cbp->c_next = cbp1; 182 cbp->c_prev = cbp1->c_prev; 183 cbp1->c_prev->c_next = cbp; 184 cbp1->c_prev = cbp; 185 } 186 187 nextf: 188 ; 189 } 190 191 /* both ends open? */ 192 if (fsp->s_occ == EMPTY) { 193 cp = &fsp->s_fval[BLACK][r]; 194 if (cp->c.b) { 195 cp->c.a += 1; 196 cp->c.b = 0; 197 } 198 cp = &fsp->s_fval[WHITE][r]; 199 if (cp->c.b) { 200 cp->c.a += 1; 201 cp->c.b = 0; 202 } 203 } 204 205 nextr: 206 ; 207 } 208 209 update_overlap(osp); 210 211 return(MOVEOK); 212 } 213 214 /* 215 * fix up the overlap array due to updating spot osp. 216 */ 217 void 218 update_overlap(osp) 219 struct spotstr *osp; 220 { 221 struct spotstr *sp, *sp1, *sp2; 222 int i, f, r, r1, d, d1, n; 223 int a, b, bmask, bmask1; 224 struct spotstr *esp = NULL; 225 char *str; 226 227 for (r = 4; --r >= 0; ) { /* for each direction */ 228 d = dd[r]; 229 sp1 = osp; 230 bmask = BFLAG << r; 231 for (f = 0; f < 6; f++, sp1 -= d) { /* for each frame */ 232 if (sp1->s_occ == BORDER) 233 break; 234 if (sp1->s_flg & bmask) 235 continue; 236 /* 237 * Update all other frames that intersect the current one 238 * to indicate whether they still overlap or not. 239 * Since F1 overlap F2 == F2 overlap F1, we only need to 240 * do the rows 0 <= r1 <= r. The r1 == r case is special 241 * since the two frames can overlap at more than one point. 242 */ 243 str = &overlap[(a = sp1->s_frame[r] - frames) * FAREA]; 244 sp2 = sp1 - d; 245 for (i = f + 1; i < 6; i++, sp2 -= d) { 246 if (sp2->s_occ == BORDER) 247 break; 248 if (sp2->s_flg & bmask) 249 continue; 250 /* 251 * count the number of empty spots to see if there is 252 * still an overlap. 253 */ 254 n = 0; 255 sp = sp1; 256 for (b = i - f; b < 5; b++, sp += d) { 257 if (sp->s_occ == EMPTY) { 258 esp = sp; /* save the intersection point */ 259 n++; 260 } 261 } 262 b = sp2->s_frame[r] - frames; 263 if (n == 0) { 264 if (sp->s_occ == EMPTY) { 265 str[b] &= 0xA; 266 overlap[b * FAREA + a] &= 0xC; 267 intersect[a * FAREA + b] = n = sp - board; 268 intersect[b * FAREA + a] = n; 269 } else { 270 str[b] = 0; 271 overlap[b * FAREA + a] = 0; 272 } 273 } else if (n == 1) { 274 if (sp->s_occ == EMPTY) { 275 str[b] &= 0xAF; 276 overlap[b * FAREA + a] &= 0xCF; 277 } else { 278 str[b] &= 0xF; 279 overlap[b * FAREA + a] &= 0xF; 280 } 281 intersect[a * FAREA + b] = n = esp - board; 282 intersect[b * FAREA + a] = n; 283 } 284 /* else no change, still multiple overlap */ 285 } 286 287 /* the other directions can only intersect at spot osp */ 288 for (r1 = r; --r1 >= 0; ) { 289 d1 = dd[r1]; 290 bmask1 = BFLAG << r1; 291 sp = osp; 292 for (i = 6; --i >= 0; sp -= d1) { /* for each spot */ 293 if (sp->s_occ == BORDER) 294 break; 295 if (sp->s_flg & bmask1) 296 continue; 297 b = sp->s_frame[r1] - frames; 298 str[b] = 0; 299 overlap[b * FAREA + a] = 0; 300 } 301 } 302 } 303 } 304 } 305