第3期 张小川，等：采用时间差分算法的九路围棋机器博弈系统 ·279· 评价采取某动作的好坏51.图1简单描述了强化学 Q(s,a)←-Q(s,a)+ 习中智能体与环境的交互过程（其中s为智能体当 n(r++y maxQ(s,+)-Q(s:,a)).(3) 4+1 前所处的环境状态)· 式中：η为更新因子，随时间的增加逐渐减小；Y为 折扣率，0≤y<1,保证返回的奖励为有限的. 回报r,a 对于动作的选取，在知识量少的初期，可以在所 有动作中随机选取，可看作“探索”.但也不希望一 智能体 动作a 环境 直探索下去，故探索到一定时，需利用当前所学知 识.为此采用一个温度变量T来实现从探索到利用 图1强化学习中智能体与环境交互过程 知识的转移，下面给出加入温度变量时选择动作a Fig.1 The agent and the environment interaction process in reinforcement learning 的概率0： 如果将强化学习应用到围棋机器博弈中，博弈 P(als)=_exp[Q(s,a)/T] (4) 程序变成具有一定智能的决策者，而围棋棋盘就被 ∑exp[Q(s,b)/T] 看作博弈环境.当博弈双方产生新着法时，围棋棋盘 当T很大时，所有概率趋近于相等，此时进行 的状态就发生了改变，博弈环境的状态也随着发生 随机探索；当T很小时，价值更大的动作被选取的 转移.同时在博弈进程中，从博弈开始到博弈结束， 可能性较大，则实现对知识的利用.所以在学习的过 其整个过程包含系列的博弈着法，即博弈着法的集 程中以一个较大的T值开始，不断地缩小T值，完 合；因此利用强化学习解决围棋博弈问题的核心，就 成探索直至利用知识， 是要建立一种合适的内部奖励机制，使得博奔程序 或围棋人工生命体能执行最大化内部奖励的局部动 2基于时间差分算法的围棋机器博奔 作，从而学会发现一个最佳的着法序列，并提高博弈 模型 水平 1.2时间差分算法 当求解问题的状态空间较大时，会使强化学习 时间差分算法(temporal difference)是强化学习 算法的收敛效率降低，这就要求增加实验次数，但降 的一种重要算法)，其利用探索所得到的下一状态 低了算法的实时性山.而在围棋机器博奔中，若搜 的价值和奖励来更新当前状态的价值⑧].本文经过 索超时则直接判负.并且当处于中局时，棋盘状态复 研究分析，构造了博弈状态转移特征方法，利用该方 杂度增加，若把每个可下点看作一个动作，则算法的 法获得的特征信息（特别是激励性信息）反馈于当 状态与动作数量大幅度增长.故需采用其他策略减 前博弈状态，并更新当前博弈状态，引导博弈系统的 少问题状态空间，以增强算法的实时性.为此，采用 价值取向，这就是本文引人时间差分算法的机器博 将静态估值与时间差分算法相结合的策略，在产生 奔的基本思路 可下节点时，选取静态估值较大的点，再在此点上利 在实际应用中，通常采用成对的状态-动作值 用时间差分算法完成动作的选取， Q(s,a,)来表示当处于状态s,时执行动作a,的价 2.1系统状态 值.在简单的确定的情况下，任意一对状态-动作只 在博弈过程中，围棋棋盘状态作为环境因素直接 有1个奖励和可能的下一状态，根据Bellman公式， 影响博弈智能体作出的决策，如开局时摆棋形、博奔过 可得如式(1)的简化公式1： 程中己方受威胁棋子、对方受威胁棋子等.本文选取环 Q(s:,a)=r++y maxQ(sI,a+). (1) 境因素中对博弈智能体的决策影响较大的因素作为系 + 统问题状态该状态集形式化描述如式(5)： 式中：max(s,+1,a+1)表示充分利用已有发现，选择 S={Sn,S。,S,0n,0.,0} (5) 具有最高价值的动作，当处于探索阶段时，若处于状 式中：S,为当前棋盘上己方棋子总数，S。为当前棋 态s,则随机选取一个动作a,返回一个奖励r+1,并 盘上己方眼总数，S:为当前棋盘上己方气总数，0 将状态转移至3+1·此时，前一动作的价值更新为 为当前棋盘上对方棋子总数，O.为当前棋盘上对方 Q(s,a)←-T+1+y maxQ(s+1,a+1).(2) 眼总数，O,为当前棋盘上对方气总数.其中，Sn与 a+1 由此可以看出Q(s+1,a+1)是更新后的值，具有更 0.直接关系到当前博弈双方对弈的局势；S。与O 高的正确概率.将式(2)引入，以减小当前Q值与一 直接关系到某串棋是否为活棋，如当某串棋有2个 个时间步骤之后的估计值之间的误差，则有式(3)： 眼，则被提掉的可能性减小至0；S,与O,则直接关