LS-Draughts - A Draughts Learning System based on genetic algorithms, neural network and temporal differences

The objective of this paper is the proposal of a learning system - the LS-Draughts - which aims at using genetic algorithms (GAs) to automatically generate a concise and efficient set of features which are relevant in representing the game board states and for optimizing the training of a draught player agent. This agent consists of an Artificial Neural Network whose weights are updated by the temporal differences (TD) reinforcement learning methods. The NET-FEATUREMAP mapping is used to represent a game board state in the Network input. The network output corresponds to a real number (prediction) that indicates to what extent the input state is favorable to the agent. The agent is trained by self-play coupled with a cloning technique. The minimax algorithm is used to choose the best action to be executed considering the current game board state. Such a learning process is close to that proposed by Mark Lynch (NeuroDraughts). However, the LS-Draughts expands the NeuroDraughts as it automatically generates an effective and concise set of features to be used in the NET-FEATUREMAP mapping, whereas the latter uses a fixed and manually defined set of features. A tournament was promoted between the best player obtained by the LS-Draughts and the best available player of the NeuroDraughts. The tournament was won by the player of the LS-Draughts, which confirms that the GAs can be an important tool for improving the general performance of automatic players.