Project Abstract

This project consists of the creation of a search algorithm known as alpha-beta pruning, an optimization of the minimax algorithm, which is used to find the best possible move in a two player game, in this case checkers (also known as draughts). The main goals of the project include the optimization of the search algorithm, in terms of runtime and memory usage, as well as attempting to make the algorithm as effective of a checkers player as possible. The optimization is achieved by adjusting the order in which the algorithm considers certain moves, among other techniques, while more effective play is obtained by developing a heuristic system, which can evaluate a checkers game state, and assign how valuable it is, by taking into account the nuances of checkers. The speedup that alpha-beta pruning has contributed has been analysed, with comparison using different parameters, such as the depth of the search.

Keywords: Artificial Intelligence, Game Theory, Tree Search

 Conference Details

Session: Poster Session B at Poster Stand 124

Location: Sir Stanley Clarke Auditorium at Wednesday 8th 09:00 – 12:30

Markers: Ulrich Berger, Jay Morgan

Course: BSc Computer Science, 3rd Year

Future Plans: I’m looking for work