棋类游戏的算法有哪些棋类游戏的算法有哪些棋类游戏通常包含三大要素：棋盘、棋子和游戏规则，其中游戏规则又包括胜负判定规则、落子的规则以及游戏的基本策略。下面小编来给大家讲讲各类棋类游戏的算法。除了棋盘和棋子的建模，棋类游戏最重要的部分就是AI算法的设计。目前棋类游戏的AI基本上就是带启发的搜索算法，那么常用的搜索算法有哪些呢?1.博弈与博弈树博弈可以理解为有限参与者进行有限策略选择的竞争性活动，比如下棋、打牌、竞技、战争等。根据参与者种类和策略选择的方式可以将博弈分成很多种，比如“二人零和、全信息、非偶然”博弈，也就是我们常说的零和博弈(Zero-sumGame)。所谓“零和”，就是有赢必有输，不存在双赢的结果。所谓“全信息”，是指参与博弈的双方进行决策时能够了解的信息是公开和透明的，不存在信息不对称的情况。比如棋类游戏的棋盘和棋子状态是公开的，下棋的双方都可以看到当前所有棋子的位置，但是很多牌类游戏则不满足全信息的条件，因为牌类游戏都不会公开自己手中的牌，也看不到对手手中的牌。所谓的“非偶然”，是指参与博弈的双方的决策都是“理智”的行为，不存在失误和碰运气的情况。在博弈过程中，任何一方都希望自己取得胜利，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利同时对对方最为不利的那个行动方案。当然，博弈的另一方也会从多个行动方案中选择一个对自己最有利的方案进行对抗。参与博弈的双方在对抗或博弈的过程中会遇到各种状态和移动(也可能是棋子落子)的选择，博弈双方交替选择，每一次选择都会产生一个新的棋局状态。假设两个棋手(可能是两个人，也可能是两台计算机)MAX和MIN正在一个棋盘上进行博弈。当MAX做选择时，主动权在MAX手中，MAX可以从多个可选决策方案中任选一个行动，一旦MAX选定某个行动方案后，主动权就转移到了MIN手中。MIN也会有若干个可选决策方案，MIN可能会选择任何一个方案行动，因此MAX必须对做好应对MIN的每一种选择。如果把棋盘抽象为状态，则MAX每选择一个决策方案就会触发产生一个新状态，MIN也同样，最终这些状态就会形成一个状态树，这个附加了MAX和MIN的决策过程信息的状态树就是博弈树(GameTree)。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所获得的极小值中最大的那个值比β小，则更新β值(用这个最大值代替β)，也就是降低β这个上限。当某个节点的α≥β时，说明该节点的所有子节点的