1 /* $NetBSD: algor.cc,v 1.6 2021/12/05 09:22:45 rillig 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 * Computer algorithm
34 */
35
36 #include "defs.h"
37 RCSID("$NetBSD: algor.cc,v 1.6 2021/12/05 09:22:45 rillig Exp $")
38
39 #include "algor.h"
40 #include "board.h"
41 #include "box.h"
42 #include "random.h"
43
ALGOR(const char c)44 ALGOR::ALGOR(const char c) : PLAYER(c)
45 {
46 #ifdef notyet
47 // Single Edges = (x + y) * 2
48 _edge1 = (_b.nx() * _b.ny()) * 2;
49 // Shared Edges = (x * (y - 1)) + ((x - 1) * y)
50 _edge2 = (_b.nx() * (_b.ny() - 1)) + ((_b.nx() - 1) * _b.ny());
51 // Maximum Edges filled before closure = x * y * 2
52 _maxedge = _b.nx() * _b.ny() * 2;
53 #endif
54 }
55
56 // Find the first closure, i.e. a box that has 3 edges
find_closure(size_t & y,size_t & x,int & dir,BOARD & b)57 int ALGOR::find_closure(size_t& y, size_t& x, int& dir, BOARD& b)
58 {
59 RANDOM rdy(b.ny()), rdx(b.nx());
60
61 for (y = rdy(); y < b.ny(); y = rdy()) {
62 rdx.clear();
63 for (x = rdx(); x < b.nx(); x = rdx()) {
64 BOX box(y, x, b);
65 if (box.count() == 3) {
66 for (dir = BOX::first; dir < BOX::last; dir++)
67 if (!box.isset(dir))
68 return 1;
69 b.abort("find_closure: 3 sided box[%zu,%zu] has no free sides",
70 y, x);
71 }
72 }
73 }
74 return 0;
75 }
76
77 #if 0
78 size_t ALGOR::find_single()
79 {
80 size_t ne;
81
82 // Find the number of single edges in use
83 for (size_t x = 0; x < b.nx(); x++) {
84 BOX tbox(0, x, b);
85 ne += tbox.isset(BOX::top);
86 BOX bbox(b.ny() - 1, x, b);
87 ne += bbox.isset(BOX::bottom);
88 }
89 for (size_t y = 0; y < _b.ny(); y++) {
90 BOX lbox(y, 0, b);
91 ne += lbox.isset(BOX::left);
92 BOX rbox(y,_b.nx() - 1, b);
93 ne += rbox.isset(BOX::right);
94 }
95 return ne;
96 }
97 #endif
98
99
100 // Count a closure, by counting all boxes that we can close in the current
101 // move
count_closure(size_t & y,size_t & x,int & dir,BOARD & b)102 size_t ALGOR::count_closure(size_t& y, size_t& x, int& dir, BOARD& b)
103 {
104 size_t i = 0;
105 size_t tx, ty;
106 int tdir, mv;
107
108 while (find_closure(ty, tx, tdir, b)) {
109 if (i == 0) {
110 // Mark the beginning of the closure
111 x = tx;
112 y = ty;
113 dir = tdir;
114 }
115 if ((mv = b.domove(ty, tx, tdir, getWho())) == -1)
116 b.abort("count_closure: Invalid move (%zu, %zu, %d)", y, x, dir);
117 else
118 i += mv;
119 }
120 return i;
121 }
122
123
124 /*
125 * Find the largest closure, by closing all possible closures.
126 * return the number of boxes closed in the maximum closure,
127 * and the first box of the maximum closure in (x, y, dir)
128 */
find_max_closure(size_t & y,size_t & x,int & dir,const BOARD & b)129 size_t ALGOR::find_max_closure(size_t& y, size_t& x, int& dir, const BOARD& b)
130 {
131 BOARD nb(b);
132 int maxdir = -1;
133 size_t nbox, maxbox = 0;
134 size_t maxx = ~0, maxy = ~0;
135 size_t tx = 0, ty = 0; /* XXX: GCC */
136 int tdir = 0; /* XXX: GCC */
137
138 while ((nbox = count_closure(ty, tx, tdir, nb)) != 0)
139 if (nbox > maxbox) {
140 // This closure is better, update max
141 maxbox = nbox;
142 maxx = tx;
143 maxy = ty;
144 maxdir = tdir;
145 }
146
147 // Return the max found
148 y = maxy;
149 x = maxx;
150 dir = maxdir;
151 return maxbox;
152 }
153
154
155 // Find if a turn does not result in a capture on the given box
156 // and return the direction if found.
try_good_turn(BOX & box,size_t y,size_t x,int & dir,BOARD & b)157 int ALGOR::try_good_turn(BOX& box, size_t y, size_t x, int& dir, BOARD& b)
158 {
159 // Sanity check; we must have a good box
160 if (box.count() >= 2)
161 b.abort("try_good_turn: box[%zu,%zu] has more than 2 sides occupied",
162 y, x);
163
164 // Make sure we don't make a closure in an adjacent box.
165 // We use a random direction to randomize the game
166 RANDOM rd(BOX::last);
167 for (dir = rd(); dir < BOX::last; dir = rd())
168 if (!box.isset(dir)) {
169 size_t by = y + BOX::edges[dir].y;
170 size_t bx = x + BOX::edges[dir].x;
171 if (!b.bounds(by, bx))
172 return 1;
173
174 BOX nbox(by, bx, b);
175 if (nbox.count() < 2)
176 return 1;
177 }
178
179 return 0;
180 }
181
182
183 // Try to find a turn that does not result in an opponent closure, and
184 // return it in (x, y, dir); if not found return 0.
find_good_turn(size_t & y,size_t & x,int & dir,const BOARD & b)185 int ALGOR::find_good_turn(size_t& y, size_t& x, int& dir, const BOARD& b)
186 {
187 BOARD nb(b);
188 RANDOM rdy(b.ny()), rdx(b.nx());
189
190 for (y = rdy(); y < b.ny(); y = rdy()) {
191 rdx.clear();
192 for (x = rdx(); x < b.nx(); x = rdx()) {
193 BOX box(y, x, nb);
194 if (box.count() < 2 && try_good_turn(box, y, x, dir, nb))
195 return 1;
196 }
197 }
198 return 0;
199 }
200
201 // On a box with 2 edges, return the first or the last free edge, depending
202 // on the order specified
try_bad_turn(BOX & box,size_t & y,size_t & x,int & dir,BOARD & b,int last)203 int ALGOR::try_bad_turn(BOX& box, size_t& y, size_t& x, int& dir, BOARD& b,
204 int last)
205 {
206 if (4 - box.count() <= last)
207 b.abort("try_bad_turn: Called at [%zu,%zu] for %d with %d",
208 y, x, last, box.count());
209 for (dir = BOX::first; dir < BOX::last; dir++)
210 if (!box.isset(dir)) {
211 if (!last)
212 return 1;
213 else
214 last--;
215 }
216 return 0;
217 }
218
219 // Find a box that has 2 edges and return the first free edge of that
220 // box or the last free edge of that box
find_bad_turn(size_t & y,size_t & x,int & dir,BOARD & b,int last)221 int ALGOR::find_bad_turn(size_t& y, size_t& x, int& dir, BOARD& b, int last)
222 {
223 RANDOM rdy(b.ny()), rdx(b.nx());
224 for (y = rdy(); y < b.ny(); y = rdy()) {
225 rdx.clear();
226 for (x = rdx(); x < b.nx(); x = rdx()) {
227 BOX box(y, x, b);
228 if ((4 - box.count()) > last &&
229 try_bad_turn(box, y, x, dir, b, last))
230 return 1;
231 }
232 }
233 return 0;
234 }
235
find_min_closure1(size_t & y,size_t & x,int & dir,const BOARD & b,int last)236 size_t ALGOR::find_min_closure1(size_t& y, size_t& x, int& dir, const BOARD& b,
237 int last)
238 {
239 BOARD nb(b);
240 int tdir, mindir = -1, mv;
241 // number of boxes per closure
242 size_t nbox, minbox = nb.nx() * nb.ny() + 1;
243 size_t tx, ty, minx = ~0, miny = ~0;
244 int xdir = 0; /* XXX: GCC */
245
246 while (find_bad_turn(ty, tx, tdir, nb, last)) {
247
248 // Play a bad move that would cause the opponent's closure
249 if ((mv = nb.domove(ty, tx, tdir, getWho())) != 0)
250 b.abort("find_min_closure1: Invalid move %d (%zu, %zu, %d)", mv,
251 ty, tx, tdir);
252
253 // Count the opponent's closure
254 if ((nbox = count_closure(y, x, xdir, nb)) == 0)
255 b.abort("find_min_closure1: no closure found");
256
257 if (nbox <= minbox) {
258 // This closure has fewer boxes
259 minbox = nbox;
260 minx = tx;
261 miny = ty;
262 mindir = tdir;
263 }
264 }
265
266 y = miny;
267 x = minx;
268 dir = mindir;
269 return minbox;
270 }
271
272
273 // Search for the move that makes the opponent close the least number of
274 // boxes; returns 1 if a move found, 0 otherwise
find_min_closure(size_t & y,size_t & x,int & dir,const BOARD & b)275 size_t ALGOR::find_min_closure(size_t& y, size_t& x, int& dir, const BOARD& b)
276 {
277 size_t x1, y1;
278 int dir1;
279 size_t count = b.ny() * b.nx() + 1, count1;
280
281 for (size_t i = 0; i < 3; i++)
282 if (count > (count1 = find_min_closure1(y1, x1, dir1, b, i))) {
283 count = count1;
284 y = y1;
285 x = x1;
286 dir = dir1;
287 }
288
289 return count != b.ny() * b.nx() + 1;
290 }
291
292 // Return a move in (y, x, dir)
play(const BOARD & b,size_t & y,size_t & x,int & dir)293 void ALGOR::play(const BOARD& b, size_t& y, size_t& x, int& dir)
294 {
295 // See if we can close the largest closure available
296 if (find_max_closure(y, x, dir, b))
297 return;
298
299 #ifdef notyet
300 size_t sgl = find_single();
301 size_t dbl = find_double();
302 #endif
303
304 // See if we can play an edge without giving the opponent a box
305 if (find_good_turn(y, x, dir, b))
306 return;
307
308 // Too bad, find the move that gives the opponent the fewer boxes
309 if (find_min_closure(y, x, dir, b))
310 return;
311 }
312