A study of Monte Carlo Methods for Phantom Go

Abstract

本論文通過研究 imperfect information games和改進版Monte Carlo方法來建立一個有效的遊戲應用。遊戲是測試人工智慧的重要領域。當今，最有效的方法是Monte Carlo法。這些方法是基於概率，並被廣泛用於創建遊戲序，特別是對於圍棋，也imperfect information games，比如橋牌，撲克牌或幻影圍棋。幻象遊戲根據 Perfect Information創建，但每個玩家只能看到自己的棋牌。 Imperfect information博弈是相當難以處理。由於玩家無法知道遊戲的狀態，因此非常困難使用Minimax演算法，或找到一個Nash equilibrium。啟用特定的Monte Carlo方法可以把上述問題處理的很好。到現在為止，最好的電子幻影圍棋遊戲是Flat Monte Carlo，Cazenave在2006年編寫。我們發展另一種方法 two-level Monte Carlo method，並作分析比較。

This thesis deals with imperfect information games and the application of Monte Carlo methods to build an effective playing program. Games are an important field for testing Artificial Intelligence. Nowadays, the most efficient methods are Monte Carlo ones. These methods are based on probabilities, and have been widely used to create playing programs, particularly for the game of go, but also for imperfect information games, as Bridge, Poker or Phantom Go; phantom games are created according to a Perfect Information game, but in which each player only sees his own moves. Imperfect information games are quite hard to handle. As the different state of the game is unknown to the players, it is very difficult to use Minimax algorithms, and also to find a Nash equilibrium. Specific Monte Carlo methods enabled to get good playing programs in these games. However, till now, the best playing program for Phantom Go was a Flat Monte Carlo one, written in 2006 by Cazenave. As new methods have been found since then, we also tried a two-level variant of Monte Carlo, which would enable to take in consideration what does or does not know each player during the playout.