Brief description:

诸葛亮和周瑜两个人正在玩曹操传。。
（反正就是某种战棋游戏。。。具体规则请参见题目。。）

Analysis:

Bug fixed : Orz 。。原来是对于移动后不攻击的操作符。。我的程序里认为它 delta 为 0 所以仍然按照一般的操作符处理，但是它会将 O[][] 数组错误覆盖掉。。。
（用来表示某个格子处棋子所属的。。）。。

前排膜拜这位仁兄的代码。。

Note : 调整搜索的顺序对 Alpha-beta 剪枝也会有效，我采用的是用这一步所造成的伤害作为第一关键字，这一步移动的距离作为第二关键字进行结点排序，
（。。感到这一步还可以往下搜若干个估价层。。然后用后几部的伤害、距离作为关键字。。。实际可能还需要设置一个 threshold 。。）

Test:

// Input 0: 。。。这组数据返回多少？
// Input 1: 敌方一名弓箭手占据地图中央的一块高地。。需要控制我方战车沿最佳路线躲避。。
// Input 2~3: 步兵和战车在一块开阔地带展开拉锯。。

Input 0:
3 3 5
0 2 2
2 0 2
2 2 0
3 1 1 1
1 1 0 1 1
2 2 1 10 0
3 3 0 100 2

0 0 0

Output 0:
91 91.5 86.75 87.25 82.75 83.25 79 79.5 75.5 76 71.5
91 91 86 86 81 81 76 76 71 71 66

Input 1:
5 5 10
0 0 0 0 1
0 0 2 2 0
0 2 0 0 2
0 0 2 2 0
0 0 0 0 0
2 1 1 1
3 4 1 1 1
1 4 0 100 2

0 0 0

Output 1:
99 99 97 97 97 97 97 97 97 97 97

Input 1:
5 5 10
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 1 0 2
1 1 0 1 1
3 5 1 4 0

5 5 10
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 1 0 2
1 1 0 100 1
3 5 1 2 0

0 0 0

Output 2:
-3 -3 -3 -3 -3 -3 -3 -3 -4 -4 -4
98 98 98 98 98 98 98 98 97 97 96

External link:

http://boj.me/onlinejudge/newoj/showProblem/show_problem.php?problem_id=240
http://en.wikipedia.org/wiki/Alpha-beta_pruning
http://blog.renren.com/blog/282892548/773158465

Posted by xiaodao
Category: 日常
Tags: Alpha-beta 剪枝, 博弈搜索, 最优搜索, 极大极小过程