象棋ai

1、搜索树

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

search_intro1

评价函数

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),节点的每个孩子节点代表一个候选方案。

img_1


1
2
3
4
5
6
假设用最小-最大搜索来搜索下面的树:

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

search_intro3

深的裁剪

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、空着裁剪