Open in app

Sign in

Write

Sign in

Let’s create a Chess AI

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 Representation
  2. Board Evaluation
  3. Move Selection
  4. Testing our AI
  5. 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

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

  • 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

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.

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

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

  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

Let’s make our AI fight itself now:

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

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

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

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

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.

Chess
Artificial Intelligence
Machine Learning
Python
Programming

--

--

Ansh Gaikwad
Google Developer Students Club Vishwakarma Institute of Technology, Pune

Written by Ansh Gaikwad

54 Followers
Writer for

Android Developer | ML Enthusiast | Quick Learner

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams