MP-Draughts: Ordering the Search Tree and Refining the Game Board Representation to Improve a Multi-agent System for Draughts

摘要

In this paper the authors present an extension of the automatic player system MP-Draughts (MultiPhase-Draughts): a self-learning multi-agent environment for draughts composed of 26 Multiple Layer Perceptrons (MLPs). The weights of the MLPs are updated by Temporal Differences (TD). The search for the best move is conducted by a search algorithm based on Alpha-Beta pruning, Iterative Deepening and Table Transposition. One of the agents is trained in such a way that it becomes an expert in the initial stages of play and the remaining (25), in endgame stages. The endgame boards used to train the endgame agents are retrieved from an endgame board database and clustered by a Kohonem-SOM Neural Network (NN). The same Kohonem-SOM NN will also be used during the games to select which endgame agent is more suitable to play each time the endgame stage of play is reached. In this paper the authors propose the following modifications to improve the performance of MP-Draughts: first, to change the mapping of the board states such that, instead of indicating the presence or not of certain features, it indicates the number of elements pointed out by each feature, second, to order the search tree of each agent in such a way as to attenuate the innumerous re-evaluations of the same board state inherent to the iterative deepening strategy.