突然迷上了博弈算法，真是一件让我疯狂的事儿，我极渴望去做。

首先让我理下思绪，起码看清楚目前前人是怎样做的：

还是先给个网站吧，前天搜到的‘计算机博弈门户网站’URL:http://www.elephantbase.net，里面有好些老外写的译文，除了估值函数那部分太过潦草外（当然作者是都不愿意公开的），其它都讲叙得非常清楚。

1，博弈为什么这么有趣，这么有挑战，现在的计算机速度如此之快不是很容易解决吗？

我的理解是，这是因为棋类对弈中的‘变换’非常之多，我有一个表哥的中国象棋下得非常好，他原来对我说过一句话‘象棋这么有趣是因为，你一辈子都不会走出两盘完全相同的棋’，不信？那就算算，在棋类算法里都考虑一个叫‘博弈树’的状态树，树中每一个结点表示一个‘局面’，子结点表示可以由一步走成的局面，每一步可以有不同的‘着法’，着法的个数叫‘分枝因子’，当然每一个局面的分枝因子不尽相同，但大致差不多，就平均来算，中国象棋比较多，有30种左右，于是从上往下，可能走出的局面数成指数增长：1+30+30^2+30^3+...，不要以为只是简单的考虑30种着法，这里面的选择可并不简单。

所以，博弈的乐趣就在于不管是人还是机器都不可能完全了解这么大一棵树上的所有信息，不可能分析到所有的可能局面，于是就可以真正的较量。不要以为这只是数量问题，觉得只要计算机速度够快就可以完全解决，指数增长的东西除了上帝谁都追不上！机器的运算速度永远也追不上它的。所以智能的体现就在于‘方法’，我们只能求近似解，那就要看谁的更精确！

2，我们不能完全考虑，那就只考虑有限深度。迭代加深是很好的方法，如果不控制深度，那将和‘死机’的现象一样，程序掉进了博弈树中，永不回溯啦~当然实际当中很可能是系统栈用完。

3，按深搜的方式搜索，再控制搜索的深度，那要怎么取舍搜索出的结果呢？估值！也就是评价啊，不过要明确的是，这样的评价只是对一个局面做评价，就是说只是对一个点做评价，象棋是活的，动态的，所以不可能精确，但是它必须是近似正确的，有多接近就有多聪明（但是有一个局面的评价是非常准确的，那就是判负的局面，由规则得到）；更加简单的说，就是一个启发值，起到的作用只不过是让搜索少走一些‘弯路’。怎么估值？各种棋类游戏方法不同，不过有一点要注意，那就是效率，因为考查的局面可能非常之多，有可能简单快速的估值可以留出时间搜索更多的局面，那反而会使棋力更强一些。

4，博弈是双方面的，估值会只倾向于一方，比如黑方，估值是10的比估值是5的更好，同样的局面对于白方却是后者比前者更好，那具体应该如何选择？这里是最小最大原理，其实简单来说，就是把对方想得非常聪明，就是要选最不利的情况中的最有利的情况，举个例子，现在下中国象棋，我走，我考虑了两种走法a和b，如果走a，对方可以有c1和d1两种对策，如果走b，对方有c2和d2两种对策，那我就考虑，如果c1非常好，比如将死，而d1非常差，反被将死，那我能天真的想对方会走c1而不会走d1吗？不能，我应该把对方想得更聪明一些，那如果c2虽然不怎么好，比如有可能丢子，但d2不会差到输棋，那你会选择怎么走？考虑着法中，最不利情况中的最好情况，这就是最小最大原理，博弈的原理。

5，分枝因子太大要怎么优化？剪枝。怎么剪？alpha-beta搜索就是一种好的方法，它在考虑局面的时候，如果出现了比已经搜索过的局面更差的就放弃后面的搜索，这是数学上的剪枝，也就是说剪了之后和原来的结果是一致的。理论上也证明了可以减小分枝因子到平方根那么大，30变为6，多大的改进啊~~佩服中~~，值得注意的就是它跟搜索局面的顺序有关，我对这个的想法是，可以用随机化的手段避开最差的情况，或者用启发式，像五子棋，可以先对局面上可以放棋的空白地方，进行启发式估值，然后按价值从高到低的顺序搜索，像那些离得很远的着法可以直接丢弃不管，像围棋一个棋盘那么大，一百多个可能着法，真要搜索全怎么可能，找到一种评价方法选出关键着法搜索，其它的剪掉是唯一的办法。

还有很多方面我不了解，需要更多的学习。‘深蓝’能够战胜人类大师不仅仅因为算法，它是用世界上最快的计算机，而且是分布式设计的，可想而知运算能力有多强。另外，我觉得人们常讨论机器战胜人有没有可能，我完全相信可能，就目前来说，棋力强得全世界只有几个人下得赢的机器都有，可以说机器的AI可以排到世界排名的前100是肯定的，地球上有多少人？50亿，它能战胜这个行星上99.99998%的人，难道说没有战胜人？不过，机器的智能是人的智能的延伸，我们也可以觉得是这位设计它的人的成就。

好像讨论到了对智能的理解，现在随便拿来个五子棋程序，然后再找来一个刚学棋的小孩和它下，结果显而易见，难道说人没机器聪明？我觉得真正意义上的智能在于学习。人的大脑一秒钟分析3个局面，而计算机一秒钟几十万个，但有时候人还是赢了，为什么，人会靠经验判断，人是不断学习的‘智能’。在这方面也有很多例子，像开局库和残局库，就是吸取了人类的经验，这样电脑也可以完美的走残局了，有的残局相当的深，如果没有残局库，基本上战胜人是不可能的。但这是一种傻瓜式学习，是直接教会的，电脑一开始不会，甚至不能说是‘学习’。

像遗传算法，我觉得就可以学习，比如五子棋的估值，我们要怎么取呢？比如活四，死四等，我们只知道谁高谁低，但不知道具体取多少合适，用遗传算法，随机产生一系列这样的评价值，然后让电脑自己跟自己下棋，就像打比赛一样，然后每一种‘个体’都会取得一个总成绩，比如胜多少负多少，那按这个成绩就形成了个体差异，然后定期从种群中去掉差的个体，保留优秀个体，然后随机选取一些优秀个体进行交叉，比方说将对应值取平均，将产生后代，形成下一代种群，如此经过N代将得到一个优秀个体群，从中取几个成绩最优秀的就知道怎么估值最好（相对）了。

还有我的想法是，可以相对估值，估值函数不好平衡的时候就模糊处理，在实战中学习，其实跟进化原理差不多，当然这些都只在我脑子里有个影，具体做法还没底儿呢。


暑假准备做一下这方面实验和研究，从最简单的五子棋着手，我会更涉及一些自己的想法，去寻求让机器真正智能之道。今天开个头，又分了个类别出来。想睡觉了~~~

评论