Course:CPSC312-2016-Project1-Chess

Chess

Authors: Brandon Sanderson, Maggie Chen

What is the problem?

We will model a chess board and analyze its state. Rules of chess here: https://en.wikipedia.org/wiki/Rules_of_chess For our project, we will not model certain idiosyncratic moves of the game. For example, transforming a pawn into a rook or a queen once it reaches the other side of the board, allowing pawns to move two squares on its first move, allowing the king to move to the side of a rook. All pieces will have standard moves that they can make and nothing more.

What is the something extra?

These are the features we plan to implement:

Given a chess board and a player (black or white), we want to analyze if that player is in checkmate, assuming it is their turn. We will need to account for moves that would lead us off of the chessboard, stalemates (i.e. we need to check if the king is in check at its current position), cases where the king may escape by killing a piece of the other colour, and cases where moving another piece of our own colour will allow the king to escape checkmate (e.g. moving in front of the attacking piece or killing the attacking piece).

Given a chess board, a number N, a player (black or white), we want to see if the player can win in N moves. (As this will require checking all permutations, during marking we suggest that the program be run on a smaller chessboard with fewer chess pieces, to reduce runtime. Or, keep N small, e.g. N = 2 or N = 3)

What did we learn from doing this?

Prolog works with chess, but its runtime is as bad as other programming languages. This is because instantiation of coordinates on the board is an issue at a low level. For example, when finding the coordinates of a piece on the board with some type T and color C, we can't just expect a chess piece to unify with those simple requirements. The program will say that it is insufficiently instantiated because it would need to search through all possible coordinates (which includes non-integers, non-number values, etc). Prolog prevents this by refusing to evaluate algebraic (in)equalities that aren't ground (i.e. have uninstantiated variables). Hence, in find_color_piece, we must use a helper function that iterates through all the possible squares checking for such a piece. The iterator is initialized to position (0, 0) so that the variables representing X and Y are ground.

Similarly, when trying to find all the possible moves that a chess piece can make on a board given its position on that board, we cannot expect it to unify with our requirements (i.e. there isn't a piece there of the same color already, it is a valid move for this particular piece, etc), because again, it would need to search through all possible coordinates. Prolog throws the same error, complaining that it will not compute algebraic in(equalities) that aren't ground. As a result, we need to explicitly iterate through the board ourselves, as we have done in destinations_on_board, with another iterator starting at (0, 0). This iteration is costly.

Compared to a language like Java, our low level Prolog code is less readable. Iteration in Java would be much easier (simply using a for loop).

However, at a higher level, Prolog can be very succinct. Once our groundwork was laid out (functions for verifying checks, checkmates, safe moves, etc), it did not take many lines to implement mate_in_n (~30 lines). We just needed to try out different moves and see if any of them lead to checkmate. While inefficient, the high-level code is more readable than if it were written in Java, because it takes advantage of negation as failure and unification of variables. In Java, this would require explicitly checking all possibilities (which is done automatically w/ backtracking in Prolog) and explicit multiple checks for equality (which is done implicitly when the same variable appears twice in a clause).

Checkmate on a sparse 8x8 board runs very quickly (almost instantaneously). It just needs to make sure that there is no single move that the losing player can make that will get the king to safety. Mate in X can become quite slow (3-10 seconds for mate-in-3 on a 8x8 board), because it has to check all possible moves of one player, followed by all possible moves by the other, followed by all possible moves of the original player, and so on until the number of moves X goes to 0.

In conclusion, the runtime for Prolog is as bad as other languages. The low-level code is less readable than other languages, and the higher-level code is more readable than other languages.