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