《Hex-六角棋AI初步设计(算法复杂度分析).pdf》由会员分享，可在线阅读，更多相关《Hex-六角棋AI初步设计(算法复杂度分析).pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 Hex 游戏 AI 的初步设计 摘要 Hex 游戏是一种在以六边形为单元格的棋盘上进行的对弈游戏。与其他对弈一样，Hex 游戏蕴含着丰富的数学知识和博弈技巧，吸引了许多博弈爱好者的关注。Hex 游戏存在先手必胜策略，然而寻找必胜策略被证明是 NP 难的问题。本文介绍了 Hex 游戏的基本规则和特性，给出 Hex 游戏 AI 的初步设计，重点介绍极小极大搜索和 alpha-beta 剪枝策略。最后将 Hex 棋抽象为网络流模型，提出基于最大流算法的估值函数，并对估值算法的时间复杂度进行分析。关键字：Hex 游戏，AI，极小极大，alpha-beta 剪枝，网络流 一、Hex 游戏 1.1 He
2、x 游戏规则 Hex 游戏（或 Hex 棋、Hex 博弈）是一种以正六边形为单元格的棋盘类游戏。Hex 棋由丹麦数学家 Piet Hein 于 1942 年发明；1948 年，该游戏又被美国数学家 John Nash 重新独立发明，曾一度被称为“Nash Game”。Hex 棋的棋盘可以有不同大小，一般采用 11 阶，即共有 11*11 个六边形单元格，每个单元格最多与6 个其他单元格相邻。一个 8*8 Hex 棋盘如图 1 所示：图 1 棋子一般采用黑色和白色，对弈双方各执一种颜色的棋子。棋盘的四个边界， 每组对边由一种颜色标识，属于对弈的一方。在上图中，黑白双方对弈，黑方执黑子，拥有黑色的
3、一对边界；白方执白子，拥有白色的一对边界。Hex 游戏的对弈规则是：双方轮流下子，可以将自己的棋子下到棋盘中任意空闲的格子里，同种颜色的棋子相邻即认为它们相互连接。任意一方将自己的两条边界用自己的棋子连接起来，该方则获胜，游戏结束。我们把将一对边界连接起来的相同颜色棋子所组成的路径成为“获胜链”。一般由黑方先下子。1.2 先手必胜 Hex 棋的一个有趣的特点是，其对弈结果永远不会出现平局。也就是说，在极端情况下，棋盘中的每个格子都被某种颜色的棋子所占据，那么一定能找到一条获胜链。David Gale 于 1979 年通过 Brouwer 不动点理论加以证明1。Jhon Nash2 证明了 He
4、x 游戏中先手必胜：1，Hex 棋不会出现平局，一定存在先手或后手的获胜策略。2，假设后手有获胜策略。3，先手可以采用如下对策来取胜：a)第一步在任意位置下子；b)接下来先手采用“2”中提到的后手的获胜策略下子，相当于先后手对换；c)因为第一步所下的子不会成为先手的劣势（如果先手下一步要下子的位置刚好被第一步的棋子占据，随便在一个空闲位置下子即可），所以先手将获胜。4，结果与后手获胜的假设矛盾，所以存在先手的必胜策略。虽然可以证明 Hex 棋存在先手必胜策略，但除了有限几个低阶的 Hex 棋盘，至今没人给出通用的获胜策略。例如，11*11 的 Hex 游戏还没有找到必胜策略。1.3 蛮力算法时
5、间复杂度 对于一个 n*n 的 Hex 棋盘，共有2个单元格，将每个单元格依次标号为 1，2，2。采用蛮力方法寻找必胜策略，即穷举每种可能的玩法。每盘棋的下棋方法可以用一列数字表示，如1,2,3,表示前三部分别占据了第 1、2、 3 个单元格。那么，一共可能出现2!种可能的数列，即1,2,3,2 1,2，1,2,3,2,2 1，2,2 1,3,2,1。当然，实际游戏中会忽略很多情况，搜索空间会小得多。例如，在棋盘未填满时游戏可能已经结束。即便如此，穷举每种可能依然是很困难的事。实际上，寻找 Hex棋必胜策略已经被证明是 NP-Hard 问题3。二、Hex 游戏 AI 设计 在计算机上下棋的想法
6、由来已久，中国象棋、国际象棋、围棋、五子棋等棋类游戏都有非常流行的下棋软件。作为下棋软件的计算机程序，要保证下棋规则的执行、正确判断胜负，更吸引人的是，许多下棋软件都有十分出色的 AI（Artificial Intelligence，人工智能），即电脑自动与人对弈。我们尝试设计 Hex 游戏的 AI 程序。2.1 极小极大搜索和 alpha-beta 剪枝 极小极大化（mimimax）4是博弈论中的决策规则。在零和博弈中，对于每种结果，一方的收益是 V，则另一方的收益一定是-V（或者说损失是 V）。所以，一方要尽可能地使另一方的收益达到最小，即使自己的损失达到最小。在 Hex 棋中，从黑方的角
7、度看，对于每种局面，都可以通过评估函数（在后面讨论）得到黑方的收益值，收益值越大，表示黑方越有可能获胜。极小极大化是个递归过程，黑方落子时，考虑不同落子位置将导致的最大损失是多少，选择可以使损失最小化的位置。极小极大化可以看做搜索树，所以也称为极大极小搜索。每个结点代表当前的棋盘局面，分支表示符合规则的落子选择。例如，根结点表示空白棋盘(n*n)，游戏开始，黑方有2 个不同的位置选择落子，根结点有2 个分支；轮到白方落子，有(2 1)个位置可供落子，所以每个子结点有(2 1)个分支.依此类推，直到游戏结束。按照这个过程，要找到对黑方最有利的落子位置，搜索空间会随着层次深入呈指数级增长，因此完成
8、整个树的搜索是不可能的。所以极大极小搜索一般指定搜索深度，值进行有限层的搜索。极小极大搜索的伪代码表示： function minimax(node,depth,player)if depth=0 then return evaluate(node)if player=Black then a=NEGATIVE_INFINITY for each child of node do a=max(a,minimax(child,depth-1,White)else do a=POSITIVE_INFINITY for each child of node do a=min(a,minimax(ch
9、ild,depth-1,Black)return a 其中 evaluate(node)表示对当前棋局的估值，即前面提到的黑方的收益值，表示在当前位置落子后，对黑方获胜的有利程度。显然，估值函数的好坏直接影响 AI 的性能。另一方面，能够搜索的深度也是影响 AI 的重要因素。可以看到，极小极大化搜索算法的时间复杂度随深度的增加呈指数级增长，因此深度值过大的话，算法运行会很慢，无法在实际对弈中使用。为了解决这一问题，采用最广泛的方法是 alpha-beta 剪枝5，主要思想是加快对搜索树的剪枝。与一般的分支限界不同的是，Hex 博弈是一个最大化与最小化交替的问题，所以采用两个界：alpha 最为
10、下界，beta 作为上界。估值函数即时我们需要的代价函数。通过 alpha-beta 界和估值函数，我们可以有效加快搜索树的剪枝，降低算法时间复杂度。通过 Alpha-beta 剪枝改进的极小极大搜索：Function alpha_beta(node,depth,alpha,beta,player)If depth=0 then return evaluate(node)if play=black then for each child of node do alpha=max(alpha,alpha_beta(child,depth-1,alpha,beta,White)if alpha=b
11、eta then break return alpha else do for each child of node do beta=min(beta,alpha_beta(child,depth-1,alpha,beta,Black)if beta=alpha then break return beta/*开始执行*/alpha_beta(root,depth,+,Black) 2.2 估值函数的设计 对弈类游戏 AI 有一些通用的设计策略，例如前面提到的极小极小搜索、alpha-beta 剪枝等，最困难的部分则在于估值函数的设计，即如何量化对当前局面好坏的评价。回顾一下 Hex 棋的获胜
12、条件：黑方（或白方）采用黑色（或白色）棋子将自己的一对边界连接起来。一种直观的想法是，在当前局势下，考察黑子最少需要几步获胜。但是，这种方法实际上无法很好地反映当前局面的好坏。例如，图 2中，黑方至少需要 4 步获胜，而白方最少只需要 2 步获胜。然而仔细分析会发现，无论轮到哪一方落子，对于这个棋局黑方都有必胜策略。因为白方试图连接两个白色边界时，很容易被黑方阻断。而黑方只要占据任意一个“1”位置和“2”位置，都会导致必然连接，不会被白方阻止。图 2 当然，我们无法找到完美的估值函数，对每个局面做出最准确的衡量。这里只给出一个简单有效的方法：通过“最大流”解决估值问题。将 Hex 棋盘用图表示
13、，图 3 是一个 5*5 棋盘在某个状态的图表示： 图 3 图 3 中，每个节点对应棋盘中的格子，边表示格子之间的相邻关系。黑色圆表示该位置被黑子占据，白色圆表示该位置被白子占据。增加两个点 s 和 t，黑方的目的是将 s、t 用黑子相连，而白方则要阻止黑方。为了通过网络流来模拟Hex 棋，对上图进行简单转化：将白子占据的结点直接删除；将黑子占据的结点的相邻结点相互连接，然后将黑子也删除。将转化后的新图称为“缩减图”。上图对应的缩减图为：图 4 图 4 中，源发 s 出的边和汇点 t 吸收的边具有无穷大的容量，其余的边的容量都是 1。于是，网络流模型与图的连通性有关，即流越大，代表有更多的路径
14、可以将 s、t 相连，我们可以近似认为在这种情况下，黑方越有可能获胜。用网络流模拟 Hex 棋局是有意义的。然而，Hex 棋对应的图是一个无向图，我们需要得到一个有向图来对应网络流模型。与源点s和汇点t关联的边可以直接指定方向，即s永远作为边的起点，t 永远作为边的终点。对于其他结点关联的边，我们这样指定边的方向：如果该边已经为有向边，直接跳过；否则，对于每个结点 v，将 v 最为坐标原点，位于y 轴正半轴或 y 轴右侧的边为由 v 流出的边，位于 y 轴负半轴或 y 轴左侧的边为流入 v 的边。例如，图 5 中的部分边指定方向的结果：图 5 这样，我们得到一个网络流模型，对 Hex 棋局面估
15、值通过求最大流完成。可以通过各种最大流算法来求解。这里采用经典的 Ford-Fulkerson 算法6： Algorithm Ford-Fulkerson Input:G=(,),for each e E,capacity of e,a source node s,a sink node t Output:maximum flow f from s to t for each edge(u,v)in E do f(u,v)=0 while there is a path p from s to t in do ()=min(,):(,)for each edge(,)in p do f(,)=
16、f(,)+()f(,)=f(,)()(,)就是最大流值，也是我们对当前局面的估值。Ford-Fulkerson 算法的时间复杂度是O(|f),|表示图中边数，f 表示最大流。对于 Hex 棋，图中除了 s 发出的边和 t 吸收的边的容量为无穷大，其他边的容量都是 1。实际上，我们没必要把 s 和 t 关联的边的容量设的那么大。对于 s发出的每条边(s,u),只要满足c(s,u)(,)即可。同样，对于任意(v,t)E,保证c(v,t)(,)。对于一些特殊情况，例如 s 和 t 直接相连（已经获胜），s 和 t 有共同相邻结点等，我们将采用规则判断的方法而不使用最大流算法。最大流值不会超过缩减图删
17、除 s、t 后剩余的边数。随着游戏的进行，缩减图的边数和顶点数会有所变化（比如白子和黑子占据的结点被删除，边有可能增多），顶 点 数 只会 越 来越少，即 顶点 的 上界是 2+2,也 就是 边数 的 上界 是(2+1)(2+2)2,所以对 n 阶 Hex 棋缩减图求解最大流的时间复杂度为：O(2+1)(2+2)(2+1)(2+2)4)=(8)三、进一步工作 用最大流来估值并不是完美的方法，一般的网络流不能代表 Hex 棋局的各种复杂变化，估值函数还有较大的提升空间。而且，时间复杂度为O(8)的估值算法对于 AI 程序依然需要提高。其实这里仅给出了一个很粗的上界，通过进一步分析可以得到更精确的
18、复杂度。也可以采用其他效率更高的最大流算法。另外，Hex 棋对应的是一种很特殊的网络流，可以对最大流算法作更有针对性的优化。也有人研究了寻找 Hex 棋获胜策略的其他方法，例如启发式规则7，蒙特卡 罗树搜索等8。我们可以利用 Hex 棋中的一些启发式规则，例如必然连接，即在该位置落子后，可以保证一定能够与边界相连，也称为“桥”。然而，完全依赖启发式规则是不现实的，我们无法找到所有有效的落子规则，而且存储每一种规则也是不实际的。因此，将启发式规则与一种搜索方法（如极大极小搜索、蒙特卡罗树搜索）相结合，往往能取得不错的效果。此外，真正实现 Hex 游戏 AI 还有许多细节问题需要考虑，比如如何设计
19、存储图的数据结构，如何快速判定胜负，等等。在后续工作中将编程实现 AI 程序及游戏界面。四、总结 本文介绍了 Hex 棋的背景和游戏规则，证明存在先手必胜策略，通过分析遍历 Hex 棋的时间复杂度说明寻找必胜策略的难度。详细介绍如何设计 Hex 游戏AI，重点介绍极小极大搜索和 alpha-beta 剪枝策略。最后将 Hex 棋抽象为网络流模型，通过求解最大流来得到对当前棋局的估值，并对估值算法的时间复杂度进行分析。最后对后续工作进行简单说明。总之，本文通过运用 alpha-beta 剪枝和最大流算法，一定程度上解决了设计 Hex 游戏 AI 的问题，具有一定的实际意义和趣味性。参考文献 1
20、Martin Gardner.Mathematical GamesConcerning the game of Hex,which may be played on the tiles of the bathroom floor.Scientific American,197:145150,1957.2 David Gale.The Game of Hex and the Brouwer Fixed-Point Theorem.The American Mathematical Monthly,86:818827,1979.3 Thomas Maarup.Everything You Alwa
21、ys Wanted to Know About Hex But Were Afraid to Ask.2005.4 Wikipedia.http:/en.wikipedia.org/wiki/Minimax.5 Wikipedia.http:/en.wikipedia.org/wiki/Alpha-beta_pruning.6 Wikipedia.http:/en.wikipedia.org/wiki/Ford-Fulkerson_algorithm.7 Jack van Rijswijck.Search and Evaluation in HEX.University of A 8 Broderick Arneson,Ryan B.Hayward,Philip Henderson.Monte Carlo Tree Search in Hex.Transactions on Computational Intelligence and AI in Games.2010.