首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，对对方不利。当评价函数小于0时，表示棋局对我方不利，对对方有利。而评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜。评价函数值越小，表示对我方越不利。当评价函数值等于负无穷大时，表示对方必胜。假设双方都是对弈高手，在只看一步棋的情况下，我方一定走评价函数值最大的一步棋，而对方一定走评价函数值最小的一步棋。会下棋的读者都知道，在只看一步的情况下最好的棋，从全局来说不一定就好，还可能很不好。因此为了走出好棋，必须多看几步，从多种可能状态中选择一步好棋。
想一想人是如何下棋的呢？人实际上采用的是一种试探性的方法。首先假定走了一步棋，看对方会有那些应法，然后再根据对方的每一种应法，看我方是否有好的回应这一过程一直进行下去，直到若干步以后，找到了一个满意的走法为止。初学者可能只能看一、两个轮次，而高手则可以看几个，甚至十几个轮次。
极小极大搜索方法，模拟的就是人的这样一种思维过程。当轮到我方走棋时，首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。然后从d-1层节点开始逆向计算：对于我方要走的节点（用MAX标记，称为极大节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）；对于对方要走的节点（用MIN标记，称为极小节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）。一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步。
在图35所示的例子中，假定搜索深度为2，D～J是7个叶节点，在它们下边括号中的数字是这些节点的评价函数值（假定可以计算得到）。A、B、C是三个极小节点，它们分别取各自子节点最小值为自己的值，得到三个节点的值分别为-6、-2和-4。s是极大节点，从A、B、C三个节点的值中取最大值，得到-2。由于-2来自于节点B，所以搜索的结果是应选择B作为我方的走步。对于我方来说，-2并不是一个好的结果，但却是在对方不犯错误的情况下，对我方最有利的结果。因为从图中可以看出，如果选择A为我方的走步，如果对方回应D的话，我方可以得到评价值9，固然对我方有利。但是如果对方是一个高手的话，他一定回选择E，而不是D。在这种情况下，我方只能得到-6，结果岂不是更差。因此，极小极大过程是一种假定对手每次回应都正确的情况下，如何从中找出对我方最有利的走步的搜索方法。
值得注意的是，不管设定的搜索深度是多少层，经过一次搜索以后，只决定了我方一步棋的走法。等到对方回应一步棋之后，需要在新的棋局下重新进行搜索，来决定下一步棋如何走。极小极大搜索策略是考虑双方对弈若干步之后，从可能的走步中选一步相对好棋的着法来走，即在有限的搜索深度范围内进行求解。为此要定义一个静态估计函数f，以便对棋局的势态（节点）作出优劣估值，这个函数可根据势态优劣特征来定义（主要用于对端节点的"价值"进行度量）。一般规定有利于MAX的势态，f（p）取正值，有利于MIN的势态，f（p）取负值，势均力敌的势态，f（p）取0值。若f（p）＝＋∞，则表示MAX赢，若f（p）＝－∞，则表示MIN赢。下面的讨论规定：顶节点深度d＝0，MAX代表程序方，MIN代表对手方，MAX先走。
图35是一个表示考虑两步棋的例子，图中端节点给出的数字是用静态函数f（p）计算得到，其他节点不用f（p）估计，因为不够精确，而应用倒推的办法取值。例如A、B、C是MIN走步的节点，MAX应考虑最坏的情况，故其估值应分别取其子节点f（p）估值中最小者，而s是MAX走步的节点，可考虑最好的情况，故估值应取A、B、C值中的最大者。这样求得f（s）＝－2，依此确定了相对较优的走步应是走向B，因为从B出发，对手不可能产生比f（s）＝－2更差的效果。实际上可根据资源条件，考虑更多层次的搜索过程，从而可得到更准确的倒推值，供MAX选取更正确的走步。当用端节点的静态估计函数f（p）求倒推值时，两位选手应采取不同的策略，从下往上逐层交替使用极小和极大的选值方法，故称极小极大过程。
棋类游戏的算法有哪些
棋类游戏通常包含三大要素：棋盘、棋子和游戏规则，其中游戏规则又包括胜负判定规则、落子的规则以及游戏的基本策略。下面我来给大家讲讲各类棋类游戏的算法。
除了棋盘和棋子的建模，棋类游戏最重要的部分就是AI算法的设计。目前棋类游戏的AI基本上就是带启发的搜索算法，那么常用的搜索算法有哪些呢
1 博弈与博弈树
博弈可以理解为有限参与者进行有限策略选择的竞争性活动，比如下棋、打牌、竞技、战争等。根据参与者种类和策略选择的方式可以将博弈分成很多种，比如“二人零和、全信息、非偶然”博弈，也就是我们常说的零和博弈(Zero-sum Game)。所谓“零和”，就是有赢必有输，不存在双赢的结果。所谓“全信息”，是指参与博弈的双方进行决策时能够了解的信息是公开和透明的，不存在信息不对称的情况。比如棋类游戏的棋盘和棋子状态是公开的，下棋的双方都可以看到当前所有棋子的位置，但是很多牌类游戏则不满足全信息的条件，因为牌类游戏都不会公开自己手中的牌，也看不到对手手中的牌。所谓的“非偶然”，是指参与博弈的双方的决策都是“理智”的行为，不存在失误和碰运气的情况。
在博弈过程中，任何一方都希望自己取得胜利，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利同时对对方最为不利的那个行动方案。当然，博弈的另一方也会从多个行动方案中选择一个对自己最有利的方案进行对抗。参与博弈的双方在对抗或博弈的过程中会遇到各种状态和移动(也可能是棋子落子)的选择，博弈双方交替选择，每一次选择都会产生一个新的棋局状态。
假设两个棋手(可能是两个人，也可能是两台计算机)MAX和MIN正在一个棋盘上进行博弈。当MAX做选择时，主动权在MAX手中，MAX可以从多个可选决策方案中任选一个行动，一旦MAX选定某个行动方案后，主动权就转移到了MIN手中。MIN也会有若干个可选决策方案，MIN可能会选择任何一个方案行动，因此MAX必须对做好应对MIN的每一种选择。如果把棋盘抽象为状态，则MAX每选择一个决策方案就会触发产生一个新状态，MIN也同样，最终这些状态就会形成一个状态树，这个附加了MAX和MIN的决策过程信息的状态树就是博弈树(Game Tree)。
2 极大极小值搜索算法
极大极小值(Min-Max)搜索算法是各种博弈树搜索算法中最基础的搜索算法。假如MAX和MIN两个人在下棋，MAX会对所有自己可能的落子后产生的局面进行评估，选择评估值最大的局面作为自己落子的选择。这时候就该MIN落子，MIN当然也会选择对自己最有利的局面，这就是双方的博弈，即总是选择最小化对手的'最大利益(令对手的最大利益最小化)的落子方法。作为一种博弈搜索算法，极大极小值搜索算法的名字就由此而来。
3 负极大值搜索算法
博弈树的搜索是一个递归的过程，极大极小值算法在递归搜索的过程中需要在每一步区分当前评估的是极大值节点还是极小值节点。1975年Knuth和Moore提出了一种消除MAX节点和MIN节点区别的简化的极大极小值算法，称为负极大值算法Negamax。该算法的理论基础是：
max(a,b) = -min(-a, -b)
简单地将递归函数MiniMax()返回值取负再返回，就可以将所有的MIN 节点都转化为MAX节点，对每个节点的搜索都尝试让节点值最大，这样就将每一步递归搜索过程都统一起来。
4 “α-β”剪枝算法
有很多资料将“α-β”剪枝算法称为“α-β”搜索算法，实际上，它不是一种独立的搜索算法，而是一种嫁接在极大极小值算法和负极大值算法上的一种优化算法。“α-β”剪枝算法维护了一个搜索的极大极小值窗口：[α,β]。其中α表示在搜索进行到当前状态时，博弈的MAX一方所追寻的最大值中最小的那个值(也就是MAX的最坏的情况)。在每一步的搜索中，如果MAX所获得的极大值中最小的那个值比α大，则更新α值(用这个最小值代替α)，也就是提高α这个下限。
而β表示在搜索进行到当前状态时，博弈的MIN一方的最小值中最大的那个值(也就是MIN的最坏的情况)。在每一步的搜索中，如果MIN所获得的极小值中最大的那个值比β小，则更新β值(用这个最大值代替β)，也就是降低β这个上限。当某个节点的α≥β时，说明该节点的所有子节点的评估值既不会对MAX更有利，也不会对MIN更有利，也就是对MAX和MIN的选择不会产生任何影响，因此就没有必要再搜索这个节点及其所有子节点了。
5 估值函数
对于很多启发式搜索算法，其“智力”的高低基本上是由估值函数(评估函数)所决定，棋类游戏的博弈树搜索算法也不例外。
估值函数的作用是把一个棋局量化成一个可直接比较的数字，这个数字在一定程度上能反映取胜的概率。棋局的量化需要考虑很多因素，量化结果是这些因素按照各种权重组合的结果。这些因素通常包括棋子的战力(棋力)、双方棋子占领的空间、落子的机动性、威胁性(能吃掉对方的棋子)、形和势等。
6 置换表与哈希函数
置换表(transposition table)也是各种启发式搜索算法中常用的辅助算法，它是一种以空间换时间的策略，使用置换表的目的就是提高搜索效率。一般情况下，置换表中的每一项代表者一个棋局中最好的落子方法，直接查找置换表获得这个落子方法能避免耗时的重复搜索，这就是使用置换表能大幅提高搜索效率的原理。
使用置换表最大的问题是置换表的组织和查找的效率。一般来说，置换表越大，查找的命中率就越高。但这个关系不是绝对的，当置换表大小达到一定规模后，不仅不会再提高命中率，反而会因为耗时的查找 *** 作影响算法的效率。所以置换表不是越大越好，需要根据计算机的性能以及搜索的深度选择一个合适的大小。此外，为了查找 *** 作更高效，通常都会用可直接访问的哈希表方式组织置换表，哈希函数的性能就成为影响置换表性能的重要因素。棋类游戏普遍采用Zobrist哈希算法。
其实这个不是难点的，那个分数是当前落子后所形成的以这个棋子为中心的9x9矩阵中所形成的棋型，计算其他地方的棋型显然没有什么意义，再有就是不是C语言才可以写算法的，对于极大极小原理，博弈树和alpha-beta剪枝算法都是基于这个原理的，如果你是刚学编程不久，而且没有数据结构的基础是写不出来运用博弈树算法的五子棋的，先把基础打好再说。。最大最小值算法现在我们来看看博弈树节点标注的另一种方法：最小最大值方法。整个博弈树尽管大的出奇，然而在只有一部分有用的情况下，利用最小最大值方法是有其优点的，很容易推广使用。
比方说，竞赛的结果是以钱为赌注的。为方便起见，设赌金为一块钱。如果棋手赢的，他就获得一块钱；如果他输了，这输一块钱。在和局的情况下，他不输也不赢。
我们把棋手赢的钱称之为收益。如果棋手赢了，其收益为1；如果输了，收益为-1；和局时为0。
现在我们来定义一个节点的值。对于w节点其收益为1；l为-1；d为0。
我们用不着一定要先把节点标上w、d或l，然后再去注明它们的值，而是可以直接计算出它们的值。
前面我们已经知道，对于每一个叶节点，比赛的结果或者是赢、或者是输、或者是和局。因此我们先把比赛能赢的那些叶节点标上1，把和局的节点标上0，把输的节点标上-1。
如同我们前面说过的那样。从叶节点开始，其余节点按照其子节点的值来计算出它的值，一直到把根结点的值算出来。
这种计算后面所包含的想法是：棋手总是选择能得到最大收益的棋步；而对手总是选择通往最小收益的棋步。更确切地说，我们按下面的规则来计算每个节点的值：
轮到棋手走时，节点的值是其子节点之中的最大值。
轮到对手走时，节点的值为其子节点中的最小值。
如何用最小最大值方法来计算节点的值，这在图中作了说明。
到现在为止，最大最小值方法已经给我们提供了一个简明而有效的手段来标注博弈树的节点。然而，这种方法不是采用任意的标号，如前面所说的w、l或d来标注节点，而是用数字来标注。这样做使得我们能够很容易的推广这个方法，不用把节点的值局限于1、0或-1。
终局评价
现在我们终于要面临这样一个不能回避的问题：即对于其国际象棋这样一类的比赛，我们不可能建造一个完整的博弈树。甚至也不可能建造该博弈树的基本部分。我们充其量所能做到的，就是围绕目前正在下的棋局，把博弈树中的很小一部分建造出来。
这样一来，我们所建造起来的博弈树的根就不再是棋赛的起始棋局，而是轮到棋手走的那个棋局。在博弈树中，我们对那些已经下过的棋局并不感兴趣，而只关心那些将要下的棋局。
同样的，这时博弈树的叶也不再代表这场棋赛赢、输或者和棋的终局，而是表示在合理的时间和允许的存储空间内，比赛路径所能达到的博弈树的最远的节点。
我们还是沿用以前采用的方法，把对应于叶节点的棋局叫做终局。那么，什么是终局的判断标准呢？或者更确切的说，在探索一条特定的比赛路径时，什么时候终止这种探索对竞赛才是有意义的呢？
一般我们倾向于首先对终局标上它们各自的值，用以反映每个终局对棋手的价值。然后我们用最小最大值方法来处理这些值。因此在考虑到双方所拥有的棋子的数量、类型以及它们在棋局中的作用等因素以后终局的值就可以很可靠的评价出来。
如果有一个棋局不能用这种方法来进行可靠的评价，那么该棋局就不是一个合适的终局。
深度优先的最大最小值算法
现在我们回头来看看棋手对当前的棋局是如何考虑的，以及应如何决定下一步的走法。假设有了一种方法，它对任何棋局都可以给出所有的合法棋步，同时还能给出采用这些合法棋步中任何一步以后所形成的新的棋局。另外我们假设已经有了上面所谈到判断终局的方法。我们希望能决定棋手应走的棋步。
我们从当前的棋局开始，将其扩展，然后再扩展它的子棋局，如此类推。这样我们就得到了一个部分博弈树。但是，每一个结点在展开之前，我们都要先检测这个节点是否为终局。如果是终局那么就不展开这个节点；如果不是那么就展开它。
上述的扩展一直进行下去，直到所有的节点都不能再展开为止。最后我们得到了这样一个博弈树，它的根结点对应于当前的棋局而其叶节点对应于我们认为的终局。
应用最小最大值方法，我们对该博弈树的每一个结点都标注上一个值。如前所述，棋手所要走的节点，它的值是其所有子节点中的最大值；而对手所走的节点，它的值是其所有子节点中的最小值。由于这些节点的计算方法本身的原故，那些非叶节点所标注的值通常称为回溯值。
对棋手来说，他所选择的最佳棋步就是能够得到具有最大回溯值棋局的棋步。
在对手的下一步棋走完以后，那么就要从这时的当前棋局开始建造一个新的博弈树。这一过程会不断重复。因此，每一个部分博弈树实际上只是用来决定一步棋。真正用到的值仅仅是根的子节点的回溯值。这些子节点所对应的棋局就是棋手自由选择棋步所能走到的棋局。
实际上，我们的确用不着一次就把整个博弈树储存起来。如果运用一个叫做深度优先的最小最大值方法，那么在只储存整个博弈树的很小一部分的情况下，我们也能计算出根的子节点的值。当节点需要计算其值时，我们就产生这个节点；当节点已经完成它的使命之后，我们便删除这个节点。
同所有的深度优先方法一样，深度优先的最小最大值方法是从根部开始处理，沿着从亲节点到子节点的方向进行，直到遇到终局为止。然后再返回，一直到找到另一条未曾探索的路径，再沿着这条路径到终局为止，如此类推。
这一方法可以同时既建立博弈树，又对其节点进行估值计算。在沿着从亲节点到子节点的方向采用这一方法时，节点是展开的。当节点第一次展开时，只新建了一个子节点。其他子节点只有在过程返回并重新访问该节点时才建立。只有那些处于当前正在搜索路径上的子节点以及那些尚未标注回溯值的子节点才被储存起来。
当采用这种方法达到终节点时，就使用评价函数来处理该终节点所对应的棋局，并对该节点标上评价值。然后，这种过程又回溯到终结点的新节点上去。
如前所述，在回溯期间如果访问到某个节点，通常要对该节点继续进行扩展，产生一个新的子节点，进而在对该新的子节点进行处理。实际上，该节点的所有子节点最终都会产生出来（即相应的棋局的所有合法棋步都会被探测到）。在处理过程重新遇到该节点时，就根据其子节点的值来计算出该节点的回溯值。是取这些之节点中的最大值还是最小值作为回溯值，这取决于轮到哪一方下棋。这时所有的子节点就不再有用了，可以删除掉。程序过程又回到刚刚赋值的亲节点上，再继续上述过程。
除了那些正处于扩展路径上的子结点以外，我们不需要储存任何别的子节点。我们对每一节点只标出其部分回溯值。在该节点产生时，该值作为节点的初始值；在以后节点每次被重新访问时，该值都会被更新。在任何时候，一个节点的部分回溯值总是其计算出来的子节点中的最大值或最小值。当一个节点的所有子节点的值都计算出来以后，其部分回溯值就作为该节点的值，也就是所有子节点中的最大值或者最小值。
对于轮到棋手下棋的一个节点来说，其部分回溯值一开始就给定为一个很大的负数。当重新访问到这个节点时，就要把这个值同刚刚计算出来的子节点的值进行比较，取它们中间大的那个作为该节点的新的回溯值。
对于轮到对手下棋的一个节点来说，其部分回溯值一开始就给定位一个很大的正数。当重新访问到这个节点时，就要把这个值同刚刚计算出来的时间点的值进行比较，取它们中间小的那个作为该节点的新的回溯值。
在我们需要储存的任何时刻，应该储存的节点仅仅是从根节点到该时刻当前节点之间的路径上的那些节点。把这些节点储存到堆栈中是非常方便的。在堆栈中，根节点在底部，当前节点在顶部。
尽管我们能实现只储存博弈树中从根节点到当前节点中的那一部分，但是却不能保证说这是最佳的方法。有些程序就是把整个博弈树储存起来的，以便先前查看过的对弈路径能被重新访问，从而做进一步的的查询。然而，在储存空间受到限制时，这种节省空间的方法却是富有吸引力的。树是图，图不一定是树，树是图的子集
树有一个根节点，图没有
树可以递归遍历，图要看情况
树有层次划分，图没有
树的非根节点必定有一个父节点，图不一定
树是一种“层次”关系，图是“网络”关系
希望对你有帮助这种的话一般可能就是自己怎么去博弈，有一个正规的方法，你根据自己的逻辑世卫去参考吧。
一、启发式搜索策略即为结点排序技术。α-β搜索/剪枝算法的剪枝效率对同一结点下的孩子结点的排列顺序非常敏感，这些结点的排列越理想，则剪枝越早发生，需要展开和估值的结点数越少，算法效率越高，反之搜索效率越低。
二、虽然无法事先预知哪个结点是最佳结点，但却可以采取一些措施，让能产生剪枝的几率越高的结点越排在前面，以优先搜索，使博弈树尽可能接近最小树。
三、在博弈过程中，任何一方都希望自己取得胜利。因此，在某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时，如果我们站在A方的立场上，则可供A方选择的若干行动方案之间是“或”关系，因为主动权 *** 在A方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由A方决定。
四、若B方也有若干个可供选择的行动方案，则对A方来说这些行动方案之间是“与”关系，因为这时主动权 *** 在B方手里，这些可供选择的行动方案中地任何一个都可能被B方选中，A方必须考虑到对自己最不利的情况发生。
五、若把上述博弈过程用图表示出来，得到的是一棵“与/或”树。这里要特别指出，该“与/或”树是始终站在某一方(例如A方)的立场上得出的，决不可一会儿站在这一方的立场上，一会儿又站在另一方的立场上。
六、在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会生成十分庞大的博弈树。据统计西洋跳棋完整的博弈树约有1040个节点。试图利用完整的博弈树来进行极大极小分析是困难的。可行的办法是只生成一定深度的博弈树，然后进行极大极小分析，找出当前最好的行动方案。以中国象棋为例，在开局状态下，最初搜索时，置换表启发、历史启发、杀手启发这些动态启发起的作用很小甚至来不及起作用，此时吃子启发起的作用较大。因此，在着法生成时，考虑首先生成车、马、炮的着法，最后生成帅的着法，往往是很有效的。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）