象棋人机对弈程序的思想

wuye

　　电脑与玩家下象棋，围棋，五子棋，斗地主，三国杀等等，我们称之为人机博弈。下面以象棋为例，说说人机博弈程序的基本思想。

　　这种对弈程序主要涉及到3个方面，分别是走法产生、估值算法和搜索技术。

　　走法产生就是遍历当前局面的所有可行走法。

　　上面的程序描述了红卒的走法。只要遍历每一种棋子的走法，通过AddMove添加到列表之中，走法表便形成了。

　　了解走法产生后，就要介绍下估值算法了，总之就是评估一个局面好坏的算法。这里介绍三种评估方法，其一是计算棋子的价值，其二是计算棋子的灵活性（棋子有没有被挡住），其三是计算棋子的关系（有没有威胁到对方棋子），将这几种方法结合起来，就可以得出较好的估值结果了。

　　有了走法产生和估值，就能够产生一颗博弈树，接下来就要了解怎样找到一个最好的走法了。

　　可以用下面的图来解释极大极小值算法，这是一个两层的博弈树，c1的估值是8，c2的估值是10。假如程序走红方，现在在B1局面，轮到黑方下棋，最坏的情况就是黑方走到c1局面，因为这时候局面对红方的估值最小。所以B1的估值是c1，c2，c3的最小值，也就是8，B2和B3同理，得出的估值分别是5和10。假如现在在局面A，轮到红方走，那自然要走一步对自己最有利的，于是选择了B3。

    如下图所示，当程序计算到c4的时候，得出c4是7，因为B2取的是下面节点的最小值，所以B2 <= 7，而B1 = 8，所以在A局面到B1，B2，B3局面选择时，就不可能选择B2了。这时候C5和C6就可以不用计算了，直接抛弃，有点像减掉一棵树的枝叶，称为剪枝，这是对搜索算法的一种优化。

　　完成了，了解了这一思想，你便也了解了五子棋、围棋、斗地主、三国杀等等人机博弈程序的思路了。

野兽神话

思路清晰，可操作性强，谢谢分享

hyu86

正在需要中，受教了，谢谢。
鲜花送上
/　\./　\/\_
　 __{^\_ _}_　 )　}/^\
　/　/\_/^\._}_/　//　/
  (　(__{(@)}\__}.//_/__A___A______A_______A_
　\__/{/(_)\_}　)\\ \\---v----V-----V--Y----v---Y-----
　　(　 (__)_)_/　)\ \>　　
　　 \__/　　 \__/\/\/
　　　　\__,--'　　　　

wuye

hyu86 发表于 2015-1-30 16:42
正在需要中，受教了，谢谢。
鲜花送上
/　\./　\/\_

你应该感谢作者么么哒！！

hyu86

wuye 发表于 2015-1-30 16:51
你应该感谢作者么么哒！！

作者谢，转者也谢，不过作者估计是看不到的

天人合一

谢谢分享，前段时间学过一个象棋的程序。现在看这个更清晰明了