Monte Carlo Tree Search is a widely used algorithm in game theory which makes decision based on updated policy devised by the tree with each iteration. If say we have played a move that has led to victory 99 out of 100 random games, it is very likely that it is good move and there are very less chances that it will lead to defeat. The solution to this problem is to get closer to the best move of the given state by using statistics. Chess alone has 10¹²⁰ states which is more than number of atoms in the world! You can increase your chance of winning.īut since the moves increase exponentially - the computation power that is required to calculate the moves also goes through the roof.Īs of now, strongest computer in the world can do 200,000 trillion calculations per second.īut sadly, that is not enough if we need to predict best move of given state of the game. Ideally if you can predict every possible move and its result that may occur in the future. These possible steps increase exponentially as the game goes forward.
The Games like Tic-Tac-Toe, Rubik’s Cube, Sudoku, Chess, Go and many others have common property that lead to exponential increase in the number of possible actions that can be played. In this article I will walk you through how I was able to implement MCTS in chess. I have made chess bot for my college semester’s project using minimax algorithm and MCTS.
Photo by Hassan Pasha on Unsplash Introduction
0 kommentar(er)
