1 /* $NetBSD: algor.cc,v 1.1 2003/12/27 01:16:55 christos Exp $ */ 2 3 /*- 4 * Copyright (c) 2003 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Christos Zoulas. 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 NetBSD 21 * Foundation, Inc. and its contributors. 22 * 4. Neither the name of The NetBSD Foundation nor the names of its 23 * contributors may be used to endorse or promote products derived 24 * from this software without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 27 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 28 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 29 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 30 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 31 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 32 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 33 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 34 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 35 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 36 * POSSIBILITY OF SUCH DAMAGE. 37 */ 38 39 /* 40 * algor.C: Computer algorithm 41 */ 42 #include "defs.h" 43 RCSID("$NetBSD: algor.cc,v 1.1 2003/12/27 01:16:55 christos Exp $") 44 45 #include "algor.h" 46 #include "board.h" 47 #include "box.h" 48 #include "random.h" 49 50 ALGOR::ALGOR(const char c) : PLAYER(c) 51 { 52 #ifdef notyet 53 // Single Edges = (x + y) * 2 54 _edge1 = (_b.nx() * _b.ny()) * 2; 55 // Shared Edges = (x * (y - 1)) + ((x - 1) * y) 56 _edge2 = (_b.nx() * (_b.ny() - 1)) + ((_b.nx() - 1) * _b.ny()); 57 // Maximum Edges filled before closure = x * y * 2 58 _maxedge = _b.nx() * _b.ny() * 2; 59 #endif 60 } 61 62 // Find the first closure, i.e. a box that has 3 edges 63 int ALGOR::find_closure(size_t& y, size_t& x, int& dir, BOARD& b) 64 { 65 RANDOM rdy(b.ny()), rdx(b.nx()); 66 67 for (y = rdy(); y < b.ny(); y = rdy()) { 68 rdx.clear(); 69 for (x = rdx(); x < b.nx(); x = rdx()) { 70 BOX box(y, x, b); 71 if (box.count() == 3) { 72 for (dir = BOX::first; dir < BOX::last; dir++) 73 if (!box.isset(dir)) 74 return 1; 75 b.abort("find_closure: 3 sided box[%d,%d] has no free sides", 76 y, x); 77 } 78 } 79 } 80 return 0; 81 } 82 83 #if 0 84 size_t ALGOR::find_single() 85 { 86 size_t ne; 87 88 // Find the number of single edges in use 89 for (size_t x = 0; x < b.nx(); x++) { 90 BOX tbox(0, x, b); 91 ne += tbox.isset(BOX::top); 92 BOX bbox(b.ny() - 1, x, b); 93 ne += bbox.isset(BOX::bottom); 94 } 95 for (size_t y = 0; y < _b.ny(); y++) { 96 BOX lbox(y, 0, b); 97 ne += lbox.isset(BOX::left); 98 BOX rbox(y,_b.nx() - 1, b); 99 ne += rbox.isset(BOX::right); 100 } 101 return ne; 102 } 103 #endif 104 105 106 // Count a closure, by counting all boxes that we can close in the current 107 // move 108 size_t ALGOR::count_closure(size_t& y, size_t& x, int& dir, BOARD& b) 109 { 110 size_t i = 0; 111 size_t tx, ty; 112 int tdir, mv; 113 114 while (find_closure(ty, tx, tdir, b)) { 115 if (i == 0) { 116 // Mark the beginning of the closure 117 x = tx; 118 y = ty; 119 dir = tdir; 120 } 121 if ((mv = b.domove(ty, tx, tdir, getWho())) == -1) 122 b.abort("count_closure: Invalid move (%d, %d, %d)", y, x, dir); 123 else 124 i += mv; 125 } 126 return i; 127 } 128 129 130 /* 131 * Find the largest closure, by closing all possible closures. 132 * return the number of boxes closed in the maximum closure, 133 * and the first box of the maximum closure in (x, y, dir) 134 */ 135 int ALGOR::find_max_closure(size_t& y, size_t& x, int& dir, const BOARD& b) 136 { 137 BOARD nb(b); 138 int tdir, maxdir = -1; 139 size_t nbox, maxbox = 0; 140 size_t tx, ty, maxx = ~0, maxy = ~0; 141 142 while ((nbox = count_closure(ty, tx, tdir, nb)) != 0) 143 if (nbox > maxbox) { 144 // This closure is better, update max 145 maxbox = nbox; 146 maxx = tx; 147 maxy = ty; 148 maxdir = tdir; 149 } 150 151 // Return the max found 152 y = maxy; 153 x = maxx; 154 dir = maxdir; 155 return maxbox; 156 } 157 158 159 // Find if a turn does not result in a capture on the given box 160 // and return the direction if found. 161 int ALGOR::try_good_turn(BOX& box, size_t y, size_t x, int& dir, BOARD& b) 162 { 163 // Sanity check; we must have a good box 164 if (box.count() >= 2) 165 b.abort("try_good_turn: box[%d,%d] has more than 2 sides occupied", 166 y, x); 167 168 // Make sure we don't make a closure in an adjacent box. 169 // We use a random direction to randomize the game 170 RANDOM rd(BOX::last); 171 for (dir = rd(); dir < BOX::last; dir = rd()) 172 if (!box.isset(dir)) { 173 size_t by = y + BOX::edges[dir].y; 174 size_t bx = x + BOX::edges[dir].x; 175 if (!b.bounds(by, bx)) 176 return 1; 177 178 BOX nbox(by, bx, b); 179 if (nbox.count() < 2) 180 return 1; 181 } 182 183 return 0; 184 } 185 186 187 // Try to find a turn that does not result in an opponent closure, and 188 // return it in (x, y, dir); if not found return 0. 189 int ALGOR::find_good_turn(size_t& y, size_t& x, int& dir, const BOARD& b) 190 { 191 BOARD nb(b); 192 RANDOM rdy(b.ny()), rdx(b.nx()); 193 194 for (y = rdy(); y < b.ny(); y = rdy()) { 195 rdx.clear(); 196 for (x = rdx(); x < b.nx(); x = rdx()) { 197 BOX box(y, x, nb); 198 if (box.count() < 2 && try_good_turn(box, y, x, dir, nb)) 199 return 1; 200 } 201 } 202 return 0; 203 } 204 205 // On a box with 2 edges, return the first or the last free edge, depending 206 // on the order specified 207 int ALGOR::try_bad_turn(BOX& box, size_t& y, size_t& x, int& dir, BOARD& b, 208 int last) 209 { 210 if (4 - box.count() <= last) 211 b.abort("try_bad_turn: Called at [%d,%d] for %d with %d", 212 y, x, last, box.count()); 213 for (dir = BOX::first; dir < BOX::last; dir++) 214 if (!box.isset(dir)) { 215 if (!last) 216 return 1; 217 else 218 last--; 219 } 220 return 0; 221 } 222 223 // Find a box that has 2 edges and return the first free edge of that 224 // box or the last free edge of that box 225 int ALGOR::find_bad_turn(size_t& y, size_t& x, int& dir, BOARD& b, int last) 226 { 227 RANDOM rdy(b.ny()), rdx(b.nx()); 228 for (y = rdy(); y < b.ny(); y = rdy()) { 229 rdx.clear(); 230 for (x = rdx(); x < b.nx(); x = rdx()) { 231 BOX box(y, x, b); 232 if ((4 - box.count()) > last && 233 try_bad_turn(box, y, x, dir, b, last)) 234 return 1; 235 } 236 } 237 return 0; 238 } 239 240 int ALGOR::find_min_closure1(size_t& y, size_t& x, int& dir, const BOARD& b, 241 int last) 242 { 243 BOARD nb(b); 244 int tdir, mindir = -1, xdir, mv; 245 // number of boxes per closure 246 size_t nbox, minbox = nb.nx() * nb.ny() + 1; 247 size_t tx, ty, minx = ~0, miny = ~0; 248 249 while (find_bad_turn(ty, tx, tdir, nb, last)) { 250 251 // Play a bad move that would cause the opponent's closure 252 if ((mv = nb.domove(ty, tx, tdir, getWho())) != 0) 253 b.abort("find_min_closure1: Invalid move %d (%d, %d, %d)", mv, 254 ty, tx, tdir); 255 256 // Count the opponent's closure 257 if ((nbox = count_closure(y, x, xdir, nb)) == 0) 258 b.abort("find_min_closure1: no closure found"); 259 260 if (nbox <= minbox) { 261 // This closure has fewer boxes 262 minbox = nbox; 263 minx = tx; 264 miny = ty; 265 mindir = tdir; 266 } 267 } 268 269 y = miny; 270 x = minx; 271 dir = mindir; 272 return minbox; 273 } 274 275 276 // Search for the move that makes the opponent close the least number of 277 // boxes; returns 1 if a move found, 0 otherwise 278 int ALGOR::find_min_closure(size_t& y, size_t& x, int& dir, const BOARD& b) 279 { 280 size_t x1, y1; 281 int dir1; 282 int count = b.ny() * b.nx() + 1, count1; 283 284 for (size_t i = 0; i < 3; i++) 285 if (count > (count1 = find_min_closure1(y1, x1, dir1, b, i))) { 286 count = count1; 287 y = y1; 288 x = x1; 289 dir = dir1; 290 } 291 292 return (size_t) count != b.ny() * b.nx() + 1; 293 } 294 295 // Return a move in (y, x, dir) 296 void ALGOR::play(const BOARD& b, size_t& y, size_t& x, int& dir) 297 { 298 // See if we can close the largest closure available 299 if (find_max_closure(y, x, dir, b)) 300 return; 301 302 #ifdef notyet 303 size_t sgl = find_single(); 304 size_t dbl = find_double(); 305 #endif 306 307 // See if we can play an edge without giving the opponent a box 308 if (find_good_turn(y, x, dir, b)) 309 return; 310 311 // Too bad, find the move that gives the opponent the fewer boxes 312 if (find_min_closure(y, x, dir, b)) 313 return; 314 } 315