Artificial Intelligence Techniques Applied
To Draughts

Abstract

This thesis documents the work done to develop a draughts playing program that learns game strategies utilising various Artificial Intelligence (AI) techniques with the goal of being able to play draughts at a reasonably high skill level as a result of having played against itself without external guidance.

Context/Background:
AI is a fast evolving field of study. The motivation being programming computers to learn from experience should eventually eliminate the need for this detailed, time consuming, and costly programming effort currently required to program solutions to problems.

Aims:
The aim is to investigate a variety of AI techniques. The program’s effectiveness will be assessed in both evaluating moves and playing a computationally intensive game.
Minimax based algorithms together with a basic scoring heuristic are used to evaluate enough of the game tree to pick high utility moves. Later the scoring heuristic is augmented using artificial intelligence techniques. As a result of this training “smart scoring behaviour” the program is expected to learn how to best assign values to each of the squares on the draughts board enabling it to play at an adequately high skill level.

Method:
In this thesis a version of the board game Draughts is implemented in the Java programming language. Players were developed using a variety of techniques. These algorithms
were tested by comparing running times, number of nodes of the game tree searched and the utility of the moves picked. In addition an algorithm is developed to assign scores to
given board states using a genetic algorithm.

Results:
The project was a success for the most part permitting the creation of the game of draughts in the JAVA programming language. Four out of the five proposed move selection techniques were successfully tested in isolation. Finally the genetic algorithm demonstrated the ability to augment the scoring heuristic without the benefit of external guidance in the form of human experience.