001 package rules;
002
003 import java.math.BigInteger;
004 import java.util.ArrayList;
005 import java.util.Collection;
006 import java.util.Collections;
007 import java.util.HashMap;
008 import java.util.Map;
009 import java.util.Random;
010
011 import core.Color;
012 import core.Move;
013 import core.Piece;
014 import core.Position;
015
016
017 /**
018 * An AntichessGameState is a GameState specific to Antichess. It represents all
019 * the information needed to play the game, but not auxiliary information like
020 * history and times.
021 *
022 * An AntichessGameState is mutable.
023 *
024 * @specfield board : map<position, piece> //Location of pieces on the board
025 * @specfield tomove : color //The color of the player whose move it is
026 * @specfield moveNum : int //The number of moves that have passed
027 *
028 * Abstract invariant: board is a valid antichess board.
029 */
030 public class GameState
031 {
032 /* The state of the board */
033 final private Board board;
034
035 /* Whose turn it is */
036 private Color toMove;
037
038 /* The number of ply the game has proceeded */
039 private int moveNum;
040
041 private Collection<Move> legalMovesCache;
042
043 private static int[][][] primeTable = computePrimeTable(16, 8, 8);
044
045 private static int[][][] computePrimeTable(int a, int b, int c){
046 int[][][] ans = new int[a][b][c];
047 Random r = new Random();
048
049 for(int x = 0; x < a; x++) {
050 for(int y = 0; y < b; y++) {
051 for(int z = 0; z < c; z++) {
052 int prime = BigInteger.probablePrime(30, r).intValue();
053 ans[x][y][z] = prime;
054 }
055 }
056 }
057 return ans;
058 }
059
060 private final boolean doCheckRep = false;
061
062 // AF:
063 // board = board
064 // tomove= toMove
065 // moveNum = moveNum
066 //
067 // RI:
068 // board, toMove != null
069 // board contains mappings from exactly the valid board positions
070 // All values in board are not null
071
072 public void checkRep()
073 {
074 if (doCheckRep)
075 {
076 assert (toMove != null);
077 assert (board != null);
078 assert (moveNum >= 0);
079 for (int x = 0; x < 8; x++)
080 {
081 for (int y = 0; y < 8; y++)
082 {
083 //assert (board.containsKey(Position.get(x, y)));
084 assert (board.get(x, y) != null);
085 }
086 }
087 }
088 }
089
090 /**
091 * Construct an Antichess-specific GameState.
092 *
093 * @requires p, n, b != null
094 */
095 public GameState(Color p, int n, Board b)
096 {
097 toMove = p;
098 moveNum = n;
099 board = b;
100 checkRep();
101 }
102
103 /**
104 * Construct an Antichess-specific GameState
105 *
106 * @requires p, n, b != null
107 * @requires s represents a valid input to board.fromString
108 */
109 public GameState(Color p, int n, String s)
110 {
111 toMove = p;
112 moveNum = n;
113 board = Board.fromString(s);
114 checkRep();
115 }
116
117 public GameState copy(){
118 return new GameState(toMove, moveNum, board.copy());
119 }
120
121 /**
122 * Construct the initial GameState, representing the starting board
123 * position.
124 */
125 public GameState()
126 {
127 this(Color.WHITE, 0, Board.startingBoard);
128 checkRep();
129 }
130
131 /**
132 * Construct the initial GameState, representing the starting board
133 * position.
134 */
135 public GameState(Map<Position, Piece> powerupDiffs)
136 {
137 this(Color.WHITE, 0, Board.startingBoard);
138 for(Position p: powerupDiffs.keySet()) {
139 board.put(p, powerupDiffs.get(p));
140 }
141 checkRep();
142 }
143
144 public Board getBoard(){
145 return board;
146 }
147
148 /**
149 * @returns A map from positions to pieces, representing the state of the
150 * board.
151 */
152 public Map<Position, Piece> getPieceMap()
153 {
154 Map<Position, Piece> ans = new HashMap<Position, Piece>();
155 for(Position pos: Position.ALL){
156 ans.put(pos, board.get(pos));
157 }
158 return Collections.unmodifiableMap(ans);
159 }
160
161 /**
162 * @returns The color of the player whose turn it is.
163 */
164 public Color getCurrentColor()
165 {
166 return toMove;
167 }
168
169 /**
170 * @returns the Color who has lost all his pieces (or NONE)
171 */
172 public Color piecesWinner()
173 {
174 boolean whiteLost = true, blackLost = true;
175 for(int x = 0; x < 8; x++){
176 for(int y = 0; y < 8; y++){
177 Piece p = board.get(x, y);
178 if (!(p instanceof King) && p.getColor() != Color.NONE){
179 if (p.getColor() == Color.WHITE) {
180 whiteLost = false;
181 if (!blackLost)
182 break;
183 } else if (p.getColor() == Color.BLACK) {
184 blackLost = false;
185 if (!whiteLost)
186 break;
187 }
188 }
189 }
190 }
191 if (whiteLost) {
192 return Color.WHITE;
193 } else if (blackLost) {
194 return Color.BLACK;
195 } else {
196 return Color.NONE;
197 }
198 }
199
200 /**
201 * @returns The Color of the player who has checkmated his opponent (or NONE)
202 */
203 public Color checkmater()
204 {
205 Position kingPos = kingPosition(toMove);
206 if (kingPos == null) {
207 System.out.println(board);
208 throw new RuntimeException("No " + toMove + " king?");
209 }
210
211 if (isThreatened(kingPos, toMove.otherColor()) && !canMove()){
212 return toMove.otherColor();
213 } else {
214 return Color.NONE;
215 }
216 }
217
218 /**
219 * @returns The Color of the player who has won (or NONE if no player has
220 * won yet).
221 */
222 public Color getWinner()
223 {
224 Color mater = checkmater();
225 if (mater != Color.NONE)
226 {
227 return mater;
228 }
229 return piecesWinner();
230 }
231
232 /**
233 * @returns The string representation of the board (mainly for debugging).
234 */
235 public String toString()
236 {
237 return boardString();
238 }
239
240 /**
241 * @returns the number of moves (by either player) since the beginning of
242 * the game.
243 */
244 public int getMoveNum()
245 {
246 return moveNum;
247 }
248
249 /**
250 * @returns whether the current player has any move other than a pass.
251 */
252 public boolean canMove()
253 {
254 Collection<Move> moves = legalMoves();
255 if (moves.size() == 1)
256 {
257 for (Move m : moves)
258 {
259 if (m.isPass())
260 {
261 return false;
262 }
263 }
264 }
265 return true;
266 }
267
268 private Collection<Move> getMoveCandidates(){
269 Collection<Move> moveCandidates = new ArrayList<Move>();
270
271 // Get all possibilities
272 for (Position pos: Position.ALL) {
273 Piece piece = board.get(pos);
274 if (piece.getColor() == toMove) {
275 moveCandidates.addAll(piece.moveCandidates(this, pos));
276 }
277 }
278 return moveCandidates;
279 }
280
281 /**
282 * @returns The set of legal moves from the current position. Always has at
283 * least one move in this set.
284 */
285 public Collection<Move> legalMoves()
286 {
287 if (legalMovesCache != null)
288 return legalMovesCache;
289 Collection<Move> result = new ArrayList<Move>();
290
291 // Remove candidates that put us in check,
292 // filter based on ability to capture.
293 boolean canCapture = false;
294 for (Move m : getMoveCandidates())
295 {
296 Map<Position, Piece> diff = m.toMap(this);
297 boolean thisIsCapture = reversibleMakeMove(diff, true);
298 if (!canCapture || thisIsCapture)
299 {
300 boolean invalid = invalidState();
301 reversibleMakeMove(diff, false);
302 if (!invalid)
303 {
304 if (thisIsCapture == canCapture)
305 {
306 result.add(m);
307 } else if (!canCapture)
308 { // && thisIsCapture
309 canCapture = true;
310 result.clear();
311 result.add(m);
312 } else
313 { // canCapture && !thisIsCapture
314 }
315 }
316 } else
317 {
318 reversibleMakeMove(diff, false);
319 }
320 }
321 if (result.size() == 0)
322 {
323 result.add(new Move()); // pass
324 }
325 legalMovesCache = result;
326 checkRep();
327 return result;
328 }
329
330 /**
331 * Does a color threaten a position? (occupying does not count).
332 *
333 * @returns whether a given position is threatened by a color
334 * @requires pos != null && color != null
335 */
336 public boolean isThreatened(Position pos, Color color)
337 {
338 return (StraightPiece.threatens(this, color, pos) ||
339 Knight.threatens(this, color, pos) ||
340 Pawn.threatens(this, color, pos) ||
341 King.threatens(this, color, pos));
342 }
343
344 /**
345 * @returns the Position of the king of a certain color (or null if that
346 * king died)
347 */
348 private Position kingPosition(Color c)
349 {
350 for(int x = 0; x < 8; x++){
351 for(int y = 0; y < 8; y++){
352 Piece p = board.get(x, y);
353 if (p instanceof King && p.getColor() == c)
354 return Position.get(x, y);
355 }
356 }
357 return null;
358 }
359
360 /**
361 * Is the current state invalid, by the opposite color being in check?
362 *
363 * @returns whether the current state is invalid.
364 */
365 public boolean invalidState()
366 {
367 Position kingPos = kingPosition(toMove.otherColor());
368 if (kingPos == null) //destroy or upgrade can do this
369 return true;
370 return isThreatened(kingPos, toMove);
371 }
372
373 /**
374 * @returns Whether a move is legal.
375 * @requires m != null
376 */
377 public boolean isLegal(Move m)
378 {
379 return legalMoves().contains(m);
380 }
381
382 public Collection<Piece> getPieces(){
383 return board.getPieces();
384 }
385
386 /**
387 * Make a move
388 *
389 * @modifies this
390 * @effects continues game by one move
391 * @requires m != null
392 */
393 public void makeMove(Move m)
394 {
395 reversibleMakeMove(m.toMap(this), true);
396 }
397
398 /**
399 * Modify the AntichessGameState to apply a move, and turn the map into its
400 * inverse.
401 *
402 * @requires m != null
403 * @modifies this
404 * @modifies m
405 * @effects this goes moves forward or backward as defined by isForward by
406 * updating by the map m.
407 * @effects m changes to its inverse on the current board, so a subsequent
408 * call to reversibleMakeMove(m, !isForward) will revert the
409 * change.
410 * @returns whether this move involves a capture.
411 * @requires m != null
412 */
413 public boolean reversibleMakeMove(Map<Position, Piece> m, boolean isForward)
414 {
415 Piece tmp;
416 boolean canCapture = false;
417 toMove = toMove.otherColor();
418 legalMovesCache = null;
419 if (isForward)
420 {
421 moveNum++;
422 } else
423 {
424 moveNum--;
425 }
426 for (Map.Entry<Position, Piece> e : m.entrySet())
427 {
428 tmp = board.get(e.getKey());
429 board.put(e.getKey(), e.getValue());
430 e.setValue(tmp);
431 if (tmp.getColor() == toMove)
432 {
433 canCapture = true;
434 }
435 }
436 checkRep();
437 return canCapture;
438 }
439
440 /**
441 * Return the String representation of the board
442 */
443 public String boardString()
444 {
445 return board.toString();
446 }
447
448 public int hashCode(){
449 int ans = 0;
450 for(int x = 0; x < 8; x++){
451 for(int y = 0; y < 8; y++){
452 Piece p = board.get(x, y);
453 ans ^= primeTable[p.hashCode()][x][y];
454 }
455 }
456 ans = ans - ans % 100 + moveNum;
457 return ans;
458 }
459 }