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