桌游有哪些算法？

象棋游戏通常包括棋盘、棋子和游戏规则三个要素，其中游戏规则包括胜负规则、走球规则和游戏的基本策略。我来给大家讲讲各种桌游的算法。

桌游除了棋盘和棋子的建模，最重要的部分就是AI算法的设计。目前桌游的AI基本都是启发性的搜索算法，那么常用的搜索算法有哪些？

游戏和游戏树。

博弈可以理解为有限的参与者做出有限的策略选择的竞技活动，如棋、牌、比赛、战争等。根据参与者的类型和策略选择的方式，游戏可以分为很多种，比如？两人零和，全信息，不是偶然？博弈，也就是我们常说的零和博弈。所谓？零和？就是赢了就是输了，没有双赢的结果。所谓？全部信息？，是指参与博弈的双方在决策时所能理解的信息是公开透明的，不存在信息不对称。比如象棋游戏中的棋盘和棋子都是开放的，双方都可以看到所有棋子的当前位置，但是很多卡牌游戏并不满足完全信息的条件，因为卡牌游戏并不公开自己的牌，看不到对手手里的牌。所谓？不是偶然？是否意味着参与博弈双方的决策都是？理性？行为，没有错误和偶然性。

在博弈的过程中，任何一方都想赢。当一方有多个行动方案可供选择时，他总是选择对自己最有利、对对方最不利的方案。当然，游戏的另一方也会从多个行动方案中选择一个最有利的方案进行对抗。在对抗或博弈的过程中，参与博弈的双方会遇到各种状态和移动的选择(或者棋子可能被移动)。博弈双方交替选择，每一次选择都会产生新的棋态。

假设两个棋手(可能是两个人或者两台电脑)MAX和MIN在棋盘上玩游戏。当MAX做出选择时，主动权在MAX手里，MAX可以从几个可供选择的决策方案中选择一个行动。一旦MAX选择了某个行动方案，主动权就转移到了MIN。MIN也会有几个可供选择的决策方案，MIN可能选择任何一个方案行动，所以MAX必须为MIN做好每一个选择。如果将棋盘抽象为状态，MAX选择的每一个决策方案都会触发一个新的状态，MIN也是如此。最后，这些状态会形成一棵状态树，这是一棵附有MAX和MIN决策过程信息的博弈树。

2.极大极小搜索算法

在各种博弈树搜索算法中，最小最大搜索算法是最基本的搜索算法。如果MAX和MIN在下棋，MAX会对自己走棋后可能出现的所有情况进行评估，选择评估值最大的情况作为自己的选择。这个时候是敏安定下来的时候了，敏当然会选择最有利于自己的情况。这就是双方的博弈，就是他总是选择最小化对方‘最大利益’(最小化对方最大利益)的方法。作为一种游戏搜索算法，极大极小搜索算法的名字由此而来。

3.负最大值搜索算法

博弈树的搜索是一个递归过程，极大极小算法需要在递归搜索过程的每一步区分最大节点和最小节点。在1975中，Knuth和Moore提出了一种简化的极大极小算法来消除极大节点和极小节点之间的差异，称为负极大算法。这种算法的理论基础是:

max(a，b) = -min(-a，-b)

只需将递归函数MiniMax()的返回值取负再返回，所有的MIN节点都可以转化为Max节点，对每个节点的搜索都尽量使节点值最大化，从而统一了每个递归的搜索过程。

4.？-?剪枝算法

很多信息会？-?剪枝算法叫什么？-?实际上，搜索算法并不是一个独立的搜索算法，而是嫁接在极大极小算法和负极大算法上的优化算法。？-?剪枝算法维护一个搜索minimax窗口:【？,?]。其中？表示搜索处于当前状态时，游戏MAX方所追求的最大值中的最小值(即MAX的最坏情况)。在搜索的每一步中，MAX得到的最大值中的最小值比是多少？大，然后更新？值(用这个最小值替换？)，也就是提高？这个下限。

然后呢。表示搜索处于当前状态时(即MIN最差情况)游戏MIN边的最大值。在搜索的每一步中，MIN的最大值是多少？小，然后更新？值(替换为这个最大值？)，也就是减少？这个上限。当一个节点的值为零时，说明其所有子节点的评价值不会更偏向MAX或MIN，即不会对MAX和MIN的选择产生任何影响，所以不需要搜索这个节点及其所有子节点。

5.估计函数

对于许多启发式搜索算法，哪一个？智力？的高低基本上是由评价函数(evaluation function)决定的，桌游的博弈树搜索算法也不例外。

估值函数的作用是将一盘棋量化成一个直接可比的数字，可以在一定程度上反映赢的概率。象棋的量化需要考虑很多因素，量化的结果就是这些因素按照各种权重组合的结果。这些因素通常包括棋子的战斗力(棋力)、双方占据的空间、棋子的机动性、威胁性(能吃掉对方的棋子)、形状和潜力。

6.置换表和散列函数

位移表也是各种启发式搜索算法中常用的辅助算法。是一种以空间换时间的策略，使用位移表的目的是为了提高搜索效率。一般来说，替换表中的每一项都代表了国际象棋比赛中的最佳方法。直接搜索替换表得到这种方法可以避免耗时的重复搜索，这就是使用替换表可以大大提高搜索效率的原理。

使用替换表最大的问题是替换表的组织和查找效率。一般来说，置换表越大，搜索的命中率越高。但这种关系不是绝对的。当置换表达到一定规模后，不但不会提高命中率，反而会因为耗时的搜索操作而影响算法的效率。因此，替换表越大越好。需要根据电脑的性能和搜索的深度来选择合适的大小。此外，为了使查找操作更加高效，置换表通常以可直接访问的哈希表形式组织，哈希函数的性能成为影响置换表性能的重要因素。Zobrist哈希算法在桌游中应用广泛。