1 /* $NetBSD: makemove.c,v 1.43 2022/06/19 10:23:48 rillig 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 /* @(#)makemove.c 8.2 (Berkeley) 5/3/95 */ 37 __RCSID("$NetBSD: makemove.c,v 1.43 2022/06/19 10:23:48 rillig Exp $"); 38 39 #include "gomoku.h" 40 41 const int dd[4] = { /* direction deltas */ 42 1, /* right */ 43 -(BSZ + 1) + 1, /* down + right */ 44 -(BSZ + 1), /* down */ 45 -(BSZ + 1) - 1 /* down + left */ 46 }; 47 48 static const int weight[5] = { 0, 1, 7, 22, 100 }; 49 50 static void update_overlap(spot_index); 51 52 static bool 53 is_tie(void) 54 { 55 56 for (int y = 1; y <= BSZ; y++) 57 for (int x = 1; x <= BSZ; x++) 58 if (board[PT(x, y)].s_wval != 0) 59 return false; 60 return true; 61 } 62 63 static void 64 sortframes_remove(struct combostr *cbp) 65 { 66 67 if (cbp->c_next == NULL) 68 return; 69 70 if (sortframes[BLACK] == cbp) 71 sortframes[BLACK] = cbp->c_next; 72 if (sortframes[WHITE] == cbp) 73 sortframes[WHITE] = cbp->c_next; 74 cbp->c_next->c_prev = cbp->c_prev; 75 cbp->c_prev->c_next = cbp->c_next; 76 } 77 78 static int 79 old_weight_value(const struct spotstr *sp, direction r) 80 { 81 union comboval cb; 82 int val = 0; 83 if ((cb = sp->s_fval[BLACK][r]).s <= 0x500) 84 val += weight[5 - cb.cv_force - cb.cv_win]; 85 if ((cb = sp->s_fval[WHITE][r]).s <= 0x500) 86 val += weight[5 - cb.cv_force - cb.cv_win]; 87 return val; 88 } 89 90 /* 91 * Return values: 92 * MOVEOK everything is OK. 93 * RESIGN Player resigned. 94 * ILLEGAL Illegal move. 95 * WIN The winning move was just played. 96 * TIE The game is a tie. 97 */ 98 int 99 makemove(player_color us, spot_index mv) 100 { 101 102 /* check for end of game */ 103 if (mv == RESIGN) 104 return RESIGN; 105 106 /* check for illegal move */ 107 struct spotstr *sp = &board[mv]; 108 if (sp->s_occ != EMPTY) 109 return ILLEGAL; 110 111 /* make move */ 112 sp->s_occ = us; 113 game.moves[game.nmoves++] = mv; 114 115 /* compute new frame values */ 116 sp->s_wval = 0; 117 for (direction r = 4; r-- > 0; ) { 118 int d = dd[r]; 119 struct spotstr *fsp = &board[mv]; 120 121 for (int f = 5; --f >= 0; fsp -= d) { /* for each frame */ 122 if (fsp->s_occ == BORDER) 123 goto nextr; 124 if (is_blocked(fsp, r)) 125 continue; 126 127 struct combostr *cbp = &frames[fsp->s_frame[r]]; 128 sortframes_remove(cbp); 129 130 int val = old_weight_value(fsp, r); 131 132 /* compute new combo value for this frame */ 133 bool space = fsp->s_occ == EMPTY; 134 int n = 0; 135 sp = fsp; 136 for (int off = 5; off-- > 0; sp += d) { /* for each spot */ 137 if (sp->s_occ == us) 138 n++; 139 else if (sp->s_occ == EMPTY) 140 sp->s_wval -= val; 141 else { 142 set_blocked(fsp, r); 143 /* adjust values */ 144 fsp->s_fval[BLACK][r].s = 0x600; 145 fsp->s_fval[WHITE][r].s = 0x600; 146 while (off-- > 0) { 147 sp += d; 148 if (sp->s_occ == EMPTY) 149 sp->s_wval -= val; 150 } 151 goto nextf; 152 } 153 } 154 155 /* check for game over */ 156 if (n == 5) { 157 game.win_spot = (spot_index)(fsp - board); 158 game.win_dir = r; 159 return WIN; 160 } 161 162 /* compute new value & combo number for this frame & color */ 163 player_color them = us != BLACK ? BLACK : WHITE; 164 fsp->s_fval[them][r].s = 0x600; 165 union comboval *cp = &fsp->s_fval[us][r]; 166 /* both ends open? */ 167 if (space && sp->s_occ == EMPTY) { 168 cp->cv_force = 4 - n; 169 cp->cv_win = 1; 170 } else { 171 cp->cv_force = 5 - n; 172 cp->cv_win = 0; 173 } 174 val = weight[n]; 175 sp = fsp; 176 for (int off = 5; off-- > 0; sp += d) /* for each spot */ 177 if (sp->s_occ == EMPTY) 178 sp->s_wval += val; 179 180 /* add this frame to the sorted list of frames by combo value */ 181 struct combostr *cbp1 = sortframes[us]; 182 if (cbp1 == NULL) 183 sortframes[us] = cbp->c_next = cbp->c_prev = cbp; 184 else { 185 union comboval *cp1 = 186 &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir]; 187 if (cp->s <= cp1->s) { 188 /* insert at the head of the list */ 189 sortframes[us] = cbp; 190 } else { 191 do { 192 cbp1 = cbp1->c_next; 193 cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir]; 194 if (cp->s <= cp1->s) 195 break; 196 } while (cbp1 != sortframes[us]); 197 } 198 cbp->c_next = cbp1; 199 cbp->c_prev = cbp1->c_prev; 200 cbp1->c_prev->c_next = cbp; 201 cbp1->c_prev = cbp; 202 } 203 204 nextf: 205 ; 206 } 207 208 /* both ends open? */ 209 if (fsp->s_occ == EMPTY) { 210 union comboval *cp = &fsp->s_fval[BLACK][r]; 211 if (cp->cv_win != 0) { 212 cp->cv_force++; 213 cp->cv_win = 0; 214 } 215 cp = &fsp->s_fval[WHITE][r]; 216 if (cp->cv_win != 0) { 217 cp->cv_force++; 218 cp->cv_win = 0; 219 } 220 } 221 222 nextr: 223 ; 224 } 225 226 update_overlap(mv); 227 228 if (is_tie()) 229 return TIE; 230 231 return MOVEOK; 232 } 233 234 static void 235 update_overlap_same_direction(spot_index s1, spot_index s2, 236 frame_index a, int d, int off_minus_f, 237 direction r) 238 { 239 /* 240 * count the number of empty spots to see if there is 241 * still an overlap. 242 */ 243 int n = 0; 244 spot_index s = s1; 245 spot_index es = 0; 246 for (int b = off_minus_f; b < 5; b++, s += d) { 247 if (board[s].s_occ == EMPTY) { 248 es = s; /* save the intersection point */ 249 n++; 250 } 251 } 252 253 frame_index b = board[s2].s_frame[r]; 254 if (n == 0) { 255 if (board[s].s_occ == EMPTY) { 256 overlap[a * FAREA + b] &= 0xA; 257 overlap[b * FAREA + a] &= 0xC; 258 intersect[a * FAREA + b] = s; 259 intersect[b * FAREA + a] = s; 260 } else { 261 overlap[a * FAREA + b] = 0; 262 overlap[b * FAREA + a] = 0; 263 } 264 } else if (n == 1) { 265 if (board[s].s_occ == EMPTY) { 266 overlap[a * FAREA + b] &= 0xAF; 267 overlap[b * FAREA + a] &= 0xCF; 268 } else { 269 overlap[a * FAREA + b] &= 0xF; 270 overlap[b * FAREA + a] &= 0xF; 271 } 272 intersect[a * FAREA + b] = es; 273 intersect[b * FAREA + a] = es; 274 } 275 /* else no change, still multiple overlap */ 276 } 277 278 /* 279 * The last move was at 'os', which is part of frame 'a'. There are 6 frames 280 * with direction 'rb' that cross frame 'a' in 'os'. Since the spot 'os' 281 * cannot be used as a double threat anymore, mark each of these crossing 282 * frames as non-overlapping with frame 'a'. 283 */ 284 static void 285 update_overlap_different_direction(spot_index os, frame_index a, direction rb) 286 { 287 288 int db = dd[rb]; 289 for (int off = 0; off < 6; off++) { 290 const struct spotstr *sp = &board[os - db * off]; 291 if (sp->s_occ == BORDER) 292 break; 293 if (is_blocked(sp, rb)) 294 continue; 295 296 frame_index b = sp->s_frame[rb]; 297 overlap[a * FAREA + b] = 0; 298 overlap[b * FAREA + a] = 0; 299 } 300 } 301 302 /* 303 * fix up the overlap array according to the changed 'os'. 304 */ 305 static void 306 update_overlap(spot_index os) 307 { 308 309 for (direction r = 4; r-- > 0; ) { 310 int d = dd[r]; 311 spot_index s1 = os; 312 313 /* for each frame 'a' that contains the spot 'os' */ 314 for (int f = 0; f < 6; f++, s1 -= d) { 315 if (board[s1].s_occ == BORDER) 316 break; 317 if (is_blocked(&board[s1], r)) 318 continue; 319 320 /* 321 * Update all other frames that intersect the current one 322 * to indicate whether they still overlap or not. 323 * Since F1 overlap F2 == F2 overlap F1, we only need to 324 * do the rows 0 <= r1 <= r. The r1 == r case is special 325 * since the two frames can overlap in more than one spot. 326 */ 327 frame_index a = board[s1].s_frame[r]; 328 329 spot_index s2 = s1 - d; 330 for (int off = f + 1; off < 6; off++, s2 -= d) { 331 if (board[s2].s_occ == BORDER) 332 break; 333 if (is_blocked(&board[s2], r)) 334 continue; 335 336 update_overlap_same_direction(s1, s2, a, d, off - f, r); 337 } 338 339 /* the other directions can only intersect at spot 'os' */ 340 for (direction rb = 0; rb < r; rb++) 341 update_overlap_different_direction(os, a, rb); 342 } 343 } 344 } 345
Indexes created Sat Sep 20 22:09:52 GMT 2025