mcts-tic-tac-toe
mcts-tic-tac-toe copied to clipboard
hayoung-kim
Monte Carlo Tree Search for tic tac toe
mcts-tic-tac-toe
https://github.com/hayoung-kim/mcts-tic-tac-toe
solve tic tac toe (3x3) problem using vanila mcts. It was made for the purpose of studying the concept of mcts.
youtube demo: https://youtu.be/9BEcOWviCjA
Requirement
- pygame
How to play
python play.py
Implement detail
selection: UCT algorithm (https://en.wikipedia.org/wiki/Monte_Carlo_tree_search)
expansion: create all possible node from state
simulation: randomly play simulation(=random roll-out policy). This simulation method lower the performance.
backprop: back propagate simulation result.
References
http://tim.hibal.org/blog/alpha-zero-how-and-why-it-works/
https://medium.com/swlh/tic-tac-toe-at-the-monte-carlo-a5e0394c7bc2
https://github.com/reinforcement-learning-kr/alpha_omok
https://github.com/JuliaPOMDP/MCTS.jl
Acknowledgement
Kyushik Min helped a lot for implementing algorithm.
hayoung-kim