Permalink
Newer
Older
100644 566 lines (463 sloc) 15.7 KB
2
#ifndef _BOARD_H_
3
#define _BOARD_H_
4
5
#include <cstdio>
6
#include <algorithm>
7
#include <vector>
8
#include <string>
9
using namespace std;
10
12
#include "string.h"
May 24, 2010
16
static const int BitsSetTable64[] = {
17
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
18
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
19
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
20
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
21
};
22
23
/*
24
* the board is represented as a flattened 2d array of the form:
25
* 1 2 3
26
* A 0 1 2 0 1 0 1
27
* B 3 4 5 => 3 4 5 => 3 4 5
28
* C 6 7 8 7 8 7 8
29
* This follows the H-Gui convention, not the 'standard' convention
32
const MoveScore neighbours[18] = {
33
MoveScore(-1,-1, 3), MoveScore(0,-1, 3), MoveScore(1, 0, 3), MoveScore(1, 1, 3), MoveScore( 0, 1, 3), MoveScore(-1, 0, 3), //direct neighbours, clockwise
34
MoveScore(-2,-2, 1), MoveScore(0,-2, 1), MoveScore(2, 0, 1), MoveScore(2, 2, 1), MoveScore( 0, 2, 1), MoveScore(-2, 0, 1), //corners of ring 2, easy to block
35
MoveScore(-1,-2, 2), MoveScore(1,-1, 2), MoveScore(2, 1, 2), MoveScore(1, 2, 2), MoveScore(-1, 1, 2), MoveScore(-2,-1, 2), //sides of ring 2, virtual connections
36
};
Timo Ewalds
Jan 24, 2010
39
struct Cell {
40
unsigned piece : 2; //who controls this cell, 0 for none, 1,2 for players
41
mutable unsigned parent : 9; //parent for this group of cells
Timo Ewalds
Apr 17, 2010
42
unsigned size : 7; //size of this group of cells
43
unsigned corner : 6; //which corners are this group connected to
44
unsigned edge : 6; //which edges are this group connected to
Timo Ewalds
Apr 17, 2010
45
unsigned local : 2; //0 for far, 1 for distance 2, 2 for virtual connection, 3 for neighbour
47
Cell() : piece(0), parent(0), size(0), corner(0), edge(0), local(0) { }
Timo Ewalds
Jan 24, 2010
48
Cell(unsigned int p, unsigned int a, unsigned int s, unsigned int c, unsigned int e) :
49
piece(p), parent(a), size(s), corner(c), edge(e) { }
May 24, 2010
51
int numcorners(){ return BitsSetTable64[corner]; }
52
int numedges() { return BitsSetTable64[edge]; }
Timo Ewalds
Mar 10, 2010
56
class MoveIterator { //only returns valid moves...
57
const Board & board;
58
int lineend;
59
Move move;
60
bool unique;
61
HashSet hashes;
Timo Ewalds
Mar 10, 2010
62
public:
63
MoveIterator(const Board & b, bool Unique, bool allowswap) : board(b), lineend(0), move(Move(M_SWAP)), unique(Unique) {
64
if(board.outcome != -1){
65
move = Move(0, board.size_d); //already done
66
}else if(!allowswap || !board.valid_move(move)){ //check if swap is valid
67
if(unique){
68
hashes.init(board.movesremain());
69
hashes.add(board.test_hash(move, board.toplay()));
70
}
71
++(*this); //find the first valid move
Timo Ewalds
Mar 10, 2010
74
75
const Move & operator * () const { return move; }
76
const Move * operator -> () const { return & move; }
77
bool done() const { return (move.y >= board.get_size_d()); }
78
bool operator == (const Board::MoveIterator & rhs) const { return (move == rhs.move); }
79
bool operator != (const Board::MoveIterator & rhs) const { return (move != rhs.move); }
Timo Ewalds
Mar 10, 2010
80
MoveIterator & operator ++ (){ //prefix form
81
do{
82
move.x++;
83
84
if(move.x >= lineend){
Timo Ewalds
Mar 10, 2010
85
move.y++;
86
if(move.y >= board.get_size_d()) //done
87
return *this;
88
89
move.x = board.linestart(move.y);
90
lineend = board.lineend(move.y);
Timo Ewalds
Mar 10, 2010
91
}
92
}while(!board.valid_move_fast(move) || (unique && hashes.exists(board.test_hash(move, board.toplay()))));
93
94
if(unique)
95
hashes.add(board.test_hash(move, board.toplay()));
Timo Ewalds
Mar 10, 2010
96
97
return *this;
98
}
99
MoveIterator operator ++ (int){ //postfix form, discouraged from being used
100
MoveIterator newit(*this);
101
++(*this);
102
return newit;
103
}
104
};
105
107
char size; //the length of one side of the hexagon
108
char size_d; //diameter of the board = size*2-1
109
110
short nummoves;
111
short unique_depth; //update and test rotations/symmetry with less than this many pieces on the board
113
char outcome; //-1 = unknown, 0 = tie, 1,2 = player win
114
char wintype; //0 no win, 1 = edge, 2 = corner, 3 = ring
115
bool allowswap;
Timo Ewalds
Jan 24, 2010
117
vector<Cell> cells;
124
125
Board(int s){
126
size = s;
127
size_d = s*2-1;
128
nummoves = 0;
Timo Ewalds
Jan 24, 2010
135
cells.resize(vecsize());
136
137
for(int y = 0; y < size_d; y++){
138
for(int x = 0; x < size_d; x++){
139
int i = xy(x, y);
Timo Ewalds
Jan 24, 2010
140
cells[i] = Cell(0, i, 1, (1 << iscorner(x, y)), (1 << isedge(x, y)));
Timo Ewalds
Jan 24, 2010
144
145
int memsize() const { return sizeof(Board) + sizeof(Cell)*vecsize(); }
Timo Ewalds
Jan 24, 2010
146
147
int get_size_d() const { return size_d; }
148
int get_size() const{ return size; }
150
int vecsize() const { return size_d*size_d; }
151
int numcells() const { return vecsize() - size*(size - 1); }
153
int num_moves() const { return nummoves; }
154
int movesremain() const { return (won() >= 0 ? 0 : numcells() - nummoves + canswap()); }
156
int xy(int x, int y) const { return y*size_d + x; }
157
int xy(const Move & m) const { return m.y*size_d + m.x; }
158
159
int xyc(int x, int y) const { return xy( x + size-1, y + size-1); }
160
int xyc(const Move & m) const { return xy(m.x + size-1, m.y + size-1); }
162
//assumes valid x,y
163
int get(int i) const { return cells[i].piece; }
164
int get(int x, int y) const { return get(xy(x,y)); }
165
int get(const Move & m) const { return get(xy(m)); }
Timo Ewalds
Apr 17, 2010
167
int local(const Move & m) const { return cells[xy(m)].local; }
168
169
//assumes x, y are in array bounds
170
bool onboard_fast(int x, int y) const { return ( y - x < size) && ( x - y < size); }
171
bool onboard_fast(const Move & m) const { return (m.y - m.x < size) && (m.x - m.y < size); }
172
//checks array bounds too
173
bool onboard(int x, int y) const { return ( x >= 0 && y >= 0 && x < size_d && y < size_d && onboard_fast(x, y) ); }
174
bool onboard(const Move & m)const { return (m.x >= 0 && m.y >= 0 && m.x < size_d && m.y < size_d && onboard_fast(m) ); }
176
void setswap(bool s) { allowswap = s; }
177
bool canswap() const { return (nummoves == 1 && toPlay == 2 && allowswap); }
179
//assumes x, y are in bounds (meaning no swap) and the game isn't already finished
180
bool valid_move_fast(int x, int y) const { return !get(x,y); }
181
bool valid_move_fast(const Move & m) const { return !get(m); }
182
//checks array bounds too
183
bool valid_move(int x, int y) const { return (outcome == -1 && onboard(x, y) && !get(x,y)); } //ignores swap rule!
184
bool valid_move(const Move & m) const { return (outcome == -1 && ((onboard(m) && !get(m)) || (m == M_SWAP && canswap()))); }
185
186
int iscorner(int x, int y) const {
187
if(!onboard(x,y))
188
return -1;
189
190
int m = size-1, e = size_d-1;
191
192
if(x == 0 && y == 0) return 0;
193
if(x == m && y == 0) return 1;
194
if(x == e && y == m) return 2;
195
if(x == e && y == e) return 3;
196
if(x == m && y == e) return 4;
197
if(x == 0 && y == m) return 5;
198
199
return -1;
200
}
201
202
int isedge(int x, int y) const {
203
if(!onboard(x,y))
204
return -1;
205
206
int m = size-1, e = size_d-1;
207
208
if(y == 0 && x != 0 && x != m) return 0;
209
if(x-y == m && x != m && x != e) return 1;
210
if(x == e && y != m && y != e) return 2;
211
if(y == e && x != e && x != m) return 3;
212
if(y-x == m && x != m && x != 0) return 4;
213
if(x == 0 && y != m && y != 0) return 5;
214
215
return -1;
216
}
217
218
219
int linestart(int y) const { return (y < size ? 0 : y - (size-1)); }
220
int lineend(int y) const { return (y < size ? size + y : size_d); }
221
int linelen(int y) const { return size_d - abs((size-1) - y); }
226
for(int i = 0; i < size; i++){
228
s += " ";
229
}
230
s += "\n";
231
232
for(int y = 0; y < size_d; y++){
233
s += string(abs(size-1 - y) + 2, ' ');
234
s += char('A' + y);
235
s += " ";
236
for(int x = linestart(y); x < lineend(y); x++){
237
int p = get(x, y);
238
if(p == 0) s += '.';
239
if(p == 1) s += 'W';
240
if(p == 2) s += 'B';
241
s += ' ';
243
if(y < size-1)
245
s += '\n';
246
}
247
return s;
248
}
249
251
printf("%s", to_s().c_str());
252
}
253
255
switch(outcome){
256
case -1: return "none";
Timo Ewalds
Mar 9, 2010
257
case 0: return "draw";
258
case 1: return "white";
259
case 2: return "black";
260
}
261
return "unknown";
265
return outcome;
266
}
267
268
int win() const{
269
if(outcome <= 0)
270
return 0;
271
return (outcome == toplay() ? 1 : -1);
272
}
273
274
char getwintype() const { return wintype; }
275
280
MoveIterator moveit(bool unique = false, int swap = -1) const {
281
return MoveIterator(*this, (unique ? nummoves <= unique_depth : false), (swap == -1 ? allowswap : swap));
Timo Ewalds
Mar 10, 2010
282
}
283
284
void set(const Move & m){
285
cells[xy(m)].piece = toPlay;
287
update_hash(m, toPlay); //depends on nummoves
290
291
void unset(const Move & m){ //break win checks, but is a poor mans undo if all you care about is the hash
292
toPlay = 3 - toPlay;
293
update_hash(m, toPlay);
294
nummoves--;
295
cells[xy(m)].piece = 0;
296
}
297
298
void doswap(){
299
for(int y = 0; y < size_d; y++){
Timo Ewalds
May 14, 2010
300
for(int x = linestart(y); x < lineend(y); x++){
301
if(get(x,y) != 0){
302
cells[xy(x,y)].piece = 2;
303
toPlay = 1;
304
return;
305
}
306
}
307
}
308
}
310
int find_group(const Move & m) const { return find_group(xy(m)); }
311
int find_group(int x, int y) const { return find_group(xy(x, y)); }
Oct 5, 2010
312
int find_group(unsigned int i) const {
Timo Ewalds
Jan 24, 2010
313
if(cells[i].parent != i)
314
cells[i].parent = find_group(cells[i].parent);
315
return cells[i].parent;
316
}
317
318
//join the groups of two positions, propagating group size, and edge/corner connections
319
//returns true if they're already the same group, false if they are now joined
320
bool join_groups(const Move & a, const Move & b) { return join_groups(xy(a), xy(b)); }
321
bool join_groups(int x1, int y1, int x2, int y2) { return join_groups(xy(x1, y1), xy(x2, y2)); }
322
bool join_groups(int i, int j){
323
i = find_group(i);
324
j = find_group(j);
325
326
if(i == j)
327
return true;
328
Timo Ewalds
Jan 24, 2010
329
if(cells[i].size < cells[j].size) //force i's subtree to be bigger
330
swap(i, j);
331
Timo Ewalds
Jan 24, 2010
332
cells[j].parent = i;
333
cells[i].size += cells[j].size;
334
cells[i].corner |= cells[j].corner;
335
cells[i].edge |= cells[j].edge;
336
337
return false;
338
}
339
340
int test_connectivity(const Move & pos) const {
341
char turn = toplay();
342
343
Cell testcell = cells[find_group(pos)];
344
for(int i = 0; i < 6; i++){
345
Move loc = pos + neighbours[i];
346
347
if(onboard(loc) && turn == get(loc)){
348
const Cell * g = & cells[find_group(loc)];
349
testcell.corner |= g->corner;
350
testcell.edge |= g->edge;
351
i++; //skip the next one
352
}
353
}
354
return testcell.numcorners() + testcell.numedges();
355
}
356
357
int test_size(const Move & pos) const {
358
char turn = toplay();
359
360
int size = 1;
361
for(int i = 0; i < 6; i++){
362
Move loc = pos + neighbours[i];
363
364
if(onboard(loc) && turn == get(loc)){
365
size += cells[find_group(loc)].size;
366
i++; //skip the next one
367
}
368
}
369
return size;
370
}
371
372
//check if a position is encirclable by a given player
373
//false if it or one of its neighbours are the opponent's and connected to an edge or corner
374
bool encirclable(const Move pos, int player) const {
375
int otherplayer = 3-player;
376
377
const Cell * g = & cells[find_group(pos)];
378
if(g->piece == otherplayer && (g->edge || g->corner))
379
return false;
380
381
for(int i = 0; i < 6; i++){
382
Move loc = pos + neighbours[i];
383
384
if(!onboard(loc))
385
return false;
386
387
const Cell * g = & cells[find_group(loc)];
388
if(g->piece == otherplayer && (g->edge || g->corner))
389
return false;
390
}
391
return true;
392
}
393
394
// recursively follow a ring
395
bool detectring(const Move & pos, char turn) const {
396
for(int i = 0; i < 4; i++){ //4 instead of 6 since any ring must have its first endpoint in the first 4
397
Move loc = pos + neighbours[i];
399
if(onboard(loc) && turn == get(loc) && followring(pos, loc, i, turn))
400
return true;
401
}
402
return false;
403
}
404
// only take the 3 directions that are valid in a ring
405
// the backwards directions are either invalid or not part of the shortest loop
406
bool followring(const Move & start, const Move & cur, const int & dir, const int & turn) const {
407
for(int i = 5; i <= 7; i++){
408
int nd = (dir + i) % 6;
409
Move next = cur + neighbours[nd];
411
if(start == next || (onboard(next) && turn == get(next) && followring(start, next, nd, turn)))
412
return true;
413
}
414
return false;
415
}
416
417
hash_t gethash() const {
418
return (nummoves > unique_depth ? hash.get(0) : hash.get());
419
}
420
421
void update_hash(const Move & pos, int turn){
422
if(nummoves > unique_depth){ //simple update, no rotations/symmetry
423
hash.update(0, 3*xy(pos) + turn);
424
return;
425
}
426
427
//mirror is simply flip x,y
428
int x = pos.x - size+1,
429
y = pos.y - size+1,
430
z = y - x;
431
432
//x,y; y,z; z,-x; -x,-y; -y,-z; -z,x
433
//y,x; z,y; -x,z; -y,-x; -z,-y; x,-z
434
435
hash.update(0, 3*xyc( x, y) + turn);
436
hash.update(1, 3*xyc( y, z) + turn);
437
hash.update(2, 3*xyc( z, -x) + turn);
438
hash.update(3, 3*xyc(-x, -y) + turn);
439
hash.update(4, 3*xyc(-y, -z) + turn);
440
hash.update(5, 3*xyc(-z, x) + turn);
441
hash.update(6, 3*xyc( y, x) + turn);
442
hash.update(7, 3*xyc( z, y) + turn);
443
hash.update(8, 3*xyc(-x, z) + turn);
444
hash.update(9, 3*xyc(-y, -x) + turn);
445
hash.update(10, 3*xyc(-z, -y) + turn);
446
hash.update(11, 3*xyc( x, -z) + turn);
447
}
448
449
hash_t test_hash(const Move & pos, int turn) const {
450
if(nummoves >= unique_depth) //simple test, no rotations/symmetry
451
return hash.test(0, 3*xy(pos) + turn);
452
453
int x = pos.x - size+1,
454
y = pos.y - size+1,
455
z = y - x;
456
457
hash_t m = hash.test(0, 3*xyc( x, y) + turn);
458
m = min(m, hash.test(1, 3*xyc( y, z) + turn));
459
m = min(m, hash.test(2, 3*xyc( z, -x) + turn));
460
m = min(m, hash.test(3, 3*xyc(-x, -y) + turn));
461
m = min(m, hash.test(4, 3*xyc(-y, -z) + turn));
462
m = min(m, hash.test(5, 3*xyc(-z, x) + turn));
463
m = min(m, hash.test(6, 3*xyc( y, x) + turn));
464
m = min(m, hash.test(7, 3*xyc( z, y) + turn));
465
m = min(m, hash.test(8, 3*xyc(-x, z) + turn));
466
m = min(m, hash.test(9, 3*xyc(-y, -x) + turn));
467
m = min(m, hash.test(10, 3*xyc(-z, -y) + turn));
468
m = min(m, hash.test(11, 3*xyc( x, -z) + turn));
469
return m;
470
}
471
472
bool move(const Move & pos, bool checkwin = true, bool locality = false, bool checkrings = true){
473
if(!valid_move(pos))
474
return false;
475
476
if(pos == M_SWAP){
477
doswap();
478
return true;
479
}
480
Timo Ewalds
Apr 17, 2010
481
char turn = toplay();
485
if(locality){
486
for(int i = 6; i < 18; i++){
Timo Ewalds
Apr 17, 2010
487
MoveScore loc = neighbours[i] + pos;
488
Timo Ewalds
Apr 17, 2010
490
cells[xy(loc)].local |= loc.score;
491
}
492
}
493
494
bool local = (cells[xy(pos)].local == 3);
495
bool alreadyjoined = false; //useful for finding rings
496
for(int i = 0; i < 6; i++){
497
Move loc = pos + neighbours[i];
500
cells[xy(loc)].local = 3;
501
if(local && turn == get(loc)){
502
alreadyjoined |= join_groups(pos, loc);
503
i++; //skip the next one. If it is the same group,
504
//it is already connected and forms a corner, which we can ignore
505
}
509
if(checkwin){
510
Cell * g = & cells[find_group(pos)];
511
if(g->numedges() >= 3){
512
outcome = turn;
513
wintype = 1;
514
}else if(g->numcorners() >= 2){
515
outcome = turn;
516
wintype = 2;
517
}else if(checkrings && alreadyjoined && g->size >= 6 && detectring(pos, turn)){
520
}else if(nummoves == numcells()){
521
outcome = 0;
522
}
523
}
524
return true;
525
}
527
bool test_local(const Move & pos) const {
528
return (cells[xy(pos)].local == 3);
529
}
530
531
//test if making this move would win, but don't actually make the move
532
int test_win(const Move & pos, char turn = 0) const {
533
if(cells[xy(pos)].local != 3)
534
return -1;
535
536
if(turn == 0)
537
turn = toplay();
539
Cell testcell = cells[find_group(pos)];
540
int numgroups = 0;
541
for(int i = 0; i < 6; i++){
542
Move loc = pos + neighbours[i];
543
544
if(onboard(loc) && turn == get(loc)){
545
const Cell * g = & cells[find_group(loc)];
546
testcell.corner |= g->corner;
547
testcell.edge |= g->edge;
549
i++; //skip the next one
550
numgroups++;
551
}
552
}
553
554
if(testcell.numcorners() >= 2 || testcell.numedges() >= 3 || (numgroups >= 2 && testcell.size >= 6 && detectring(pos, turn)))
555
return turn;
556
557
if(nummoves+1 == numcells())
558
return 0;
559
560
return -1;
561
}