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