前面我们介绍了提取人类知识然后用模糊推理来进行模糊控制。现在我们尝试下用人工智能来做斗地主。所选择的玩法规则是上海三打一，即两副牌、四个玩家。
根据该规则，我们可以将整个打牌过程分为：
-
洗牌：这个是最简单的，随机生成108张牌
-
发牌：将生成的牌的前100张按顺序发给四个玩家，留8张暗牌
-
叫牌：玩家评估自己手中的25张牌，计算叫牌牌力，并根据之前是否有玩家叫牌，确定自己的叫牌档数
-
整理牌型：根据自己手中的牌，整理出合适的牌型，即确定最佳的牌手组合，如2应该是算做对，还是放到A23456中
-
确定打牌策略：根据自己的牌型，评估牌力大小，弱点与优势，确定自己的出牌策略，即防守还是攻击、攻击路线等宏观的出牌思路以指导自己先后出牌的衔接、和同伴/对手的配合与对抗
-
出牌：根据自己的策略和实际每轮次各家的出牌情况，确定本轮次自己应如何出牌，如果有必要还需要重新调整出牌策略
其中，洗牌、发牌都非常简单，我们最后视情况看是否做个简单的讲解；叫牌的核心是如何计算自己手中的叫牌牌力，但这个计算过程其实比较简单，我们先放一下；整理牌型是后继确定出牌策略和实际确定每轮次如何出牌的基础，所以我们先解决这个问题。
整理牌型，也就是对25张（农民）或33张（地主）牌进行各种各样的组合尝试，以确定什么样的组合对自己最为有利。对于这样的问题，首选自然是蚁群算法。蚁群算法模拟一群蚂蚁外出寻找食物，每只蚂蚁自主的探索从蚁穴到食物之间的路线，然后布放信息素以告诉其它蚂蚁自己找到的路线，最后综合所有蚂蚁找到的路径来确定最短路线。简单的说，蚁群算法的要点是：
-
每一轮次，所有蚂蚁在全局信息素的引导下自主的寻找路径
-
对全局信息素进行一次蒸发（即影响越来越小）
-
确定本轮次各蚂蚁爬出来的最短路径
-
在最短路径上布放信息素（强化该路径的吸引力）
-
重复上述动作，直到找到最短路径或达到遇到最高轮次数
蚁群算法属于人工智能中的一个非常基础的元算法，而所谓的元算法就是一种算法框架，大家可以根据实际的应用领域加以变换来解决相应的问题。蚁群算法主要用来解决存在组合爆炸的难问题（NP）性质的构造性复杂问题，具体算法过程与介绍大家可以自行百度或购买书籍进行了解，我这里只简单讲述我对蚁群算法的理解。
首先，蚁群算法主要解决的是构造性的问题，即问题的解是通过一步步的选择下一步干什么从而构造出来的。对于此类问题，在每一步选择下一步的行为时如果存在一个非常大的选择空间，而且问题比较复杂，需要的步数比较多，则显然解空间是非常庞大的（其规模通常是n!起），此即我们通常所说的组合爆炸，也即通常所说的NP难问题。典型的此类问题有旅行家问题、最小背包问题等。蚁群算法的应用领域非常广泛，笔者之前就用蚁群算法解决过非常有用的贝叶斯网的生成问题。
各种游戏中就会大量用到贝叶斯网来做NPC的互动反应，如和玩家进行格斗时的动作选择等；其它诸如各种故障的自动排查、医院的门诊预检分科等应用贝叶斯网都能节省大量的专家人力
蚁群算法针对该类问题的算法框架包括两个层面：
- 单体的蚂蚁层面：实际爬出（从头到尾构造）一个解。这是实际的解题过程，根据不同的问题实现自然不同，但相对其它算法会简单了很多。不同的蚂蚁个体之间不需要协作，所以蚁群算法天然的具有分布式算法的特点
某些蚁群算法的改进版本可能需要频繁的对全局数据进行修改，这种情况下就不太适合分布式运行了
- 蚁群层面：主要是对蚁群进行管理，包括生成一定数量的蚂蚁、初始化（先让某个蚂蚁爬一下，以确定算法的基本参数）、控制蚁群分轮次爬、然后从中挑出本轮次的最优解，根据每轮次的最优解刷新算法参数，直到算法已经收敛（即最近几个轮次爬出的是同一个解）或达到了设定的轮次上限。这是蚁群算法的主体框架，一般不随问题的不同而变化
蚁群算法非常高效，针对我们的牌型选择问题，100只蚂蚁几乎是瞬间就爬出结果了，而且一般在第7、8趟就已经收敛了。
蚁群算法解决这类问题这么高效性的原因主要是：
-
问题自身的启发性知识，对于这类问题，由于解空间太过庞大，如果没有启发性知识，本质上就是对整个解空间的穷举！而启发性知识就是用来在面对庞大复杂的问题时的优先选择，人工智能本质上就是如何利用好启发性知识来降低问题难度的。对于我们的牌型选择问题，就是看当前牌（即手中的2、J等）如何组合牌型最优：如当前牌是9，那么是选择4个9做炸弹、还是选择3个9带对4、还是选择3456789做顺子，所以我们的启发性知识，就是对可选择的各手牌的牌力估计（下一讲我们来介绍如何评估牌力），然后进行加权概率选择，牌力越大，被选中的概率自然也越大
-
逐步寻找并保存优势结构最后组装出最优解，蚁群算法的核心思路其实是单只蚂蚁尝试性构造各种可能解，然后从这些可能解中选出比较好的结构保存下来。随着轮次的增多，优势结构就逐渐凸显出来了，最后通过将这些优势结构组合成最优解。这其实和进化算法的原理是一样的，但解决思路、具体手段是不同的
为了达到这个保存优势结构逼近最优解的目的，蚁群算法会：
-
为每轮次优胜的蚂蚁所爬出来的解在其所爬行的路径上布放信息素，即保存本轮次的优胜解，使得下一轮次本结构被选中的可能性增大。这其实会导致有更多的蚂蚁围绕着这个优胜结构进行探索，也就是对这个优胜结构进行优化
-
同时，对所有路径进行一次信息素的蒸发，即如果优势不能保持（发现了其它更好的选择）则其影响就会逐渐淡化
这样，随着一轮一轮优胜的蚂蚁布放自己爬行的信息素，优势结构就慢慢显现出来了。
蚁群算法之所以有效，归根结底是由于解分布的不均匀性：也就是说，绝大多数的情况下，大家都喜欢报团取暖:)
而解的相近性就表现在对于大多数的问题其有效解是成团聚集的，所以我们构造出一个优胜解之后，围绕这个优胜解进行优化（各个蚂蚁以加权概率的方式围绕着优胜解进行探索）就可以逐步逼近最优解。当然，由于解并不是围绕全局最优解聚集，而是围绕相邻的局部最优解进行聚集，也就是说解是在整个解空间分成了很多团，所以蚁群算法找到的这个最优解未必是整个解空间中的全局最优解，也可能只是一个局部最优解。针对这个情况，就需要我们具体问题具体分析了：
-
如果对最优解比较敏感，也就是说想尽可能的找到全局最优解，那么可以采用爬山法：即当算法收敛后，不再按启发性信息的指示来构造解，而是反向进行一次过冲，希图跳出当前解所在的山洼。看看这次得到的还是不是之前算法收敛得到的最优解，如果两次得到的最优解相同，一般情况下就认为我们找到的就是最优解，不同？！那麻烦就比较大啦，只好不停的爬山喽:)
-
如果不是太敏感，那么我们所找到的就可以作为满意解提交，这种情况下满意解比我们上面用爬山法所找到的最优解（还只是有可能是最优解）所花费的成本要小很多
一般来说，对于复杂些的问题，我们都只要求满意解即可，即给出的解符合一定的精度要求就可以了，因为对于NP难问题来说最优解的确定只能通过穷举来实现，实在得不偿失
对牌型选择来说，有了强大的蚁群算法，找到最优解不是问题，问题是如何保持牌型的灵活。因为斗地主是四个玩家分成两派的对抗，我们现在找出来的牌型是在对其他人的牌型一无所知的情况下按对自己最有利的方式找出来的。但随着牌局的推进，随着每个玩家出的每一手牌有利与否都在变化！比如，对A的牌力一般般，即算不上太大但也不算小；但当有玩家出了单张小鬼，自己还有三个2的情况下，对A的牌力就比较大了（对大鬼的可能比较小，即便有但用来打对A也非常不划算，那就剩5张2）；如果自己出了一个三带二，然后对家拿三张2进行了封堵，那么自己的对A的牌力就是非常大了（现在外面还有两张2还得在一家才能打掉对A）。
因此，如何进行这种动态判断在我们用蚁群算法解决了牌型选择问题之后就成了问题的关键。
针对这个问题，我们的解决方法有两个，一是反正计算机比人要记的多、记的牢，所以多挑选一些比较好的牌型（由于收敛的比较快，所以还不能只是每轮次的优胜解）用于评估，随时视情况更换备选的最优解；二是牌力评估随玩家的每手出牌动态的进行调整，这就会用到我们的模糊推理喽
====================================================================================================
关注我的公众号及时获取推送的最新文章
