[BACK]Return to algor.cc CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / games / dab

Annotation of src/games/dab/algor.cc, Revision 1.5

1.5     ! joerg       1: /*     $NetBSD: algor.cc,v 1.4 2008/04/28 20:22:53 martin Exp $        */
1.1       christos    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"
1.5     ! joerg      36: RCSID("$NetBSD: algor.cc,v 1.4 2008/04/28 20:22:53 martin Exp $")
1.1       christos   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;
1.5     ! joerg      68:                b.abort("find_closure: 3 sided box[%zu,%zu] has no free sides",
1.1       christos   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)
1.5     ! joerg     115:            b.abort("count_closure: Invalid move (%zu, %zu, %d)", y, x, dir);
1.1       christos  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:  */
1.2       christos  128: size_t ALGOR::find_max_closure(size_t& y, size_t& x, int& dir, const BOARD& b)
1.1       christos  129: {
                    130:     BOARD nb(b);
1.3       christos  131:     int maxdir = -1;
1.1       christos  132:     size_t nbox, maxbox = 0;
1.3       christos  133:     size_t maxx = ~0, maxy = ~0;
                    134:     size_t tx = 0, ty = 0;     /* XXX: GCC */
                    135:     int tdir = 0;              /* XXX: GCC */
1.1       christos  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)
1.5     ! joerg     160:        b.abort("try_good_turn: box[%zu,%zu] has more than 2 sides occupied",
1.1       christos  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)
1.5     ! joerg     206:        b.abort("try_bad_turn: Called at [%zu,%zu] for %d with %d",
1.1       christos  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:
1.2       christos  235: size_t ALGOR::find_min_closure1(size_t& y, size_t& x, int& dir, const BOARD& b,
                    236:     int last)
1.1       christos  237: {
                    238:     BOARD nb(b);
1.3       christos  239:     int tdir, mindir = -1, mv;
1.1       christos  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;
1.3       christos  243:     int xdir = 0;      /* XXX: GCC */
1.1       christos  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)
1.5     ! joerg     249:            b.abort("find_min_closure1: Invalid move %d (%zu, %zu, %d)", mv,
1.1       christos  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
1.2       christos  274: size_t ALGOR::find_min_closure(size_t& y, size_t& x, int& dir, const BOARD& b)
1.1       christos  275: {
                    276:     size_t x1, y1;
                    277:     int dir1;
1.2       christos  278:     size_t count = b.ny() * b.nx() + 1, count1;
1.1       christos  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:
1.2       christos  288:     return count != b.ny() * b.nx() + 1;
1.1       christos  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: }

CVSweb <webmaster@jp.NetBSD.org>