蒙特卡洛樹搜索算法（UCT）: 一個程序猿進化的故事
前言：
本文是根據(jù)的文章Introduction to Monte Carlo Tree Search by Jeff Bradberry所寫。
Jeff Bradberry還提供了一整套的例子，用python寫的。
board game server
board game client
Tic Tac Toe board
AI implementation of Tic Tac Toe
阿袁工作的第一天 - 蒙特卡羅樹搜索算法 - 游戲的通用接口board 和 player
阿袁看到阿靜最近在學習蒙特卡羅樹搜索算法。急忙湊上去問：“蒙特卡羅樹搜索算法是干什么用的？”
"蒙特卡羅樹搜索算法是一種方法（或者說框架），用于解決完美信息博弈。我現(xiàn)在學習一個蒙特卡羅樹搜索算法的變種：UCT算法，用于提供一種通用的游戲對弈解決算法。"
注: perfect information games (完美信息)博弈，指的是沒有任何信息被隱藏的游戲。
"通用的游戲對弈算法，是對任何游戲都有效，是嗎？"
"簡單的說，是這樣的。重要的一點是，算法并不用了解游戲的領域知識。"
"領域知識？不是很好理解。難道連游戲規(guī)則也不知道，就可以贏嗎？"
"游戲的領域知識。舉個例子，國際象棋中每個棋子的子力，比如皇后的子力是10，車是5等等。這些就是領域知識。在通用的情況下，馬的走法-這樣的規(guī)則，也算是領域知識。"
"有點糊涂了！AI算法該如何下子呢？"
"用面向對象的邏輯來說，我們可以給游戲定義有一個通用接口(board)，具體的游戲只能實現(xiàn)這個接口，不能提供其它的信息。"
"對于程序猿來說，這就容易理解多了。我們可以先看看這個接口(board)，都應該定義什么樣屬性和方法。"
"首先，有一個num_players屬性，返回游戲的玩家數(shù)。"
"嗯，讓我想想，游戲開始的時候，需要一個方法start，啟動一個游戲。"
"很好，這個方法需要返回一個state對象，用于記錄游戲當前的狀態(tài)。state對象的內容，外部是不可知的。使用board自己可以解釋。"
"然后，需要顯示棋盤的狀態(tài)。這樣，board就需要提供一個display方法，返回當前的狀態(tài)或者是棋盤狀態(tài)。"
"對。應該有個方法返回誰是該下子的玩家:current_player."
"當前玩家是一個AI玩家（也就是對弈算法的使用者），怎么知道如何下子呢？這里需要許多的領域知識吧？"
"一個技巧是讓board根據(jù)歷史的狀態(tài)列表，返回當前允許的所有下法
