首页 > 搜索 > 信任度上限树算法,蒙特卡洛树搜索算法(UCT): 一个程序猿进化的故事

信任度上限树算法,蒙特卡洛树搜索算法(UCT): 一个程序猿进化的故事

互联网 2020-10-21 03:48:19
在线算命,八字测算命理

前言:

本文是根据的文章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 StepsMonte Carlo Tree Search Stepscluster0Loop: limit simulation period time. One loop one path.cluster0Loop: limit max actions. One loop one action.StartStartreach_time_limiattionReach time limiattion?Start->reach_time_limiattionEndEndloop_meet_max_actionsMeet max actions?reach_time_limiattion->loop_meet_max_actionsnoselect_best_actionSelect the best action and returnreach_time_limiattion->select_best_actionyesback_propagationback_propagation->reach_time_limiattionloop_meet_max_actions->back_propagationyesget_children_actionsGet children actionsloop_meet_max_actions->get_children_actionsnomeet_selection_criteriaMeet selection criteria?get_children_actions->meet_selection_criteriaselectionmeet_selection_criteria->selectionyesexpansionmeet_selection_criteria->expansionnosimulationselection->simulationexpansion->simulationhas_winnerHas Winner?simulation->has_winnerhas_winner->back_propagationyeshas_winner->loop_meet_max_actionsnoselect_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)

xˉi±zlnnni?????√where:xˉi : the mean of choose i.ni : the number of plays of choose i.n : the total number of plays.z : 1.96 for 95% confidence level.(1)(1)xˉi±zln?nniwhere:xˉi : the mean of choose i.ni : the number of plays of choose i.n : the total number of plays.z : 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 StateMonte Carlo Tree Search Steps - Initialize State No statistics records for all children actions.L0CL1_1L0->L1_1L1_2L0->L1_2L1_3L0->L1_3L1_4L0->L1_4

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

Monte Carlo Tree Search StepsMonte Carlo Tree Search Steps - ExpansionL0CL1_1L0->L1_1L1_20/1L0->L1_2L1_3L0->L1_3L1_4L0->L1_4L1_2_1L1_2->L1_2_1L1_2_1_1L1_2_1->L1_2_1_1L1_2_1_1_1LoseL1_2_1_1->L1_2_1_1_1

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

Monte Carlo Tree Search Steps - SelectionMonte Carlo Tree Search Steps - Selection After some expansions, all children actions are recorded. Select the one with max win rate.L0CL1_12/5L0->L1_1L1_23/4L0->L1_2L1_30/1L0->L1_3L1_44/6L0->L1_4

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

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

Monte Carlo Tree Search Steps - More Expansion, Simulation and Back-PropagationMonte Carlo Tree Search Steps - More Expansion, Simulation and Back-Propagation Would lead the best action is changed to another one.L0CL1_12/5L0->L1_1L1_23/5L0->L1_2L1_30/1L0->L1_3L1_44/6L0->L1_4L1_2_10/1L1_2->L1_2_1L1_2_1_1L1_2_1->L1_2_1_1L1_2_1_1_1LoseL1_2_1_1->L1_2_1_1_1

阿袁的日记

2016年10月X日 星期六

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

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

步骤价值计算是否可以在没有赢的情况下,计算价值?

是否可以计算一个步骤是没有价值的,因而可以及早的砍掉它。

还有许多问题:

是否AI程序可以理解规则?比如,理解马走日。

是否AI程序可以算出一些领域规则。开局的方法、子力计算等。

参考

Introduction to Monte Carlo Tree Search by Jeff Bradberry

Confidence interval

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多