Kool AI Chess - A command line Chess program using Python - Player vs Computer
For my Code Institute Portfolio Project 3,
I would like to implement a Chess Program in Python
in order to play Chess against a Computer opponent.
In my search for a suitable algorithm I came across this 476-line BASIC PROGRAM by DEAN MENEZES
Let me reiterate: the basis of my project is a Chess Program written in
BASIC (Beginners' All-purpose Symbolic Instruction Code) which is available here.
I found it amazing how Denezes has written such a highly interesting chess playing program in under 500 lines.
My goal then is to convert Denezes' BASIC program to Python; moreover, to add castling and en passant chess moves so that the user can play a complete game of Chess against their Computer opponent, namely, Kool AI.
To quote Boardgamegeek
Chess is a two-player, abstract strategy board game that represents medieval warfare on an 8x8 board with alternating light and dark squares. Opposing pieces, traditionally designated White and Black, are initially lined up on either side. Each type of piece has a unique form of movement and capturing occurs when a piece, via its movement, occupies the square of an opposing piece. Players take turns moving one of their pieces in an attempt to capture, attack, defend, or develop their positions.
Chess games can end in checkmate, resignation, or one of several types of draws.
Chess is one of the most popular games in the world, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.
To quote Wikipedia
Chess is an abstract strategy game that involves no hidden information and no elements of chance. It is played on a chessboard with 64 squares arranged in an eight-by-eight grid.
At the start, each player controls sixteen pieces:
one king, one queen, two rooks, two bishops, two knights, and eight pawns.
White moves first, followed by Black. The game is won by checkmating the opponent's king,
i.e. threatening it with inescapable capture.
There are also several ways a game can end in a draw.
For the rules and further information on the game of Chess please refer to the following Wikipedia articles:
Thank You.
- As a user I want to be able to enjoy a game of Chess against a Computer opponent.
- As a user I want to know whether I have entered a correct Chess move. Moreover, if I have not,
then an explanation of why a move is incorrect ought to be displayed, if possible. - As a user, I want to know whether I have placed the Computer in Check.
- As a user, I want to know whether I have placed the Computer in Checkmate. That is, have I won?
- As a user, I want to know whether I am in Check.
- As a user, I want to know whether the Computer has placed me in Checkmate. That is, have I lost?
- As a user, I want the option to Resign when realising that I cannot beat my opponent or I no longer want to continue the game.
In the context of this game the user is referred to as The Player. So I will describe the user in this manner in the following sections.
The Player goes first and is prompted to do so.
The Player is designated White however seeing that this is a monochrome console game,
the Player's pieces are depicted as lowercase letters at the bottom of the board.
Kool AI, the Computer opponent will go second. The Computer is designated Black.
The Computer's pieces are depicted as uppercase letters at the top of the board.
From this point onwards each, that is, the Player and the Computer, will play their corresponding moves until one of the following scenarios:
- The Player beats Kool AI ! That is, Checkmate! The Player has Won!
- Kool AI recognises it cannot win therefore it resigns. The Player has Won!
- Kool AI beats the Player and informs the Player that the Player is in Checkmate. Kool AI has Won!
- The Player resigns because of one of the following reasons:
-
- The Player can foresee that Checkmate is inevitable.
-
- The Player realises that the game is Stalemate.
(Stalemate is a situation in Chess where the player whose turn it is to move is not in Check and has no legal move.)
- The Player realises that the game is Stalemate.
-
- The Player realises that the game is a Draw.
-
- Or the Player chooses to no longer continue the game.
The chessboard has the following coordinates:
The chessboard at the beginning of the game is shown as:
Therefore, the form of how one enters a Chess move is of the form <FromSquare><ToSquare> e.g. d2d4
That is, pawn (p) from square d2 to square d4.
Another example, would be g1f3
That is, knight (n) from square g1 to square f3.
If the Player enters a move in UPPERCASE, the input algorithm will lowercase the input in order to process the move.
For matching a Castling move, either O-O or O-O-O, the input algorithm will UPPERCASE the input in order to test for Castling.
From the outset a prompt (e.g. e2e4) is displayed reminding the Player of the format of a Chess move.
Please Note: A description of both the Player's and Computer's moves is always shown.
The descriptions will be in these formats:
Player moves g1-f3 Piece: Pawn
Computer moves g7-g6 Piece: Pawn
Therefore, the description will always show:
- Who played
- The From Square
- The To Square
- The Piece Played
Each piece has a letter. Starting from the top of the board:
- R for Rook
- N for Knight
- B for Bishop
- Q for Queen
- K for King
- P for Pawn
The Computer's pieces (Black) are depicted as uppercase, capital letters - R, N, B, Q, K, P
The Player's pieces (White) are depicted as lowercase letters - r, n, b, q, k, p
The program will prompt the Player then await the Player's input
The Player's input needs to be a four-character string which uses files-first Chess Algebraic notation
For example, to move one's pawn from square e2 to e4, enter e2e4
The program will then respond with a message such as
Checking Player move for e2-e4 Piece: Pawn
Since the Player has moved the pawn from square e2 to e4 and the move is valid, the program will display the following board:
Kool AI will inform the Player that it is Thinking - That is, it is evaluating its next move:
Please note: sometimes Kool AI takes over 20 seconds to respond! Please Be Patient :)
Subsequently, Kool AI has responded with e7e6
That is, Pawn from square E7 to E6
Please Note: A description of both the Player's and Computer's moves is always shown.
The Player's input will always be validated. Here are some examples:
- When it cannot understand the input - that is, it does not fit the Chess move format
In this scenario, the Player entered the word, hello
- A null entry
- Trying to play a Blank Square
- Trying to play an opponent's piece
- Trying to play an illegal move for a piece
This is the general catchall response. Kool AI's algorithm will examine the Player's move against all the possible moves for the chosen piece. If the Player's move does not appear in the list of all possible moves it will display an Illegal Move message. In such a scenario it would be up to the Player to determine why such a move cannot be played. For example:
In this case, a rook cannot pass through pieces. It is blocked by a pawn.
Here is an example of Check:
Here are a couple of examples of illegal moves whilst in Check
That is, the king cannot move towards an attacking piece whilst being attacked!
A king however, can take an attacking piece if the king is in a position to do so.
The only legal moves when in Check is to protect your king, whether by
- Taking the attacking piece
- Moving a piece to block the attacking piece
- Or moving the king out of its position where it is currently under attack
So, in this example, the Knight move does none of the above, therefore, it is an illegal move!
When Checkmate occurs, this signifies a win.
The game is won by checkmating the opponent's king, i.e. threatening it with inescapable capture.
The program will print a message declaring the victor and all the moves played are output to the screen.
(They are also outputted to output.pgn for testing purposes only! See TESTING.md for details.)
The moves are outputted in Long algebraic notation (LAN).
(See Resignation
below for details)
Here is an example of Checkmate:
Kool AI first declares that the Player is in Check.
Seeing this is the case, Kool AI does a further test to see whether it is Checkmate?
In the above scenario, this is indeed the case. Therefore, Kool AI declares itself the Victor!
However, for reasons explained below, the Game will continue until the Player resigns!
By the way, the above chessboard Checkmate configuration, is known in the Chess world, as
Fool's Mate - Checkmate in two moves! 1. f2f3 e7e5 2. g2g4 Qd8h4# 0-1
The Computer Chess algorithm as designed by Dean Menezes is clever enough to make these moves and to Checkmate the opponent.
Here is an example of Resignation:
Resignation in Chess is the player conceding the game to their opponent, that is, to acknowledge defeat.
Resignation immediately ends the game.
To resign, the Player has to enter either R or r to resign.
Please note however:
- Kool AI's algorithm will score each of its own potential moves before its play and if the score is too low, Kool AI will resign.
That is, if the score is below the constant STALEMATE_THRESHOLD_SCORE which is equal to -2500;
Kool AI will deem that it cannot possibly win the game; therefore, Kool AI will resign! - Unfortunately, the program is not smart enough to determine whether a game is Stalemate or a Draw;
so it relies on the human user to end the game by entering 'r' to resign. - I am a novice chess player. So in writing this program, there is the possibility that my program may declare Checkmate against the human opponent when in fact, it is not! (Although personally, throughout my testing I have not come across such a scenario!)
Therefore, in regards to this: even after Kool AI declares Checkmate, I leave it up to the Player to resign.
That is, this program does not force the end of the game - the Player can play on!
When either the Player or Kool AI resigns or if Kool AI checkmates its opponent; all the moves played are output to the screen.
(They are also outputted to output.pgn for testing purposes only! See TESTING.md for details.)
The moves are outputted in Long algebraic notation (LAN).
To quote Wikipedia,
In long algebraic notation (LAN), also known as full/fully expanded algebraic notation,
both the starting and ending squares are specified,
for example: e2e4. Sometimes these are separated by a hyphen, e.g. Nb1-c3, while captures are indicated by an "x", e.g. Rd3xd7.
Long algebraic notation takes more space and is no longer commonly used in print; however, it has the advantage of clarity.
Therefore, this program produces the output of all moves in LAN without hyphens so that an user such as I,
can read the moves clearly without too much difficulty;
that is,
what moves were made from what square to which square, and what piece was moved.
The Player can then copy these moves from the console terminal for further study!
When it comes to Pawn Promotion, Kool AI solely promotes its Pawns to Queens.
The Player, however, has the option to promote a White Pawn to another piece besides Queen.
Here is an example of Pawn Promotion - The Player's pawn has reached c8:
The Player has the option to enter either r for Rook, b for Bishop, n for Knight or q for Queen.
Note: the default is Queen. So, the Player can just hit Enter!
When the Player enters their choice, the Pawn in question is promoted to the requested piece.
A message will be printed of the form: Pawn promoted to <whichever piece was chosen>.
For example:
In the above scenario, the result of the promotion of the Player's Pawn to Queen resulted in a win for the Player!
Here is the full response:
The Computer Chess algorithm as designed by Dean Menezes uses what is known as negamax to determine its next move.
To quote Rod Bird as he describes the evaluate function:
This function checks all squares for players to move then recursively test plays.
It plays its own move then plays the opponent's best move, recursively over four moves.
So getting the potential net worth of each moveable player on the board.
The highest scored determines the computer's next move.
It is a classic mini max evaluation shortened to its a negamax form with pruning
i.e. it does not waste time on lower value plays.
I will not pretend that I understand the mathematics involved. I can only verify that it indeed works!
Nonetheless, for more information please see the following Wikipedia articles: minimax and negamax.
- When it comes to Pawn Promotion, Kool AI solely promotes its Pawns to Queens.
Nonetheless, the Player is given the option to promote a White Pawn to another piece besides Queen. - The program is not smart enough to determine whether a game is Stalemate or a Draw;
so it relies on the Player to end the game by entering 'r' to resign.
Kool AI will designate such an ending as a Draw i.e. 1/2-1/2. - Unfortunately, this program is slow. Sometimes, it takes over 20 seconds for Kool AI to respond with its move!
- To speed up this process, the constant MAXLEVEL which is currently equal to 5, can be lowered to 4 or 3.
This will indeed quicken the Computer's response, however, it will play a dumber game!
- Attempt to speed up the program by using a library such as itertools
- The ability to switch sides
- Undo/Redo ability when playing moves
- Saving board positions during the game
- Loading of saved positions
- Explore further the possibilities of Chess-Playing Automation using the existing functionality
- Loading and playing of PGN chess files
- A Colour Chessboard using a library such as Colorama
- Better Graphics for the Chess Pieces and the Chessboard
The Chessboard and Pieces as designed by Dean Menezes had the following values:
-500,"R",-270,"N",-300,"B",-900,"Q",-7500,"K",-300,"B",-270,"N",-500,"R"
-100,"P",-100,"P",-100,"P",-100,"P",-100,"P",-100,"P",-100,"P",-100,"P"
0," ",0," ",0," ",0," ",0," ",0," ",0," ",0," "
0," ",0," ",0," ",0," ",0," ",0," ",0," ",0," "
0," ",0," ",0," ",0," ",0," ",0," ",0," ",0," "
0," ",0," ",0," ",0," ",0," ",0," ",0," ",0," "
100,"P",100,"P",100,"P",100,"P",100,"P",100,"P",100,"P",100,"P"
500,"R",270,"N",300,"B",900,"Q",5000,"K",300,"B",270,"N",500,"R"
- Black Pieces at the top have negative values
- Each piece has a value followed by its letter
- Zero and Space show the empty squares
- Then the White Pieces are at the bottom with corresponding positive values
I chose not to use a 8X8 array with numerical indices for the following reason.
In the Chess World, this is how a chessboard is depicted:
The chessboard consists of eight files and eight ranks.
Columns are known as files and are labelled left to right with letters, a to h.
Rows are known as ranks and are numbered from the bottom of the board upwards, 1 to 8.
Therefore, rather than a 8X8 array with numerical indices; instead I chose to use a Python dictionary to reflect the above scheme.
The keys being a string e.g. "h8" for the square h8
Then each value would be a Piece Class instance of the form Piece(VALUE, LETTER, SIGN)
Therefore the Dictionary would look like this:
{a8:value, b8:value, ..., d1:None, ..., e1:None, a1:value, ..., h1:value}
Blank squares have the value None
Thereby if a variable for example board represents the chessboard, each square can be accessed using a string key.
For example to refer to square "h3" I can use the code
square = board["h3"]
In order to incorporate Object Oriented programming I have used three classes in this program.
- Piece
- Game
- CustomException(Exception)
This Class is the Base Class for all the Chess Pieces.
As a basis I adopted the way that X.S. had implemented the Piece Class in this code
In my version the rationale is as follows:
Attributes:
-----------
piece : string
Each piece is depicted by a letter which represents
the name of a piece as following :-
Pawn -> P
Rook -> R
Knight -> N
Bishop -> B
Queen -> Q
King -> K
sign (represents the colour) : it is depicted by a number
1 if the piece belongs to the Player i.e. white
-1 if the piece belongs to the Computer i.e. black
Each piece has
-
self.sign: -1 for the Computer (Black Pieces); 1 for the Player (White Pieces)
-
self.letter: P R N B Q K
-
self.value:
-
- Player:
-
- Pawn's value is 100
-
- Rook's value is 500
-
- Knight's value is 270
-
- Bishop's value is 300
-
- Queen's value is 900
-
- Note: The Player's King value is 5000 and the Computer's King value is -7500
-
- The Computer's values of each of the above is the negative equivalent i.e. -100, -500, -270, -300, -900
-
- The Kings' values differ as shown above
-
Note: Blank squares have a value and a sign of ZERO
-
piece_string(self): This method returns a string description of each piece to describe which piece had been taken in a Chess move.
-
- "Pawn"
-
- "Rook"
-
- "Knight"
-
- "Bishop"
-
- "Queen"
-
- Note: King piece cannot be taken - So no 'piece_string'
-
promote(self): This method handles Pawn Promotion.
When a Pawn is promoted, two new attributes are added to the Pawn object. -
- self.promoted_letter: the letter of the piece that the Pawn was promoted to.
-
- self.promoted_value: the corresponding value of the piece that the Pawn was promoted to.
This class represents the status of the Chess Game. It is the main workspace of the program containing all the global flags, properties and variables related to the state of play of the Game.
So instead of global variables I use Class Variables belonging to this Class to hold important values.
I have tested my program to the best of my ability however I am a novice Chess Player.
So just in case this program does some absurd illegal move such as trying to take a king or capturing a piece of its own colour;
I have added a Try-Except method to catch a Custom Exception which will be generated if some strange chess move occurs.
Hopefully this will never happen! :)
In order to avoid the usage of magic numbers I created this file to hold all the constants needed for this program. So if this program needs to be amended, this would be the main place to look at for making adjustments of major values.
The exception is that the function showboard in run.py uses numbers and strings specific to usage on the ANSI terminal used for this project. So I suggest an entire new function will need to be written if displaying the chessboard on a different display media.
This program was originally one file - run.py
As this project began to grow I realised that run.py was getting unwieldy
Therefore, I split it up into different modules:
- constants.py - Holds all the major constants used in this program
- extras.py - I moved the routines that manage how piece moves are generated - Pawn/Rook/Knight/Bishop/Queen/King - into this module
Also any routines that caused import circular issues with the Python interpreter are placed in extras.py - fileio.py - This program can essentially perform Chess-Playing Automation by playing chess moves read from the input.pgn file
All routines related to this process are placed in fileio.py
(see TESTING.md for more details) - game.py - The Game Class and its related routines
- moves.py - The functionality for the chess moves: Castling and En Passant
- piece.py - The Piece Class and its related routines
- run.py - the main module of the program
- Passed the code through the PEP8 linter and confirmed there are no problems.
- Carried out tests of the program on both the local terminal and the Code Institute Heroku terminal.
- Added functionality so that this program could read Chess moves from a PGN file, namely, input.pgn.
My rationale is that if my program can play recorded chess games identically then the chess-playing algorithm works correctly.
See TESTING.md for further details.
At the top level of the program I have added the following try-except :-
def main():
try:
main_part2()
except CustomException as error:
print(error)
handle_internal_error()
quit()
except Exception as error:
raise error
That way, if there is some logic error that I have not anticipated or some internal error occurs;
it would be caught here and a suitable message would be printed.
The message will be of the form:
Internal Error: <The Error Message>
Computer resigns due to an internal error
Please investigate
Thank You For Playing
Goodbye
Initially when I defined my 'Game' class I thought I could call the following 'initialise_class_variables' function to initialise all the relevant Class Variables
class Game:
"""
"""
def initialise_class_variables():
print("Initialise")
# the number of valid moves found for chosen piece
num_moves = -1
...
However when I tried to access a Class Variable defined that way I got
print(Game.num_moves)
^^^^^^^^^^^^^^
AttributeError: type object 'Game' has no attribute 'num_moves'
I know the error has something to do with scoping, however to resolve this issue, I removed the function 'initialise_class_variables' and defined all my Class Variables directly beneath the 'Game' Class definition.
class Game:
player_first_move = True
...
...
Kool AI determines its next move by calling the evaluate function recursively over four moves.
The highest scored move is Kool AI's next move.
The evaluation process involves moving the chess pieces then scoring the resultant chessboard configuration.
Therefore, before calling evaluate a copy of the original pieces are saved in order to be restored after the function call is completed.
As shown:
# store From and To data so that it may be restored
save_from_square = chess.board[from_square]
save_to_square = chess.board[to_square]
If during evaluation, a piece happens to be a Black Pawn that is moved to rank 8 this will result in a promotion of the Pawn to a Queen in accordance with the rules of Chess and Kool AI's handling of its own Pawns.
However, when the evaluate function call was returned, any Pawns that happened to be promoted to Queens were remaining Queens!
Pawns-to-Queens ought to have been restored back to Pawns!
See for example:
There are two Black Queens - two capital Qs - when there should only be one!
Despite the fact, that I was restoring the original pieces as shown in this code:
# Restore previous squares
chess.board[from_square] = save_from_square
chess.board[to_square] = save_to_square
Nonetheless, two Black Queens - capital Qs appeared!
Therefore, I concluded that I needed to make a deep copy of chess.board[from_square] and chess.board[to_square] to be used to restore their contents when the function evaluate returned.
I used copy.deepcopy from the copy library.
Unfortunately, my program is not fast as it stands, and deepcopy appeared to be taking a very long time - so using this option was not viable.
I therefore chose to use a List of Sets to act as a Stack that grows and shrinks with the calls of evaluate. That is, at each function call level, an empty Set is added to the undo_stack.
Game.undo_stack.append(set())
If any Pawn Promotion happens, the coordinates of the square in question is added to the current set at the top of the Stack.
Game.undo_stack[-1].add(to_square)
When the function call is over, the following two operations take place.
- If the current set at the top of the Stack is not empty; then each coordinate in the Set has their Pawn Promotion attributes removed; which in effect, undoes the Pawn Promotion of each Pawn in question.
if not Game.undo_stack[-1]:
return
undo_set = Game.undo_stack[-1]
for index in undo_set:
# Remove the Pawn Promotion attributes
# i.e. Undo them!
del chess.board[index].promoted_value
del chess.board[index].promoted_letter
# empty the set
Game.undo_stack[-1].clear()
- The current set is popped of from the top of the Stack.
# Regardless of whether the current set was empty or not
# Pop the stack
Game.undo_stack.pop()
The project is deployed on Heroku. These are the steps in order to deploy on Heroku:
-
Regarding your project:
- create a Procfile with the following one line entry
web: node index.js -
Then ensure that you have pushed your latest version including Procfile to GitHub
-
Create a Heroku account. You will need to enter
- first name
- last name
- email address,
- role e.g. student
- location
- primary development language i.e. Python
-
Click Create free account
-
Proceed with confirmation via email
-
Log into Heroku
-
Create a new application by clicking the Create New App button.
You will need to enter
- The App name
- The region
- Then click the Create app button
-
Go into settings -> Config Var and add the following:
- key by the name of PORT with the value of 8000.
-
The next step is to add a couple of buildpacks to your application.
Then click the Add buildpack button -
Include the following buildpacks:
- The first buildpack is heroku/python - then click "Save changes"
- The second buildpack is heroku/nodejs - then click "Save changes"
- Please note: the order is significant - the Python buildpack must appear on top before the NodeJs buildpack.
One can use the mouse to drag the buildpacks into the correct order
-
Then click the Deploy option. This is where you choose the deployment method of GitHub
-
Find the repo with the project you want to deploy
-
Confirm that you want to connect to GitHub by clicking the Connect button
-
Scroll down to the two options, Automatic deploys - Manual deploy
-
In this section, you can click Enable Automatic deploys - Heroku will rebuild your app every time you push a new change
to your code to GitHub -
Or you can choose to manually deploy using the Deploy Branch option here
-
Pick which branch you want to deploy -- Generally this would be main
-
Click Deploy Branch and wait until the project is built
-
Ensure there are no errors. Heroku will display the message Your app was successfully deployed
-
Click the View button and you will be taken to an URL of the form https://<project-name>.herokuapp.com/
This is your deployed app in operation
- Python3
- os - I use this library for the clear function in order to clear the console before displaying an updated chessboard.
- re - I use regular expressions in order to validate user input of chess moves.
- time - I use the sleep function to cause the program to delay for a few seconds, in order so that the user can see the updated chessboard.
- GitHub - for hosting the site
- Gitpod - for editing the files
- Heroku - for the deployment of the site
- Code Institute's GitHub full template - in order to run Python on Heroku
- Background image photo by Chris Burns on Unsplash
- I would like to credit asiask97's CLI Battleship game which shows how to present a Python program against a background image
- Thanks to Code Institute for the template by which a terminal could be created; in order that my game could be displayed on a webpage.
- Thanks to Code Institute for the CI Python Linter which ensures that Python code complies with PEP 8
- Boardgamegeek for the explanation of the game of Chess
- Wikipedia for the explanation of the game of Chess
- The depiction of the chessboard with letters and numbers is from Naming Ranks and Files in Chess
- Flowchart Fun was used to create the flowchart for the Logic Flow of the Program
- Miro was used to create the flowchart for the Evaluation Algorithm
- I would like to thank my mentor Derek McAuley for his advice and guidance.
- I would like to acknowledge Dean Menezes, the author of the BASIC program on which my project is based on.
- I would like to acknowledge Rod Bird who also adopted Menezes' code.
I preferred and adopted Bird's display of the Chessboard. - I would like to acknowledge the Pythoneer X.S.
- X.S.'s article How to Code a Simple Chess Game in Python
- X.S.'s Pythonic style of coding can be seen in the following Chess Program.
- I would like to acknowledge Steven J. Edwards who designed Portable Game Notation in order to record chess games