0%
1、搜索树
1 2
| 任何棋类游戏都要定义一棵有根的树(即“博弈树”),一个结点就代表棋类的一个局面,子结点就是这个局面 走一步可以到达的一个局面。例如下图是井子棋(Tic-tac-toe)的搜索树:
|

评价函数
1 2 3 4 5 6 7
| 评价函数首先应该返回局面的准确值,在没办法得到准确值的情况下,如果可能的话启发值也可以。它可 以由两种方法来决定:
- 如果黑方被将死了,评价函数返回一个充分大的正数;如果白方被将死了,评价函数返回一个充分大的 负数;如果棋局是和棋,那么返回一个常数,通常是零或接近零。如果不是棋局结束局面,那么它返回 一个启发值。如果棋局是均势或者是和棋,那么返回在零左右的数值。 - 如果当前局面要走子的一方优势,那么它返回正数,反之是负数。
|
假设
1 2 3 4 5 6
| 假设某个中间结点的所有子结点都是叶子结点,那么棋局会在一回合内结束。现在我们假设棋手会挑选最 好的着法,
- 如果有一个着法能使他赢下棋局,那么他一定会走这步。 - 如果没有可以赢的着法,但是有取得和局的着法,那么他会走这步取得和局的着法。 - 如果所有的着法都使得对手获胜,那么无论如何他都会输。
|
应用
1 2 3 4 5 6
| - 推演棋局的结果。 - 在实战中,搜索算法只能对博弈树展开一部分。我们用一些“中止规则”来决定搜索树展开到哪个结点就 停下来。 - 评价函数来猜哪一方获胜。棋手甲总是希望棋局到达评价函数大的局面,而棋手乙总是希望棋局到达评 价函数小的局面。
|
2、Alpha-Beta搜索
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| 举个例子: > 每个口袋里有几件物品,你能取其中的一件,你来挑这件物品所在的口袋,而他来挑这个口袋里的物 品。 > 假设你一次只能找一只口袋,在找口袋时一次只能从里面摸出一样东西。 > 很显然,当你挑口袋时,你的死敌会把口袋里最糟糕的物品给你,因此你的目标是挑出“诸多最糟的 物品当中是最好的”那个口袋。 > 假设你可以正确地评价物品的好坏。 > 从第一个口袋开始,看每一件物品,并对口袋作出评价。比方说口袋里有一只花生黄油三明治和一辆 新汽车的钥匙。因此如果你挑了这只口袋就会得到三明治。因为我们的对手也会跟我们一样正确评价 物品。 > 现在你开始翻第二个口袋,你每次看一件物品,并跟你能得到的最好的那件物品(三明治)去比较。只 要物品比三明治更好,那么你就按照最小-最大方案来办——去找最糟的,如果最糟的要比三明治更好, 那么你就可以挑这个口袋,因为它比装有三明治的那个口袋好。比方这个口袋里的第一件物品是一张 20美元的钞票,它比三明治好。 > 如果二个口袋再下一件物品是一条烂鱼,那无论口袋里还有什么东西,或许还有另一辆汽车的钥匙, 也没有用了,因为你会得到那条烂鱼。
|
Alpha-Beta就是这么工作的。
最小-最大搜索
1 2 3 4 5 6
| A和B对弈,轮到A走棋了,那么我们会遍历A的每一个可能走棋方法,然后对于前面A的每一个走棋方 法,遍历B的每一个走棋方法,然后接着遍历A的每一个走棋方法,如此下去,直到得到确定的结果或 者达到了搜索深度的限制。当达到了搜索深度限制,此时无法判断结局如何,一般都是根据当前局面 的形式给出一个得分。 如下图:设圆形代表自己(A),正方形代表对手(B),节点的每个孩子节点代表一个候选方案。
|

1 2 3 4 5 6
| 假设用最小-最大搜索来搜索下面的树:
- 你搜索到F,发现子结点的评价分别是11、12、7和9,在这层是棋手甲走,我们希望他选择最好的值, 即12。所以,F的最小-最大值是12。 - 现在你开始搜索G,并且第一个子结点就返回15。一旦如此,你就知道G的值至少是15,可能更高。 这就意味着棋手乙肯定不走G这步。我们可以裁剪(Prune)结点G下面的其他子结点。
|

深的裁剪
1 2 3
| - 同一棵搜索树中,我们评价的G、H和I都比12好,因此12就是结点B的评价。 - 搜索结点C,在下面两层我们找到了评价为10的结点N。 - 如果从J返回到C的是10或者更小的值,那么我们可以在结点C上作裁剪,因为它有更好的兄弟结点B。
|
期望搜索
1 2 3
| - Alpha和Beta定义了一个评价的实数区间(Alpha, Beta),这个区间是我们“感兴趣的”。 - 如果某值比Beta大我们就会做裁剪并立即返回。 - 如果某值比Alpha小,我们不作裁剪,但是仍然对它不感兴趣,因为搜索树里肯定有一个着法会更好。
|
alpha-beta伪代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| double alphabeta(int depth, double alpha, double beta) { if (depth <= 0 || 棋局结束) { return evaluation(); } 就当前局面,生成并排序一系列着法; for (每个着法 m) { 执行着法 m; double val = -alphabeta(depth - 1, -beta, -alpha); 撤消着法 m; if (val >= beta) { return val; } if (val > alpha) { alpha = val; } } return alpha; }
|
3、数据结构的设计
4、开局库
5、置换表
6、空着裁剪