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