Voice Controlled Chess

Every one of us might have seen the first movie of the Harry Potter series. There we have seen the game “Wizard chess” where the chess pieces move using voice commands and kill the other pieces by breaking them. This was very interesting to watch and so we thought of creating a game which can work like this. We are a team of 4 members and started working on this project from 25th October 2020.

The Problem Statement

The primary objective is to make a chess game (either 2D or 3D) and make it work through speaking words. So, first we need to make a working chess board and it should be a single player game. Next we need to use some speech recognition API to convert speech to text and then use it to make a move. We have to choose a platform where we can do both the game development and the speech recognition part. We thought using UNITY for designing the 3D game would be more attractive and thought of using the python program to run the speech recognition part. But merging these two is a tough challenge and we started to use pygame library for game development using python.

In our project

• A person can move his/her pieces using simple voice inputs which consist of both the initial position of a square and a final position.
• The position can be in the format of numbers like 24, 36… Which represent the row and column respectively or in the format B4, C6… which is generally used in the chess game.
• The game can check all valid moves and invalid moves and can respond accordingly.
• The computer opponent in this game using minimax algorithm along with alpha, beta pruning in order to make efficient moves.

Developing a chess game

Step 1: Move generation and board visualization

• FEN representation
• Halfmove counter for fifty move rule
• Fullmove counter for number of full moves
• bitboard representation

Step 2: Position evaluation

• Valid moves for each piece in the board
• Attack moves and normal moves

Step 3: Search tree using Minimax

Step 4: Alpha-beta pruning

Step 5: Improved evaluation function

• Other factors that can improve the quality of the game played by the computer

Move generation and board visualization

First we need to create a basic interface using pygame library. This is the GUI part of our project and it helps us to know what is happening to all the pieces in the game while performing different functions. This part is discussed later in this report.

After creating the GUI part we need to use certain representations in order to mark the pieces and make them move. These representations are important because we need to be able to process them fast.

FEN representation

Forsyth–Edwards Notation (FEN) is a standard notation for describing a particular board position of a chess game. The purpose of FEN is to provide all the necessary information to restart a game from a particular position. A FEN “record” defines a particular game position, all in one text line and using only the ASCII character set. A text file with only FEN data records should have the file extension “.fen”.

A FEN record contains six fields. The separator between fields is a space. The fields are:

• Piece placement (from White’s perspective). Each rank is described, starting with rank 8 and ending with rank 1; within each rank, the contents of each square are described from file “a” through file “h”. Following the Standard Algebraic Notation (SAN), each piece is identified by a single letter taken from the Standard English names (pawn = “P”, knight = “N”, bishop = “B”, rook = “R”, queen = “Q” and king = “K”). White pieces are designated using upper-case letters (“PNBRQK”) while black pieces use lowercase (“pnbrqk”). Empty squares are noted using digits 1 through 8 (the number of empty squares), and “/” separates ranks.
• Active color “w” means White moves next; “b” means Black moves next.
• Castling availability. If neither side can castle, this is “-”. Otherwise, this has one or more letters: “K” (White can castle kingside), “Q” (White can castle queenside), “k” (Black can castle kingside), and/or “q” (Black can castle queenside). A move that temporarily prevents castling does not negate this notation.
• ▪ En passant target square in algebraic notation. If there’s no en passant target square, this is “-”. If a pawn has just made a twosquare move, this is the position “behind” the pawn. This is recorded regardless of whether there is a pawn in position to make an en passant capture.
• Halfmove clock: This is the number of half moves since the last capture or pawn advance. The reason for this field is that the value is used in the fifty-move rule.
• Fullmove number: The number of the full move. It starts at 1, and is incremented after Black’s move.

Halfmove counter for fifty move rule

The fifty-move rule in chess states that a player can claim a draw if no capture has been made and no pawn has been moved in the last fifty moves (for this purpose a “move” consists of a player completing their turn followed by the opponent completing their turn). The purpose of this rule is to prevent a player with no chance of winning from obstinately continuing to play indefinitely or seeking to win by tiring the opponent.

Fullmove counter for number of full moves

It is already been discussed in the FEN representation.

Bitboard representation

Bitboards, also called bitsets or bitmaps, are among other things used to represent the board inside a chess program in a piece centric manner. Bitboards, are in essence, finite sets of up to 64 elements — all the squares of a chessboard, one bit per square. Other board games with greater board sizes may be using set-wise representations as well, but classical chess has the advantage that one 64-bit word or register covers the whole board.

For example if we consider white horse

The corresponding bitboard is converted into a 64 bit string that is 0000000000000000000000000000000000000000000000000000000001 000010 and this string stores the information. This is basically a long and so we can easily use shift operations to get other positions on the board.

So for each colour there are 6 different pieces i.e., King, Queen, Rook, Knight, Bishop, Pawn. So we need a total of 12 different bitboards to keep track of all the pieces on the board at one configuration of the board.

So for the initial position of the chess board the overlap of all the 12 bitboards looks like this.

Why use bitboards?

• This is more efficient on 64 bit technology
• Computer processors are made to work with binary efficiently including shifting and using arithmetic binary numbers.
• We can shift all the bits over from the 64 bit string in any direction and by any number using >> or << to get new positions on the board.
• For example:

Assume this red bitboard to represent the white pawns. After converting this into a 64 bit string and then applying a right shift by 2 we get this blue configuration which represents some of the attack positions of the white pawns.

Position evaluation

Now let’s try to understand which side is stronger in a certain position. The simplest way to achieve this is to count the relative strength of the pieces on the board using the following table. With the evaluation function, we’re able to create an algorithm that chooses the move that gives the highest evaluation.

Valid moves for each piece in the board

As shown in the above figure all the valid moves are specified for each piece in the chess board and this part is so big and we had to directly copy it from the internet. It includes every possible scenario that a piece can face while playing the game like knights can jump over other pieces where as other pieces cannot move over any piece. This also has castling moves for the king and the conditions are to be met in order to castle.

Attack moves and normal moves

This piece of code here gives the possible attacks in priority order depending on the score of the piece that can be attacked. If there is no attack move or a check mate present it chooses a normal move depending on the bonuses given to the positions of the board for each piece.

Search tree using Minimax algorithm

Next we’re going to create a search tree from which the algorithm can choose the best move. This is done by using the Minimax algorithm. In this algorithm, the recursive tree of all possible moves is explored to a given depth, and the position is evaluated at the ending “leaves” of the tree.

After that, we return either the smallest or the largest value of the child to the parent node, depending on whether it’s a white or black to move. (That is, we try to either minimize or maximize the outcome at each level.)

A visualization of the minimax algorithm in an artificial position. The best move for white is b2-c3, because we can guarantee that we can get to a position where the evaluation is -50

The effectiveness of the minimax algorithm is heavily based on the search depth we can achieve.

• Depth = 1 → easy
• Depth = 2 → medium
• Depth = 3 → hard (and obviously takes more time to process)

This is the pseudo code which we have used to develop of actual code:

Here is the code which we have written in our program:

Alpha-Beta pruning

It is an optimization method to the minimax algorithm that allows us to disregard some branches in the search tree. This helps us evaluate the minimax search tree much deeper, while using the same resources. The alpha-beta pruning is based on the situation where we can stop evaluating a part of the search tree if we find a move that leads to a worse situation than a previously discovered move. The alpha-beta pruning does not influence the outcome of the minimax algorithm — it only makes it faster.

The alpha-beta algorithm also is more efficient if we happen to visit first those paths that lead to good moves.

The pseudo code which we used is

Based on this we have implemented the alpha-beta pruning to the code in order to minimize the number of sub-tree traversals thereby minimizing the time taken for processing.

Improved evaluation function

The initial evaluation function is quite naive as we only count the material that is found on the board. To improve this, we add to the evaluation a factor that takes in account the position of the pieces. For example, a knight on the center of the board is better (because it has more options and is thus more active) than a knight on the edge of the board. So, we had to introduce piece bonuses for each piece in the board in order to decide to make a move which can increase the chances of winning. For example

• Opening the pawns in front of the king and queen helps to give access to more powers on the board there by increasing the chances of winning.
• Similarly horses on the middle of the board are probably more helpful than on the edges of the board so that they can have a more moving space.

These bonuses are just relative and they are completely based on pure intuition and experience of different players. We have taken these values from the internet.

GUI and speech recognition:

The game basically runs with the help of GUI part. With this one can control the size of the board and squares it is having escalate difficulty level, Press particular keys on keyboard to do specific functions.

Importing modules into GUI part:

Making of chess board:

With the help of Pygame library of python, a chessboard was made. Screen was made and updated with a title, an icon and a caption.

On the squares of board, images of chess pieces and Numbers were uploaded.

In print_board function, an inbuilt Blit function was used to add another surface on one surface. Here we had loaded images of numbers on the board. And we have scaled the images to occupy one-half of the space provided in length-wise. Square size, image and rectangular coordinates were provided as parameters to the function.

Functions:

Basic functions were made to resize the screen, to print a board, paint a square.

Play:

The player will get white or black as their play in the very beginning of the game and it is completely random. The game can be initialized by a mouse click and it takes the voice command as an input and it shows the output on the chess board and as well as on Shell.

For recognizing the voice, Google’s API has been used.

When we right-click our mouse, it takes the command for 5 seconds and then starts recognizing it and makes a move. Here, we extracted the first 2 letters and the last 2 letters of the string spoken and with this, it makes a move.

Additionally, if we make an invalid move, the computer asks us for a “valid move” and even if we say something invalid then it says us “I didn’t get that. Say again”.

Features in the game:

• Depth: One can increase the difficulty level of the game by increasing the “depth” value. But on increasing “depth” the game gets slower since it tries to find the best move with the algorithm used.
• By pressing Esc key One can get out of the game or exit from the game.
• Theme colors were added.
• One change the theme color by pressing ‘c’.
• One can get ‘p’ or ‘d’ to get the list of moves you had made.
• Pressing ‘e’ will evaluate your score.
• Pressing ‘u’ will undo your move.
• If you are struck in the middle of the game and need some help you can use ‘h’ key and a move for you will be chosen by the computer. If you don’t like it you can always undo your move.

Further innovations that can be done:

• We can use UNITY to develop better graphics for movement of chess pieces and even add sounds to give a better game experience.
• We can use Reinforcement learning so that the AI opponent can give a better competition and make the game tougher.
• We need to improve the speech recognition part so that the system can understand various formats of inputs just like a person who can understand the move that is to be made even if we speak it in a different way.

Picture of our final working project