The Monte Carlo Method for Game AI
When a computer program runs games of chess, a common approach is to build up a big tree of moves (“if I move here, then he’ll probably move there, then I can move here” etc.) With a nice limited set of moves, the tree won’t get too gigantic. After all, there’s only so much you can do in chess—your rook can never move diagonally (unless your opponent has left the room to visit the toilet)—so the tree doesn’t get prohibitively large, and the AI can look ahead many moves before running out of memory.
Contrast this to a game like Go, where the board is 19×19, and players can play at basically any position. The tree gets huge, and it gets huge fast. Looking ahead a mere five moves considers over 6 trillion board positions. Of course, the tree can be “pruned” to only consider the likely moves, or the board can be considered in smaller bite-sized pieces, or piles of specialized pattern matching knowledge can be built in, but computer Go players have enjoyed limited results using these techniques.
Enter the Monte Carlo Method. This is a technique where the computer does a bunch of random simulations and tries to draw conclusions based on the results.
