In this article, to answer these questions, we go through the Monte Carlo Tree Search fundamentals. Since in the next articles, we will implement this algorithm on "HEX" board game, I try to explain the concepts through examples in this board game environment. If you're more interested in the code, find it in this link. There is also a more optimized version which is applicable on linux due to utilizing cython and you can find it in here. Monte Carlo method was coined by Stanislaw Ulam for the first time after applying statistical approach "The Monte Carlo method".

Hex is a complex game with a high branching factor. For the first time Hex is being attempted to be solved without the use of game tree structures and associated methods of pruning. We also are abstaining from any heuristic information about Virtual Connections or Semi Virtual Connections which were previously used in all previous known computer versions of the game. The H-search algorithm which was the basis of finding such connections and had been used with success in previous Hex playing agents has been forgone. Instead what we use is reinforcement learning through self play and approximations through neural networks to by pass the problem of high branching factor and maintaining large tables for state-action evaluations. Our code is based primarily on NeuroHex. The inspiration is drawn from the recent success of AlphaGo Zero.

In this paper, several techniques for learning game state evaluation functions by reinforcement are proposed. The first is a generalization of tree bootstrapping (tree learning): it is adapted to the context of reinforcement learning without knowledge based on non-linear functions. With this technique, no information is lost during the reinforcement learning process. The second is a modification of minimax with unbounded depth extending the best sequences of actions to the terminal states. This modified search is intended to be used during the learning process. The third is to replace the classic gain of a game (+1 / -1) with a reinforcement heuristic. We study particular reinforcement heuristics such as: quick wins and slow defeats ; scoring ; mobility or presence. The four is another variant of unbounded minimax, which plays the safest action instead of playing the best action. This modified search is intended to be used after the learning process. The five is a new action selection distribution. The conducted experiments suggest that these techniques improve the level of play. Finally, we apply these different techniques to design program-players to the game of Hex (size 11 and 13) surpassing the level of Mohex 2.0 with reinforcement learning from self-play without knowledge. At Hex size 11 (without swap), the program-player reaches the level of Mohex 3HNN.

Welcome to the home page of the computer Hex research group. We --- Kenny Young, Kelly Li, Broderick, Phil, Ryan, Jakub (and previously Aja, David, Jack, Mike, Morgan, Nathan Po, Maryia, Martha, Leah, Yngvi, Geoff Ryan, and Robert Budac) --- build Hex players and solvers. The group informally dates from 1999, when Jack, who wrote Queenbee, started an MSc with Jonathan. Current projects include MoHex, and Solver. Previous projects include Wolve, Mongoose and Queenbee.

Hex is a two-player game invented by Piet Hein in 1942 while a student at Niels Bohr's Institute for Theoretical Physics, and subsequently and independently by John Nash in 1948 while a mathematics graduate student at Princeton. The game was originally called Nash or John, with the latter name at the same time crediting its inventor and referring to the fact that it was frequently played on the tiled floors of bathrooms (Gardner 1959, pp. The name Hex was invented in 1952, when a commercial version was issued by the game company Parker Brothers. Hex is played on a diamond-shaped board made up of hexagons. The game is usually played on a boards of size 11 on a side, for a total of 121 hexagons, as illustrated above.