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

dc.contributor.advisorFu, Michaelen_US
dc.contributor.authorLin, Jonathan Funen_US
dc.contributor.departmentSystems Engineeringen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2018-01-25T06:36:18Z
dc.date.available2018-01-25T06:36:18Z
dc.date.issued2017en_US
dc.description.abstractMonte 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.en_US
dc.identifierhttps://doi.org/10.13016/M2VD6P64Q
dc.identifier.urihttp://hdl.handle.net/1903/20449
dc.language.isoenen_US
dc.subject.pqcontrolledEngineeringen_US
dc.subject.pquncontrolledMonte Carlo Tree Searchen_US
dc.titleMONTE CARLO TREE SEARCH AND MINIMAX COMBINATION – APPLICATION OF SOLVING PROBLEMS IN THE GAME OF GOen_US
dc.typeThesisen_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Lin_umd_0117N_18677.pdf
Size:
22.94 MB
Format:
Adobe Portable Document Format