Enumerating Chess Piece Moves

There was a question asked recently here that went through enumerating moves for a chess piece. I was going to write an answer for this question, but while I was bashing out some code to throw into an answer, I figured why not build it out completely instead and have it critiqued. Note that this doesn't implement en-passant or castling, as these are a bit of a pain.

'''
chess.py

A very simple implementation of a chess board and pieces, mainly
for the purposes of enumerating all possible moves a piece can
make from a given board state.
'''

from __future__ import print_function

from itertools import chain, imap, takewhile

board_size = range(8)
BLACK = 'black'
WHITE = 'white'

class InvalidMoveError(Exception):
'''Exception that is raised when an invalid move is
attempted.
'''

def __init__(self, msg):
super(InvalidMoveError, self).__init__(msg)

class Square(object):
'''Defines a board square. This is given an x and y co-ordinate,
and can optionally be populated with a piece. The co-ordinates
go from (0, 0) to (7, 7), where (0, 0) is the top left corner
and (7, 7) the bottom right. The first value indicates the row,
the second the column.
'''

def __init__(self, x, y, piece=None):
self._x = x
self._y = y
self._piece = piece

@property
def piece(self):
return self._piece

@property
def x(self):
return self._x

@property
def y(self):
return self._y

@property
def coordinates(self):
return (self._x, self._y)

def is_empty(self):
'''Returns True if this Square is not populated with,
True otherwise.
'''
return self._piece is None

def can_move_to(self, piece):
'''Checks if the piece passed as an argument can move to
this square. A piece may move to a square that is empty or
that contains a piece of the opposing colour.
Returns True if the piece can make the move, False otherwise.
'''
return self.is_empty() or (self._piece.colour != piece.colour)

def enumerate_moves(self, board):
'''Enumerates moves for the piece contained on this square.
Returns a list of moves, or an empty list if the square is
empty or the piece has no valid moves.
'''
if not self._piece:
return []
return self._piece.enumerate_moves(board, self._x, self._y)

def __eq__(self, other):
if other is not None and isinstance(other, Square):
return all((self.x == other.x, self.y == other.y))
return False

def __ne__(self, other):
return not self == other

def __str__(self):
return str(self._piece) if not self.is_empty() else '_'

class InvalidSquare(object):
'''Class that defines a "non-square" that can be used to signal
a square that does not exist on the board.
This supports methods that Square supports, but does not
have any of the properties (that is x, y, piece).
'''

def is_empty(self):
return False

def can_move_to(self, piece):
return False

def enumerate_moves(self, board):
return []

def __eq__(self, other):
if other is not None and isinstance(other, InvalidSquare):
return True
return False

def __ne__(self, other):
return not self == other

def __str__(self):
return 'Invalid'

class Piece(object):

def __init__(self, colour):
self._colour = colour

@property
def colour(self):
return self._colour

class Pawn(Piece):

def __init__(self, colour):
super(Pawn, self).__init__(colour)

def enumerate_moves(self, board, x, y):
move_dir = 1 if self.colour == BLACK else -1
start_row = 1 if self.colour == BLACK else 6
return self._enumerate_moves(board, x, y, start_row, move_dir)

def _enumerate_moves(self, board, x, y, start_x_row, move_dir):

moves = []
# Is the pawn at its starting position? If so, we can
# (potentially) move it forward two rows.
if all((x == start_x_row,
board.at(x + move_dir, y).is_empty(),
board.at(x + 2 * move_dir, y).is_empty())):
moves.append(board.at(x + 2 * move_dir, y))

# Check if we can move it forward one row
if board.at(x + move_dir, y).can_move_to(self):
moves.append(board.at(x + move_dir, y))

# Test the diagonals. Pawns can only move (one) square
# diagonally if there is a piece to take.
left_diagonal = board.at(x + move_dir, y - 1)
right_diagonal = board.at(x + move_dir, y + 1)

def opponent_piece_exists(square):
if not square.is_empty():
return (square != InvalidSquare() and
square.piece.color != self.colour)
return False

if opponent_piece_exists(left_diagonal):
moves.append(left_diagonal)
if opponent_piece_exists(right_diagonal):
moves.append(right_diagonal)

return moves

def __str__(self):
return 'P'

class Knight(Piece):

def __init__(self, colour):
super(Knight, self).__init__(colour)

def enumerate_moves(self, board, x, y):
indices = [board.at(x + 2, y + 1),
board.at(x + 2, y - 1),
board.at(x + 1, y + 2),
board.at(x + 1, y - 2),
board.at(x - 1, y + 2),
board.at(x - 1, y - 2),
board.at(x + 2, y + 1),
board.at(x + 2, y - 1)]

return [square for square in indices if
square != InvalidSquare()]

def __str__(self):
return 'Kn'

class Bishop(Piece):

def __init__(self, colour):
super(Bishop, self).__init__(colour)

def enumerate_moves(self, board, x, y):

def not_invalid(square):
return square.can_move_to(self)

positive = takewhile(not_invalid,
(board.at(x + n, y + n) for n in board_size[1:]))
negative = takewhile(not_invalid,
(board.at(x - n, y - n) for n in board_size[1:]))
pos_neg = takewhile(not_invalid,
(board.at(x + n, y - n) for n in board_size[1:]))
neg_pos = takewhile(not_invalid,
(board.at(x - n, y + n) for n in board_size[1:]))

return list(chain(positive, negative, pos_neg, neg_pos))

def __str__(self):
return 'B'

class Rook(Piece):

def __init__(self, colour):
super(Rook, self).__init__(colour)

def enumerate_moves(self, board, x, y):

def not_invalid(square):
return square.can_move_to(self)

x_positive = takewhile(not_invalid,
(board.at(x + n, y) for n in board_size[1:]))
x_negative = takewhile(not_invalid,
(board.at(x - n, y) for n in board_size[1:]))
y_positive = takewhile(not_invalid,
(board.at(x, y + n) for n in board_size[1:]))
y_negative = takewhile(not_invalid,
(board.at(x, y - n) for n in board_size[1:]))

return list(chain(x_positive, x_negative, y_positive, y_negative))

def __str__(self):
return 'R'

class Queen(Piece):

def __init__(self, colour):
super(Queen, self).__init__(colour)

def enumerate_moves(self, board, x, y):
# Moves for a queen are the union of those from a rook
# and a bishop.
bishop = Bishop(self.colour)
rook = Rook(self.colour)

bishop_moves = bishop.enumerate_moves(board, x, y)
rook_moves = rook.enumerate_moves(board, x, y)
bishop_moves.extend(rook_moves)
return bishop_moves

def __str__(self):
return 'Q'

class King(Piece):

def __init(self, colour):
super(King, self).__init__(colour)

def enumerate_moves(self, board, x, y):
indices = [board.at(x + 1, y),
board.at(x - 1, y),
board.at(x, y + 1),
board.at(x, y - 1),
board.at(x - 1, y + 1),
board.at(x - 1, y - 1),
board.at(x + 1, y + 1),
board.at(x + 1, y - 1)]

return [square for square in indices if square != InvalidSquare()]

def __str__(self):
return 'Ki'

class Board(object):
'''A Board defines an object that encapsulates the 64 squares of
an 8x8 chess board. This is initialized to a default starting
board.
'''

def __init__(self):
self._squares = [list() for _ in board_size]
order = (Rook, Knight, Bishop, Queen, King, Bishop, Knight, Rook)

self._squares[0] = [Square(0, idx, piece(BLACK))
for idx, piece in enumerate(order)]
self._squares[-1] = [Square(7, idx, piece(WHITE))
for idx, piece in enumerate(order)]

self._squares[1] = [Square(1, idx, Pawn(BLACK)) for idx in board_size]
self._squares[6] = [Square(6, idx, Pawn(WHITE)) for idx in board_size]

for row in board_size[2:-2]:
self._squares[row] = [Square(row, col) for col in board_size]

def at(self, x, y):
'''Retrives the square at (row x, column y). Numbering starts from
0, where (0, 0) denotes the left-top hand of the board, and (7, 7)
denotes the bottom right hand side of the board.
'''

if all((x >= board_size[0], y >= board_size[0],
x <= board_size[-1], y <= board_size[-1])):
return self._squares[x][y]
return InvalidSquare()

def move_piece(self, from_square, to_square):
'''Updates the board by moving the piece in from_square
to the square having coordinates in to_square. This does
not check that the move is valid.
If no piece exists on from_square, an InvalidMoveError is
raised.
'''
if from_square.is_empty():
raise InvalidMoveError('No piece exists on the square to move from!')
to_x, to_y = to_square.coordinates
from_x, from_y = from_square.coordinates
self._squares[to_x][to_y] = Square(to_x, to_y, from_square.piece)
self._squares[from_x][from_y] = Square(from_x, from_y)

def checked_move_piece(self, from_square, to_square):
'''Updates the board by moving the piece in from_square
to the square having coorindates in to_square.
This is checked to ensure that the move is valid for the
piece that is on from_square. If this is not a valid move,
or from_square does not contain a piece, an InvalidMoveError
is raised.
'''
if to_square.coordinates not in imap(lambda square: square.coordinates,
from_square.enumerate_moves(self)):
raise InvalidMoveError('Piece cannot be moved to {},{}'.format(
to_square.x, to_square.y))
self.move_piece(from_square, to_square)

def print(self):
'''Prints a textual representation of the current board state.'''
for row in self._squares:
for col in row:
print(' {0} '.format(str(col)), end='')
print('\n')


A small __main__ to show an example of how this fits together:

if __name__ == '__main__':

b = Board()
b.print()

print('-' * 80)
print()

print('Piece type: {}'.format(b.at(0, 1).piece))
moves = b.at(0, 1).enumerate_moves(b)
print('Valid Moves:')
print(list(imap(lambda x: '({},{})'.format(x.x, x.y), moves)))

print()
print('-' * 80)
print()

knight_square = b.at(0, 1)
b.checked_move_piece(knight_square, b.at(2, 0))
b.checked_move_piece(b.at(2, 0), b.at(3, 2))
b.checked_move_piece(b.at(1, 1), b.at(3, 1))
b.checked_move_piece(b.at(1, 2), b.at(2, 2))
b.checked_move_piece(b.at(0, 2), b.at(2, 0))
b.checked_move_piece(b.at(0, 3), b.at(3, 0))
b.print()

• Just a minor thing: why bother implementing an __init__ (or any method) that only calls the inherited implementation? – jonrsharpe Jun 30 '15 at 20:43
• As you note, castling and enpassant mean that you cant work out the valid moves from board position alone. You need the move history – Ewan Jul 1 '15 at 7:57

I answered the other chess question I think you're referring to, and I'm going to have a go at answering yours; I'm still not a chess player, though, or an very experienced object oriented coder, so I'm speaking more to the lines of code, naming, readability and possible bugs than the big-picture design. It's nit-picky, but I hope with some merit.

Overall, I'm not loving the interaction between board, squares and pieces. Pieces don't know where they are, so to list the moves you give a piece its coordinates, the piece asks the board for squares in its move pattern, the board returns some squares, and the piece asks the squares if it can move to them. The piece is proxying all the data through it, but not adding much to it.

Then squares can enumerate the moves of the piece on them, which feels like a shortcut to avoid asking a square for a piece, then asking the piece for its moves; why build lots of objects to keep things separate, then mix up their responsibilities like that?

Pieces could have move_dir and start_row as instance properties calculated once in init; calculating the start_row of a piece every time it enumerate_moves() for the entire game, feels like the wrong place to put that code.

Presumably you read the answers in the other chess question from other people, about how enumerating the moves piece by piece, turn by turn is very costly, and pre-computing the moves for all pieces before the game is the only way to get fast enough performance for a chess engine to try many possible moves? That looks like it applies to your code (e.g. no caching), but it might not be relevant.

Okay, from the top...

def can_move_to(self, piece):
'''Checks if the piece passed as an argument can move to
this square.


The square doesn't move, so 'can_move_to' feels misleading. a_square.is_valid_destination_for(piece) or a_square.is_available_to(piece) might make the intent more clear. But I think the piece should be responsible for the check, asking the square if it is empty, or what colour the piece on the square is, then deciding if it can move there or not.

What is the wider intent for being able to compare squares with eq? Is it right that two squares are considered equal if they have the same co-ordinates, but one is empty and one has a piece on it?

Can this:

if other is not None and isinstance(other, Square):


become:

if isinstance(other, Square):


? isinstance(None, Square) is False, so the first test seems unnecessary.

In English: "an empty square" - empty is an adjective, which suggests it might be a better fit for a property (square.empty) rather than a method (square.is_empty()). How a square determines whether it is empty (calculation vs. storing it as a bool) is an implementation detail and irrelevant to the outside world.

In the Pawn class, American spelling of color typo:

   def opponent_piece_exists(square):
if not square.is_empty():
return (square != InvalidSquare() and
square.piece.color != self.colour)


In the Knight class, the Knight adds eight squares to its move list, you exclude squares which are off the board, but what if one of the squares in the move list has a same-colour piece on it? (I think the board will move the Knight onto it, and the piece in to_square disappears from the game).

indices = but it's not index-plural, it's squares, or possible move destinations.

Bishops. not_invalid could be called valid.

If the bishop is at 0,0 then board_size[1:] moves the bishop.x 0+1, 0+2, 0+3... ok. But if the bishop is at 7,7 then board_size[1:] moves the bishop.x 7+1, 7+2, ... so the [1:] in four places makes the code slightly harder to read, to save checking if the bishop can move onto itself. (Which it can't, because of the can_move colour check).

Rooks. Same comment as bishops.

Kings. Same comment as knights - they can move on top of other same-colour pieces.

(I can deal with 0,0 being in the top left corner, but using x to move vertically and y to move horizontally keeps tripping me up. Is that a Chess thing? A common game or graphics thing?)

I almost flagged up the use of itertools.takewhile as a bug, until I realised it constrains the possible moves at the edge of the board, and also cutting off when other pieces are involved. That's neat.

class Board(object):
'''A Board defines an object that encapsulates the 64 squares of
an 8x8 chess board. This is initialized to a default starting
board.
'''


But it doesn't do that, it defines an object that encapsulates the ?? squares of a len(board_size)*len(board_size) chess board.

And board_size is taken from the module(?) scope, instead of being a parameter to the board init, that seems risky.

Is board_size ever going to be non-consecutive numbers? Can you replace:

    if all((x >= board_size[0], y >= board_size[0],
x <= board_size[-1], y <= board_size[-1])):
return self._squares[x][y]


with:

   if x in board_size and y in board_size:
return self._squares[x][y]


?

def checked_move_piece(self, from_square, to_square):
#[..]#
if to_square.coordinates not in imap(lambda square: square.coordinates,
from_square.enumerate_moves(self)):
raise InvalidMoveError('Piece cannot be moved to {},{}'.format(
to_square.x, to_square.y))


itertools.imap and a lambda function? It's a fine use for a more common list comprehension:

    if to_square.coordinates not in [square.coordinates
for square in from_square.enumerate_moves(self)]:
raise InvalidMoveError('Piece cannot be moved to {},{}'.format(
to_square.x, to_square.y))


    for row in self._squares:
for col in row:


rows don't contain columns, they contain squares.

Minor docstring typos:

'''Returns True if this Square is not populated with, (with?)

to the square having coorindates

• A few points: the (self._piece.colour != piece.colour) takes care of checking that a piece cannot move to a square with the same colour piece. I'm not American, so colour is the correct spelling, but if this were code that was anything more than a quick bit of fun, I'd probably use the American spelling. Performance isn't a concern, if I was planning on doing this with performance in mind, I wouldn't write it in Python :) – Yuushi Jul 1 '15 at 5:56
• As for the naming comments, I agree completely, I think is_valid_destination is much better. I was trying to keep the interface uniform, but adding move_dir and start_row for Pawns is probably a good idea. I can probably get rid of __eq__ on Square, now that I check specifically using coordinates. not_invalid...I'm not sure why I thought that was a good idea, valid makes much more sense. Finally, the board_size[1:] is needed as otherwise takewhile will stop immediately. – Yuushi Jul 1 '15 at 6:04
• In opponent_piece_exists it should be square.piece.coloUr !=self.colours, typo because inconsistent with the rest of the code, not just because of UK/US spelling. I get that the colour test in can_move_to stops pieces moving to squares with the same colour - but you never call can_move_to for the King or knight, you only test them against InvalidSquare. Ahh, I understand about the board_size[1:]/takewhile. (I haven't used takewhile and jumped to assuming it was the same as filter, but in itertools. I learned better but didn't follow all the consequences). – TessellatingHeckler Jul 1 '15 at 11:25
• Oops, you're 100% right for both. I didn't read what you said about the typo closely enough. Also completely overlooked that I didn't do the test in Knight/King. This is why unit tests are important! – Yuushi Jul 1 '15 at 18:08