Draughts in Python
Emma Parsley
40206111@live.napier.ac.uk
Edinburgh Napier University - Algorithms and Data Structures SET09117
Abstract having an odd width will cause one player to have more
pieces than the other.
This project aims to create playable Draughts in Python Rows In a standard game of Draughts each players
using the most useful and relevant algorithms and data pieces take up the first 3 rows of the board however as
structures. It should be possible to play this with two hu- we can define the height of the board there are situations
man players as well as with one human player against the where this doesn’t work, such as when the boards height
computer. It should be possible to undo, redo and replay is 6 or less, to fix this the rows must be set to be at least
the games. 1 and at most;
Keywords – Python, Algorithms, Data Structures, AI,
Minimax rows = (height/2) − 1
Create Grid Any square in the grid can contain a white
space, a black space, player 1’s piece or player 2’s piece.
1 Introduction A white space is a space that can never have a piece in
it, a black space however can have a piece on it.
This rules for draughts used in this project are those listed
on the English Draughts Wikipedia[1]. These rules must for i = 0 to height do
be implement as such that a user can play a game without for j = 0 to width do
breaking these rules and will win or lose the game when if (i is even and j is odd) or (i is odd and j is even)
win conditions have been met. An artificial intelligence then
should also be able to play this game against a human square[i][j] contains white space
obeying all of the rules. At any point in the game the user end
should be able to undo back to the start of the game. If the else if i < rows then
user has undone anything provided they haven’t changed square[i][j] contains player 2’s piece
anything since they should be able to redo back to where else if i >= height - rows then
they were before they started undoing. Previous games square[i][j] contains player 1’s piece
should also be able to be replayed. else
square[i][j] contains black space
end
end
2 Design
end
Algorithm 1: FizzBuzz
2.1 Grid
Squares To create the board a class was created called Squares are stored in the list at squares[i][j] with i being
grid which would take a width and height and create the the height of the grid at it’s position and j being the width
equivalent of a 2D array. It is standard in Draughts to of the grid at it’s position.
have an 8x8 board of pieces, however as python does
not have 2D arrays (which would need to have their size Viewing Grid A grid stored like this is really simple to
defined at the start) the board squares where created as view in console, just having a nested loop though the
a list of lists meaning the board width and height could be height and then width will print out what the squares con-
set at any size. tain.
To make the grid more user friendly the width numbers
Listing 1: Creating 2D array equivelant in Python are turned into letters using ASCII values (which puts an-
1 other restriction on the grid width as if it exceeds 26 non
2 class Grid:
3 def __init__(self, width, height): letter ASCII characters will start printing) and these are
4 self.squares = [] printed below and above the grid. 1 is added to the height
5 for i in range(height):
6 self.squares.append([])
numbers and they are printed to the left and right of the
grid with a tab for separation (This puts restrictions on the
height of the grid as if the height number exceeds the tab
Restrictions do need to be put on the width and height
it will skew the grid).
sizes to keep the game fair and readable, for example
1
For this project player 1’s pieces are shown with the letter
"w" player 2’s pieces are shown with the letter "b" and
both black and white spaces are shown with a space. See
Figure 1.
Figure 2: Different Pieces- Kings are capital letters of
the regular pieces
"forwards" - Towards the other players starting side mov-
ing diagonally.
Figure 1: Board - This is how the grid ended up looking "forwards and backwards" - If a piece makes it to the edge
by default of the opposite side of the board to where it starts it be-
comes a king, kings are allowed to move one space in all
diagonal direction.
2.2 Pieces
Piece Class Each piece in this project needs to know "jumping" - If there is an opponents piece one space
where it currently is, weather or not it has been taken, and away diagonally from the player’s piece in a way that it
weather or not it is a king.In order to help with the undoing can move it may jump over this piece if the next diagonal
and redoing it also knows every time it has moved. piece is empty. The piece may continue to do this from
the space it has jumped to until there are no more valid
Data Structures A piece’s current position is stored in spaces it can jump to. When a piece is jumped over it is
a tuple (i, j), with i being the height of the square and j "taken" and is removed from the board.
being the width, so this can be easily transferred into grid
square positions. 2.4 User Movement
Whether or not a piece is taken is stored as an int, this To take movement from a human user, the program must
is to help with undoing. When a piece is taken this is set first check if any pieces can jump. If a piece can jump
to the turn it was taken on so when undoing the piece another piece it must so the program most first check if
knows it needs to re-appear on the board on this turn. As the user must do this and if they must force them to. Then
it is impossible to take a piece on turn 0 this can be set to input must be taken from the user of the coordinates of
0 when the piece has not been taken. piece they would like to move and it should be converted
into a form that can be used by the program. If the user is
Whether or not a piece is a king is used in much the same allowed to can move this piece the program should then
way as a piece being taken, it is impossible for there to be take in the coordinated of the square the piece should be
a king on turn 0 so it is that by default and changes to the moved to and convert this into the form the program is
current turn when it becomes a king. using.
Every time a piece moves it stores the (i, j) tuple of coordi-
nates that it moved to in a dictionary with the key being the Normal Movement If a user is simply moving one of it’s
turn it made this move. Using this data structure means pieces forward moving this piece is simple. First in or-
pieces only have to remember a turn if they moved on it der to check if the coordinates given to move to are valid,
and as keys are unique they can’t somehow have more when a piece is given the program should look for all the
than one move per turn. valid places it can move (it will check for empty squares
in front of it diagonally and if it’s a king it will also check
Viewing Pieces Pieces are viewed by overriding the to behind it). All the valid spaces it can move to are added
string method in the class to return the symbol for either to a set and then the program simply needs to check if
the default piece or the king of that piece if it’s a king. See the given coordinates to move to are in that set. A set
Figure 2. should be used rather than a list because all valid spaces
to move to should be unique and sets don’t have any du-
plicates and also because set’s are quicker to search than
2.3 Movement
doing a linear search through a list.
There are 3 ways a piece can move in draughts;
To complete the move the program simply swaps the
2
piece from it’s current square to the given square, sets References
the pieces current coordinates to the new coordinates,
adds this move to the pieces list of moves and checks if
the piece has reached the other side. If the piece has [1] Wikipedia, “English draughts.” https://en.m.
reached the other side and it is not already king it sets it’s wikipedia.org/wiki/English_draughts#Rules.
turn kinged variable to the current turn. [2] TicTacTo, “Minimax.” http://neverstopbuilding.
com/minimax.
Jumps If a user can jump they must jump, so when
checking if the current players pieces can jump any other
pieces all the pieces that can jump added to a set (again
because they will all be unique and sets are quick to
search through). If this set contains items a jump has
been forced so this time to find the valid places for the
given piece the program looks for all the places this piece
can jump to and adds any spaces it can jump to in multi-
ple ways to a set.
To complete this move is more complicated than a nor-
mal move as the route the user wants to take isn’t al-
ways clear. If the space the user has given to move to
is only 2 spaces away and there is an opponents piece
in-between it and there it simply needs to jump over that
piece, add the same information to the piece as with a
normal move and also tell the piece in-between that it’s
been taken that turn and remove it from the board. The
program then needs to check if any more jumps can hap-
pen and if they can it takes user input again and repeats
this until no more can happen.
If the user inputs a space further than 2 spaces away or
the opponents piece is not in-between then the program
works out what pieces it would have to jump to get there
unless any pieces are in the set made earlier of spaces
with multiple ways to get to in which case the program
can’t work it out and asks the user to input one jump at a
time.
3 Memory
A memory class is used to store all pieces moved on a
turn and the turn you can redo up to. When undo is called
the memory class checks the take turns, movements, and
turns kinged of all pieces in that turn of it’s list and resets
them to before that happened. Redo works doing the op-
posite.
4 AI
The AI is implemented using a minimax algorithm which
can look to any depth but is by default at a depth of 5.
If this algorithms max/min returns multiple of the same
score it will choose a random one of these moves.
4.1 Take Tree
The AI uses an n-ary tree to store the possible routes
it can take to take the opponents pieces. The take tree
is stored in the same file as the Memory class as both
are very short classes so having a file each is a waste of
space.[2])
