(1)任务简述
参考Quoridor的游戏规则,在7×7的棋盘中,己方和对方车模交替上场摆放棋子或者障碍,到达对岸耗时最少的队伍获得胜利。比赛细则见《全国大学生智能汽车竞赛创意组决赛棋局规则》。步步为营棋盘展示图如图11.57所示。
增强学习作为当前人工智能领域最热门的一种算法,能解决这个问题:一个能感知环境的自主对象,通过学习,选择能达到其目标的最优动作。这个算法非常适合学习棋类对弈,前几年轰动围棋界的阿尔法狗就是基于深度增强学习算法实现的,因此本项目利用这个算法来解决步步为营的对抗问题。
图11.57 步步为营棋盘
增强学习的原理:如图11.58所示增强算法简介图,当对象在其环境中做出每个动作时,施教者会提供奖励或惩罚信息,以表示结果状态的正确与否。例如,对于下棋这个增强学习问题,目的就是要从决定中获得最大化的奖励。在训练对象进行棋类对弈时,施教者可在游戏胜利时给出正回报,在游戏失败时给出负回报。对象的任务就是从这个非直接的、有延迟的回报中学习,以便后续的动作产生最大的累积效应。
图11.58 增强学习算法简图
价值函数:为了找到获得最多累积奖励的动作,首先得定义在当前环境中最有价值的动作。一旦决定了哪些状态是有价值的,就可以将奖励附加于它们。例如当对方达到的路经比我方少,奖励就是负的。反之,就可以得到一个正的奖励。当达到对岸时,奖励值达到最大,同时比赛结束。
通过这种方式,可以构建出一个离散的函数来表示出状态和奖励之间的关系。对于有些作为间接的状态,它们虽然没有直接的奖励,但是对于到达一个奖励来说是非常有必要的铺垫。比如在很远处放一个挡板,有可能在未来改变棋局。训练后的价值函数将部分奖励赋给了间接的状态中,这能帮助对象做出好的决定。
价值函数也能够抓住一个问题的微妙之处。比如,在棋盘中给对方放置更多的挡板会带来更多的正面奖励,因为可以增加对手的路径,但是可用挡板的数量会越来越少,在后期的竞争中会处于劣势,因此路径和挡板数量之间是相互制约的。价值函数的确定,会改变最终每种状态的选择。如果当前在对方路径上放置挡板带来较高的奖励,价值函数就会将更高的值赋给那些更早使用挡板的状态。(www.xing528.com)
在这个算法中,设计的价值函数考虑了两种情况,如果棋子到达对岸,给予最大的奖励100,如果对手到达对岸,给予最大的惩罚-100;如果放置一块挡板给对手带来大量路径的增加,给予中等奖励30,如果放置一块挡板给对手带来少量路径增加,给予小奖励10。
折扣因子:每当一个状态改变,在局部奖励上乘上一个折扣因子。折扣因子为0.5的话,原有的奖励在三个状态改变后就会变成1/8,这会使agent更加关注于接近的奖励而不是很远的奖励。因此,折扣因子是一个权重决定着价值函数偏向于谨慎或者贪婪的行为,对对象会产生长期影响。在这个算法中将折扣因子设置为0.5。
(3)Q-learning算法
用强化学习中最广泛的方法Q-learning完成对抗,这种方法结合了蒙特卡罗方法和动态规划的优点,拥有优秀的性能,本算法的目的是构建一个指导决策的Q-table表。Q-table表以状态为行、动作为列。
状态:根据需求分析,需要考虑的状态有己方的位置、对方的位置、场上挡板的位置,棋盘格有49个格,因此己方的位置和对方的位置都有49种状态。在7×7棋盘中,每个横挡板有36种摆法,竖挡板有36种摆法,如果把棋盘中挡板的位置都考虑完整,那么有272种情况,这个数据量太庞大了,完全不可能实现。因此作了简化,只考虑棋子当前位置的正前方、左边、右边是否有挡板。故状态空间可以用Aposition、Bposition、Aforward、Aleft、Aright、Bforward、Bleft、Bright表示,Aposition和Bposition有49种状态,Aforward、Aleft、Aright、Bforward、Bleft、Bright包含有和无两种状态。排除棋子同在一个棋格的可能,则共有49×48×2×2×2×2×2×2×2=150 528,所以状态空间的大小是150 528。
在训练的过程中,发现上述状态空间还是过于庞大,因此算法再次优化,用抵达对岸的距离来代替棋子在棋盘中距离的精确位置。Aposition和Bposition有距离0(胜利)到距离6(初始状态)共7种情况,简化后的状态空间大小为7×7×2×2×2×2×2×2=3 136。动作:每个棋子有移动和放置挡板两类动作,移动有上下左右四种动作,如果把放置挡板的位置考虑完全,数据量会很大,算法作简化如下:只在对手位置附近放置挡板。有正前方、左侧、右侧紧靠着棋子,距离棋子一个棋格共12种动作,因此每个棋子都有16种动作可以选择。
(4)算法流程
设置初始的状态-动作对为零,之后让agent经历各种状态直到找到一个奖励。然后观察每一个决策带来的回馈,再利用贝尔曼公式更新Q-table。训练次数达到一定次数,Agent便具备了一定的智能。决策的时候,只需要查找并执行Q-table中增益最大的动作即可。算法流程图如图11.59所示。
图11.59 增强学习程序框图
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
