蒙特卡洛树搜索算法(UCT): 一个程序猿进化的故事

[comment]: # 蒙特卡洛树搜索算法(UCT): 一个程序猿进化的故事

前言:

本文是根据的文章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

阿袁看到阿静最近在学习蒙特卡罗树搜索算法。急忙凑上去问:“蒙特卡罗树搜索算法是干什么用的?”

"蒙特卡罗树搜索算法是一种方法(或者说框架),用于解决完美信息博弈。我现在学习一个蒙特卡罗树搜索算法的变种:UCT算法,用于提供一种通用的游戏对弈解决算法。"

注: perfect information games (完美信息)博弈,指的是没有任何信息被隐藏的游戏。

"通用的游戏对弈算法,是对任何游戏都有效,是吗?"

"简单的说,是这样的。重要的一点是,算法并不用了解游戏的领域知识。"

"领域知识?不是很好理解。难道连游戏规则也不知道,就可以赢吗?"

"游戏的领域知识。举个例子,国际象棋中每个棋子的子力,比如皇后的子力是10,车是5等等。这些就是领域知识。在通用的情况下,马的走法-这样的规则,也算是领域知识。"

"有点糊涂了!AI算法该如何下子呢?"

"用面向对象的逻辑来说,我们可以给游戏定义有一个通用接口(board),具体的游戏只能实现这个接口,不能提供其它的信息。"

"对于程序猿来说,这就容易理解多了。我们可以先看看这个接口(board),都应该定义什么样属性和方法。"

"首先,有一个num_players属性,返回游戏的玩家数。"

"嗯,让我想想,游戏开始的时候,需要一个方法start,启动一个游戏。"

"很好,这个方法需要返回一个state对象,用于记录游戏当前的状态。state对象的内容,外部是不可知的。使用board自己可以解释。"

"然后,需要显示棋盘的状态。这样,board就需要提供一个display方法,返回当前的状态或者是棋盘状态。"

"对。应该有个方法返回谁是该下子的玩家:current_player."

"当前玩家是一个AI玩家(也就是对弈算法的使用者),怎么知道如何下子呢?这里需要许多的领域知识吧?"

"一个技巧是让board根据历史的状态列表,返回当前允许的所有下法:legal_actions。"

"再加上一个is_legal(action),来判断一个下法是否合适。"

"下来应该是根据现在的action,返回下一个游戏状态,next_state。"

"为了判断胜负,需要一个winner方法。"

"如果有了赢家,board需要返回一个winner_message信息。通知玩家谁胜了。"

"看起来不错!我们总结一下board接口的内容。"

class Board(object):
'''
Define general rules of a game.
State: State is an object which is only be used inside the board class.
Normally, a state include game board information (e.g. chessmen positions, action index, current action, current player, etc.)
Action: an object to describe a move.
''' '''
num_players: The player numbers of the board.
'''
num_players = 2 def start(self):
'''
Start the game
Return: the initial state
'''
return None def display(self, state, action, _unicode=True):
'''
Dispaly the board
state: current state
action: current action
Return: display information
'''
return None def parse(self, action):
'''
Parse player input text into an action.
If the input action is invalid, return None.
The method is used by a human player to parse human input.
action: player input action texxt.
Return: action if input is a valid action, otherwise None.
'''
return None def next_state(self, state, action):
'''
Calculate the next state base on current state and action.
state: the current state
action: the current action
Return: the next state
'''
return tuple(state) def is_legal(self, history, action):
'''
Check if an action is legal.
The method is used by a human player to validate human input.
history: an array of history states.
Return: ture if the action is legal, otherwise return false.
'''
return (R, C) == (state[20], state[21]) def legal_actions(self, history):
'''
Calculate legal action from history states.
The method is mainly used by AI players.
history: an array of history states.
Return: an array of legal actions.
'''
return actions def current_player(self, state):
'''
Gets the current player.
state: the current state.
Return: the current player number.
'''
return None def winner(self, history):
'''
Gets the win player.
history: an array of history states.
Return: win player number. 0: no winner and no end, players numbers + 1: draw.
'''
return 0 def winner_message(self, winner):
'''
Gets game result.
winner: win player number
Return: winner message, the game result.
'''
return ""

"另外,我们需要定义一个player接口,玩家主要是下子,所以需要一个get_action方法。"

"当一个玩家下完子后,需要通过一个update方法通知所有的玩家,状态要更新了。"

class Player(object):
def update(self, state):
'''
Update current state into all states.
state: the current state.
'''
self.states.append(state) def display(self, state, action):
'''
Display board.
state: the current state.
action: the current action.
Return: display information.
'''
return self.board.display(state, action) def winner_message(self, msg):
'''
Display winner message.
msg: winner infomation
Return: winner message
'''
return self.board.winner_message(msg) def get_action(self):
'''
Get player next action.
Return: the next action.
'''
return action

注:方法: diplay and winner_message用于向游戏的客户端提供board的信息。这样隔离了客户端和board。

阿袁工作的第2天 - 蒙特卡罗树搜索算法 - MonteCarlo Player

阿袁和阿静继续关于蒙特卡罗树搜索算法的讨论。

阿静说道,“在编写一个人工智能游戏对弈的应用中,至少需要两个具体的player,一个是human player,一个是MonteCarlo player。”

"human player向人类玩家提供了一个交互界面。"

“对,MonteCarlo player是一个AI player,也是我们要讨论的重点,MonteCarlo player在实现get_action中,通过board,模拟后面可能下法;并根据模拟的结果,获得一个最优的下法。”

"我们先从一个简单的问题开始:一个游戏下法的组合可能是一个很大的数,我们如何控制这个模拟行为是满足一定时间上的限制的。"

“对于这个问题,解决方法有一些。这里,我们允许一个参数calculation_time来控制时间。每次模拟一条路径,模拟完后,检测一下是否到时。”

“一条路径就是从游戏的当前状态到对局结束的所有步骤。如果这些步骤太长了呢?”

“尽管游戏的下法组合数会很大。但是一个游戏的正常步骤却不会很大哦。我们也可以通过另外一个参数max_actions来控制。”

“明白了。代码大概是这个样子。”

class MonteCarlo(object):

    def __init__(self, board, **kwargs):
# ... self.calculation_time = float(kwargs.get('time', 30))
self.max_actions = int(kwargs.get('max_actions', 1000)) # ... def get_action(self):
# ... # Control period of simulation
moves = 0
begin = time.time()
while time.time() - begin < self.calculation_time:
self.run_simulation()
moves += 1 # ... def run_simulation(self):
# ... # Control number of simulation actions
for t in range(1, self.max_actions + 1):
# ... # ...

注:为了易于理解,我简单地重构了源代码,主要是rename了一些变量名。

"今天时间有些紧张,明天我们讨论蒙特卡罗树搜索的步骤"

阿袁工作的第3天 - 蒙特卡罗树搜索 - 蒙特卡罗树搜索的步骤

阿袁昨天晚上,也好好学习了蒙特卡罗树搜索。今天,他开始发言。

"蒙特卡罗树搜索是一个方法,应该是来自于蒙特卡罗方法。这个方法定义了几个步骤,用于找到最优的下法。"

“严格的说,蒙特卡罗树搜索并不是一个算法。”

“是的。所以蒙特卡罗树搜索有很多变种,我们现在学习的算法是蒙特卡罗树搜索算法的一个变种:信任度上限树(Upper Confidence bound applied to Trees(UCT))。这个我们明天研究。”

“好,今天主要了解蒙特卡罗树搜索方法的步骤

"从文章上看一共有四个步骤。"

"是的。分别是选举(selection),扩展(expansion),模拟(simulation),反向传播(Back-Propagation)。"

“我们看看这张图。绿色部分是蒙特卡罗树搜索的四个步骤。”


Monte Carlo Tree Search Steps

Monte Carlo Tree Search Steps
cluster0

Loop: limit simulation period time.
One loop one path.

cluster0

Loop: limit max actions.
One loop one action.


Start

Start


reach_time_limitation

Reach time limitation?


Start->reach_time_limitation


End

End


loop_meet_max_actions

Meet max actions?


reach_time_limitation->loop_meet_max_actions

no


select_best_action

Select the best action and return


reach_time_limitation->select_best_action

yes


back_propagation
Back-Propagation


back_propagation->reach_time_limitation


loop_meet_max_actions->back_propagation

yes


get_children_actions

Get children actions


loop_meet_max_actions->get_children_actions

no


meet_selection_criteria

Meet selection criteria?


get_children_actions->meet_selection_criteria


selection
Selection


meet_selection_criteria->selection

yes


expansion
Expansion


meet_selection_criteria->expansion

no


simulation
Simulation


selection->simulation


expansion->simulation


has_winner

Has Winner?


simulation->has_winner


has_winner->back_propagation

yes


has_winner->loop_meet_max_actions

no


select_best_action->End

“**选举(selection)**是根据当前获得所有子步骤的统计结果,选择一个最优的子步骤。”
“**扩展(expansion)**在当前获得的统计结果不足以计算出下一个步骤时,随机选择一个子步骤。”
“**模拟(simulation)**模拟游戏,进入下一步。”
“**反向传播(Back-Propagation)**根据游戏结束的结果,计算对应路径上统计记录的值。”
“从上面这张图可以看出,选举的算法很重要,这个算法可以说是来评价每个步骤的价值的。”
“好了。今天,我们了解了蒙特卡罗树搜索的步骤。”
“明天,可以学习Upper Confidence bound applied to Trees(UCT) - 信任度上限树算法。”

阿袁工作的第4天 - 蒙特卡罗树搜索 - Upper Confidence bound applied to Trees(UCT) - 信任度上限树算法

一开始,阿静就开始讲到。

“信任度上限树算法UCT是根据统计学的信任区间公式,来计算一个步骤的价值。这个方法比较简单,只需要每个步骤的访问数和获胜数就可以了。”

“信任区间公式的是什么呢?”

阿静写下信任区间公式。

置信区间(confidence intervals)

\[\bar{x}_i \pm \sqrt{\frac{z\ln{n}}{n_i}} \\
where: \\
\qquad \bar{x}_i \text{ : the mean of choose i.} \\
\qquad n_i \text{ : the number of plays of choose i.} \\
\qquad n \text{ : the total number of plays.} \\
\qquad z \text{ : 1.96 for 95% confidence level.}
\]

阿静进一步解释道。

“置信区间是一个统计上的计算值,如果z使用1.96,可以使置信区间的置信度达到95%。也就是说:有95%的信心,样本的平均值在置信区间内。”

“UCT算法使用了置信区间的上限值做为每个步骤的价值。”

“使用置信区间的上限值带来的一个好处是:如果当前选择的最优子步骤在多次失败的模拟后,这个值会变小,从而导致另一个同级的子步骤可能会变得更优。”

“另外一个关键点是选举的条件,文章中的选举条件是当前所有子步骤都有了统计记录(也就是至少访问了一次,有了访问数。)。”

阿袁工作的第5天 - 蒙特卡罗树搜索 - 图形化模拟 Upper Confidence bound applied to Trees(UCT) - 信任度上限树算法

阿袁今天做了一天功课,画了一些图来说明UCT算法的过程。

  • 首先,初始状态下,所有的子步骤都没有统计数据。

Monte Carlo Tree Search Steps - Initialize State

Monte Carlo Tree Search Steps - Initialize State
No statistics records for all children actions.

L0

C


L1_1


L0->L1_1


L1_2


L0->L1_2


L1_3


L0->L1_3


L1_4


L0->L1_4

  • 所以,先做扩展(Expansion),随机选择一个子步骤,不停的模拟(Simulation),直到游戏结束。然后反向传播(Back-Propagation),记录扩展步骤的统计数据。

Monte Carlo Tree Search Steps

Monte Carlo Tree Search Steps - Expansion

L0

C


L1_1


L0->L1_1


L1_2

0/1


L0->L1_2


L1_3


L0->L1_3


L1_4


L0->L1_4


L1_2_1


L1_2->L1_2_1


L1_2_1_1


L1_2_1->L1_2_1_1


L1_2_1_1_1

Lose


L1_2_1_1->L1_2_1_1_1

  • 多次扩展(Expansion)之后,达到了选举(selection)的条件,开始选举(selection),选出最优的一个子步骤。

Monte Carlo Tree Search Steps - Selection

Monte Carlo Tree Search Steps - Selection
After some expansions, all children actions are recorded.
Select the one with max win rate.

L0

C


L1_1

2/5


L0->L1_1


L1_2

3/4


L0->L1_2


L1_3

0/1


L0->L1_3


L1_4

4/6


L0->L1_4

  • 继续扩展(Expansion)模拟(Simulation)反向传播(Back-Propagation)

    下图说明以前最优的子步骤,可能在多次扩展后,发生变化。

Monte Carlo Tree Search Steps - More Expansion, Simulation and Back-Propagation

Monte Carlo Tree Search Steps - More Expansion, Simulation and Back-Propagation
Would lead the best action is changed to another one.

L0

C


L1_1

2/5


L0->L1_1


L1_2

3/5


L0->L1_2


L1_3

0/1


L0->L1_3


L1_4

4/6


L0->L1_4


L1_2_1

0/1


L1_2->L1_2_1


L1_2_1_1


L1_2_1->L1_2_1_1


L1_2_1_1_1

Lose


L1_2_1_1->L1_2_1_1_1

阿袁的日记

2016年10月X日 星期六

这周和阿静一起学习了蒙特卡罗树搜索的一些知识。基本上了解了蒙特卡罗树搜索的步骤和使用方法。

发现在使用蒙特卡罗树搜索方法中,有许多可以优化的地方。比如:

  • 步骤价值计算
    • 是否可以在没有赢的情况下,计算价值?
    • 是否可以计算一个步骤是没有价值的,因而可以及早的砍掉它。

还有许多问题:

  • 是否AI程序可以理解规则?比如,理解马走日。
  • 是否AI程序可以算出一些领域规则。开局的方法、子力计算等。

参考

上一篇:9.18碎碎念


下一篇:一款用于对 WiFi 接入点安全进行渗透测试的工具