Project Abstract

This research project provided opportunities to work on a discrete area of work bringing together learning from the undergraduate computer science syllabus and application of coding skills to an area of emerging interest, namely an AI application. The project aim was to develop functional Java code to explore the impact of pruning techniques in a chess engine, and to address the research question: ?��in comparing minimax search algorithm against minimax optimised with alpha-beta pruning, what impact do depth search and space search have on performance??�� alongside examining the effect of move-ordering heuristics. A chess engine was used to evaluate the comparative performance of the search algorithms, each variant playing against each other 100 times, with the game result recorded. Another test was also conducted to calculate time per move. Results demonstrated that (1) deeper search produced stronger levels of play. (2) Average time taken per move was significantly reduced with pruning, depth 4 producing results that were 82% faster. (3) Use of a move ordering heuristic reduced the time further, achieving 26% reduction at depth 6. (4) Impact of move ordering varied depending on depth and the number of moves, showing maximum effect on middle game moves 30-50. In conclusion, since increasing the levels of depth made for stronger play, a chess engine that can adjust this will provide differential challenges for human players, and alpha-beta pruning will allow for faster execution times. The obtained results, with quantifiable metrics, adds to our knowledge and understanding of search algorithms and optimisation techniques that can be applied to other AI applications. Further research might examine the impact of other move ordering techniques, such as static exchange evaluation, which could help to mitigate the variance in the time reduction per move.Key words: alpha-beta pruning, chess AI, minimax, move ordering

Keywords: Artificial Intelligence, Minimax algorithm, alpha-beta pruning optimisation

 Conference Details

Session: Poster Session A at Poster Stand 108

Location: Sir Stanley Clarke Auditorium at Tuesday 7th 13:30 – 17:00

Markers: Jiaxiang Zhang, Daniele Cafolla

Course: BSc Computer Science, 3rd Year

Future Plans: I’m looking for work