Let’s create a Chess AI

Ansh Gaikwad
Oct 14 · 12 min read
Image for post
Image for post

Chess has been played by the world’s masterminds for ages and is the game where the brain needs a lot of processing. So, how can we teach a computer to play a mastermind game like chess? Let’s check it out.

To get started all you need is a python3 interpreter installed in your system and the basic level of python3. Cool right?

Image for post
Image for post

Today’s Outline

Board Representation

Image for post
Image for post

Before writing any algorithm for our engine it’s important for us to code the logic behind chess pieces i.e. assign every possible legal move to each and every chess piece.

For that, our work has been made a lot simpler by the python-chess library which will provide us with all of the move generation and validation. So, let’s start by installing it.

!pip install python-chess

Now, as we have the library installed, we can start by importing and then initializing the board.

import chess
board = chess.Board()
board

This will be the output which you will be able to see in your notebook.

Image for post
Image for post
Output-1

This board object will be the complete board representation which will provide us with some important functions such as board.is_checkmate() to check if there’s a checkmate, board.push() to append a move, board.pop() to undo the last move, etc. You can read the complete documentation here.

Board Evaluation

For evaluating the board initially, we must think about how a Grandmaster would think in his respective match.

Image for post
Image for post

By simplifying the above equations, we get Bishop > Knight > 3 Pawns. Also, we must convert the third equation as Bishop + Knight = Rook + 1.5 Pawn as two minor pieces are worth a rook and two pawns.

Image for post
Image for post

We will use piece square tables to evaluate our board pieces and the values will be set in an 8x8 matrix such as in chess such that it must have a higher value at favorable positions and a lower value at a non-favorable place.

For example, the probability of the white’s king crossing the centerline will be less than 20% and therefore we will place negative values in that matrix.

Let’s take another example, suppose the Queen, she would like her to be placed at the center position as she can dominate more number of positions from the center and therefore we will set higher values at the center and the same for the other pieces as chess is all about defending the king and dominating the center.

Enough of the theory lets initialize the piece square tables:

pawntable = [
0, 0, 0, 0, 0, 0, 0, 0,
5, 10, 10, -20, -20, 10, 10, 5,
5, -5, -10, 0, 0, -10, -5, 5,
0, 0, 0, 20, 20, 0, 0, 0,
5, 5, 10, 25, 25, 10, 5, 5,
10, 10, 20, 30, 30, 20, 10, 10,
50, 50, 50, 50, 50, 50, 50, 50,
0, 0, 0, 0, 0, 0, 0, 0]

knightstable = [
-50, -40, -30, -30, -30, -30, -40, -50,
-40, -20, 0, 5, 5, 0, -20, -40,
-30, 5, 10, 15, 15, 10, 5, -30,
-30, 0, 15, 20, 20, 15, 0, -30,
-30, 5, 15, 20, 20, 15, 5, -30,
-30, 0, 10, 15, 15, 10, 0, -30,
-40, -20, 0, 0, 0, 0, -20, -40,
-50, -40, -30, -30, -30, -30, -40, -50]
bishopstable = [
-20, -10, -10, -10, -10, -10, -10, -20,
-10, 5, 0, 0, 0, 0, 5, -10,
-10, 10, 10, 10, 10, 10, 10, -10,
-10, 0, 10, 10, 10, 10, 0, -10,
-10, 5, 5, 10, 10, 5, 5, -10,
-10, 0, 5, 10, 10, 5, 0, -10,
-10, 0, 0, 0, 0, 0, 0, -10,
-20, -10, -10, -10, -10, -10, -10, -20]
rookstable = [
0, 0, 0, 5, 5, 0, 0, 0,
-5, 0, 0, 0, 0, 0, 0, -5,
-5, 0, 0, 0, 0, 0, 0, -5,
-5, 0, 0, 0, 0, 0, 0, -5,
-5, 0, 0, 0, 0, 0, 0, -5,
-5, 0, 0, 0, 0, 0, 0, -5,
5, 10, 10, 10, 10, 10, 10, 5,
0, 0, 0, 0, 0, 0, 0, 0]
queenstable = [
-20, -10, -10, -5, -5, -10, -10, -20,
-10, 0, 0, 0, 0, 0, 0, -10,
-10, 5, 5, 5, 5, 5, 0, -10,
0, 0, 5, 5, 5, 5, 0, -5,
-5, 0, 5, 5, 5, 5, 0, -5,
-10, 0, 5, 5, 5, 5, 0, -10,
-10, 0, 0, 0, 0, 0, 0, -10,
-20, -10, -10, -5, -5, -10, -10, -20]
kingstable = [
20, 30, 10, 0, 0, 10, 30, 20,
20, 20, 0, 0, 0, 0, 20, 20,
-10, -20, -20, -20, -20, -20, -20, -10,
-20, -30, -30, -40, -40, -30, -30, -20,
-30, -40, -40, -50, -50, -40, -40, -30,
-30, -40, -40, -50, -50, -40, -40, -30,
-30, -40, -40, -50, -50, -40, -40, -30,
-30, -40, -40, -50, -50, -40, -40, -30]

Now let’s get our evaluation function by following these four methods:

Image for post
Image for post

Firstly, let’s check if the game is still going on.

Now the logic behind coding this stage is that If it returns true at checkmate then it will check whose turn to make a move, if the current turn is of WHITE it must return -9999 i.e previous turn must be of BLACK, and BLACK wins or else it must return +9999 and then White wins. For stalemate or any insufficient material, let’s return 0 as its draw.

So, let’s code:

if board.is_checkmate():
if board.turn:
return -9999
else:
return 9999
if board.is_stalemate():
return 0
if board.is_insufficient_material():
return 0

Secondly, we must calculate the total number of pieces so that we can pass it into our material function.

wp = len(board.pieces(chess.PAWN, chess.WHITE))
bp = len(board.pieces(chess.PAWN, chess.BLACK))
wn = len(board.pieces(chess.KNIGHT, chess.WHITE))
bn = len(board.pieces(chess.KNIGHT, chess.BLACK))
wb = len(board.pieces(chess.BISHOP, chess.WHITE))
bb = len(board.pieces(chess.BISHOP, chess.BLACK))
wr = len(board.pieces(chess.ROOK, chess.WHITE))
br = len(board.pieces(chess.ROOK, chess.BLACK))
wq = len(board.pieces(chess.QUEEN, chess.WHITE))
bq = len(board.pieces(chess.QUEEN, chess.BLACK))

Third, let’s calculate the scores.

The material score is calculated by the summation of all respective piece’s weights multiplied by the difference between the number of that respective piece between white and black.

The individual pieces score is the sum of piece-square values of positions where the respective piece is present at that instance of the game.

material = 100 * (wp - bp) + 320 * (wn - bn) + 330 * (wb - bb) + 500 * (wr - br) + 900 * (wq - bq)pawnsq = sum([pawntable[i] for i in board.pieces(chess.PAWN, chess.WHITE)])
pawnsq = pawnsq + sum([-pawntable[chess.square_mirror(i)]
for i in board.pieces(chess.PAWN, chess.BLACK)])
knightsq = sum([knightstable[i] for i in board.pieces(chess.KNIGHT, chess.WHITE)])
knightsq = knightsq + sum([-knightstable[chess.square_mirror(i)]
for i in board.pieces(chess.KNIGHT, chess.BLACK)])
bishopsq = sum([bishopstable[i] for i in board.pieces(chess.BISHOP, chess.WHITE)])
bishopsq = bishopsq + sum([-bishopstable[chess.square_mirror(i)]
for i in board.pieces(chess.BISHOP, chess.BLACK)])
rooksq = sum([rookstable[i] for i in board.pieces(chess.ROOK, chess.WHITE)])
rooksq = rooksq + sum([-rookstable[chess.square_mirror(i)]
for i in board.pieces(chess.ROOK, chess.BLACK)])
queensq = sum([queenstable[i] for i in board.pieces(chess.QUEEN, chess.WHITE)])
queensq = queensq + sum([-queenstable[chess.square_mirror(i)]
for i in board.pieces(chess.QUEEN, chess.BLACK)])
kingsq = sum([kingstable[i] for i in board.pieces(chess.KING, chess.WHITE)])
kingsq = kingsq + sum([-kingstable[chess.square_mirror(i)]
for i in board.pieces(chess.KING, chess.BLACK)])

At last, let’s calculate the evaluation function which will return the summation of the material scores and the individual scores for white and when it comes for black, let’s negate it.

(As, favorable conditions for White = unfavorable conditions for Black)

eval = material + pawnsq + knightsq + bishopsq + rooksq + queensq + kingsqif board.turn:
return eval
else:
return -eval

Let's summarize our evaluation function right now, with the help of the flowchart given below:

Image for post
Image for post
Flowchart for the evaluation function

Move Selection

This will be the last step for our algorithm where we will use the Negamax Implementation of the Minimax Algorithm which is a mostly used algorithm for any two-player games such as checkers, snake, and ladders, etc. Then will later optimize it using Alpha-Beta pruning which will in turn reduce our execution time.

Image for post
Image for post

For the smartness of our engine, we can use the initial moves from a book in which moves will be stored with a lot of opening moves by chess Grandmasters in a bin format. You can download some of them from here.

import chess.polygot
try:
move = chess.polyglot.MemoryMappedReader("C:/Users/your_path/books/human.bin").weighted_choice(board).move
return move

Now, let’s dig into our minimax algorithm. It’s a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst-case scenario. In simple words, at each step, it assumes that player A is trying to maximize its chances of winning, and in the next turn player B is trying to minimize the chances of winning.

Check out the tree from below for a better understanding of the algorithm:

Image for post
Image for post
A minimax tree example from Wikipedia

But we will be using the negamax variant of minimax for better results as we will need only one function that is to maximize the utility of both the players. The difference is that here, one player loss is equal to another player’s gain and vice versa. In terms of the game, the value of the given position to the first player is the negation of the value to the second player.

You can differentiate the tree given below.

Image for post
Image for post
A negamax tree example

Initially, we will set alpha as negative infinity and beta is positive infinity so that, both players start with the worst possible score. So, let's code.

except:
bestMove = chess.Move.null()
bestValue = -99999
alpha = -100000
beta = 100000
for move in board.legal_moves:
board.push(move)
boardValue = -alphabeta(-beta, -alpha, depth - 1)
if boardValue > bestValue:
bestValue = boardValue
bestMove = move
if (boardValue > alpha):
alpha = boardValue
board.pop()
return bestMove

Okay, so let's understand what we did here with this flowchart:

Image for post
Image for post
Flowchart for the search function

Now, the next step is the alpha-beta pruning for the optimization of our execution speed.

Let’s not go deep in the algorithm but just understand that we are applying this logic just to eliminate most of the unnecessary iterations.

Image for post
Image for post
An illustration of alpha-beta pruning from Wikipedia

Let’s Code:

def alphabeta(alpha, beta, depthleft):
bestscore = -9999
if (depthleft == 0):
return quiesce(alpha, beta)
for move in board.legal_moves:
board.push(move)
score = -alphabeta(-beta, -alpha, depthleft - 1)
board.pop()
if (score >= beta):
return score
if (score > bestscore):
bestscore = score
if (score > alpha):
alpha = score
return bestscore

Now, let’s revise the alphabeta function with this flowchart given below:

Image for post
Image for post
Flowchart for the alphabeta function

Now comes the Quiescence search, the purpose of this search is to only evaluate “quiet” positions, i.e the positions where there are no winning tactical moves to be made.

This search is needed to avoid the horizon effect which is caused by the depth limitation of the search algorithm.

Image for post
Image for post
A Gif for illustrating the horizon effect

Let’s understand the horizon effect with the above-given gif like there’s a stage when our brain stops to respond when we are overthinking something and this same happens here and that’s why we apply the quiescence search.

Okay, let’s code:

def quiesce(alpha, beta):
stand_pat = evaluate_board()
if (stand_pat >= beta):
return beta
if (alpha < stand_pat):
alpha = stand_pat
for move in board.legal_moves:
if board.is_capture(move):
board.push(move)
score = -quiesce(-beta, -alpha)
board.pop()
if (score >= beta):
return beta
if (score > alpha):
alpha = score
return alpha

So let’s summarise the function in a bit:

Image for post
Image for post
Flowchart for the quiesce function

And now we are ready with our algorithm. Thanks for your patience guys.

Image for post
Image for post

Testing our AI

Before starting to code the testing part we will need to import some of the libraries so let’s get to it:

import chess.svg
import chess.pgn
import chess.engine
from IPython.display import SVG

Now, today we will be doing three tests today which will be

So, without wasting any further time let’s get started.

AI Vs Human

Image for post
Image for post
# use this for computer move
mov = selectmove(3)
board.push(mov)
board
# use this for human move, where e5 is the example move
board.push_san("e5")
board
Image for post
Image for post
Image for post
Image for post
Output-2

So, the AI chooses to go g1f3, which is a pretty smart move.

Self-Play

Let’s make our AI fight itself now:

Image for post
Image for post
count = 0
movehistory = []
game = chess.pgn.Game()
board = chess.Board()
while not board.is_game_over(claim_draw=True):
if board.turn:
count += 1
print(f'\n{count}]\n')
move = selectmove(3)
board.push(move)
print(board)
print()
else:
move = selectmove(3)
board.push(move)
print(board)
game.add_line(movehistory)
game.headers["Event"] = "Self Tournament 2020"
game.headers["Site"] = "Pune"
game.headers["Date"] = str(datetime.datetime.now().date())
game.headers["Round"] = 1
game.headers["White"] = "Ai"
game.headers["Black"] = "Ai"
game.headers["Result"] = str(board.result(claim_draw=True))
print(game)
SVG(chess.svg.board(board=board,size=400))
Image for post
Image for post
Output-3

AI Vs Stockfish

Now, let’s make our AI fight Stockfish. You can download the Stockfish engine from here.

Image for post
Image for post
count = 0
movehistory = []
game = chess.pgn.Game()
board = chess.Board()
engine = chess.engine.SimpleEngine.popen_uci("your_path/stockfish.exe")
while not board.is_game_over(claim_draw=True):
if board.turn:
count += 1
print(f'\n{count}]\n')
move = engine.play(board, chess.engine.Limit(time=0.1))
movehistory.append(move.move)
board.push(move.move)
print(board)
else:
move = selectmove(3)
movehistory.append(move)
board.push(move)
print(board)
game.add_line(movehistory)
game.headers["Result"] = str(board.result(claim_draw=True))
print(game)SVG(chess.svg.board(board=board, size=400))
Image for post
Image for post
Output-4

So, yes our AI is not smart enough to beat the stockfish 12 but still, he managed to keep the fight for 20 moves.

There are a lot more open-source UCI compatible chess engines available for more of the testing purposes, you can find them here.

Making an Interface

The above testing seems to be a lot of code. That’s why let’s code an interface, clean up our code, and then test our AI again.

# Remaining imports
import traceback
from flask import Flask, Response, request
import webbrowser
# Searching Ai's Move
def aimove():
move = selectmove(3)
board.push(move)
# Searching Stockfish's Move
def stockfish():
engine = chess.engine.SimpleEngine.popen_uci(
"your_path/stockfish.exe")
move = engine.play(board, chess.engine.Limit(time=0.1))
board.push(move.move)
app = Flask(__name__)# Front Page of the Flask Web Page
@app.route("/")
def main():
global count, board
ret = '<html><head>'
ret += '<style>input {font-size: 20px; } button { font-size: 20px; }</style>'
ret += '</head><body>'
ret += '<img width=510 height=510 src="/board.svg?%f"></img></br></br>' % time.time()
ret += '<form action="/game/" method="post"><button name="New Game" type="submit">New Game</button></form>'
ret += '<form action="/undo/" method="post"><button name="Undo" type="submit">Undo Last Move</button></form>'
ret += '<form action="/move/"><input type="submit" value="Make Human Move:"><input name="move" type="text"></input></form>'
ret += '<form action="/dev/" method="post"><button name="Comp Move" type="submit">Make Ai Move</button></form>'
ret += '<form action="/engine/" method="post"><button name="Stockfish Move" type="submit">Make Stockfish Move</button></form>'
return ret
# Display Board
@app.route("/board.svg/")
def board():
return Response(chess.svg.board(board=board, size=700), mimetype='image/svg+xml')
# Human Move
@app.route("/move/")
def move():
try:
move = request.args.get('move', default="")
board.push_san(move)
except Exception:
traceback.print_exc()
return main()
# Make Ai’s Move
@app.route("/dev/", methods=['POST'])
def dev():
try:
aimove()
except Exception:
traceback.print_exc()
return main()
# Make UCI Compatible engine's move
@app.route("/engine/", methods=['POST'])
def engine():
try:
stockfish()
except Exception:
traceback.print_exc()
return main()
# New Game
@app.route("/game/", methods=['POST'])
def game():
board.reset()
return main()
# Undo
@app.route("/undo/", methods=['POST'])
def undo():
try:
board.pop()
except Exception:
traceback.print_exc()
return main()

Now, let's execute it all in the next block.

board = chess.Board()
webbrowser.open("http://127.0.0.1:5000/")
app.run()
Image for post
Image for post
Final Output

Thanks for reading out patiently guys. We have successfully completed our Chess AI in about 12 minutes. Now, we can have fun.

Image for post
Image for post

Conclusion

I hope you guys understood most of the things we coded. If not, don’t hesitate to ask your questions in the comment box. As this was a basic implementation of creating a chess engine, I would like to hear what you guys think can make this Chess AI more smarter? Comment down below.

Also, for more information, you can visit here.

And all of the code can be found here.

Developer Student Clubs, Vishwakarma Institute of Technology, Pune

Helping students bridge the gap between theory and practice

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store