1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
|
/*******************************************************************************
* Copyright (c) 2000, 2005 IBM Corporation and others.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* http://www.eclipse.org/legal/epl-v10.html
*
* Contributors:
* IBM Corporation - initial API and implementation
*******************************************************************************/
package org.eclipse.swt.examples.browser.demos;
public class Pawns {
/* Current board representation in compacted form */
byte[] game = new byte[64];
/* Best move */
int bestIndex = -1;
/* Related best score */
int bestScore = Integer.MIN_VALUE;
/* Estimated strategic value of each cell based on proximity to walls */
static int[] gameWallWeight = new int[64];
Thread thread = null;
boolean threadStop = false;
final static byte EMPTY = 0;
final static byte WHITE = 1;
final static byte BLACK = 2;
final static byte WALL = 3;
public Pawns() {
}
/* Provide the current game and ignitiate the search of the best move for the given type
* Must return immediately as it will be called from the UI thread.
* The UI thread will fetch the best move any time thereafter.
*/
public void playRequest(byte[][] game, int type) {
threadStop = true;
synchronized (this) {
bestIndex = -1;
bestScore = Integer.MIN_VALUE;
convert(game, this.game);
initPawnBorders(this.game, gameWallWeight);
/* Quickly compute a legal move */
for (int i = 0; i < this.game.length; i++) {
if (this.game[i] == EMPTY) {
bestIndex = i;
break;
}
}
new Thread() {
public void run() {
synchronized(Pawns.this) {
threadStop = false;
int[] result = new int[2];
/* if long time, must check for threadStop and exit early */
evalBest(Pawns.this.game, BLACK, 2, result);
bestIndex = result[0];
bestScore = result[1];
}
}
}.start();
}
}
/* Fetch best move in natural coordinates for the board previously given in
* the call to playRequest.
*/
public void getBestMove(int[] point) {
convert(bestIndex, point);
threadStop = true;
}
/* Given an expanded representation of the board, format internal compact mode */
static void convert(byte[][] board, byte[] g) {
for (int i = 0; i < board.length; i++) System.arraycopy(board[i], 0, g, i * 8, 8);
}
/* Update given compact model based on player move in natural coordinates */
static void set(byte[] g, int x, int y, byte type) {
g[x*8+y] = type;
}
/* Given an index in compact representation, return natural coordinates */
static void convert(int index, /*out [0] x [1] y */int[] point) {
point[0] = index / 8;
point[1] = index % 8;
}
/* Given an index into the compact model and the neighbour code,
* return the index of the corresponding neighbour index.
* Returns -1 if there is no neighbour.
*
* Neighbour code for the index X
* 0 1 2
* 3 X 4
* 5 6 7
*/
static int getNeighbourIndex(byte[] g, int index, int neighbour) {
if (index < 0 || index >= g.length) return -1;
int result = -1;
switch (neighbour) {
case 0: result = index < 8 || index % 8 == 0 ? -1 : index - 9; break;
case 1: result = index < 8 ? -1 : index - 8; break;
case 2: result = index < 8 || index % 8 == 7 ? -1 : index - 7; break;
case 3: result = index % 8 == 0 ? -1 : index - 1; break;
case 4: result = index % 8 == 7 ? -1 : index + 1; break;
case 5: result = index % 8 == 0 || index >= 56 ? -1 : index + 7; break;
case 6: result = index >= 56 ? -1 : index + 8; break;
case 7: result = index % 8 == 7 || index >= 56 ? -1 : index + 9; break;
}
return result;
}
/* Make the player type play at index on given compact board
* Compute all pawns that must be reversed.
*/
static void play(byte[] g, int index, byte type) {
byte opponentType = type == WHITE ? BLACK : WHITE;
for (int neighbour = 0; neighbour <= 7; neighbour++) {
int nIndex = getNeighbourIndex(g, index, neighbour);
int[] reversiIndeces = new int[6];
int nReversi = 0;
while (nIndex != -1 && nReversi < 6 && g[nIndex] == opponentType) {
reversiIndeces[nReversi] = nIndex;
nReversi++;
nIndex = getNeighbourIndex(g, nIndex, neighbour);
}
if (nReversi > 0 && nIndex != -1 && g[nIndex] == type) {
for (int i = 0; i < nReversi; i++) g[reversiIndeces[i]] = type;
}
}
g[index] = type;
}
/* Evaluate the given compact model based on pawns distribution
* High means white has advantage. Below zero means black has advantage.
*/
static int eval(byte[] g) {
int cntWhite = 0, cntBlack = 0, cntEmpty = 0;
int cntWhiteWallAdvantage = 0, cntBlackWallAdvantage = 0;
for (int i = 0; i < 64; i++) {
if (g[i] == WHITE) {
cntWhite++;
cntWhiteWallAdvantage += gameWallWeight[i];
}
else if (g[i] == BLACK) {
cntBlack++;
cntBlackWallAdvantage += gameWallWeight[i];
}
else if (g[i] == EMPTY) cntEmpty++;
}
if (cntEmpty == 0) {
if (cntWhite > cntBlack) return Integer.MAX_VALUE; /* White wins */
if (cntWhite < cntBlack) return Integer.MIN_VALUE; /* Black wins */
return 0; /* Stalemate */
}
return cntWhite + cntWhiteWallAdvantage - cntBlack - cntBlackWallAdvantage;
}
/* Recognize pawns protected by walls or borders
* TBD - note this should be called only once for each cell and stored
* in a separate byte[] gWallGain
* */
static void initPawnBorders(byte[] g, int[] gameWallWeight) {
/* A pawn has 8 neighbours on 4 axes.
* Strategic pawns have one side of each axis protected by a wall and the other
* side not closed by a wall.
* A pawn cannot be reversed when each of its 4 axes are protected by a wall on
* one side. Pawns that have more than 4 walls are less interesting since they
* are not open enough to the board.
*
* Nbr walls, nbr axis covered, estimated value
* 0 n/a 0
* 1 1 2
* 2 1 1
* 2 2 6
* 3 2 4
* 4 2 2
* 3 3 9
* 4 3 8
* 4 4 16
* 5 4 14
* 6 4 9
* 7 4 6
* 8 4 0
*/
int[] nTypes = new int[8];
for (int i = 0; i < 64; i++) {
int nWalls = 0;
int nAxis = 0;
for (int n = 0; n < 8; n++) {
int nIndex = getNeighbourIndex(g, i, n);
nTypes[n] = nIndex != -1 ? g[nIndex] : WALL;
if (nTypes[n] == WALL) nWalls++;
}
int score = nWalls;
if (nWalls > 0) {
if (nTypes[0] == WALL || nTypes[7] == WALL) nAxis++;
if (nTypes[1] == WALL || nTypes[6] == WALL) nAxis++;
if (nTypes[2] == WALL || nTypes[5] == WALL) nAxis++;
if (nTypes[4] == WALL || nTypes[3] == WALL) nAxis++;
switch (nAxis) {
case 4: switch (nWalls) { case 4: score = 16; break; case 5: score = 14; break; case 6: score = 9; case 7: score = 6; break; case 8: score = 0; break;} break;
case 3: switch (nWalls) { case 3: score = 9; break; case 4: score = 8;} break;
case 2: switch (nWalls) { case 2: score = 6; break; case 3: score = 4; break; case 4: score = 2; } break;
case 1: switch (nWalls) { case 1: score = 2; break; case 2: score = 1; break;} break;
}
}
gameWallWeight[i] = score;
}
}
/* Evaluate the best move for player type for the given board, doing a depth 1 search */
static void evalBest(byte[] g, byte type, int depth, /* out [0] best move, [1] minimax */int[] result) {
byte[] tmp = new byte[64];
byte opponentType = type == WHITE ? BLACK : WHITE;
result[0] = -1; result[1] = Integer.MIN_VALUE;
for (int i = 0; i < 64; i++) {
if (g[i] == EMPTY) {
System.arraycopy(g, 0, tmp, 0, 64);
play(tmp, i, type);
int score = eval(tmp);
if (depth > 1) {
int[] tmpResult = new int[2];
evalBest(tmp, opponentType, depth - 1, tmpResult);
score = tmpResult[1];
}
if ((type == WHITE && score > result[1]) || (type == BLACK && score < result[1]) || result[0] == -1) {
result[0] = i;
result[1] = score;
}
}
}
}
}
|
