在下图中，第一层节点表示开始局面，我方先走，第二层节点表示我方可走的三个位置，第三层节点表示对于我方的每一种走法对手的各种走法，下方数字代表了对每个局面的评价值。这里的评价值都是相对于我方来说的。
根据常规，我方在第二层选择时会选择评价值最大的节点去走，在第三层选择时，要考虑对手走相对我方最不利的棋，因此选择评价值最低的节点，这样评价值从最底层更新到最高层，被称为极小极大搜索过程。
举例说明，节点值为-2, 2节点值为1，选择最小值，因此3节点被更新为-2，传递到上层，目前4节点>=-2，接着走中间这条路，根据5节点传递到6节点，目前6节点<=-3，现在因为4节点>=-2，6节点<=-3，出现剪枝，6节点的其余节点便可以不用访问，这就被称为alpha-beta剪枝技术。
以上说明了父子节点间可以进行alpha-beta剪枝，那隔代之间可不可以呢，如下图已知1节点<=0，2节点>=4，选择为空集，是不是应该出现剪枝呢？
下面我们来证明这个问题。 假设2节点值经过中间节点传递到了3节点（若3节点值不是由2节点传递的，则2节点的剪枝与否与3节点不起关系），2节点处发生剪枝，当且仅当其他子节点值大于4才会对2节点值产生影响，假设为5，不管2节点值为4还是5传递到3节点，都对1节点产生不了影响，因为1节点要求<=0，因此2节点处可以发生剪枝。
由上面论证看出，隔代剪枝可行，这样也大大提升了剪枝的效果，但同时带来了编程的复杂度，于是我们想到，为每个节点设立 α 值和 β 值，初始 α=−∞ ， β=+∞ ，表示一个节点的值范围，通过这两个值的向下传递和向上更新来完成隔代剪枝，具体的例子可以看链接，里面例子写的很详细。
下面是伪代码：
int alpha_beta(int h, int player, int alpha, int beta) //h搜索深度，player=1表示自己,player=0表示对手 { if(h==6 || (result != 0)) //若到达深度 或是出现胜负 { if(result != 0){ //若是胜负返回-inf 或+inf return result; } else{ return evaluate(player) - evaluate(player^1); //否则返回此局面的评价值 } } int i, j; if(player){//自己 for(i=1; i<=n; i++) for(j=1; j<=n; j++) { if(ch[i][j] == '.') { ch[i][j] = 'o'; int ans = alpha_beta(h+1, player^1, alpha, beta); ch[i][j] = '.'; if(ans > alpha){ //通过向上传递的子节点beta值修正alpha值 alpha = ans; ansx = i; //记录位置 ansy = j; } if(alpha >= beta) //发生 alpha剪枝 { return alpha; } } } return alpha; } else{//对手 for(i=1; i<=n; i++) for(j=1; j<=n; j++) { if(ch[i][j] == '.') { ch[i][j] = 'x'; int ans = alpha_beta(h+1, player^1, alpha, beta); ch[i][j] = '.'; if(ans < beta){ //通过向上传递的子节点alpha值修正beta值 beta = ans; } if(alpha >= beta) //发生 beta剪枝 { return beta; } } } return beta; } }在递归过程中， α 和 β 值随着递归调用向下传递，同时回溯时根据这一层来更新上一层 α 和 β ，所以隔代间也能发生剪枝。
f(p)规定如下 f(p) = （所有空格放上我方棋子后，n子连线的总个数）-（所有空格放上对方棋子后，n子连线的总个数）。
具体程序代码如下：
int evaluate(int player) { char x; if(player){ x = 'o'; } else{ x = 'x'; } int i, j; int ans = 0; for(i=1; i<=n; i++) //横行所有情况 { int w = 0; for(j=1; j<=n; j++) { if(ch[i][j] == x || ch[i][j] == '.') { w++; } } if(w==m){ ans++; } } for(i=1; i<=n; i++) //竖行所有情况 { int w = 0; for(j=1; j<=n; j++) { if(ch[j][i] == x || ch[j][i] == '.') { w++; } } if(w==m){ ans++; } } int w = 0; for(i=1; i<=n; i++) //正对角线 { if(ch[i][i] == x || ch[i][i] == '.') { w++; } } if(w==m){ ans++; } w = 0; for(i=1; i<=n; i++) //反对角线 { if(ch[i][n-i+1] == x || ch[i][n-i+1] == '.') { w++; } } if(w==m){ ans++; } return ans; }判断此局面是赢还是输的思路完全枚举即可 代码如下
int check(char x, char y) //自己标志是x 别人标志是y { int i, j; for(i=1; i<=n; i++) { int w = 0, l = 0; for(j=1; j<=n; j++) { if(ch[i][j] == x) { w++; } if(ch[i][j] == y) { l++; } } if(w==m){ return INF; } if(l==m){ return FINF; } } for(i=1; i<=n; i++) { int w = 0, l = 0; for(j=1; j<=n; j++) { if(ch[j][i] == x) { w++; } if(ch[j][i] == y) { l++; } } if(w==m){ return INF; } if(l==m){ return FINF; } } int w = 0, l = 0; for(i=1; i<=n; i++) { if(ch[i][i] == x) { w++; } if(ch[i][i] == y) { l++; } } if(w==m){ return INF; } if(l==m){ return FINF; } w = 0; l = 0; for(i=1; i<=n; i++) { if(ch[i][4-i+1] == x) { w++; } if(ch[i][4-i+1] == y) { l++; } } if(w==m){ return INF; } if(l==m){ return FINF; } return 0; }这样，配上其他界面代码，一个简单的一字棋程序就完成了。
欢迎评论。
