algor.cc revision 1.5 
1/*	$NetBSD: algor.cc,v 1.5 2012/02/29 23:39:53 joerg 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"
36RCSID("$NetBSD: algor.cc,v 1.5 2012/02/29 23:39:53 joerg Exp $")
37
38#include "algor.h"
39#include "board.h"
40#include "box.h"
41#include "random.h"
42
43ALGOR::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
56int 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[%zu,%zu] has no free sides",
69			y, x);
70	    }
71	}
72    }
73    return 0;
74}
75
76#if 0
77size_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
101size_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 (%zu, %zu, %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 */
128size_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.
156int 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[%zu,%zu] 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.
184int 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
202int 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 [%zu,%zu] 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
220int 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
235size_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 (%zu, %zu, %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
274size_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)
292void 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}
311