MONTE CARLO TREE SEARCH AND MINIMAX COMBINATION – APPLICATION OF SOLVING PROBLEMS IN THE GAME OF GO

Monte Carlo Tree Search (MCTS) has been successfully applied to a variety of games. Its best-first algorithm enables implementations without evaluation functions. Combined with Upper Confidence bounds applied to Trees (UCT), MCTS has an advantage over traditional depth-limited minimax search with alpha-beta pruning in games with high branching factors such as Go. However, minimax search with alpha-beta pruning still surpasses MCTS in domains like Chess. Studies show that MCTS does not detect shallow traps, where opponents can win within a few moves, as well as minimax search. Thus, minimax search performs better than MCTS in games like Chess, which can end instantly (king is captured). A combination of MCTS and minimax algorithm is proposed in this thesis to see the effectiveness of detecting shallow traps in Go problems.

Department dc:contributor.department

Systems Engineering

Year dc:date.issued

2017

Author dc:creator

• Lin, Jonathan Fun

Advisor dc:contributor.advisor

• Fu, Michael

Language dc:language.iso

en

Identifier

https://doi.org/10.13016/M2VD6P64Q

OAI identifier oai:identifier

oai:drum.lib.umd.edu:1903/20449