# English Checkers game

I've written this English checkers game. Meanwhile, it's a human vs. human game, although it is easily extensible to a game between other players (such as a computer one).

"""Play English Checkers.
see https://en.wikipedia.org/wiki/English_draughts
"""

from collections import namedtuple
from itertools import cycle

# square - a number between 1 and 35, that isn't divisible by 9:
#    . 35  . 34  . 33  . 32
#   31  . 30  . 29  . 28  .
#    . 26  . 25  . 24  . 23
#   22  . 21  . 20  . 19  .
#    . 17  . 16  . 15  . 14
#   13  . 12  . 11  . 10  .
#    .  8  .  7  .  6  .  5
#    4  .  3  .  2  .  1  .
# Pay attention that in this representation, the numbers that are
# divisible by 9 are skipped - thus, two squares are adjacents if and
# only if their difference is 4 or 5. Also, this representation may
# be different from the representation that is used in the program's
# interface (for example, in UserPlayer).

# move - a tuple of squares - the first square is the piece we want to
#     move, and the others are the sequence of moves. Usually that tuple
#     is 2 squares long - it's only longer if the player made a multiple
#     jump.

# In some places of the program, the word "edges" will mean pairs of
# squares that have only one reachable square between them (in a
# diagonal line), so you can jump between them if they are both empty
# and there is an opponent's piece in the middle.
# The square in the middle of the two edges will just be called
# "the middle".
SQUARES = [s for s in xrange(1, 36) if s%9 != 0]

# a "jump" means both single and multiple jumps.

class MovingErrors:
"""A namespace for error constants for illegal moves."""
NotASquare = "The move included a number that is not a square."
TooShort = ("The move should start at one square and finish at "
"another one.")
NotYourPiece = "The player should move his own piece."
MoveToPiece = "The player should move to an empty square."
LongSimpleMove = "A simple move must include exactly 2 squares in it."
NotKing = "Only a king can move backwards."
JumpAvaliable = ("If a player can jump, he must do it; And if a player"
" can make multiple jumps, he must make all available"
" jumps in the sequence he chose.")
JumpThroughKingRow = ("If a man jumps to the king's row, the move"
" terminates immediately.")
SometimesJumps = ("If a move starts with a jump, ALL of it should be"
" composed of jumps.")
WeirdCapturing = ("You have to capture your opponent's piece - not "
"empty pieces and not your own ones")
JustInvalid = ("What. A simple move should move a piece to an adjacent"
" square, and a jump should jump above opponents. "
"Is that hard?")

### Checkers Stuff ###

class State(namedtuple('State', 'turn reds whites kings')):
"""A state in the English Checkers game.

The board is always represented in the red's point of view, so the
1-4 rank is the closest rank to the red's side, and the 32-35 rank
is the closest rank to the white's side.

Attributes:
turn - the player that should play now - either State.RED or
State.WHITE.
reds, whites - frozensets of squares, where there are red and
white pieces accordingly.
kings - the squares where there are kings (red and white).
These 4 attributes can also be like elements of a tuple - so you can
unpack them:
>>> turn, reds, whites, kings = state
and you can access them also by doing state[n]. This is useful,
because State.RED is 1 and State.WHITE is 2 - thus state[state.turn]
will return all of the squares that belong to the current player.

Other Attributes:
opponent - the player that shouldn't play now, the opposite of
self.turn.
These attributes can't be accessed like in a tuple.

Main Methods:
state.move(move) - return a new state, that describes the game
after the current player has made the given move.
state.did_end() - True if the game ended, False otherwise.

Other Methods:
simple_move_avaliable(pieces) - return True if any of the given
pieces can make a simple move. (The returned value may be
incorrect if any piece can make a jump)
jump_avaliable(pieces) - return True if any of the given
pieces can make a jump.
farther(s1, s2) - True if s1 is farther from the current player
than the second square, False otherwise.
pieces_after_simple_move(move) - Return a tuple of (red pieces,
white pieces, kings), that describes the board's pieces after
the given (not necessarily legal) simple move.
pieces_after_jump(move) - Return a tuple of (red pieces,
white pieces, kings), that describes the board's pieces
after the given (not necessarily legal) jump.
"""

RED, WHITE = 1, 2  # pay attention that state[RED] == state.reds and
# state[WHITE] == state.whites
KINGS_ROW = {RED: frozenset(range(32, 36)), WHITE: frozenset(range(1, 5))}

def __new__(cls, turn, reds, whites, kings):
# now you can create a new state by passing any kind of iterable
# as pieces
pieces = [frozenset(filter(is_square, xs))
for xs in (reds, whites, kings)]
self = super(State, cls).__new__(cls, turn, *pieces)
self.opponent = cls.WHITE if turn == cls.RED else cls.RED
return self

def move(self, move):
"""If the given move is legal, make it and return the new state,
after the move. If it is illegal, raise ValueError with an
appropriate error message from MovingErrors."""
self.stupid_errors(move)

if are_adjacents(*move[0:2]):  # Simple move
if len(move) > 2:
raise ValueError(MovingErrors.LongSimpleMove)
if self.jump_avaliable(self[self.turn]):
raise ValueError(MovingErrors.JumpAvaliable)
return State(self.opponent, *self.pieces_after_simple_move(move))

elif are_edges(*move[0:2]):  # jump
if not is_jump(move[2:]):
raise ValueError(MovingErrors.SometimesJumps)
if any(s in self.KINGS_ROW[self.turn] and s not in self.kings
for s in move[1:-1]):
raise ValueError(MovingErrors.JumpThroughKingRow)
if any(middle(*pair) not in self[self.opponent]
for pair in pairs(move)):
raise ValueError(MovingErrors.WeirdCapturing)
# If a man jumps to the king's row, he can't make more jumps.
# Otherwise, if he can make more jumps the player must do them.
new_board = self.pieces_after_jump(move)
if (move[-1] in self.KINGS_ROW[self.turn] and
move[0] not in self.kings):
return State(self.opponent, *new_board)
temp_state = State(self.turn, *new_board)
if temp_state.jump_avaliable([move[-1]]):
raise ValueError(MovingErrors.JumpAvaliable)
return State(self.opponent, *new_board)

# Not a simple move, and not a jump
raise ValueError(MovingErrors.JustInvalid)

# Phew.

def stupid_errors(self, move):
"""If the move has an "stupid error" (explained later), raise
ValueError with that error from MovingErrors. Otherwise, do
nothing.

Stupid error - TooShort, NotASquare, NotYourPiece, MoveToPiece,
NotKing.
"""
if len(move) <= 1:
raise ValueError(MovingErrors.TooShort)
if not all(is_square(k) for k in move):
raise ValueError(MovingErrors.NotASquare)
if move[0] not in self[self.turn]:
raise ValueError(MovingErrors.NotYourPiece)
if any(s in self.reds|self.whites for s in move[1:]):
raise ValueError(MovingErrors.MoveToPiece)
if move[0] not in self.kings and not self.farther(move[1], move[0]):
raise ValueError(MovingErrors.NotKing)

def did_end(self):
"""Return True if the game has ended, and False if the player
can do a move."""
return (not self.simple_move_avaliable(self[self.turn]) and
not self.jump_avaliable(self[self.turn]))

def simple_move_avaliable(self, pieces):
"""Return True if any piece from the given iterable of pieces can
make a simple move, False otherwise. It doesn't check if all of
the given pieces exist. Also, if a jump is avaliable it won't
return False because of that, so the returned value would be
incorrect in that case."""
assert all(piece in self[self.turn] for piece in pieces)
for piece in pieces:
for adj in adjacents(piece):
if adj not in self.reds | self.whites:
return True
return False

def jump_avaliable(self, pieces):
"""Return True if any piece from the given iterable of pieces can
do a jump, False otherwise. It doesn't check if all of the given
pieces exist."""
assert all(piece in self[self.turn] for piece in pieces)
for piece in pieces:
# Every jump starts with a single jump.
for edge, mid in edges_middles(piece):
if (edge not in self[self.turn] | self[self.opponent] and
mid in self[self.opponent] and
(piece in self.kings or self.farther(edge, piece))):
return True
return False

def farther(self, s1, s2):
"""Return True if the first square is farther than the second one
(so the second square is closer to the current player's side),
False otherwise."""
return s1 > s2 if self.turn == self.RED else s1 < s2

def pieces_after_simple_move(self, move):
"""Return a tuple of (red pieces, white pieces, kings),
that describes the board's pieces after the given simple move.

This method doesn't check that the given move is simple, or even
legal, and won't necessarily raise an exception.
"""
assert (move[0] in self[self.turn] and
move[1] not in self.reds | self.whites and len(move) == 2)
player = self[self.turn] - {move[0]} | {move[1]}
if move[0] in self.kings:
kings = self.kings - {move[0]} | {move[1]}
else:
kings = self.kings | ({move[1]} & self.KINGS_ROW[self.turn])
return ((player, self[self.opponent], kings) if self.turn == self.RED
else (self[self.opponent], player, kings))

def pieces_after_jump(self, move):
"""Return a tuple of (red pieces, white pieces, kings),
that describes the board's pieces after the given jump.

This method doesn't check that the given move is a jump, or even
legal, and won't necessarily raise an exception.
"""
assert is_jump(move)
single_jumps = pairs(move)
captured = {middle(*p) for p in single_jumps}
player = self[self.turn] - {move[0]} | {move[-1]}
opponent = self[self.opponent] - captured
if move[0] in self.kings:
kings = self.kings - {move[0]} | {move[-1]}
else:
kings = self.kings | ({move[-1]} & self.KINGS_ROW[self.turn])
kings = kings - captured
return ((player, opponent, kings) if self.turn == self.RED
else (opponent, player, kings))

### Square Stuff ###

def are_adjacents(s1, s2):
"""Return True if the two given squares are diagonally adjacent,
False otherwise."""
return abs(s1-s2) in (4, 5)

def are_edges(s1, s2):
"""Return True if two given squares are edges, False otherwise."""
return abs(s1-s2) in (8, 10)

def middle(edge1, edge2):
"""Return the middle of the two given edges."""
assert are_edges(edge1, edge2)
return (edge1 + edge2) / 2

def edges_middles(s):
"""Return a list of all (edge, middle) tuples, where edge is
another square that is an edge with the given square, and middle is
the middle square of s and edge."""
edges = [s + n for n in (8, 10, -8, -10)]
middles = [middle(s, edge) for edge in edges]
tuples = zip(edges, middles)
return [t for t in tuples if is_square(t[0]) and is_square(t[1])]

def adjacents(s):
"""Return a list of all of the adjacent squares to the given square."""
return [s+n for n in (4, 5, -4, -5) if is_square(s+n)]

def is_square(n):
"""Return True if the given number represents a square, False if it
doesn't."""
return 1 <= n <= 35 and n % 9 != 0

def is_jump(move):
"""Return True if each pair in the given sequence of squares is a
pair of edges. False otherwise."""
return all(are_edges(a, b) for a, b in pairs(move))

def rank(s):
"""Return the rank of the given squares. Counting starts from zero."""
return ((s-s//9)-1) // 4

def human_square_to_normal(human_s):
"""Convert the given square from human representation (where squares
are identified by numbers 1-32 and squares that are divisible by 9
aren't skipped) to the normal program's representation.
Raise KeyError if the square doesn't exist."""
return SQUARES[human_s-1]

### Playing Stuff ###

# starting position of checkers
START = State(State.RED, xrange(1, 14), xrange(23, 36), [])

def checkers(red, white):
"""Play English Checkers between the two given players - red makes
the first move. After each turn, yield the move.

A player is a function that has two parameters - a state, and an
optional parameter of an error. The state is an instance of the State
class, that describes the current game, and the player should return
its move, given that state. If the player gets the error
parameter, it means that in the previous time it was called, it
returned an illegal move - so it is called again, with the same state,
and with an error from MovingErrors.
"""
state = START
yield None, state
for player in cycle((red, white)):
if state.did_end():
return
move = player(state)
while True:
try:
state = state.move(move)
except ValueError, err:
move = player(state, str(err))
else:
break
yield move, state

def display_checkers(game, upper_color=State.RED):
"""Display each state in the given game, from the first one to the
last. The "game" is an iterable of (move, state) pairs (the state is
the state of the game after the move), for example the one that is
returned by the function checkers.

upper_color is the color that its player's side appears at the
top of the displayed boards. It can get one of two values:
State.RED or State.WHITE.
"""
for _, state in game:
print_board(state, upper_color)

def play_display_checkers(red, white, upper_color=State.RED):
"""Play a game of checkers with the given players red and white,
and display every new board.
upper_color is the color that appears at the top of the displayed
boards. (color = either State.RED or State.WHITE)
See the docstring of checkers for more information about players.
"""
display_checkers(checkers(red, white), upper_color)

def UserPlayer(dummy_state, error=None):
"""A player function that uses the protocol of the checkers function.
It doesn't display the board to the user, but if there is an error, it
will print it.
It asks the user for a move in a human notation (where the squares are
identified by numbers 1-32, instead of 1-35, and squares that are
divisible by 9 aren't skipped). It returns the move in the program's
notation.
"""
if error is not None:
print error
inp = raw_input("What's your move? Seperate the squares by dashes (-). ")
while True:
try:
human_squares = map(int, inp.split('-'))
move = map(human_square_to_normal, human_squares)
except ValueError:
inp = raw_input('Invalid input. Try again: ')
except KeyError:  # Because of human_square_to_normal
print MovingErrors.NotASquare
inp = raw_input('Try again: ')
else:
break
return tuple(move)

### Utilities ###

def pairs(seq):
"""Return a list of all of the consecutive pairs in the sequence.
Each element (except the first and the last ones) appears in exactly
two pairs: one where it is the first element, and another one where
it is the second one."""
return [(seq[i], seq[i+1]) for i in xrange(len(seq)-1)]

def print_board(state, upper_color=State.RED):
"""Print the given state to the user as a board."""
line = []
# the first squares should be the upper ones.
squares = SQUARES if upper_color == State.RED else SQUARES[::-1]
# zip(*[iterator]*n) clusters the iterator elements into n-length groups.
rows = zip(*[iter(squares)]*4)
for row in rows:
for square in row:
player_ch = ('x' if square in state.reds
else 'y' if square in state.whites else '.')
char = player_ch.upper() if square in state.kings else player_ch
# == is used as an XNOR operator here
if (rank(square) % 2 == 1) == (upper_color == State.WHITE):
line.append('   {}'.format(char))
else:
line.append(' {}  '.format(char))
print ''.join(line)
line = []

###############

if __name__ == '__main__':
play_display_checkers(UserPlayer, UserPlayer, upper_color=State.WHITE)

• I welcome all feedback. If you want, you can choose only one aspect of the code to review (for example, the code in the "### Checkers Stuff ###" section, or the general structure of the whole code). Commented Sep 23, 2015 at 14:12

## 2 Answers

I’m just going to dive in and run the script. Let’s see what happens!

• I get this instruction:

What's your move? Seperate the squares by dashes (-).


I’m nitpicking, but the correct spelling is “separate”.

• More concerningly, I’m not sure what I’m supposed to type here. How do I specify a square? Some sample input would have been useful, because I just typed the first thing that came to mind:

What's your move? Seperate the squares by dashes (-). 23-45
Traceback (most recent call last):
File "checkers.py", line 417, in <module>
play_display_checkers(UserPlayer, UserPlayer, upper_color=State.WHITE)
File "checkers.py", line 357, in play_display_checkers
display_checkers(checkers(red, white), upper_color)
File "checkers.py", line 347, in display_checkers
for _, state in game:
File "checkers.py", line 332, in checkers
move = player(state, str(err))
File "checkers.py", line 374, in UserPlayer
move = map(human_square_to_normal, human_squares)
File "checkers.py", line 302, in human_square_to_normal
return SQUARES[human_s-1]
IndexError: list index out of range


Looks like you’ve failed to range-check my input. Be careful – just because I give you something that looks like an integer doesn’t mean it’s correct.

However, brownie points for not falling over when I try to type in non-numeric input.

One case that could do with slight tidying: what if I specify multiple dashes?

Invalid input. Try again: 1-3-5
The player should move to an empty square.


That should also count as invalid input.

• If I peek under the hood, I found a comment which seems to specify numbers that line up with cells. Okay, let me try that.

 . 35  . 34  . 33  . 32
31  . 30  . 29  . 28  .
. 26  . 25  . 24  . 23
22  . 21  . 20  . 19  .
. 17  . 16  . 15  . 14
13  . 12  . 11  . 10  .
.  8  .  7  .  6  .  5
4  .  3  .  2  .  1  .


Hmm, it didn’t behave quite as I expected (actual vs. expected on left/right):

What's your move? Seperate the squares by dashes (-). 12-16
y   y   y   y                        #    y   y   y   y
y   y   y   y                          #  y   y   y   y
y   y   y   y                        #    y   y   y   y
.   .   .   .                          #  .   .   .   .
x   .   .   .                        #    .   x   .   .
.   x   x   x                          #  x   .   x   x
x   x   x   x                        #    x   x   x   x
x   x   x   x                          #  x   x   x   x


I’m not sure if that’s a bug or a misunderstanding on my part – but it is weird.

I played a few more moves, and they didn’t quite line up with the grid in the comment at the top of the file.

• This is a rather unfriendly message:

What's your move? Seperate the squares by dashes (-). 9-15
What. A simple move should move a piece to an adjacent square, and a jump should jump above opponents. Is that hard?


Don’t be condescending to your users, especially if you haven’t provided any good instructions for playing the game. It’s not my fault if I don’t know what I should be doing.

• What’s going on with the number 9?

The best thing you could do for this program is improve the introductory process. It’s very difficult (perhaps impossible) to work out how to play the game from the instructions printed to stdout. The quality of your code is irrelevant if I can’t play the game.

I don’t have time to review the code properly, but here are a few things that jumped out at me:

• I was a bit confused by the name of the is_square() function, because it conflicts with my idea of a square number. Perhaps rename to is_grid_square()?

• There isn’t much wrong PEP 8-wise, except a bit of missing whitespace around operators and the fact that functions should be separated by two blank lines, not one.

• There’s a spelling error in a few method names: “avaliable” should be “available”.

• The docstring for stupid_errors reads:

If the move has an "stupid error" (explained later), raise ValueError with that error from MovingErrors. Otherwise, do nothing.

Stupid error - TooShort, NotASquare, NotYourPiece, MoveToPiece, NotKing.

I’m assuming the list of errors in the line below wasn’t what you meant by “explained later”, but I don’t find any other reference to stupid errors if I grep for “stupid”.

I would also refrain from using derogatory terms like “stupid” to describe errors.

• I think this is just a bit bizarre:

# == is used as an XNOR operator here
if (rank(square) % 2 == 1) == (upper_color == State.WHITE):


If you really want to do an XNOR operator, I think a more intuitive construction is

if ~(condition1 ^ condition2)


but the problem isn’t so much the way the condition is written, as the fact that I don’t know why the condition is significant. There isn’t a comment to explain why the code has been written this way.

In general, there aren’t many comments in this file, which make it hard to read, review and maintain.

• OK, thanks. The interface doesn't use the internal representation of squares, but rather the more common one, where squares that are divisible by 9 do exist - I will add instructions for that. Commented Sep 25, 2015 at 10:46

I have some notes on comments, naming and other ways that you communicate your code's intent. You have a lot of comments and try to give information, but there's room to improve it.

Reading through and this sentence sets off an alarm:

# In some places of the program, the word "edges" will mean


"edges" only means the edge of a square in some places? Why is the meaning of this contextually based? From checking the usage, I see that you're consistently using "edges" to actually mean just one thing. Be careful of opening your documentation with unclear language like this, it makes a user go down entirely the wrong path. It'd be better to say

# In this program, the word "edges" means


So it's more clear and definite, not changeable. It also is odd how much you danced around the definition of edges. I thought at first you meant the corner squares from which there's only one square to move to (unless you can jump over the opponent's piece/s). Why not just say they mean the edges of the board? Unless there's semantics I'm missing, that would mean the same and be clearer to a user reading your script. After all, they haven't gotten to any of the logic used to calculate the edges yet, and that seems to be what your definition is concerned with.

Now you start talking about move in this long comment too, why not just in the move function? Oh, because move is used in two entirely different contexts. Even worse you're passing move tuples to the move method. This is circular sounding and confusing. Much better would be something like maybe passing a tuple named positions. Just think about how readable piece.move(positions) is, and you wont confuse the user about which is which.

Your errors being collected together and all named is a good idea, but they don't need to be a class. A dictionary works fine. And since they're constants, they should be named in UPPER_SNAKE_CASE. It's the convention for Python constants, and makes it clear that you haven't created Exception objects, they're just string constants.

MOVING_ERRORS = { # A namespace for error constants for illegal moves. "NOT_A_SQUARE": "The move included a number that is not a square.", "TOO_SHORT": ("The move should start at one square and finish at " "another one."),

You misspelled available in simple_move_avaliable every time it came up. If that was a copy pasted typo, be careful of them as you can entirely miss an error that way that only gets found when a user tries to play with your code.

You should use inline comments sparingly, a sign not to use them is when they're too long to fit on one line and the formatting is ruined a bit by having it inline.

RED, WHITE = 1, 2  # pay attention that state[RED] == state.reds and
# state[WHITE] == state.whites


I think this is better:

RED, WHITE = 1, 2
# Note state[RED] == state.reds and state[WHITE] == state.whites


Aside from stupid_errors being a bit insulting, it's not a good name because it doesn't indicate to me what trait these errors share. In addition to that, it implies that there is an error that needs to be dealt with but it's actually checking if there are errors. You should instead call it validate_input or is_valid_input.

One last note, having a lot of docstrings is great, you're trying to inform the user of what each does. But the format could be better. They should have one single line summary, then an empty line and then extra details.

def jump_avaliable(self, pieces):
"""Returns whether or not any piece given can do a jump

Takes a list 'pieces' and returns a boolean.
It doesn't check if all of the given pieces exist."""


Read the PEP specifically about docstrings to learn more.

• I'm now thinking about it, and I'm not really sure that making MOVING_ERRORS a dictionary is a good idea. If a typo is made (for example MOVING_ERRORS['TWO_SHORT']), KeyError - "could not be found" - will be raised, instead of AttributeError- "does not exist". (the latter is better - the dictionary will never be changed). I also find that the occasion of using dictionaries of constants is quite rare. Are you sure about that? Commented Sep 27, 2015 at 16:01
• @MrHezi It's mostly personal preference really. A dictionary is designed to hold a collection of related values while a class isn't really designed for this even if it can do the same job. There's no particular downside to your approach that I'm aware of, except that initially I thought you were creating actual Exceptions and not just string messages. If you used UPPER_SNAKE_CASE the usage would probably be clear enough for people to understand that it was just a string. Commented Sep 27, 2015 at 19:44