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