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