大型网站开发用什么语言,深圳市坪山区,看装修效果图哪个网站好,深圳市区是哪个区0 摘要
近年来#xff0c;游戏 2048 获得了巨大的人气 [6]。游戏允许玩家移动屏幕上的数字#xff08;2 的幂#xff0c;例如 2、4、8、16 等#xff09;#xff0c;总和至少为 2048。因为它只有 4 个动作#xff0c;所以很容易上手: 上、下、左、右。但是#xff0c;很…0 摘要
近年来游戏 2048 获得了巨大的人气 [6]。游戏允许玩家移动屏幕上的数字2 的幂例如 2、4、8、16 等总和至少为 2048。因为它只有 4 个动作所以很容易上手: 上、下、左、右。但是很难获得大于或等于 2048 的数字因为您在当前状态下所做的每个操作都会导致数百个不可预知的结果。在本文中我们提出了一种用于 AlphaGo Zero 和 2048 游戏的类似算法具有独特的奖励和惩罚系统以提高人工智能 (AI) 的自学速度并为 AI的自动播放模式获得更高的分数。此外基于具有 Alpha-Beta 修剪的 Minimax 算法、Expectiminimax 算法和蒙特卡洛树搜索 (MCTS) 的结果我们得出结论蒙特卡洛树搜索在应用于 2048 游戏时优于其他算法。最后我们表明具有强化学习的人工智能 [9] 可以击败人类在 2048 年游戏中取得的最高分。
1 引言
AlphaGo [10] 是一个玩棋盘游戏 Go [12] 的计算机程序。而且它是第一个击败职业人类围棋选手的计算机程序也是第一个击败世界围棋冠军的程序。 AlphaGo 是由 Alphabet Inc. 在伦敦的 Google DeepMind 开发的。它有三个更强大的继任者称为 AlphaGo Master、AlphaGo Zero 和 AlphaZero [12]。最早的版本 AlphaGo 需要成千上万的人类业余和专业游戏来学习和掌握围棋游戏而 AlphaGo Zero 是第一个从完全随机的游戏开始通过与自己玩围棋游戏来学习的版本。已经证明 AlphaGo Zero 比之前的版本 [11] 更好。自从 AlphaGo Zero 广受好评后人们就开始尝试研究 AlphaGo Zero 的算法/方法以便将其应用到其他游戏中。在本文中我们将展示一个可以自动玩游戏 2048 并在合理的运行时间内最大化游戏分数的 AI。 Game 2048 是一款单人益智游戏。 Gabriele Cirulli 是一位意大利用户界面设计师和 Web 开发人员他创建了这款游戏并于 2014 年 3 月发布了它 [13]。游戏 2048 很简单给玩家一个 4 × 4 的棋盘其中每个牌可能包含一个 2 的幂的数字。开始时只有两个编号的牌编号为 2 或 4。玩家控制并通过按箭头键更改棋盘棋盘中的图块会根据玩家移动。例如如果你按向上键所有的图块都会向上。如果相邻单元格上的数字匹配它们将合并否则它们将保持在原来的位置见图 1。此外每次移动后一个新的数字2 或 4将均匀地出现在一个空单元格上配给可以设置。在本文中我们将 2 和 4 之间的出现比率设置为 9:1。玩家的目标是在 4 × 4 网格上滑动编号的图块以合并并创建一个编号为 2048 或更大的图块参见图 1。当没有空单元格且没有更多有效动作时游戏结束。如果在游戏结束前棋盘上出现了编号为 2048 的棋子则玩家获胜。 图 1游戏 2048 中的移动示例。左图显示当前状态右图显示“向上”移动后的下一个状态。 左边有两个 8。 向上移动瓷砖后底部的 8 将向上移动并与上面相同的数字 8 合并组合成一个 16。
我们认为以下三种方法是最流行和最有效的策略带有 alpha-beta 剪枝的 Minimax 算法、Expectimax 算法和 Monte Carlo Tree Search (MCTS)。 然后我们根据我们在训练 AI 时为游戏设置的规则设置奖励和惩罚。 这样一来2048就可以从单人益智游戏衍生到自动AI游戏这意味着在整个自学过程中不再需要人机交互。 在没有来自人类专家的数据集的情况下训练人工智能对于开发具有超人技能的人工智能具有重要意义因为专家数据通常很昂贵、不可靠或根本不可用。
论文主要分为三个部分
两种奖惩制度三种树搜索算法 a) 带有 alpha-beta-pruning 的 Minimax 算法 b) Expectimax 算法 c) 蒙特卡洛树搜索 (MCTS)上述三种算法的结果比较。
2 两种奖惩制度
我们设置了两种奖惩系统一种使用权重矩阵α另一种使用权重矩阵β。 权重矩阵 α 是一个在右上角具有最高值且其值沿对角线递减的矩阵见图 2。 权重矩阵 β 看起来像一个贪食蛇形状玩家沿着路径滑动图块并将它们合并到同一个右上角参见图 3。 Figure 2: Weight Matrix α 图 3左横向贪食蛇形状的权重矩阵 β 右图水平-垂直贪食蛇形状的权重矩阵 β
根据我们的实验将具有接近值的图块放在一起通常会导致更多可能的合并。 显然单次滑动可以合并两个相同编号的图块同时按升序或降序管理不同的图块这可以帮助图块以后连续合并。 从直觉上可以看出将具有接近值的图块放置在彼此附近通常会导致更多可能的合并。 对于相同编号的图块单次滑动即可合并 对于不同编号的图块按升序或降序排列是合理的这样它们就可以连续合并。 因此它似乎试图使用在一个角上具有最高权重并沿对角线递减的矩阵 α。 由于矩阵 α 并没有在很大程度上区分图块两个图块的不同权重可能会因它们承载的数量差异而减弱因此创建权重矩阵 β 以扩大权重范围。 权重矩阵 β 是贪食蛇形的见图 3。 启发式是我们期望沿着贪食蛇的滑动和合并将更大的数字放在角落里。 在尝试了具有各种权重值的对称和贪食蛇形权重矩阵后我们发现贪食蛇形权重矩阵的性能最好。
3 三种树搜索算法
游戏2048可以被视为两人游戏人类玩家与计算机对战。 轮到人类通过选择四个基本方向之一来移动棋盘上、下、左或右 然后计算机扮演在其中一个空单元格中随机放置一个数字 2 或 4 的角色。 因此Minimax 算法首先引起了我们的注意因为它是一种在包含两个玩家的游戏中广泛使用的决策规则。 将 Minimax 算法应用于 2048 游戏时计算机扮演对手角色只需以 9:1 的概率比放置 2 或 4 的新图块。 首先我们解释算法中的符号 (1) players:agent,opponent 代理人对手 (2) s: the grid board that reflects the current state 反映当前状态的网格板 (3) a: the action taken 采取的行动 (4) actions(s): possible actions at state s 状态 s 的可能动作 (5) result(s, a): resulting state if action a is chosen at state s 如果在状态 s 选择动作 a则结果状态 (6) isEnd(s): whether s is an end state (the game is over) s是否为结束状态游戏结束 (7) eval(s): evaluation at state s 状态 s 的评估 (8) player(s) ∈ players: the player that controls state s 控制状态 s 的玩家 (9) totalScore(s): the score at the end of the game 比赛结束时的比分 (10) d: the current depth of the search tree 搜索树的当前深度 Minimax算法的数学公式如下 玩家可以从每一轮中的四个动作中选择一个即动作a∈{上下左右}。 动作a随机将2或4放入当前棋盘的空格子中。 当达到最大深度或导致游戏结束时每轮评估函数将重新调整每个turn作为当前分数。 接下来我们从上面的Mini-Max算法派生了Expectimax算法。 不同之处在于我们在代理节点和对手节点之间添加了机会节点。 因此当我们将启发式和域知识添加到我们的评估功能时当AI到达最后一个深度级别时或者游戏结束时算法的伪代码如下 Expectimax算法具有一些缺点例如要分析的移动次数快速增加深度并且计算功率限制了算法可以走的深度。 因此我们尝试了第三种方法蒙特卡罗树搜索。 蒙特卡罗树搜索的基本思想是基于强盗Bandit-based的方法。 一名球员需要选择K个动作中的某个动作并通过不断选择最佳移动来最大化累积奖励。 一旦玩家选择此动作的真正奖励将取决于随后可能的移动。 蒙特卡罗树搜索算法列举了将游戏2048的状态S作为输入的神经网络作为输入并输出移动概率和值PV。 标量值V表示状态s的“善良”。 在AZGv代表了从这个状态获胜的概率但由于我们只有一个玩家它也是使用当前网络的预期当前游戏结果和平均结果之间的比率。 这样大于1的值为良好低于1的值不是那么好见图4 [1]。 Figure 4: MCTS 在每个状态下执行 MCTS并构建一棵树根节点为初始状态 s0s_0s0。 对于树中的每个状态 sss有四个边(s,a)(s, a)(s,a) 对应于可能的移动每个边包含统计信息
(1) N(s,a)N(s, a)N(s,a) - number of times action has been taken from state s 从状态 s 采取行动的次数(2) W(s,a)W (s, a)W(s,a) - total value of move a from state s 从状态 s 移动 a 的总值(3) Q(s,a)Q(s, a)Q(s,a) - mean value of move a from state s 从状态 s 移动 a 的平均值(4) P(s,a)P(s, a)P(s,a) - prior probability of selection move a 选择移动a的先验概率
该算法迭代三个阶段最初 1600 次
(1) 选择每次迭代从 s0s_0s0 开始并在模拟到达叶节点 sLs_LsL 时结束。 在每个时间 ttt根据搜索树中的统计信息选择一个移动。 U(s,a)P(s,a)∑bN(s,b)1N(s,a)(1)U(s, a)P(s, a) \frac{\sqrt{\sum_{b} N(s, b)}}{1N(s, a)} \tag1U(s,a)P(s,a)1N(s,a)∑bN(s,b)(1)
此搜索控制策略最初更喜欢高概率和低访问计数的操作但渐近地更喜欢具有高动作值的动作。
(2) 扩展和评估使用当前神经网络进行评估叶节点sLs_LsL 。 叶节点被扩展每个边缘sLs_LsLaaa初始化为N0W0Q0PpaN 0W 0Q 0P paN0W0Q0Ppa。 然后备份值vvv。
-(3) 反向传播边缘统计信息在反向传播中更新。
N(s,a)N(s,a)1,W(s,a)W(s,a)v,Q(s,a)W(s,a)/N(s,a).N(s, a) N(s, a) 1, \\W (s, a) W (s, a) v, \\Q(s, a) W (s, a)/N(s, a).N(s,a)N(s,a)1,W(s,a)W(s,a)v,Q(s,a)W(s,a)/N(s,a).
一旦迭代完成计算概率。 下一步移动只是最大选择。 在其训练阶段AGZ按分布进行抽样。 我们使用了一个确定性的选择因为2048游戏存在如此多的随机性。
我们注意到更深入的深度导致搜索树的维度爆炸。 此外整个树搜索算法探讨了树的一些不必要的部分。 因此我们在所有三种树搜索算法中实现了Alpha-Beta修剪以防止这些问题。Alpha-Beta修剪估计两个值Alpha增益的较低限制和Beta增益的上限。 在任何情况下在Beta小于Alpha的情况下将修剪其余的子树。
在利用蛇形权重矩阵βββ的人启发式时我们只考虑一些最重要的空图块它们对它们具有更高的权重。 经过具有最小值深度空图块的数目4或深度空图块的数目6的几个图块后这些界限通常更靠近在一起。 只要α和β的范围内存在一些重叠这种会聚不是问题。 在评估节点时我们可能会发现它已经移动了其中一个界限使得α和β之间不再存在任何重叠。此时我们知道此节点永远不会导致我们将考虑的解决方案路径因此我们可能会停止处理此节点。 换句话说我们停止生成其子节点然后返回其父节点并完成这个子树修剪。 4 具有Alpha-Beta修剪的Minimax算法
2048游戏具有离散状态空间其包含完美的信息。它也是棋盘和跳棋等转向的游戏。因此我们可以使用alpha-beta修剪应用于Minimax Search这已被证明在这种类型的游戏上工作。单调性启发式试图确保图块的值沿左/右和上/下方向呈增加或减小。这个启发式唯一表明了许多其他人提到的直觉那么高价值的图块应该被聚集在一个角落里。它通常会阻止孤立的较小值图块并将游戏板组织得非常好较小的图块级联并填充较大的图块。独自启发式倾向于创建一个结构其中相邻的图块的值下降。然而为了合并相邻的图块需要显然是相同的价值。因此平滑性启发式只是测量相邻图块之间的值差异以便最小化这一计数。最后免费图块太少有惩罚因为当游戏板变得过于狭窄时选择可以快速耗尽。 表1说明了具有alpha-beta修剪的Minimax算法的结果。
4.1 Expectimax Optimization预期优化
AI需要10ms到200ms以执行移动具体取决于游戏板位置的复杂性。 此期望算法有四种启发式方法
1为开放方块授予“奖金”2在边缘上有大值的授予“奖金”3在级别增加时对增加的非单调行和列进行惩罚因为大量的非单调行大幅影响了得分。4除了打开空间之外第二启发式计算潜在合并的数量相邻的等值。
通过远程控制运行100次后预期算法的结果如表2所示。 基于表2中的结果观察到深度2, 3和4的平均分数分别为11279,16766和59436并且每个深度的实现最大得分为31924,33940和59436。 AI永远不会获得至少一次2048图块。 这场比赛花费了27830次移动超过96分钟平均每秒4.8次移动。 最初存在两个启发式方法为开放方块授予“奖金”并且在边缘上具有大值。
4.2 Monte Carlo Tree Search蒙特卡洛树搜索
如果我们从随机初始化的神经网络开始所实现的模拟器的分数在500到4000的范围内。这些分数类似于随机播放的结果。 训练进行了10个小时。 当我们在蒙特卡罗树中使用100种模拟时总共进行66个训练周期。 所有16个模拟器组合的都能每秒执行大约7个移动。 在所有66个周期中新的训练模型能够用旧的权重击败神经网络四次。 最好的得分为2638。 在Monte Carlo树中使用50模拟时32个游戏模拟器能够每秒执行大约40个移动。 在10小时的游戏和训练期间完成了334个训练周期并且新版本的初始模型实现了一个更好的中位数得分两倍。 在开发和测试过程中中性网络的参数大多保持不变同时仅尝试不同的学习率和残留层的量。 其他参数如网络所在的样本数量在每个训练周期上训练也试图播放评估模型的游戏量以实现更好的结果。 遗憾的是尝试的组合都无法在游戏玩法的10小时内从自行播放中改进模型并且在训练过程中的结果与随机初始化网络所实现的结果类似。 蒙特卡罗树搜索的结果已显示在表3。
