极大极小搜索：
A和Ｂ对弈，轮到Ａ走棋了，那么我们会遍历A的每一个可能走棋方法，然后对于前面A的每一个走棋方法，遍历B的每一个走棋方法，然后接着遍历A的每一个走棋方法，如此下去，直到得到确定的结果或者达到了搜索深度的限制。当达到了搜索深度限制，此时无法判断结局如何，一般都是根据当前局面的形式，给出一个得分，计算得分的方法被称为评价函数，不同游戏的评价函数差别很大，需要很好的设计。
在搜索树中，表示A走棋的节点即为极大节点，表示B走棋的节点为极小节点。称A为极大节点，是因为A会选择局面评分最大的一个走棋方法，称B为极小节点，是因为B会选择局面评分最小的一个走棋方法，这里的局面评分都是相对于A来说的。这样做就是假设A和B都会选择在有限的搜索深度内，得到的最好的走棋方法。
α-β剪枝：
设α为当前状态A可获取的最大值，β为B可获取的最小值，当搜索到某一层的某个子节点时α<=β，因此对于后面节点α只会更大β只会更小，因此仍满足α<=β，因此这个节点下A无获胜可能，则进行剪纸不继续搜索其子节点。
伪代码：
function alphabeta(node, depth, α, β, Player)
if depth = 0 or node is a terminal node
return the heuristic value of node
if Player = MaxPlayer // 极大节点
for each child of node // 极小节点
α := max(α, alphabeta(child, depth-1, α, β, not(Player) ))
if β ≤ α // 该极大节点的值>=α>=β，该极大节点后面的搜索到的值肯定会大于β，因此不会被其上层的极小节点所选用了。对于根节点，β为正无穷
break (* Beta cut-off *)
return α
else // 极小节点
for each child of node // 极大节点
β := min(β, alphabeta(child, depth-1, α, β, not(Player) )) // 极小节点
if β ≤ α // 该极大节点的值<=β<=α，该极小节点后面的搜索到的值肯定会小于α，因此不会被其上层的极大节点所选用了。对于根节点，α为负无穷
break (* Alpha cut-off *)
return β
(* Initial call *)
alphabeta(origin, depth, -infinity, +infinity, MaxPlayer)
注意：
alpha-beta剪枝使得每一个子状态在它的父亲兄弟们的约束下，得出一个相应得值，所以与其父兄节点有关系，而记忆化搜索则默认子节点只与自己的状态有关系，忽略了父兄的约束条件，实际上一颗博弈树上可能有多颗节点同时指向一个节点，若把alpha-beta与记忆化结合起来，那么该节点将只被一组父兄节点限制一次，也就只考虑了这组父兄所带来的alpha-beta界剪枝下的结果，很有可能把本属于另外组别父兄节点的最优解给误剪掉了。
例题：poj 1568 Find the Winning Move
题意：tic-tac-toe棋，讯问下一步是否存在必胜态。
import java.util.Scanner;
public class FindWin1568 {
int map[][] = new int[5][5];
boolean check(int x, int y) {
int cnt = 0;
for (int i = 1; i <= 4; i++)
cnt += map[x][i];
if (cnt == 4 || cnt == -4)
return true;
cnt = 0;
for (int i = 1; i <= 4; i++)
cnt += map[i][y];
if (cnt == 4 || cnt == -4)
return true;
if (x == y) {
cnt = 0;
for (int i = 1; i <= 4; i++)
cnt += map[i][i];
if (cnt == 4 || cnt == -4)
return true;
}
if (x + y == 5) {
cnt = 0;
for (int i = 1; i <= 4; i++)
cnt += map[i][5 - i];
if (cnt == 4 || cnt == -4)
return true;
}
return false;
}
int inf = 1 << 28, tie = 16;
int max_min(int d, int player, int x, int y, int alpha, int beta) {
if (check(x, y))
return -inf * player;
if (d == tie)
return 0;
outer: for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
if (map[i][j] == 0) {
map[i][j] = player;
int temp = max_min(d + 1, -player, i, j, alpha, beta);
map[i][j] = 0;
if (player == 1)
alpha = Math.max(temp, alpha);
else
beta = Math.min(temp, beta);
if (beta <= alpha)
break outer;
}
if(player==1)
return alpha;
else
return beta;
}
boolean work() {
int cnt = 0;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
if (map[i][j] != 0)
cnt++;
if (cnt <= 4)
return false;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
if (map[i][j] == 0) {
map[i][j] = 1;
int ans = max_min(cnt + 1, -1, i, j, -inf, inf);
map[i][j] = 0;
if (ans == inf) {
i--;
j--;
System.out.println("(" + i + "," + j + ")");
return true;
}
}
return false;
}
Scanner scan = new Scanner(System.in);
void run() {
while (true) {
String s = scan.next();
if (s.charAt(0) == '$')
break;
for (int i = 1; i <= 4; i++) {
s = scan.next();
for (int j = 1; j <= 4; j++)
if (s.charAt(j - 1) == '.')
map[i][j] = 0;
else if (s.charAt(j - 1) == 'x')
map[i][j] = 1;
else
map[i][j] = -1;
}
if (!work())
System.out.println("#####");
}
}
public static void main(String[] args) {
new FindWin1568().run();
}
}