dab/algor.cc

   1 /*      $NetBSD: algor.cc,v 1.3 2006/05/14 03:20:42 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.3 2006/05/14 03:20:42 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 size_t ALGOR::find_max_closure(size_t& y, size_t& x, int& dir, const BOARD& b)
 136 {
 137     BOARD nb(b);
 138     int maxdir = -1;
 139     size_t nbox, maxbox = 0;
 140     size_t maxx = ~0, maxy = ~0;
 141     size_t tx = 0, ty = 0;      /* XXX: GCC */
 142     int tdir = 0;               /* XXX: GCC */
 143
 144     while ((nbox = count_closure(ty, tx, tdir, nb)) != 0)
 145         if (nbox > maxbox) {
 146             // This closure is better, update max
 147             maxbox = nbox;
 148             maxx = tx;
 149             maxy = ty;
 150             maxdir = tdir;
 151         }
 152
 153     // Return the max found
 154     y = maxy;
 155     x = maxx;
 156     dir = maxdir;
 157     return maxbox;
 158 }
 159
 160
 161 // Find if a turn does not result in a capture on the given box
 162 // and return the direction if found.
 163 int ALGOR::try_good_turn(BOX& box, size_t y, size_t x, int& dir, BOARD& b)
 164 {
 165     // Sanity check; we must have a good box
 166     if (box.count() >= 2)
 167         b.abort("try_good_turn: box[%d,%d] has more than 2 sides occupied",
 168                 y, x);
 169
 170     // Make sure we don't make a closure in an adjacent box.
 171     // We use a random direction to randomize the game
 172     RANDOM rd(BOX::last);
 173     for (dir = rd(); dir < BOX::last; dir = rd())
 174         if (!box.isset(dir)) {
 175             size_t by = y + BOX::edges[dir].y;
 176             size_t bx = x + BOX::edges[dir].x;
 177             if (!b.bounds(by, bx))
 178                 return 1;
 179
 180             BOX nbox(by, bx, b);
 181             if (nbox.count() < 2)
 182                 return 1;
 183         }
 184
 185     return 0;
 186 }
 187
 188
 189 // Try to find a turn that does not result in an opponent closure, and
 190 // return it in (x, y, dir); if not found return 0.
 191 int ALGOR::find_good_turn(size_t& y, size_t& x, int& dir, const BOARD& b)
 192 {
 193     BOARD nb(b);
 194     RANDOM rdy(b.ny()), rdx(b.nx());
 195
 196     for (y = rdy(); y < b.ny(); y = rdy()) {
 197         rdx.clear();
 198         for (x = rdx(); x < b.nx(); x = rdx()) {
 199             BOX box(y, x, nb);
 200             if (box.count() < 2 && try_good_turn(box, y, x, dir, nb))
 201                 return 1;
 202         }
 203     }
 204     return 0;
 205 }
 206
 207 // On a box with 2 edges, return the first or the last free edge, depending
 208 // on the order specified
 209 int ALGOR::try_bad_turn(BOX& box, size_t& y, size_t& x, int& dir, BOARD& b,
 210                         int last)
 211 {
 212     if (4 - box.count() <= last)
 213         b.abort("try_bad_turn: Called at [%d,%d] for %d with %d",
 214                 y, x, last, box.count());
 215     for (dir = BOX::first; dir < BOX::last; dir++)
 216         if (!box.isset(dir)) {
 217             if (!last)
 218                 return 1;
 219             else
 220                 last--;
 221         }
 222     return 0;
 223 }
 224
 225 // Find a box that has 2 edges and return the first free edge of that
 226 // box or the last free edge of that box
 227 int ALGOR::find_bad_turn(size_t& y, size_t& x, int& dir, BOARD& b, int last)
 228 {
 229     RANDOM rdy(b.ny()), rdx(b.nx());
 230     for (y = rdy(); y < b.ny(); y = rdy()) {
 231         rdx.clear();
 232         for (x = rdx(); x < b.nx(); x = rdx()) {
 233             BOX box(y, x, b);
 234             if ((4 - box.count()) > last &&
 235                 try_bad_turn(box, y, x, dir, b, last))
 236                 return 1;
 237         }
 238     }
 239     return 0;
 240 }
 241
 242 size_t ALGOR::find_min_closure1(size_t& y, size_t& x, int& dir, const BOARD& b,
 243     int last)
 244 {
 245     BOARD nb(b);
 246     int tdir, mindir = -1, mv;
 247     // number of boxes per closure
 248     size_t nbox, minbox = nb.nx() * nb.ny() + 1;
 249     size_t tx, ty, minx = ~0, miny = ~0;
 250     int xdir = 0;       /* XXX: GCC */
 251
 252     while (find_bad_turn(ty, tx, tdir, nb, last)) {
 253
 254         // Play a bad move that would cause the opponent's closure
 255         if ((mv = nb.domove(ty, tx, tdir, getWho())) != 0)
 256             b.abort("find_min_closure1: Invalid move %d (%d, %d, %d)", mv,
 257                     ty, tx, tdir);
 258
 259         // Count the opponent's closure
 260         if ((nbox = count_closure(y, x, xdir, nb)) == 0)
 261             b.abort("find_min_closure1: no closure found");
 262
 263         if (nbox <= minbox) {
 264             // This closure has fewer boxes
 265             minbox = nbox;
 266             minx = tx;
 267             miny = ty;
 268             mindir = tdir;
 269         }
 270     }
 271
 272     y = miny;
 273     x = minx;
 274     dir = mindir;
 275     return minbox;
 276 }
 277
 278
 279 // Search for the move that makes the opponent close the least number of
 280 // boxes; returns 1 if a move found, 0 otherwise
 281 size_t ALGOR::find_min_closure(size_t& y, size_t& x, int& dir, const BOARD& b)
 282 {
 283     size_t x1, y1;
 284     int dir1;
 285     size_t count = b.ny() * b.nx() + 1, count1;
 286
 287     for (size_t i = 0; i < 3; i++)
 288         if (count > (count1 = find_min_closure1(y1, x1, dir1, b, i))) {
 289             count = count1;
 290             y = y1;
 291             x = x1;
 292             dir = dir1;
 293         }
 294
 295     return count != b.ny() * b.nx() + 1;
 296 }
 297
 298 // Return a move in (y, x, dir)
 299 void ALGOR::play(const BOARD& b, size_t& y, size_t& x, int& dir)
 300 {
 301     // See if we can close the largest closure available
 302     if (find_max_closure(y, x, dir, b))
 303         return;
 304
 305 #ifdef notyet
 306     size_t sgl = find_single();
 307     size_t dbl = find_double();
 308 #endif
 309
 310     // See if we can play an edge without giving the opponent a box
 311     if (find_good_turn(y, x, dir, b))
 312         return;
 313
 314     // Too bad, find the move that gives the opponent the fewer boxes
 315     if (find_min_closure(y, x, dir, b))
 316         return;
 317 }