博文
置换表与迭代加深(2006-08-02 16:13:00)
摘要：alpha-beta搜索是个很好的搜索方法，在这基础之上为了加快搜索速度，为了让程序搜索到更深的局面中去，才引入了置换表（实际上大部分棋类程序是离不开置换表的，像象棋，我可以让车左右重复走动，那相同的局面会一直出现，直接搜索真是费尽了力气）。
置换表实际上就是一个哈希表，它存储的是之前搜索过的局面，可以是一次搜索时遇到的相同局面，也可以是多次搜索时遇到的相同局面。它工作的时候，简单的来说，就是当搜索一个局面时，首先看是否在哈希表中，如果是直接取出来，而不进行搜索，同时每当完成一次搜索后，就把搜索出的结果存进哈希表。
这个表中要放些什么？
首先是评价值，在alpha-beta搜索中，有三种不同类型的评价值，alpha型：它在搜索的子结点中没有找到比当前最好的更好，也就是说至多是那么多，beta型：它在搜索的子结点中有比当前最差的更差，也就是说至少是那么多（差），如果搜出的评价值落在alpha-beta之间，那就是exact型，精确型。其次要放搜索深度，如果当前要对局面进行d层搜索，而发现该局面在置换表中存在，且搜索过d'层（d'>=d），那就可以直接取出来不进行搜索了。最后还有最佳着法。
置换表如何哈希？
比较常见的是使用Zobrist键值，这只是一种哈希方法，简单来看就是随机哈希。一个局面有哪些因素：当前谁走棋，每一格上有哪种类型棋，棋子的颜色，等等，我们把所有因素全部用随机数表示，然后将它们进行模2加得到的结果就看成是当前局面的一个key。拿黑白棋来说，可以这样表示Zobrist[pos][color]来表示局面上的棋子，pos取0~63,color取0~1，将局面上所有值模2加起来，然后如果是黑先就得到key，如果是白先就将它取反得到key，整个Zobrist[][]以64位的随机数填满。将得到的key再模上哈希表表长就得到了哈希值。哈希表最重要的是进行冲突处理，我看到一些程序根本没有冲突处理，想了好久不得其解，细细思来：冲突产生的原因在哪？可能是不同的局面得到了相同的key，也可能是不同的key存到了相同的哈希表位置，如果是前者，大可以不必担心，采用64位的Zobrist键值，随机性很大，如果随机数取得好，‘撞’到相同key的机率非常之低，如果是后者那就会产生非常严重的后果，当前局面分明没有搜索过，却和另外一个局面的哈希值一样，而误以为......
估值函数与优化搜索(2006-07-30 00:21:00)
摘要：前面说了最小最大原理，为什么要最小最大原理？为什么要搜索？我们可以更简单的看对弈这件事儿，下棋的时候，从一开始到结束，每当我要走棋时，我会考虑怎么走？有N种可行走法，但只能选一种，换个方式想这问题，人工智能不过是作一种‘选择’，而这里的‘选择’要能促使你最终赢棋！
可以选择的前提是要能分出谁高谁低，哪步着法臭，哪步着法妙，于是就需要要一个估值函数Eval(p),p是局面，也就是由这个评价函数分出哪个局面（或者着法，着法可以看成下一个局面）更好，如果Eval(p1)<Eval(p2)，我们就有理由说，或者大胆地说，p2比p1更好！但是很多时候，你并不能断言，你做的决定是最好的，这在于棋类游戏的复杂程度，像一些高深的棋类游戏，棋的变化非常多非常复杂，那你能完全相信你的估值函数吗？不能，有可能，现在看来一步很臭的棋，在不久的将来将会使局面变得很好，这就是妙手，这是经常出现的。出现这样情况的原因是，我们找到的估值函数都是从一个局面来看的，它是静止的，它看不到未来的变化，所以它是非常粗糙的。而搜索的目的正是为了‘更好的’评价棋局，可以把搜索看成是动态的估值！
如何估值？
这和具体的棋类游戏有关，同时也和你最终打包的程序的棋力有关，估得好，棋力高，这是很显然的。不管什么棋类的估值，它都有一个共同点：
对特定的局面估值要非常准确！特定的局面是那些‘胜负’非常明显的局面，你要为‘胜’打一个最高的分HScore，为‘负’打一个负最高的分-HScore，而‘平局’可以适中给分，可以给一个稍大于0的分，在不能获胜的局面里，会趋向于平局。
然后就是要有前瞻性，从一个局面分析，不搜索也不是不可以看得‘深刻’，也可以说是‘全局观’，估值函数要体现游戏的全局观，它是从整体上把握，从一个点看到了一条线！这样才是好的估值。
好了，下一个话题是‘优化搜索’，哦，这可难了，我现在还看不懂一些高级搜索算法。其实用负极大搜索算法编出来的程序是不能搜的，基本上不能搜。因为搜索量实在太大了！在一些规则简单的棋类游戏中，像黑白棋，平均分支因子都有10左右，直接去搜索，是搜不了几层的，这样的指数效应太明显了！最简单和最基本的优化方法是alpha-beta剪枝！
这是一种纯数学上的方法，是在不对搜索的结果影响的前提下剪枝，它可以使分支因子变为原来的开根号那么大（平均情况）！alpha是......
最小最大原理与搜索方法(2006-07-28 16:14:00)
摘要：我的黑白棋终于算是会走棋了，高兴了好一阵子，而且还能战胜我自己。我想把资料总结一下，以下所述的将从最简单的开始，与黑白棋无关，是广义的棋类博弈算法。网上有好多算法文章介绍，我只是简单概括一下。
最小最大原理
最小和最大是相反的矛盾的，正如下棋的两个人，他们是对手，他们在进行对抗，其中一个叫最小者，另一个叫最大者，最大者（想像成我）希望棋面对‘我’最好（最好是赢棋），最好就是最大，反过来，对手就希望棋面对‘我’最差，最差就是最小，最大就是对已最有利，最小就是对对方最有利。这里的最小最大，是有一个参照物的，不管以谁为参照物，它是固定的。最小和最大是对称的，平等的，就像两个重物挂在一杆称上，不断的在较劲。
而最小最大原理是说什么，它是说‘最大者’在选择最大（好）的棋走的时候，它要选对方在回应这步棋时最小（对对方最好）着法中的最大着法！（着法就是可以走的棋）这里涉及了一棵树，它叫博弈树，根在上面，倒长的一棵树。
根是当前局面，我要从当前局面的所有可行着法中选一个‘我认为’‘最佳’的着法走这步棋，这所有的可行着法，就对应着所有的子树，当走了某一步后，就到达了子树的根，同样的情况发生了，这时你是站在最小者的立场上想棋的，所以最小最大反了过来，孙子曰过‘知已知彼，百战不殆’，你不能站在对方的立场想问题，就无法取得胜利！
注意到，这其实是对博弈树的深度优先搜索，只是搜索的时候有两个对立的处理模块，最大搜索和最小搜索，最大的调用最小的，最小的调用最大的，是一个双递归。像这样：
int Max(int depth)//最大搜索
{
int best = -INFINITY;
if (depth <= 0)//depth是控制深度
{
return Evaluate();//返回对当前局面的‘看法’，估值
}
GenerateLegalMoves();//生成当前所有着法
while (MovesLeft())//遍历每一个着法
{
MakeNextMove();//实施着法
val = Min(depth - 1);//反过来搜索，站在最小者一方
UnmakeMove();//撤销着法
if (val > be......
了解遗传算法(2006-06-29 22:08:00)
摘要：了解遗传算法
遗传算法是一种最优化算法，所谓最优化问题，就是这样一类问题，满足它的解（称为可行解）有很多（通常是极多）对于每一种解有一个评价函数得到一个评价值，也就确定了解集的一个偏序关系，在这个偏序关系的求最小值（或最大值）或者近似最小值（或最大值）。因为通常可行解非常之多，所以确定性算法很难做到这一点，而遗传算法是模拟了生物学中物种进化的过程的一种最优化算法，简单来说，遗传算法=遗传操作+遗传选择。
在算法开始之前要做一下准备工作：编码。
对于不同的问题有不同的解的形式，但要运行遗传算法就要对其进行抽象的编码，也就是确定染色体的形式，这里的染色体就是用某种特定的编码方式描述一个解，通常一个具体的解也称为个体。而多个不同的个体就组成一个种群，一个种群内有统一的编码方式。这些概念都完全等同于生物学中的概念，它们是平行的。
例如，N个城市的旅行商问题(TSP)，假如用1,2,...N表示这N个城市，那对于任意这样的一个排列1p2p3...pN就表示了一个解，这个串就可以认为是一个染色体，它表示一个个体的基因。
遗传算法有一些基本的操作，如选择、交叉和变异等。
选择操作：
首先要知道适应度函数，所谓的适应度函数就是评价函数，通常是问题的目的函数（或它的倒数），它描述了个体的优劣程度同时也决定了选择操作的概率，设fi表示第i个个体的适应度值，那选择第i个个体的概率就是fi/∑fj，简单来说，这个概率的大小就决定了该个体是被淘汰还是被保留。通常的具体做法是用类似赌盘的方法，每个个体占它的适应度那么宽的转盘大小，每次掷色子，落到哪一格就选哪一格对应的个体。
交叉操作：
交叉操作就是让2个以上的染色体进行交叉产生后代的过程，具体的交叉操作要看具体的问题。不过我觉得有一个原则，就是要有对称性，交叉得到的后代中的基因要来源于父代的所有个体中，也就是说n个个体进行交叉是和它们的排列没关系，这样子代才有机会得到更优秀的基因。交叉操作是遗传算法中最重要的操作。最简单的基本方式是交换父代中染色体片段。
变异操作：
生物可以突变，有时候突变是好的，有时候却是坏的，但正是因为有了突变才让有限的种群中基因库可以非常丰富，也保证了种群的适应能力。变异操作通常是翻转个体中某段染色体，编码后的染色体在计算机中都是01串，也就可以......
博弈与人工智能(2006-06-15 02:50:00)
摘要：突然迷上了博弈算法，真是一件让我疯狂的事儿，我极渴望去做。
首先让我理下思绪，起码看清楚目前前人是怎样做的：
还是先给个网站吧，前天搜到的‘计算机博弈门户网站’URL:http://www.elephantbase.net，里面有好些老外写的译文，除了估值函数那部分太过潦草外（当然作者是都不愿意公开的），其它都讲叙得非常清楚。
1，博弈为什么这么有趣，这么有挑战，现在的计算机速度如此之快不是很容易解决吗？
我的理解是，这是因为棋类对弈中的‘变换’非常之多，我有一个表哥的中国象棋下得非常好，他原来对我说过一句话‘象棋这么有趣是因为，你一辈子都不会走出两盘完全相同的棋’，不信？那就算算，在棋类算法里都考虑一个叫‘博弈树’的状态树，树中每一个结点表示一个‘局面’，子结点表示可以由一步走成的局面，每一步可以有不同的‘着法’，着法的个数叫‘分枝因子’，当然每一个局面的分枝因子不尽相同，但大致差不多，就平均来算，中国象棋比较多，有30种左右，于是从上往下，可能走出的局面数成指数增长：1+30+30^2+30^3+...，不要以为只是简单的考虑30种着法，这里面的选择可并不简单。
所以，博弈的乐趣就在于不管是人还是机器都不可能完全了解这么大一棵树上的所有信息，不可能分析到所有的可能局面，于是就可以真正的较量。不要以为这只是数量问题，觉得只要计算机速度够快就可以完全解决，指数增长的东西除了上帝谁都追不上！机器的运算速度永远也追不上它的。所以智能的体现就在于‘方法’，我们只能求近似解，那就要看谁的更精确！
2，我们不能完全考虑，那就只考虑有限深度。迭代加深是很好的方法，如果不控制深度，那将和‘死机’的现象一样，程序掉进了博弈树中，永不回溯啦~当然实际当中很可能是系统栈用完。
3，按深搜的方式搜索，再控制搜索的深度，那要怎么取舍搜索出的结果呢？估值！也就是评价啊，不过要明确的是，这样的评价只是对一个局面做评价，就是说只是对一个点做评价，象棋是活的，动态的，所以不可能精确，但是它必须是近似正确的，有多接近就有多聪明（但是有一个局面的评价是非常准确的，那就是判负的局面，由规则得到）；更加简单的说，就是一个启发值，起到的作用只不过是让搜索少走一些‘弯路’。怎么估值？各种棋类游戏方法不同，不过有一......