Let’s create a Chess AI

Ansh Gaikwad
Oct 14, 2020 · 12 min read

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?

Today’s Outline

  1. Board Evaluation
  2. Move Selection
  3. Testing our AI
  4. Making an Interface

Board Representation

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.

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

  • Some of the points which should come in our mind are:
  1. Avoid exchanging one minor piece for three pawns.
  2. Always have the bishop in pairs.
  3. Avoid exchanging two minor pieces for a rook and a pawn.
  • So, the equations from the above insights will be:
  1. Bishop > 3 Pawns & Knight > 3 Pawns
  2. Bishop > Knight
  3. Bishop + Knight > Rook + Pawn

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.

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:

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:

Flowchart for the evaluation function

Move Selection

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:

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.

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:

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.

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:

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.

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:

Flowchart for the quiesce function

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

Testing our AI

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

  1. AI Vs Human
  2. Self Play (i.e AI vs AI)
  3. AI Vs Stockfish (You can get info about stockfish12 here)

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

AI Vs Human

# 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
Output-2

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

Self-Play

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))
Output-3

AI Vs Stockfish

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))
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

# 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()
Final Output

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

Conclusion

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