Thesis Topic Details

Topic ID:
3379
Title:
Learning a Strategy for Multi-Player Chess
Supervisor:
Alan Blair
Research Area:
Machine Learning, Artificial Intelligence
Associated Staff
Assessor:
Malcolm Ryan
Topic Details
Status:
Active
Type:
R & D
Programs:
CS CE BIOM BINF SE
Group Suitable:
No
Industrial:
No
Pre-requisites:
COMP3411 Artificial Intelligence or COMP9444 Neural Networks or COMP9417 Machine Learning and Data Mining
Description:
The aim of this project is to use machine learning to develop an evaluation function for a multi-player chess game called Duchess (www.duchessgame.org).
Duchess is similar to Chess, but has some additional pieces and a larger board size, so the branching factor is considerably greater. Games of this complexity have not previously been able to be learned by self-play. However, in 2009 a new algorithm called TreeStrap was developed within the group and used to demonstrate, for the first time, that a Chess player could be trained to Master level, entirely through self-play.
The TreeStrap algorithm essentially improves the evaluation of all nodes in the alpha-beta search tree, based on the evaluation of positions further down the tree.

This project would involve adapting existing code in C or Java, writing new code to implement the TreeStrap algorithm, and devising appropriate features for the evaluation function, based on the features used in the KnightCap Chess player, but suitably adapted for the more complex multi-player game Duchess. It would suit a student with an interest in game tree search, reinforcement learning or neural networks, who has completed a course in Artificial Intelligence or Machine Learning.

If successful, this research could be published in a high-profile
conference or journal, and could potentially be incorporated into a
Duchess iPad app which would allow users to play against the computer,
or against other humans.
Comments:
J.Veness, D.Silver, W.Uther & A.Blair, 2009.
Bootstrapping from Game Tree Search,
Advances in Neural Information Processing Systems 22 (NIPS'2009), pp.1937-1945.
books.nips.cc/papers/files/nips22/NIPS2009_0508.pdf
http://videolectures.net/nips09_veness_bfg/

J.Baxter, A.Tridgell & L.Weaver, 1999. KnightCap: A chess program that
learns by combining TD(lambda) with game-tree search, Proceedings of
the Fifteenth International Conference on Machine Learning (ICML '98),
pages 28-36. http://arxiv.org/abs/cs/9901002
Past Student Reports
  Joseph Reid BARCHAM in s2, 2013
Learning a Strategy for Multi-Player Chess
 

Download report from the CSE Thesis Report Library

NOTE: only current CSE students can login to view and select reports to download.