Robustness and generality of Alpha Zero

[bahriddin]

Hypothesis

Authors of recently published research Alpha Zero stated that this technique could be easily generalised to other problems without significant human effort and it approached better than other state-of-the-art alternatives [1]. They tested the system in 3 board games, specifically, Go, Chess and Shogi. We would like to check it in the different game(s) with closer game-space and game-tree complexities.

Questions

• How well can Alpha Zero algorithm perform in other games than Go, Chess and Shogi?
• Can Alpha Zero perform better than other alternatives?
• Can AI agent discover some remarkable knowledge during its self-play training process using Alpha Zero?
• After comparing the performance of multiple algorithms, can we make a better one (in the future)?

Methods

• Deep Reinforcement Learning + Monte Carlo Tree Search (Alpha Zero)
• Alpha-beta Pruning
• Adaptive Dynamic Programming
• Hand-coded rules

This list can be modified in the later stages of the research.

Candidate Games

We would like to find an answer to our research questions using at least one of this board games:

Gomoku

*Gomoku*, also called Gobang or Five in a Row, is an abstract strategy board game. It is traditionally played with Go pieces (black and white stones) on a Go board, using 15×15 of the 19×19 grid intersections. Because pieces are not moved or removed from the board, Gomoku may also be played as a paper and pencil game. The game is known in several countries under different names.

-- Wikipedia

It's space complexity in 15x15 board is about 3²²⁵ while game tree complexity 10⁷⁰ [3].

Abalone

Abalone is an award-winning two-player abstract strategy board game designed by Michel Lalet and Laurent Lévi in 1987. Players are represented by opposing black and white marbles on a hexagonal board with the objective of pushing six of the opponent's marbles off the edge of the board.

-- Wikipedia

It's space complexity is about 6.5 * 10²³ while average branching factor 60 and game tree complexity 5 * 10¹⁵⁴ [4].

Related Work:

1. Silver D. et al. (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. Retrieved from https://arxiv.org/abs/1712.01815.
2. Jose Camacho Collados josecamachocollados@gmail.com 11 December 2017, Is AlphaZero really a scientific breakthrough in AI? viewed 21 March, https://medium.com/@josecamachocollados/is-alphazero-really-a-scientific-breakthrough-in-ai-bf66ae1c84f2
3. Loos A. (2012). Machine Learning for k-in-a-row Type Games Using Random Forest and Genetic Algorithm. Retrieved from https://comserv.cs.ut.ee/home/files/thesis_final_mod.pdf?study=ATILoputoo&reference=5D52AF13A55F51ADB1F03E3C1EEAF628BA1BC580
4. Lemmens N. (2005). Constructing an Abalone Game-Playing Agent. Retrieved from https://project.dke.maastrichtuniversity.nl/games/files/bsc/Lemmens_BSc-paper.pdf
5. Zhao, D., Zhang, Z., & Dai, Y. (2012). Self-teaching adaptive dynamic programming for Gomoku. Neurocomputing, 78(1), 23-29.
6. Shao, K., Zhao, D., Tang, Z., & Zhu, Y. (2016, November). Move prediction in Gomoku using deep learning. In Chinese Association of Automation (YAC), Youth Academic Annual Conference of (pp. 292-297). IEEE.
7. Tan, Q., & Hu, X. CS221 Project Final Report Gomoku Game Agent.
8. Oswin,A & Franz,A & Tino,W. Algorithmic Fun - Abalone. Retrieved from http://www.ist.tugraz.at/aichholzer/research/rp/abalone/tele1-02_aich-abalone.pdf.

[lotharJiang]

Also, I suggest we should test the algorithm performance with some public Gomoku/Abalone engines. I list some below after researching.

Gomoku

1. Yixin, developed by Kai Sun, is the winner of the 13th, 14th, 15th, 16th, 17th and 18th Gomocup. It is widely known as the best Gomoku AI in the world.
   http://www.aiexp.info/pages/yixin.html

2. Gomocup – The Gomoku AI Tournament
   Gomocup released different versions of the top 39 AI in 2017 tournament, including Yixin listed above.
   http://gomocup.org/download-gomoku-ai/

Abalone

1. ABA-PRO, an Abalone playing program designed and developed by Tino Werner, is the winner of the 8th ICGA Computer Olympiad 2003
   http://www.ist.tugraz.at/aichholzer/research/rp/abalone/