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和Ｂ对弈，轮到Ａ走棋了，那么我们会遍历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、空着裁剪