games/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  *
  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.3 2006/05/14 03:20:42 christos 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 }