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>