精华内容
下载资源
问答
  • 2021-12-08 23:02:42

    阿尔法狗下棋的时候,做决策的不是策略网络和价值网络,而是蒙特卡洛树搜索(Monte Carlo Tree Search, MCTS)。

    训练好的策略网络和价值网络均能单独地直接做决策。MCTS不需要训练,也可以单独地直接做决策。在阿尔法狗中,训练策略网络和价值网络的目的是辅助MCTS,降低MCTS的深度和宽度。

    在机巧围棋中,除阿尔法狗之外,还分别集成了策略网络、价值网络和蒙特卡洛落子策略,可以任意更改黑白双方的落子策略,查看不同落子策略之间的效果。

    1. MCTS的基本思想

    人类玩家下围棋时,通常会往前看几步,越是高手,看的越远。与此同时,人类玩家不会分析棋盘上所有不违反规则的走法,而只会针对性地分析几个貌似可能的走法。

    假如现在该我放置棋子了,我会这样思考:现在貌似有几个可行的走法,如果我的动作是 a t = 234 a_t=234 at=234,对手会怎么走呢?假如对手接下来将棋子放在 a ′ = 30 a^\prime=30 a=30的位置上,那我下一步动作 a t + 1 a_{t+1} at+1应该是什么呢?

    人类玩家在做决策之前,会在大脑里面进行推演,确保几步以后很可能会占优势。同样的道理,AI下棋时候,也应该枚举未来可能发生的情况,从而判断当前执行什么动作的胜算更大。这样做远好于使用策略网络直接算出一个动作。

    MCTS的基本原理就是向前看,模拟未来可能发生的情况,从而找出当前最优的动作。这种向前看不是遍历所有可能的情况,而是与人类玩家类似,只遍历几种貌似可能的走法,而哪些动作是貌似可行的动作以及几步之后的局面优劣情况是由神经网络所决定的。阿尔法狗每走一步棋,都要用MCTS做成千上万次模拟,从而判断出哪个动作的胜算更大,并执行胜算最大的动作。

    2. 阿尔法狗2016版中的MCTS(MCTS in AlphaGo)

    在阿尔法狗2016版本中,MCTS的每一次模拟分为4个步骤:选择(selection)、扩展(expansion)、求值(evaluation)和回溯(backup)。

    2.1 选择(Selection)

    给定棋盘上的当前格局,可以确定所有符合围棋规则的可落子位置,每个位置对应一个可行的动作。在围棋中,每一步很有可能存在几十甚至上百个可行的动作,挨个搜索和评估所有可行的动作,计算量会大到无法承受。人类玩家做决策前,在大脑里面推演的时候不会考虑所有可行的动作,只会考虑少数几个认为胜算较高的动作。

    MCTS第一步【选择】的目的就是找出胜算较高的动作,只搜索这些好的动作,忽略掉其它的动作。

    判断动作 a a a的好坏有两个指标:第一,动作 a a a的胜率;第二,策略网络给动作 a a a的评分(概率值)。结合这两个指标,用下面的公式评价动作 a a a的好坏:
    s c o r e ( a ) ≜ Q ( a ) + η 1 + N ( a ) ⋅ π ( a ∣ s ; θ )                                     ( 1 ) score(a)\triangleq{Q(a)}+\frac{\eta}{1+N(a)}\cdot\pi(a|s;\theta)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(1) score(a)Q(a)+1+N(a)ηπ(as;θ)                                   (1)
    其中:

    • N ( a ) N(a) N(a)是动作 a a a已经被访问过的次数。初始时,对于所有 a a a,令 N ( a ) ← 0 N(a)\gets{0} N(a)0。动作 a a a每被选中一次,就把 N ( a ) N(a) N(a)的值加1: N ( a ) ← N ( a ) + 1 N(a)\gets{N(a)+1} N(a)N(a)+1

    • Q ( a ) Q(a) Q(a)是之前 N ( a ) N(a) N(a)次模拟算出来的动作价值,主要由胜率和价值函数决定。 Q ( a ) Q(a) Q(a)的初始值是0,动作 a a a每被选中一次,就会更新一次 Q ( a ) Q(a) Q(a)

    • η \eta η是一个超参数,需要手动调整;

    • π ( a ∣ s ; θ ) \pi(a|s;\theta) π(as;θ)是策略网络对动作 a a a的评分。

    可以这样理解上述公式(1):

    • 如果动作 a a a还没有被选中过,则 Q ( a ) Q(a) Q(a) N ( a ) N(a) N(a)均等于0,因此 s c o r e ( a ) ∝ π ( a ∣ s ; θ ) score(a)\propto{\pi(a|s;\theta)} score(a)π(as;θ),即完全由策略网络评价动作 a a a的好坏;
    • 如果动作 a a a已经被选中过很多次,则 N ( a ) N(a) N(a)会很大,因此策略网络给动作 a a a的评分在 s c o r e ( a ) score(a) score(a)中的权重会降低。当 N ( a ) N(a) N(a)很大的时候,有 s c o r e ( a ) ≈ Q ( a ) score(a)\approx{Q(a)} score(a)Q(a),即此时主要基于 Q ( a ) Q(a) Q(a)判断 a a a的好坏,策略网络给动作 a a a的评分已经无关紧要了;
    • 系数 η 1 + N ( a ) \frac{\eta}{1+N(a)} 1+N(a)η的另一个作用是鼓励探索。如果两个动作有相近的 Q Q Q分数和 π \pi π分数,那么被选中次数少的动作的 s c o r e score score会更高,也就是让被选中次数少的动作有更多的机会被选中。

    给定某个状态 s s s,对于所有可行的动作,MCTS会使用公式(1)算出所有动作的分数 s c o r e ( a ) score(a) score(a),找到分数最高的动作,并在这轮模拟中,执行这个动作(选择出的动作只是在模拟器中执行,类似于人类玩家在大脑中推演,并不是阿尔法狗真正走的一步棋)。

    2.2 扩展(Expansion)

    将第一步选中的动作记为 a t a_t at,在模拟器中执行动作 a t a_t at,环境应该根据状态转移函数 p ( s k + 1 ∣ s k , a k ) p(s_{k+1}|s_k,a_k) p(sk+1sk,ak)返回给阿尔法狗一个新的状态 s t + 1 s_{t+1} st+1

    假如阿尔法狗执行动作 a t a_t at,对手并不会告诉阿尔法狗他会执行什么动作,因此阿尔法狗只能自己猜测对手的动作,从而确定新的状态 s t + 1 s_{t+1} st+1。和人类玩家一样,阿尔法狗可以推己及人:如果阿尔法狗认为几个动作很好,那么就假设对手也怎么认为。所以阿尔法狗用策略网络模拟对手,根据策略网络随机抽样一个动作:
    a t ′ ∼ π ( ⋅ ∣ s t ′ ; θ )                               ( 2 ) a_t^\prime\sim\pi(\cdot|s_t^\prime;\theta)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(2) atπ(st;θ)                             (2)
    此处的状态 s t ′ s_t^\prime st是站在对手的角度观测到的棋盘上的格局,动作 a t ′ a_t^\prime at是假想的对手选择的动作。

    进行MCTS需要模拟阿尔法狗和对手对局,阿尔法狗每执行一个动作 a k a_k ak,环境应该返回一个新的状态 s k + 1 s_{k+1} sk+1。围棋游戏具有对称性,阿尔法狗的策略,在对手看来是状态转移函数;对手的策略,在阿尔法狗看来是状态转移函数。最理想情况下,模拟器的状态转移函数是对手的真实策略,然而阿尔法狗并不知道对手的真实策略,因此阿尔法狗退而求其次,用自己训练出的策略网络 π \pi π代替对手的策略,作为模拟器的状态转移函数。

    2.3 求值(Evaluation)

    从状态 s t + 1 s_{t+1} st+1开始,双方都用策略网络 π \pi π做决策,在模拟器中交替落子,直至分出胜负(见图一)。阿尔法狗基于状态 s k s_k sk,根据策略网络抽样得到动作:
    a k ∼ π ( ⋅ ∣ s k ; θ )                               ( 3 ) a_k\sim\pi(\cdot|s_k;\theta)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(3) akπ(sk;θ)                             (3)
    对手基于状态 s k ′ s_k^\prime sk(从对手角度观测到的棋盘上的格局),根据策略网络抽样得到动作:
    a k ′ ∼ π ( ⋅ ∣ s k ′ ; θ )                               ( 4 ) a_k^\prime\sim\pi(\cdot|s_k^\prime;\theta)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(4) akπ(sk;θ)                             (4)
    模拟对局直至分出胜负,可以观测到奖励 r r r。如果阿尔法狗胜利,则 r = + 1 r=+1 r=+1,否则 r = − 1 r=-1 r=1

    1

    综上所述,棋盘上真实的状态是 s t s_t st,阿尔法狗在模拟器中执行动作 a t a_t at,然后模拟器中的对手执行动作 a t ′ a_t^\prime at,带来新的状态 s t + 1 s_{t+1} st+1。对于阿尔法狗来说,如果状态 s t + 1 s_{t+1} st+1越好,则这局游戏胜算越大,因此:

    • 如果阿尔法狗赢得了这局模拟( r = + 1 r=+1 r=+1),则说明 s t + 1 s_{t+1} st+1可能很好;如果输了( r = − 1 r=-1 r=1),则说明可能不好。因此,奖励 r r r可以反映出 s t + 1 s_{t+1} st+1的好坏。
    • 此外,还可以使用价值网络评价状态 s t + 1 s_{t+1} st+1的好坏。价值 v ( s t + 1 ; ω ) v(s_{t+1};\omega) v(st+1;ω)越大,则说明状态 s t + 1 s_{t+1} st+1越好。

    奖励 r r r是模拟对局获得的胜负,是对 s t + 1 s_{t+1} st+1很可靠的评价,但是随机性很大。价值网络的评估 v ( s t + 1 ; ω ) v(s_{t+1};\omega) v(st+1;ω)没有 r r r可靠,但是价值网络更稳定,随机性小。阿尔法狗将奖励 r r r与价值网络的输出 v ( s t + 1 ; ω ) v(s_{t+1};\omega) v(st+1;ω)取平均,作为对状态 s t + 1 s_{t+1} st+1的评价,记作: V ( s t + 1 ) ≜ r + v ( s t + 1 ; w ) 2 V(s_{t+1})\triangleq\frac{r+v(s_{t+1;w})}{2} V(st+1)2r+v(st+1;w)

    使用策略网络交替落子,直至分出胜负,通常要走一两百步。在实际实现时候,阿尔法狗训练了一个更小的神经网络(称为快速走子网络)来代替大的策略网络,以加速MCTS。

    2.4 回溯(Backup)

    第三步【求值】计算出了 t + 1 t+1 t+1步某一个状态的价值,记作 V ( s t + 1 ) V(s_{t+1}) V(st+1)。每一次模拟都会得出这样一个价值,并且记录下来。模拟会重复很多次,于是第 t + 1 t+1 t+1步每一种状态下面可以有多条记录,如图二所示。

    2

    t t t步的动作 a t a_t at下面有多个可能的状态(子节点),每个状态下面有若干条记录。把 a t a_t at下面所有的记录取平均,记为价值 Q ( a t ) Q(a_t) Q(at),它可以反映出动作 a t a_t at的好坏。

    给定棋盘上真实的状态 s t s_t st,有多个可行的动作 a a a可供选择。对于所有的 a a a,价值 Q ( a ) Q(a) Q(a)的初始值为0。动作 a a a每被选中一次(成为 a t a_t at),它下面就会多一条记录,我们就对 Q ( a ) Q(a) Q(a)做一次更新。

    2.5 MCTS的决策

    上述4个步骤为一次MCTS的流程,MCTS想要真正做出一个决策(即往真正的棋盘上落一个棋子),需要做成千上万次模拟。在无数次模拟之后,MCTS做出真正的决策:
    a t = a a r g m a x   N ( a )                               ( 5 ) a_t=\overset{argmax}{_a}~N(a)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(5) at=aargmax N(a)                             (5)
    此时阿尔法狗才会真正往棋盘上放一个棋子。

    为什么要依据 N ( a ) N(a) N(a)来做决策呢?

    在每一次模拟中,MCTS找出所有可行的动作 { a } \{a\} {a},计算他们的分数 s c o r e ( a ) score(a) score(a),然后选择其中分数最高的动作,并在模拟器中执行。如果某个动作 a a a在模拟时胜率很大,那么它的价值 Q ( a ) Q(a) Q(a)就会很大,它的分数 s c o r e ( a ) score(a) score(a)会很高,于是它被选中的几率就很大。也就是说如果某个动作 a a a很好,他被选中的次数 N ( a ) N(a) N(a)就会大。

    观测到棋盘上当前状态 s t s_t st,MCTS做成千上万次模拟,记录每个动作 a a a被选中的次数 N ( a ) N(a) N(a),最终做出决策 a t = a a r g m a x   N ( a ) a_t=\overset{argmax}{_a}~N(a) at=aargmax N(a)。到了下一时刻,状态变成了 s t + 1 s_{t+1} st+1,MCTS会把所有动作 a a a Q ( a ) Q(a) Q(a) N ( a ) N(a) N(a)全都初始化为0,然后从头开始做模拟,而不能利用上一次的结果。

    3. 零狗中的MCTS(MCTS in AlphaGo Zero)

    零狗中对MCTS进行了简化,放弃了快速走子网络,合并了【扩展】和【求值】,并且更改了【选择】和【决策】逻辑。零狗中维护了一个蒙特卡洛搜索树,搜索树的每一个节点保存了 N ( s , a ) N(s,a) N(s,a)(节点访问次数)、 W ( s , a ) W(s,a) W(s,a)(合计动作价值)、 Q ( s , a ) Q(s,a) Q(s,a)(平均动作价值)和 P ( s , a ) P(s,a) P(s,a)(选择该节点的先验概率)。每一次模拟会遍历一条从搜索树根结点到叶节点的路径。

    3

    如图三所示,零狗中每一次MCTS共有三个流程:

    • 选择(Select):

      在选择阶段,从搜索树的根节点开始,不断选择 a c = a a r g m a x   ( Q ( s , a ) + U ( s , a ) ) a_c=\overset{argmax}{_a}~\bigg(Q(s,a)+U(s,a)\bigg) ac=aargmax (Q(s,a)+U(s,a)),其中 U ( s , a ) = c p u c t P ( s , a ) ∑ b N ( s , b ) 1 + N ( s , a ) U(s,a)=c_{puct}P(s,a)\frac{\sqrt{\sum_bN(s,b)}}{1+N(s,a)} U(s,a)=cpuctP(s,a)1+N(s,a)bN(s,b) ,直至搜索树的叶节点终止。

      s s s:为搜索树的一个节点代表的棋局状态;

      a a a:表示某一个可行的动作;

      N ( s , a ) N(s,a) N(s,a):表示状态 s s s下可行动作 a a a被选中的次数;

      P ( s , a ) P(s,a) P(s,a):为状态 s s s下的可行动作 a a a的先验概率;

      Q ( s , a ) Q(s,a) Q(s,a):表示状态 s s s下可行动作 a a a的动作价值;

      c p u c t c_{puct} cpuct:为一个决定探索程度超参数。

    • 拓展和求值(Expand and evaluate):

      选择阶段,在搜索树中不断选择 Q + U Q+U Q+U最大的动作,直至游戏结束或某一个不是终局的叶结点。如果到了不是终局的叶结点 l l l,对于 l l l对应的棋局状态 s s s,使用策略网络和价值网络对状态 s s s进行评估,得到 l l l对应棋局状态 s s s下一步各个可能动作的概率 p p p l l l的价值 v v v。为所有可能动作对应的棋局状态分别创建一个节点,将这些节点的先验概率设置为策略网络的输出概率值。

    • 回溯(Backup):

      进过上述扩展之后,之前的叶子节点 l l l,现在变成了内部节点。做完了扩展和求值后,从节点 l l l开始,逐层向搜索树根节点回溯,并依次更新搜索树当次被遍历的路径上各层节点的信息:
      N ( s n , a n ) = N ( s n , a n ) + 1 W ( s n , a n ) = W ( s n , a n ) + v n Q ( s n , a n ) = W ( s n , a n ) N ( s n , a n ) N(s_n,a_n)=N(s_n,a_n)+1\\ W(s_n,a_n)=W(s_n,a_n)+v_n\\ Q(s_n,a_n)=\frac{W(s_n,a_n)}{N(s_n,a_n)} N(sn,an)=N(sn,an)+1W(sn,an)=W(sn,an)+vnQ(sn,an)=N(sn,an)W(sn,an)

      s n s_n sn:表示搜索树中当次被遍历路径上节点对应的棋局状态;
      a n a_n an:表示搜索树中当次被遍历路径上节点对应棋局状态下选择的动作;
      v n v_n vn:表示搜索树中当次被遍历路径上节点的价值,由于搜索树中相邻两层的落子方是不同的,因此相邻两层的节点价值互为相反数。

    上述三个流程为零狗中的一次MCTS模拟,在零狗往真正的棋盘上落一个棋子之前,会进行1600次模拟。在上千次MCTS完成之后,MCTS基于下述公式做出真正的决策:
    π ( a ∣ s ) = N ( s , a ) 1 / τ ∑ b N ( s , b ) 1 / τ                               ( 6 ) \pi(a|s)=\frac{N(s,a)^{1/\tau}}{\sum_bN(s,b)^{1/\tau}}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(6) π(as)=bN(s,b)1/τN(s,a)1/τ                             (6)

    τ \tau τ为温度参数,控制探索的程度。 τ \tau τ越大,不同走法间差异变小,探索比例增大。反之,则更多选择当前最优操作。在零狗中,每一次自我对弈的前30步,参数 τ = 1 \tau=1 τ=1,即早期鼓励探索。游戏剩下的步数,该参数将逐渐降低至0。如果是比赛,则直接为0。

    4. MCTS的程序实现

    机巧围棋是基于AlphaGo Zero算法的一款点击按钮就能可视化训练围棋人工智能的程序,机巧围棋中的MCTS与零狗中的MCTS一致,不过不支持多线程搜索,具体代码如下:

    class TreeNode:
        """蒙特卡洛树节点"""
        def __init__(self, parent, prior_p):
            self.parent = parent  # 节点的父节点
            self.children = {}  # 一个字典,用来存节点的子节点
            self.n_visits = 0  # 节点被访问的次数
            self.Q = 0  # 节点的平均行动价值
            self.U = 0  # MCTS选择Q+U最大的节点,公式里的U
            self.P = prior_p  # 节点被选择的概率
    
        def select(self, c_puct):
            """
            蒙特卡洛树搜索的第一步:选择
            蒙特卡洛树搜索通过不断选择 最大上置信限Q+U 的子节点,直至一个树的叶结点
            该函数为进行一步选择函数
    
            :param c_puct: 为计算U值公式中的c_puct,是一个决定探索水平的常数
            :return: 返回一个元组(action, next_node)
            """
            return max(self.children.items(),
                       key=lambda act_node: act_node[1].get_value(c_puct))
    
        def expand(self, action_priors):
            """
            当select搜索到一个叶结点,且该叶节点代表的局面游戏没有结束,
            需要expand树,创建一系列可能得节点,即对应节点所有可能选择的动作对应的子节点
    
            :param action_priors: 为一个列表,列表中的每一个元素为一个 特定动作及其先验概率 的元组
            :return:
            """
            for action, prob in action_priors:
                if action not in self.children:
                    self.children[action] = TreeNode(self, prob)
    
        def update(self, leaf_value):
            """
            根据子树的价值更新当前节点的价值
    
            :param leaf_value: 以当前玩家的视角看待得到的子树的价值
            :return:
            """
            self.n_visits += 1  # 当前节点的访问次数+1
            # 更新当前节点的Q值,下述公式可由Q =  W / N 推导得到
            # Q_old = W_old / N_old
            # Q = (W_old + v) / (N_old + 1) = (Q_old * N_old + v) / (N_old + 1)
            self.Q += 1.0 * (leaf_value - self.Q) / self.n_visits
    
        def update_recursive(self, leaf_value):
            """
            跟心所有祖先的Q值及访问次数
    
            :param leaf_value:
            :return:
            """
            if self.parent:  # 如果有父节点,证明还没到根节点
                self.parent.update_recursive(-leaf_value)  # -leaf_value是因为每向上一层,以当前玩家视角,价值反转
            self.update(leaf_value)
    
        def get_value(self, c_puct):
            """
            计算并返回一个节点的 上置信限 评价,即Q+U值
    
            :param c_puct: 为计算U值公式中的c_puct,是一个决定探索水平的常数
            :return:
            """
            self.U = c_puct * self.P * np.sqrt(self.parent.n_visits) / (1 + self.n_visits)
            return self.Q + self.U
    
        def is_leaf(self):
            """
            判断当前节点是否为叶结点
    
            :return:
            """
            return self.children == {}
    
        def is_root(self):
            """
            判断当前节点是否为根节点
    
            :return:
            """
            return self.parent is None
    
    
    class MCTS:
        """蒙特卡洛树搜索主体"""
        def __init__(self, policy_value_fn, c_puct=5, n_playout=10000):
            self.root = TreeNode(None, 1.0)  # 整个蒙特卡洛搜索树的根节点
            # policy_value_fn是一个函数,该函数的输入为game_state,
            # 输出为一个列表,列表中的每一个元素为(action, probability)形式的元组
            self.policy = policy_value_fn
            # c_puct为一个正数,用于控制多块收敛到策略的最大值。这个数越大,意味着越依赖前面的结果。
            self.c_puct = c_puct
            self.n_playout = n_playout
    
        def playout(self, simulate_game_state):
            """
            从根节点不断选择直到叶结点,并获取叶结点的值,反向传播到叶结点的祖先节点
    
            :param simulate_game_state: 模拟游戏对象
            :return:
            """
            node = self.root
            while True:  # 从根节点一直定位到叶结点
                if node.is_leaf():
                    break
                # 贪婪地选择下一步动作
                action, node = node.select(self.c_puct)
                simulate_game_state.step(action)
            # 使用网络来评估叶结点,产生一个每一个元素均为(action, probability)元组的列表,以及
            # 一个以当前玩家视角看待的在[-1, 1]之间的v值
            action_probs, leaf_value = self.policy(simulate_game_state)
            # 检查模拟游戏是否结束
            end, winner = simulate_game_state.game_ended(), simulate_game_state.winner()
            if not end:  # 没结束则扩展
                node.expand(action_probs)
            else:
                if winner == -1:  # 和棋
                    leaf_value = 0.0
                else:
                    leaf_value = (
                        1.0 if winner == simulate_game_state.turn() else -1.0
                    )
            # 更新此条遍历路径上的节点的访问次数和value
            # 这里的值要符号反转,因为这个值是根据根节点的player视角来得到的
            # 但是做出下一步落子的是根节点对应player的对手
            node.update_recursive(-leaf_value)
    
        def get_move_probs(self, game, temp=1e-3, player=None):
            """
            执行n_playout次模拟,并根据子节点的访问次数,获得每个动作对应的概率
    
            :param game: 游戏模拟器
            :param temp: 制探索水平的温度参数
            :param player: 调用该函数的player,用于进行进度绘制
            :return:
            """
            for i in range(self.n_playout):
                if not player.valid:
                    return -1, -1
                if player is not None:
                    player.speed = (i + 1, self.n_playout)
                simulate_game_state = game.game_state_simulator(player.is_selfplay)
                self.playout(simulate_game_state)
            # 基于节点访问次数,计算每个动作对应的概率
            act_visits = [(act, node.n_visits)
                          for act, node in self.root.children.items()]
            acts, visits = zip(*act_visits)
            act_probs = softmax(1.0 / temp * np.log(np.array(visits) + 1e-10))
            return acts, act_probs
    
        def get_move(self, game, player=None):
            """
            执行n_playout次模拟,返回访问次数最多的动作
    
            :param game: 游戏模拟器
            :param player: 调用该函数的player,用于进行进度绘制
            :return: 返回访问次数最多的动作
            """
            for i in range(self.n_playout):
                if not player.valid:
                    return -1
                if player is not None:
                    player.speed = (i + 1, self.n_playout)
                game_state = game.game_state_simulator()
                self.playout(game_state)
            return max(self.root.children.items(), key=lambda act_node: act_node[1].n_visits)[0]
    
        def update_with_move(self, last_move):
            """
            蒙特卡洛搜索树向深层前进一步,并且保存对应子树的全部信息
    
            :param last_move: 上一步选择的动作
            :return:
            """
            if last_move in self.root.children:
                self.root = self.root.children[last_move]
                self.root.parent = None
            else:
                self.root = TreeNode(None, 1.0)
    

    5. 结束语

    本文介绍了阿尔法狗2016版本和零狗中的蒙特卡洛树搜索及其实现,在机巧围棋中也集成了纯蒙特卡洛落子策略(所有可行动作的概率值是随机的,节点的状态价值通过随机落子到游戏终局,根据胜负确定),大家可以在GitHub上clone机巧围棋的代码,体验纯蒙特卡洛落子策略的效果。

    最后,期待您能够给本文点个赞,同时去GitHub上给机巧围棋项目点个Star呀~

    机巧围棋项目链接:https://github.com/QPT-Family/QPT-CleverGo

    更多相关内容
  • Elephant Art是基于卷积神经网络和Monte Carlo搜索的中国象棋引擎。 他还支持UCCI协议。 警告! 大象艺术仍然是Alpha版。 许多组件不完整(包括UCCI,PGN和永久追求)。 我们不保证他将来会采用相同的格式。 在...
  • 该软件使用的神经网络将我方落子、敌方落子、当前落子位置以及当前落子玩家,四个矩阵作为输入数据,加强了网络提取特征的速度和拟合效率,并获取每个点的概率值。在蒙特卡洛树搜索算法中使用了快速落子方式,即标注...
  • 论文、报告形式阐述此算法,近2w字,非常详细、格式标准、可编辑。
  • 基于深度神经网络和蒙特卡罗搜索的神经网络搜索
  • 基于蒙特卡洛树搜索和策略价值网络的AI五子棋算法设计摘要蒙特卡洛树搜索算法五子棋博弈的状态价值函数附1:详细论文说明下载:附2:实现代码下载: 摘要 随着人工智能领域的发展,深度学习、强化学习等算法被广泛...

    摘要

    随着人工智能领域的发展,深度学习、强化学习等算法被广泛应用于解决各种游戏博弈问题,通过训练神经网络来得到各种游戏的人工智能算法,人工智能来到了一个新的发展水平。在此类游戏博弈问题上,其他的方法要么是类似穷举法的搜索算法,它们在有限计算资源的情况下博弈能力较弱;要么是基于机器学习的方法,它们虽然博弈能力强,但是需要花费大量资源,训练和预测时都十分缓慢。因此,在设计此类游戏博弈的算法中,有必要既兼顾计算的时间问题,也兼顾算法的博弈能力的问题。在本次课程设计中,我们使用蒙特卡洛树搜索与深度神经网络来设计一种基于强化学习的AI五子棋算法,实现了从零开始学习五子棋博弈的人工智能算法。其中神经网络是经过设计的策略价值网络; 蒙特卡洛树搜索可根据多次模拟博弈的结果预测最优的移动方案。将五子棋规则与蒙特卡洛树搜索和策略价值网络相结合,蒙特卡洛树搜索使用策略价值网络评估落子位置和选择移动,增强树的搜索强度,提高落子质量,优化自对弈迭代。通过蒙特卡洛树搜索进行自对弈,训练一个神经网络来预测落子选择以及游戏的赢家。最后,该算法与其他方法进行了对比,测试结果表明我们设计的算法在五子棋的对弈上相对于其他方法有着更好的性能以及要求更低的计算资源。

    蒙特卡洛树搜索算法

    蒙特卡洛树搜索是由前里尔第三大学助理教授Rémi Coulom首次提出,并应用于围棋博弈程序Crazy Stone,Crazy Stone成为了第一个达到职业围棋五段水平的人工智能算法[16][17],蒙特卡洛树搜索最主要的目的就是要根据当前的游戏状态给出价值最高的博弈方案。在本章节中会解释蒙特卡洛树搜索的原理与过程,并做详细的分析与介绍。

    • 蒙特卡洛树搜索的基本过程

    蒙特卡洛树搜索算法将采用一种全新的方法去计算最优动作。顾名思义,蒙特卡洛树搜索采用蒙特卡洛方法,以某一状态作为根节点,进行随机模拟,由根节点开始向下扩展博弈树,最后根据模拟结果预测最优的决策方案。蒙特卡洛树搜索的核心是搜索,即沿着博弈树向下模拟并扩展的一组遍历过程。单次遍历从根节点(当前博弈状态)出发,向下选择延伸,直到遇到未完全展开的节点,未完全展开的节点表示其至少有一个未被访问的子节点。遇到未完全展开的节点时,将采用某种策略进行扩展,选择其中一个未被访问过的子节点作为本次模拟的端节点,随后采取反向传播的方法将模拟结果逐级向上更新,直至回到根节点。一旦搜索达到设定的次数上限或时间上限,即停止蒙特卡洛树搜索,根据根节点的子节点所获得的统计量做出最优决策[31]。

    下图展示了蒙特卡洛树搜索的基本过程。蒙特卡洛树搜索由选择(Selection)、扩展(Expansion)、模拟(Simulation)、更新(Backpropagation)四个基本过程组成。

    在这里插入图片描述
    第一步是选择(Selection):这一步会从根节点开始,每次都选一个“最值得搜索的子节点”,一般使用最大置信上界(UCT)选择分数最高的节点,直到来到一个“存在未扩展的子节点”的节点,如图中的 3/3 节点。之所以叫做“存在未扩展的子节点”,是因为这个局面存在未走过的后续着法,也就是MCTS中没有后续的动作可以参考了。这时我们进入第二步。
    第二步是扩展(Expansion),在这个搜索到的存在未扩展的子节点,加上一个0/0的子节点,表示没有历史记录参考。这时我们进入第三步。
    第三步是仿真(Simulation),从上面这个没有试过的着法开始,用一个简单策略比如快速走子策略(Rollout policy)走到底,得到一个胜负结果。快速走子策略一般适合选择走子很快可能不是很精确的策略。因为如果这个策略走得慢,结果虽然会更准确,但由于耗时多了,在单位时间内的模拟次数就少了,所以不一定会棋力更强,有可能会更弱。这也是为什么我们一般只模拟一次,因为如果模拟多次,虽然更准确,但更慢。
    第四步是回溯(Backpropagation), 将我们最后得到的胜负结果回溯加到MCTS树结构上。注意除了之前的MCTS树要回溯外,新加入的节点也要加上一次胜负历史记录,如图最右边所示。

    • 最大置信上界算法

    最大置信上界算法(Upper Confidence Bound Apply to Tree,UCT),是一种博弈树搜索算法,该算法将蒙特卡洛树搜索(Monte-Carlo Tree Search,MCTS)方法与Upper Confidence Bound(UCB)公式结合,极大提高了大规模博弈树在搜索过程中的效率,降低了搜索的空间复杂度。UTC算法可以表示为:
    在这里插入图片描述
    蒙特卡洛树搜索遍历过程中总是优先选择UCT值最大的节点。首先,该函数的对象为节点v及其子节点v(i),它包括两个组件。第一个组件为:
    在这里插入图片描述
    该组件被称为exploitation组件,可以简单理解为博弈获胜的概率,其值为子节点v(i)的总模拟奖励Q(v_i)除以总访问次数N(v_i),即节点v_i的胜率评估结果。我们总是希望优先遍历具有更高胜率的节点,但是一味贪婪最大化胜率评估值会导致偏差。假设仅使用exploitation UCT组件开始蒙特卡洛树搜索。从根节点开始,对子节点进行一次模拟,然后下一步仅访问那些模拟结果至少有一次是赢的节点。第一次模拟结果不幸失败的节点会立刻被舍弃,而那些第一次模拟中获胜的节点会被不断的探索,这导致整个博弈树的展开与首次模拟的位置有着极大的关联,更多潜在的优质策略动作未被足够的探索。因此本文通过某种方式均衡探索和利用,这就是第二个UCT组件exploration:
    在这里插入图片描述
    exploration组件提高了那些未被充分探索的节点被访问到的概率,这些节点被访问到的次数相对较少(N(v_i)较低),exploration随着节点访问量的增加而递减,访问量少的节点有着更高的exploration,从而增大其被选中几率,指引exploration更充分的探索。
    最后,本文使用UCT公式中的参数c来控制exploitation和exploration两个组件之间的权衡。通常c的取值为0.5。

    • 终止蒙特卡洛树搜索

    不难知道,蒙特卡洛树搜索策略的好坏与模拟次数有着直接的关系,模拟的次数越多,搜索的结果越可靠。但是受限于计算资源与时间,模拟不可能一直进行下去。通常情况,算法会设置一个模拟的上限,当从根节点开始模拟到一定盘数时,就停止搜索。随后根据根节点的子节点的访问量N(v_i),选择最佳的动作。

    当使用蒙特卡洛树搜索执行完一个动作时,博弈状态往前推进了一步,新的状态为对手的起始状态。当对手也完成落子时,新的状态即为新一轮蒙特卡洛树搜索的根节点(起始状态)。而如果对手的落子选择在上一次模拟的情况之内,可以从上一轮展开的博弈树中截取相应的子树成为新的博弈树,这样就实现了博弈树模拟结果的复用,提高了模拟的效率。当对手的落子选择不在上一次模拟情况内的时候,则需要构建一颗新的博弈树,上一轮的模拟结果均被舍弃。

    五子棋博弈的状态价值函数

    基于上述分析,本文采用神经网络作为状态价值函数的逼近器,使用蒙特卡洛策略评估方法作为更新方法,神经网络最小化估计值和奖赏的均方误差
    在这里插入图片描述
    由于蒙特卡洛策略评估具有零偏差和高方差,因此本文引入策略函数,以提高决策的正确性及鲁棒性。

    附1:详细论文说明下载:

    https://download.csdn.net/download/weixin_39589455/15465016

    附2:实现代码下载:

    https://download.csdn.net/download/weixin_39589455/15465068

    展开全文
  • 这是使用蒙特卡洛树搜索(MCTS)解决旅行商问题(TSP)的源代码。 纸 如果您想了解更多详细信息,请参阅我们的论文“通过蒙特卡罗树搜索TSP的扩大邻域目标抽样” 。 依存关系 gcc> = 4.8.5 计算平台:Linux 快速...
  • 否是是否初始化根节点...执行神经网络模拟估值游戏结束设置叶子节点胜平负valueb.扩展叶子节点设置该节点value为神经网络预测的valuec.根据value递归反向更新父节点和自身的Q和u执行真实移动当前节点作为根节点 ...

    先从《Mastering the Game of Go without Human Knowledge》说起,算法根据这篇论文来实现,AlphaZero只有几点不同而已。

    总的来说,AlphaGo Zero分为两个部分,一部分是MCTS(蒙特卡洛树搜索),一部分是神经网络。

    我们是要抛弃人类棋谱的,学会如何下棋完全是通过自对弈来完成。

    过程是这样,首先生成棋谱,然后将棋谱作为输入训练神经网络,训练好的神经网络用来预测落子和胜率。如下图:

    蒙特卡洛树搜索算法

    MCTS就是用来自对弈生成棋谱的,结合论文中的图示进行说明:

    论文中的描述:

    AlphaGo Zero中的蒙特卡洛树搜索。

    • a.每次模拟通过选择具有最大行动价值Q的边加上取决于所存储的先验概率P和该边的访问计数N(每次访问都被增加一次)的上限置信区间U来遍历树。
    • b.展开叶子节点,通过神经网络(P(s, ·), V (s)) = 来评估局面s;向量P的值存储在叶子结点扩展的边上。
    • c.更新行动价值Q等于在该行动下的子树中的所有评估值V的均值。
    • d.一旦MCTS搜索完成,返回局面s下的落子概率π,与N^(1 /τ)成正比,其中N是从根状态每次移动的访问计数, τ是控制温度的参数。

    按照论文所述,每次MCTS使用1600次模拟。过程是这样的,现在AI从白板一块开始自己跟自己下棋,只知道规则,不知道套路,那只好乱下。每下一步棋,都要通过MCTS模拟1600次上图中的a~c,从而得出我这次要怎么走子。

    来说说a~c,MCTS本质上是我们来维护一棵树,这棵树的每个节点保存了每一个局面(situation)该如何走子(action)的信息。这些信息是,N(s, a)是访问次数,W(s, a)是总行动价值,Q(s, a)是平均行动价值,P(s, a)是被选择的概率。

    a. Select

    每次模拟的过程都一样,从父节点的局面开始,选择一个走子。比如开局的时候,所有合法的走子都是可能的选择,那么我该选哪个走子呢?这就是select要做的事情。MCTS选择Q(s, a) + U(s, a)最大的那个action。Q的公式一会在Backup中描述。U的公式如下:

    这个可以理解成:U(s, a) = c_puct × 概率P(s, a) × np.sqrt(父节点访问次数N) / ( 1 + 某子节点action的访问次数N(s, a) )

    用论文中的话说,c_puct是一个决定探索水平的常数;这种搜索控制策略最初倾向于具有高先验概率和低访问次数的行为,但是渐近地倾向于具有高行动价值的行为。

    计算过后,我就知道当前局面下,哪个action的Q+U值最大,那这个action走子之后的局面就是第二次模拟的当前局面。比如开局,Q+U最大的是当头炮,然后我就Select当头炮这个action,再下一次Select就从当头炮的这个棋局选择下一个走子。

    b. Expand

    现在开始第二次模拟了,假如之前的action是当头炮,我们要接着这个局面选择action,但是这个局面是个叶子节点。就是说当头炮之后可以选择哪些action不知道,这样就需要expand了,通过expand得到一系列可能的action节点。这样实际上就是在扩展这棵树,从只有根节点开始,一点一点的扩展。

    Expand and evaluate这个部分有个需要关注的地方。论文中说:在队列中的局面由神经网络使用最小批量mini-batch 大小为8进行评估;搜索线程被锁定,直到评估完成。叶子节点被展开,每个边(s_L, a)被初始化为然后值v被回传(backed up)

    如果我当前的局面没有被expand过,不知道下一步该怎么下,所以要expand,这个时候要用我们的神经网络出马。把当前的局面作为输入传给神经网络,神经网络会返回给我们一个action向量p和当前胜率v。其中action向量是当前局面每个合法action的走子概率。当然,因为神经网络还没有训练好,输出作为参考添加到我们的蒙特卡洛树上。这样在当前局面下,所有可走的action以及对应的概率p就都有了,每个新增的action节点都按照论文中说的对若干信息赋值, 。这些新增的节点作为当前局面节点的子节点。

    c. Backup

    接下来就是重点,evaluate和Backup一起说,先看看Backup做什么事吧:边的统计数据在每一步t≤L中反向更新。访问计数递增,,并且动作价值更新为平均值, 。我们使用虚拟损失来确保每个线程评估不同的节点。

    我们来整理一下思路,任意一个局面(就是节点),要么被展开过(expand),要么没有展开过(就是叶子节点)。展开过的节点可以使用Select选择动作进入下一个局面,下一个局面仍然是这个过程,如果展开过还是可以通过Select进入下下个局面,这个过程一直持续下去直到这盘棋分出胜平负了,或者遇到某个局面没有被展开过为止。

    如果没有展开过,那么执行expand操作,通过神经网络得到每个动作的概率和胜率v,把这些动作添加到树上,最后把胜率v回传(backed up),backed up给谁?

    我们知道这其实是一路递归下去的过程,一直在Select,递归必须要有结束条件,不然就是死循环了。所以分出胜负和遇到叶子节点就是递归结束条件,把胜率v或者分出的胜平负value作为返回值,回传给上一层。

    这个过程就是evaluate,是为了Backup步骤做准备。因为在Backup步骤,我们要用v来更新W和Q的,但是如果只做了一次Select,棋局还没有结束,此时的v是不明确的,必须要等到一盘棋完整的下完才能知道v到底是多少。就是说我现在下了一步棋,不管这步棋是好棋还是臭棋,只有下完整盘期分出胜负,才能给我下的这步棋评分。不管这步棋的得失,即使我这步棋丢了个车,但最后我赢了,那这个v就是积极的。同样即使我这步棋吃了对方一个子,但最后输棋了,也不能认为我这步棋就是好棋。

    用一幅图概括一下这个过程:

    当值被回传,就要做Backup了,这里很关键。因为我们是多线程同时在做MCTS,由于Select算法都一样,都是选择Q+U最大节点,所以很有可能所有的线程最终选择的是同一个节点,这就尴尬了。我们的目的是尽可能在树上搜索出各种不同的着法,最终选择一步好棋,怎么办呢?论文中已经给出了办法,“我们使用虚拟损失来确保每个线程评估不同的节点。”

    就是说,通过Select选出某节点后,人为增大这个节点的访问次数N,并减少节点的总行动价值W,因为平均行动价值Q = W / N,这样分子减少,分母增加,就减少了Q值,这样递归进行的时候,此节点的Q+U不是最大,避免被选中,让其他的线程尝试选择别的节点进行树搜索。这个人为增加和减少的量就是虚拟损失virtual loss。

    现在MCTS的过程越来越清晰了,Select选择节点,选择后,对当前节点使用虚拟损失,通过递归继续Select,直到分出胜负或Expand节点,得到返回值value。现在就可以使用value进行Backup了,但首先要还原W和N,之前N增加了虚拟损失,这次要减回去,之前减少了虚拟损失的W也要加回来。

    然后开始做Backup,“边的统计数据在每一步t≤L中反向更新。访问计数递增,,并且动作价值更新为平均值,。”,这些不用我再解释了吧?同时我们还要更新U,U的公式上面给出过。这个反向更新,其实就是递归的把值返回回去。有一点一定要注意,就是我们的返回值一定要符号反转,怎么理解?就是说对于当前节点是胜,那么对于上一个节点一定是负,明白这个意思了吧?所以返回的是-value。

    d. play

    按照上述过程执行ac,论文中是每步棋执行1600次模拟,那就是1600次的ac,这个MCTS的过程就是模拟自我对弈的过程。模拟结束后,基本上能覆盖大多数的棋局和着法,每步棋该怎么下,下完以后胜率是多少,得到什么样的局面都能在树上找到。然后从树上选择当前局面应该下哪一步棋,这就是步骤d.play:“在搜索结束时,AlphaGo Zero在根节点s0选择一个走子a,与其访问计数幂指数成正比,,其中τ是控制探索水平的温度参数。在随后的时间步重新使用搜索树:与所走子的动作对应的子节点成为新的根节点;保留这个节点下面的子树所有的统计信息,而树的其余部分被丢弃。如果根节点的价值和最好的子节点价值低于阈值v_resign,则AlphaGo Zero会认输。”

    当模拟结束后,对于当前局面(就是树的根节点)的所有子节点就是每一步对应的action节点,选择哪一个action呢?按照论文所说是通过访问计数N来确定的。这个好理解吧?实现上也容易,当前节点的所有节点是可以获得的,每个子节点的信息N都可以获得,然后从多个action中选一个,这其实是多分类问题。我们使用softmax来得到选择某个action的概率,传给softmax的是每个action的logits(N(s_0,a)^(1/τ)),这其实可以改成1/τ * log(N(s_0,a))。这样就得到了当前局面所有可选action的概率向量,最终选择概率最大的那个action作为要下的一步棋,并且将这个选择的节点作为树的根节点。

    按照图1中a.Self-Play的说法就是,从局面进行自我对弈的树搜索(模拟),得到a_t∼ π_t,a_t就是动作action,π_t就是所有动作的概率向量。最终在局面s_T的时候得到胜平负的结果z,就是我们上面所说的value。

    MCTS算法流程如下:

    初始化根节点
    判断是否是叶子节点
    a.选择节点
    执行模拟节点移动
    b.执行神经网络模拟估值
    游戏结束
    设置叶子节点胜平负value
    b.扩展叶子节点
    设置该节点value为神经网络预测的value
    c.根据value递归反向更新父节点和自身的Q和u
    执行真实移动
    当前节点作为根节点

    实现代码如下:

    import numpy as np
    import copy
    
    def softmax(x):
        probs = np.exp(x - np.max(x))
        probs /= np.sum(probs)
        return probs
        
    class TreeNode(object):
        """A node in the MCTS tree.
        Each node keeps track of its own value Q, prior probability P, and
        its visit-count-adjusted prior score u.
        """
        def __init__(self, parent, prior_p):
            self._parent = parent
            self._children = {}  # a map from action to TreeNode
            self._n_visits = 0
            self._Q = 0
            self._u = 0
            self._P = prior_p
    
        def expand(self, action_priors):
            """Expand tree by creating new children.
            action_priors: a list of tuples of actions and their prior probability
                according to the policy function.
            """
            for action, prob in action_priors:
                if action not in self._children:
                    self._children[action] = TreeNode(self, prob)
    
        def select(self, c_puct):
            """Select action among children that gives maximum action value Q
            plus bonus u(P).
            Return: A tuple of (action, next_node)
            """
            return max(self._children.items(),
                       key=lambda act_node: act_node[1].get_value(c_puct))
    
        def update(self, leaf_value):
            """Update node values from leaf evaluation.
            leaf_value: the value of subtree evaluation from the current player's
                perspective.
            """
            # Count visit.
            self._n_visits += 1
            # Update Q, a running average of values for all visits.
            self._Q += 1.0*(leaf_value - self._Q) / self._n_visits
    
        def update_recursive(self, leaf_value):
            """Like a call to update(), but applied recursively for all ancestors.
            """
            # If it is not root, this node's parent should be updated first.
            if self._parent:
                self._parent.update_recursive(-leaf_value)
            self.update(leaf_value)
    
        def get_value(self, c_puct):
            """Calculate and return the value for this node.
            It is a combination of leaf evaluations Q, and this node's prior
            adjusted for its visit count, u.
            c_puct: a number in (0, inf) controlling the relative impact of
                value Q, and prior probability P, on this node's score.
            """
            self._u = (c_puct * self._P *
                       np.sqrt(self._parent._n_visits) / (1 + self._n_visits))
            return self._Q + self._u
    
        def is_leaf(self):
            """Check if leaf node (i.e. no nodes below this have been expanded)."""
            return self._children == {}
    
        def is_root(self):
            return self._parent is None
    
    class MCTS(object):
        """An implementation of Monte Carlo Tree Search."""
    
        def __init__(self, policy_value_fn, c_puct=5, n_playout=10000):
            """
            policy_value_fn: a function that takes in a board state and outputs
                a list of (action, probability) tuples and also a score in [-1, 1]
                (i.e. the expected value of the end game score from the current
                player's perspective) for the current player.
            c_puct: a number in (0, inf) that controls how quickly exploration
                converges to the maximum-value policy. A higher value means
                relying on the prior more.
            """
            self._root = TreeNode(None, 1.0)
            self._policy = policy_value_fn
            self._c_puct = c_puct
            self._n_playout = n_playout
    
        def _playout(self, state):
            """Run a single playout from the root to the leaf, getting a value at
            the leaf and propagating it back through its parents.
            State is modified in-place, so a copy must be provided.
            """
            node = self._root
            while(1):
                if node.is_leaf():
                    break
                # Greedily select next move.
                action, node = node.select(self._c_puct)
                state.do_move(action)
    
            # Evaluate the leaf using a network which outputs a list of
            # (action, probability) tuples p and also a score v in [-1, 1]
            # for the current player.
            action_probs, leaf_value = self._policy(state)
            # Check for end of game.
            end, winner = state.game_end()
            if not end:
                node.expand(action_probs)
            else:
                # for end state,return the "true" leaf_value
                if winner == -1:  # tie
                    leaf_value = 0.0
                else:
                    leaf_value = (
                        1.0 if winner == state.get_current_player() else -1.0
                    )
    
            # Update value and visit count of nodes in this traversal.
            node.update_recursive(-leaf_value)
    
        def get_move_probs(self, state, temp=1e-3):
            """Run all playouts sequentially and return the available actions and
            their corresponding probabilities.
            state: the current game state
            temp: temperature parameter in (0, 1] controls the level of exploration
            """
            for n in range(self._n_playout):
                state_copy = copy.deepcopy(state)
                self._playout(state_copy)
    
            # calc the move probabilities based on visit counts at the root node
            act_visits = [(act, node._n_visits)
                          for act, node in self._root._children.items()]
            acts, visits = zip(*act_visits)
            act_probs = softmax(1.0/temp * np.log(np.array(visits) + 1e-10))
    
            return acts, act_probs
    
        def update_with_move(self, last_move):
            """Step forward in the tree, keeping everything we already know
            about the subtree.
            """
            if last_move in self._root._children:
                self._root = self._root._children[last_move]
                self._root._parent = None
            else:
                self._root = TreeNode(None, 1.0)
    
        def __str__(self):
            return "MCTS"
    
    class MCTSPlayer(object):
        """AI player based on MCTS"""
    
        def __init__(self, policy_value_function,
                     c_puct=5, n_playout=2000, is_selfplay=0):
            self.mcts = MCTS(policy_value_function, c_puct, n_playout)
            self._is_selfplay = is_selfplay
    
        def set_player_ind(self, p):
            self.player = p
    
        def reset_player(self):
            self.mcts.update_with_move(-1)
    
        def get_action(self, board, temp=1e-3, return_prob=0):
            sensible_moves = board.availables
            # the pi vector returned by MCTS as in the alphaGo Zero paper
            move_probs = np.zeros(board.width*board.height)
            if len(sensible_moves) > 0:
                acts, probs = self.mcts.get_move_probs(board, temp)
                move_probs[list(acts)] = probs
                if self._is_selfplay:
                    # add Dirichlet Noise for exploration (needed for
                    # self-play training)
                    move = np.random.choice(
                        acts,
                        p=0.75*probs + 0.25*np.random.dirichlet(0.3*np.ones(len(probs)))
                    )
                    # update the root node and reuse the search tree
                    self.mcts.update_with_move(move)
                else:
                    # with the default temp=1e-3, it is almost equivalent
                    # to choosing the move with the highest prob
                    move = np.random.choice(acts, p=probs)
                    # reset the root node
                    self.mcts.update_with_move(-1)
    #                location = board.move_to_location(move)
    #                print("AI move: %d,%d\n" % (location[0], location[1]))
    
                if return_prob:
                    return move, move_probs
                else:
                    return move
            else:
                print("WARNING: the board is full")
    
        def __str__(self):
            return "MCTS {}".format(self.player)
    ```
    转自:[http://blog.csdn.net/chengcheng1394/article/details/79526474](http://blog.csdn.net/chengcheng1394/article/details/79526474)
    
    展开全文
  • 这项工作结合了蒙特卡洛树搜索(带有针对不完美游戏的扩展)、深度神经网络和高性能游戏引擎。 在基本练习模式中与法师竞争。在 Macbook Pro 上运行。AI 可以轻松击败旅店老板 (8 = 0)。 动机 AlphaGo 成功地结合...
  • 这是一个简单的国际象棋引擎,使用的神经网络经过训练,可从数据库中的800,000多个历史游戏中提取2300万个棋盘+动作对。 还没有关于如何下棋或如何评估棋盘位置的任何知识。 它不希望探讨可能采取的行动的后果。 它...
  • 本文考虑了以下神经网络模型:DQN,DDQN,PPO,TD(基于方法(Q-Learning)上),这是一种将神经网络蒙特卡洛树搜索结合使用的方法。 在数独问题上使用5039个组合(尺寸为2×2、4×4和9×9)的数据集对所提出的...
  • 近年来,计算机软硬件和互联网迅猛发展,相关学科也在不断进步。人工智能是长期以来的热点话题,而计算机博弈是它的一个受到广泛关注的研究方向。
  • 蒙特卡洛树搜索又称随机抽样或统计试验方法,属于计算数学的一个分支,它是在上世纪四十年代中期为了适应当时原子能事业的发展而发展起来的。传统的经验方法由于不能逼近真实的物理过程,很难得到满意的结果,而...

    蒙特卡洛树搜索又称随机抽样或统计试验方法,属于计算数学的一个分支,它是在上世纪四十年代中期为了适应当时原子能事业的发展而发展起来的。传统的经验方法由于不能逼近真实的物理过程,很难得到满意的结果,而蒙特卡洛树搜索方法由于能够真实地模拟实际物理过程,故解决问题与实际非常符合,可以得到很圆满的结果。这也是以概率和统计理论方法为基础的一种计算方法,是使用随机数(或更常见的伪随机数)来解决很多计算问题的方法。将所求解的问题同一定的概率模型相联系,用电子计算机实现统计模拟或抽样,以获得问题的近似解。

    在搜索空间巨大的情况下会比较有效

    从全局来看,其主要目标为给定一个游戏状态来选择最佳的下一步

    经典应用:alpha go

    算法过程

    选择:选择能够最大化UCB值的结点,即UCB越大,越有可能选择这条路径
    在这里插入图片描述
    在这里插入图片描述该节点下的平均value大小

    C:常数,通常可以取2
    N:总探索次数
    ni:当前阶段的探索次数

    扩展:创建一个或多个子节点

    在这里插入图片描述

    仿真:在某一点用随机策略进行决策,又称palyout或rollout

    在这里插入图片描述

    反向传播:使用随机搜索的结果来更新整个搜索树
    在这里插入图片描述
    在这里插入图片描述

    算法过程
    流程图

    算法的终结机制

    1,限定运行时间
    2,给固定的迭代次数

    迭代完成后,选择value更大的节点即可完成决策

    示例:
    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    左边搜索在这里插入图片描述
    在前面的基础上,进行右边搜索
    在这里插入图片描述
    计算
    在这里插入图片描述
    左边再深一层搜索
    在这里插入图片描述

    计算
    在这里插入图片描述

    右边深一层搜索
    在这里插入图片描述

    蒙特卡洛树搜索与深度神经网络的结合

    这是alpha go的计算原理

    最初的解决方案是使用小型网络:
    即rollout policy
    原理:对棋盘的特征做新性组合,再做softmax借此得到行动的概率
    当时使用了8百万人类棋手的数据进行训练

    这样做对局时每一步的准确率为24.2%

    考虑到围棋变化的复杂度,他们上了神经网络
    效果:3毫秒内完成计算,落子准确率为57%
    原理:
    以输入棋盘状态S为输入数据
    以选择不同行动的概率为输出
    训练方法:梯度下降

    网络总体架构:
    分成两个网络:策略网络(给出决策)与价值网络(评估胜率)

    公式
    在这里插入图片描述

    现在将神经网络用到搜索树中
    在这里插入图片描述

    下面针对上面的UCT公式进行说明:
    策略树
    即UCT算法(Upper Confidence Bound Apply to Tree)
    公式:
    行动价值选择函数
    在这里插入图片描述

    c为常数,c所乘公式用于表示不确定的项

    s表示状态 a表示行动
    Q(s,a):该函数表示状态行动对的价值。
    N(s,a):状态行动对的访问次数,没有采取过的行动的不确定性比较大,潜力亦比较大。
    在这里插入图片描述

    最初的价值和访问次数都是0,那么我们最初就要随机选择
    即rollout policy(随机policy)方法(一般利用MC估计值函数的策略叫做rollout policy,因为这个策略就是用来roll out出一个轨迹的),而不是找到一个最优策略。经验表明,rollout算法虽然简单,但是在实际中十分有效。)

    在反向传播的过程中,如果这个决断使得棋局走向了胜利,那么就标记为1,反之标记为-1

    backup:
    故W表示的就是节点的总价值
    backup:
    这是基本结构
    在这里插入图片描述
    为了定制阈值的生长速度,这里加以改进

    在这里插入图片描述

    有了这种网络,我们一开始就能考虑那些高概率的行为,而不必像UCT那样从0开始学习,大大减少了计算负担。

    总体来说alpha go具有以下优点:
    神经网络+rollout 构成快速决策系统
    价值网络估计叶节点的价值→与rollout的价值做加权平均
    反向传播

    展开全文
  • Model-free:类似monte carlo control, sarsa, q-learning, ac算法都是model-free算法。样本完全从经验中获得。...因为MCTS在模拟的过程中,用到了模型的对下一个state或者reward的预测蒙特卡洛方法。随机抽样来预估...
  • 蒙特卡洛树搜索算法可以通过自我对弈模拟得到不同状态分支中获胜的概率,从而获得最优的策略。代码部分可以分为Node类和State类。Node类通过关联父节点和子节点实现树结构,同时保存每个节点的属性;State类描述游戏...
  • 蒙特卡洛树搜索(新手教程)

    万次阅读 多人点赞 2018-11-01 20:44:47
    残差卷积神经网络——使用policy network(策略网络)和value network(价值网络)来进行比赛的评估和落子先验概率的估计 强化学习——通过自我对局来训练网络 本篇文章只关注蒙特卡洛树搜索(Monte Carlo ...
  • 面向初学者的蒙特卡洛树搜索MCTS详解及其实现

    千次阅读 多人点赞 2019-11-24 20:48:44
    蒙特卡洛搜索算法是棋类博弈中常用的算法,本文介绍了蒙特卡洛搜索算法的原理,实现以及示例等内容,让读者对这一经典算法能有更加透彻的认识。
  • 蒙特卡洛树搜索全称 Monte Carlo Tree Search(MCTS),是一种人工智能问题中做出最优决策的方法,一般是在组合博弈中的行动(move)规划形式。它结合了随机模拟的一般性和树搜索的准确性。MCTS 受到快速关注主要是...
  • “博弈”——蒙特卡洛树搜索运行的框架或者说环境,其本身就是一个非常抽象的广义术语 ,因此本文会将讨论范围限定在一种博弈类型:有限双人零和回合制博弈 —— 乍一听这个词好像很复杂,但其实很简单,让我们把它...
  • 为什么需要蒙特卡洛方法 在现实世界中,大量存在一些复杂性过程,由于这类模型含有不确定的随机因素,我们很难直接用一个确定性模型来分析和描述。面对这种情况.数据科学家难以作定量分析,得不到解析的结果,或者...
  • 深度学习视频讲座:2017年最新深度学习视频讲座...第10课 计算机博弈原理,蒙特卡洛树搜索,深度学与AlphaGo,价值网络与策略网络的设计,构成和训练 第11课 堆叠150层的超深度网络:深度残差网络 第12课 递归神经网络
  • 【python】蒙特卡洛树搜索(MCTS)简单实现

    万次阅读 多人点赞 2018-12-24 16:46:47
    def monte_carlo_tree_search(node):#蒙特卡洛树搜索总函数 computation_budget=1000 for i in range(computation_budget): expend_node = tree_policy(node) reward = default_policy(expand_node) backup...
  • 选自int8 Blog机器之心编译我们都知道 DeepMind 的围棋程序 AlphaGo,以及它超越人类的强大能力,也经常会听到「蒙特卡洛树搜索」这个概念。事实上,蒙特卡洛树搜索是在完美信息博弈场景中进行决策的一种通用技术,...
  • 关于蒙特卡洛树搜索,国内真的很难找到特别好的入门资料,很多还是错的,本文是前段时间为了实现自己的一个 AI,在阅读了几十篇国内外文章之后根据自己的理解整合写的,主要参照 INT8 的一篇英语博文 Monte Carlo ...
  • 蒙特卡洛树和alpha go

    2017-11-12 19:42:06
    对Alpha-zero很感兴趣,所以耐心阅读了mastering the game of go without ...在阅读的过程中,对蒙特卡洛树搜索算法不甚了解,下面翻译了youtube上一位英国教授的网络课程视频。 蒙特卡洛树搜索(MCTS)算法
  • 本文考虑了以下神经网络模型:DQN,DDQN,PPO,TD(基于方法(Q-Learning)上),这是一种将神经网络蒙特卡洛树搜索结合使用的方法。 在数独问题上使用5039个组合(尺寸分别为2x2、4x4和9x9)对数据模型进行了测试...
  • 遗传算法 神经网络 深度学习 概率论 ???
  • 深度学习与围棋:为围棋数据设计神经网络

    千次阅读 多人点赞 2021-03-27 15:55:22
    本文主要内容 构建一个深度学习应用,可以根据数据预测围棋的下...特别地,我们将使用第4章开发的搜索技术来生成围棋游戏数据,然后用它们来训练神经网络。图6-1是我们将在本章中构建的应用的概览。 如图6-1所示,
  • 首先,简要介绍了围棋博弈的难点,通过对蒙特卡洛树搜索方法的分析,指出围棋棋步预测方法才是解决围棋博弈问题的有效途径;然后,从卷积神经网络的整体结构、各层子结构以及网络的训练三个方面阐述了与围棋棋步预测相关...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,328
精华内容 931
关键字:

蒙特卡洛树神经网络