Creating a Chess Algorithm using Deep Learning and Monte Carlo Methods

Over the past few weeks I have tried two distinct approaches to create a chess algorithm that can play with great strategic depth without looking too far ahead and blundering.

The first method I used was to convert chess moves and chess boards into one-hot encoding, and then using these values to train a deep neural network to come up with the best move, when given a certain board. There are few problems with this method. It would be far too easy for the computer to make illegal moves, that is, moves that are not possible on the board configuration, making training learning legal moves before best moves, which would significantly slow down convergence.

The second method I used was manually creating a heuristic algorithm from scratch that took numerical measures of the board and calculated a numerical value that was the score of the board. I then wrote a search algorithm that used Monte Carlo methods by picking random moves after a recorded first move. However, I found that the heuristic values that my algorithm calculated were largely inaccurate and had no foresight for more complex tactics or positional advantages.

I found out that putting two of the algorithms together would yield great results. Here’s the concept:

Concept:

I would train a deep neural network based on the evaluation made by the Stockfish algorithm from a dataset. For each legal move for the position given, for a given depth, a random move would be made. The position would then be evaluated and recorded. The first move that has the highest score would therefore be the best move.

This would be better than the deep learning algorithm as it would only make legal moves and better than the search algorithm as it had the evaluation abilities of the stockfish algorithm. The computation would be relatively low as training the stockfish deep learning algorithm could be done beforehand, and due to only running random moves, it would take less computational power.

Code:

Step 1| Access Data:

import os
from pandas import read_csv
os.chdir('XXXXXX')
csv = read_csv('chessData.csv')

Access the first dataset from Kaggle. Download it onto your local drive and import it using the read_csv function from pandas.

Step 2| Prepare Data:

chess_dict = {
    'p' : [1,0,0,0,0,0,0,0,0,0,0,0],
    'P' : [0,0,0,0,0,0,1,0,0,0,0,0],
    'n' : [0,1,0,0,0,0,0,0,0,0,0,0],
    'N' : [0,0,0,0,0,0,0,1,0,0,0,0],
    'b' : [0,0,1,0,0,0,0,0,0,0,0,0],
    'B' : [0,0,0,0,0,0,0,0,1,0,0,0],
    'r' : [0,0,0,1,0,0,0,0,0,0,0,0],
    'R' : [0,0,0,0,0,0,0,0,0,1,0,0],
    'q' : [0,0,0,0,1,0,0,0,0,0,0,0],
    'Q' : [0,0,0,0,0,0,0,0,0,0,1,0],
    'k' : [0,0,0,0,0,1,0,0,0,0,0,0],
    'K' : [0,0,0,0,0,0,0,0,0,0,0,1],
    '.' : [0,0,0,0,0,0,0,0,0,0,0,0],
}

def make_matrix(board): 
    pgn = board.epd()
    foo = []  
    pieces = pgn.split(" ", 1)[0]
    rows = pieces.split("/")
    for row in rows:
        foo2 = []  
        for thing in row:
            if thing.isdigit():
                for i in range(0, int(thing)):
                    foo2.append('.')
            else:
                foo2.append(thing)
        foo.append(foo2)
    return foo

def translate(matrix,chess_dict):
    rows = []
    for row in matrix:
        terms = []
        for term in row:
            terms.append(chess_dict[term])
        rows.append(terms)
    return rows

The chess_dict is a dictionary that can be used to change each board into a matrix of one-hot encoded arrays. Based on basic functions of the python-chess function, one can convert a chess board into a matrix of strings. This matrix of strings can be one-hot encoded to form a matrix of one-hot encodings. This matrix can then be fed into a neural network.

import chess
import numpy as np

fen = csv['FEN'].values
values = csv['Evaluation'].values
length = 10000

X =[]
y= values[:length]
defects = []

for i in range(length):
    board = chess.Board(fen[i])
    matrix = make_matrix(board.copy())
    translated = translate(matrix,chess_dict)
    X.append(translated)

This script gets the actual values and performs the two sets of operations on the boards so that the data can be fed into a neural network.

for i in range(length):
    if '#' in y[i]:
        y[i] = float(y[i][-1]) * 1000
y = y.astype('float32')

As the evaluation could return with a value of M5, or #5, we have to remove this and change this to a numerical value. For every occurence of a hash, multiple the last value in the string by 1000.

minimum = min(y)
maximum = max(y)
for i in range(len(y)):
    y[i] = (y[i]-minimum)/(maximum-minimum)

After a few preliminary runs with the training function with the data at this state, I found that normalizing the data (setting the data as a value between 0 and 1) yielded better results. Of course, the last layer of the neural network must therefore be a sigmoid function.

Step 3| Create and train the neural network:

from keras import callbacks, optimizers
from keras.layers import (LSTM, BatchNormalization, Dense, Dropout, Flatten,
                          TimeDistributed)
from keras.layers.convolutional import Conv2D, MaxPooling2D
from keras.models import Sequential, load_model, model_from_json
from IPython.display import clear_output
from matplotlib import pyplot as plt

model = Sequential()
model.add(Conv2D(filters=10, kernel_size=1, activation='relu', input_shape=(8,8,12)))
model.add(MaxPooling2D(pool_size=2, strides=None))
model.add(Flatten())
model.add(BatchNormalization())
model.add(Dense(1,activation = 'sigmoid'))

model.compile(optimizer = 'Adam',loss='mse')
h5 = 'chess' + '_best_model' + '.h5'
checkpoint = callbacks.ModelCheckpoint(h5,
                                           monitor='val_loss',
                                           verbose=0,
                                           save_best_only=True,
                                           save_weights_only=True,
                                           mode='auto',
                                           period=1)
es = callbacks.EarlyStopping(monitor='val_loss', mode='min', verbose=1, patience=5000/10)
callback = [checkpoint,es]
json = 'chess' + '_best_model' + '.json'
model_json = model.to_json()
with open(json, "w") as json_file:
    json_file.write(model_json)
print('Training Network...')

test = 1000
X = np.array(X)
X_train = X[test:]
y_train = y[test:]

X_test = X[:test]
y_test = y[:test]
model.fit(X_train,y_train,epochs = 1000,verbose = 2,validation_data = (X_test,y_test),callbacks = callback)

Now that the data has been properly normalized, we can create the neural network. The neural network is a basic convolutional neural network, with batch normalization at the end of it. I am saving the best weights so that the model can be loaded later to prevent wasting computational power on training the model everytime a move needs to be made. I created a test and train set to make sure that everything is working as intended.

Step 4| Load Model:

from keras.models import Sequential, load_model, model_from_json
def load_keras_model(dataset,loss,optimizer):
        json_file = open(dataset+'_best_model'+'.json', 'r')
        loaded_model_json = json_file.read()
        json_file.close()
        model = model_from_json(loaded_model_json)
        model.compile(optimizer=optimizer, loss=loss, metrics = None)
        model.load_weights(dataset+'_best_model'+'.h5')
        return model

This function loads the model based on the best weights saved earlier. It is reasonably simple, but one must make sure that the file is in the directory that the program is in or a path must be defined to access the file.

Step 5| Monte Carlo Algorithm:

import random
import chess
board = chess.Board()

moves = []
model = load_keras_model('chess','mse','Adam')

def calculate_move(depth,board,epochs):
    first_legal_moves = str(board.legal_moves)[38:-2].replace(',','').split()
    scores = [[0]] * len(first_legal_moves)
    for epoch in range(epochs):
        for first_move in range(len(first_legal_moves)):
            play_board = board.copy()
            play_board.push_san(first_legal_moves[first_move])
            for _ in range(depth):
                legal_moves = str(play_board.legal_moves)[38:-2].replace(',','').split()
                try:
                    move = random.choice(legal_moves)
                except:
                    scores[first_move] *= 1000

matrix = make_matrix(play_board.copy())
            translated = np.array(translate(matrix,chess_dict))
            scores[first_move] += model.predict(translated.reshape(1,8,8,12))*(maximum-minimum)+minimum
        print('Epoch',str(epoch+1)+'/'+str(epochs))
    return first_legal_moves[scores.index(max(scores))]

move= calculate_move(10,chess.Board(),100)

Basically the program collects the first set of legal moves possible to make given the board configuration. F or a defined test_depth, the algorithm will choose random legal moves. The final board it comes up with will be evaluated using the model, and a numerical evaluation will be calculated. This numerical evaluation will be added to the score of that move. The move with the highest score will be the move played by the computer.

Conclusion:

I wrote a little prototype script to play against the chess algorithm:

while True:
    legal_moves = str(board.legal_moves)[38:-2].replace(',','').split()
    print(board)
    print(str(board.legal_moves)[38:-2].replace(',','').split())
    move = input('Which move do you want to Play?')
    board.push_san(move)
    print(board)
    matrix = make_matrix(board.copy())
    translated = np.array(translate(matrix,chess_dict))
    print(model.predict(translated.reshape(1,8,8,12)))
    clear_output()
    move = calculate_move(10,board,100)
    board.push_san(move)
    clear_output()

It fared much better than any other algorithm I have written, moving quite rapidly as well! I hope you learnt how to use monte carlo algorithms and deep learning algorithms in conjunction to solve problems with my article.