GGP: Monte Carlo Search

In the previous post, we looked at a heuristic-based general game player, which worked for single player and two player zero-sum games. There are a few problems with this approach though: We need to come up with a good heuristic for the game at hand but more importantly, heuristics exploit local properties of states (properties that do not depend on the game tree as a whole) and for many games, there may not be any correlation between these local properties and global success. It would be better if we didn’t have to come up with a heuristic; if the heuristic was somehow built into the search algorithm itself i.e., the algorithm were itself capable of ordering the moves, and the ordering depended on the whole game tree instead of local state properties.

Continue reading