Chess AI

Introduction

This project was developed to improve my knowledge of AI programming and various concepts used by AI within games.

This involved the creation of a chess AI to play against the player, taking into account various factors including piece values, movements and the impacts of various moves.

To do as such, I had implemented MiniMax, NegaMax, Alpha-beta pruning and Move Ordering making use of piece and position scores.

MiniMax & Basic Scoring

The first implementation made use of the MiniMax algorithm, where in which every available move has its resultant board scored and each resultant board is also checked for each available move. This iteration is repeated until reaching a specified horizon. 

Following this the highest and lowest scores are picked, alternating for each layer of the permutation tree, allowing the AI to select for the route with the best possible moves for itself while assuming the player to also take the worst possible routes for the AI.

For the evaluation, the pieces were given scores based on the chess programming WIKI recommendations. Another quick improvement was the addition of position scoring, simply making use of additional values based on board position, these values being unique to piece types.

Alpha-beta Pruning

MiniMax was initially improved upon using AB pruning. AB pruning is a notable improvement as the result is the same as when not using AB pruning but with the benefit of not searching the entire permutation tree.

AB pruning works through passing alpha and beta values along during the search. For instance, if we are on a maximum search (highest board value), we know we will take the highest valued child node. Equally, we know the next node will be a minimum search (lowest value child board). As a result, if a child node returns a lower value than our current highest value child node, the rest of that nodes children can be ignored as they will not return a higher value than our current highest.

The saving from AB pruning can reduce the searched nodes from n nodes to around √n nodes. However, this is dependant on the permutation tree, as if the moves are ordered in the worst possible way, the time taken to search would be the same as without AB pruning.

It is worth noting fail-soft was used to allow results out of the AB bounds, retaining slightly more data for the search, resulting in better results.

NegaMax

To simplify and shorten the code, MiniMax was swapped for NegaMax. As chess is a zero-sum game, the evaluation of a board or move is the equivalent to the negation of the evaluation from the opponent. 

Scoring

As stated before, piece and position values were used for scoring, promoting taking and protecting high value pieces and promoting beneficial positions.

This scoring was improved upon through various means. The first of which being move scoring, whereby a board is given bonus points for each available move from a piece ensuring rooks or bishops with many available moves are preferred over constrained ones.

To complement this, attack scoring was implemented, whereby a board was awarded points for each piece that could be taken using the boards configuration. 

Move Ordering

In order to improve the efficiency of AB pruning, Move Ordering was implemented. 

Moves are awarded points based on:

• Piece values of target and attacker (Most Valuable Victim and Least Valuable Aggressor)

• Pawn Promotion (+ value of the queen)

• Remove score of a piece if an opponents pawn can capture it

Scoring the moves and ordering them on their scores ensures that moves leading to beneficial trades, captures or promotions are favoured while losses, losing trades or vulnerable positions are avoided. This reduced the time taken for move searching in the later stages of the game where there are many possible moves available. 

Board Representation

The board was initially implemented as a 2D array. This was swapped to a 1D array, marginally improving the speed of the AI.

An improvement to this would include the use of bit-boards, making use of bit arithmetic for any calculations.

What I Learned

Throughout the project, I had come to understand the constraints and mechanisms for winning within zero-sum games and how these can be used to optimise search algorithms.

If I were to return to this project, I would swap out the array representation for bit-boards, alongside Iterative Deepening using Principal Variation, removing the constraint of the horizon and instead limiting the search by a time-limit (if a valid win condition is not found earlier).

• Roberts, P. (2022). Artificial Intelligence in Games. [Online]. Milton, UNITED KINGDOM: CRC Press, Taylor & Francis Group. Available from: http://ebookcentral.proquest.com/lib/staffordshire/detail.action?docID=7007113. [Accessed: 4 December 2025].