|
人机对弈的程序：
1）某种在机器中表示棋局的方法，能让程序知道博弈的状态
2）产生合法走法的规则，以使博弈公正地进行，并可判断人类对手是否乱走。
3）从所有合法的走法中选择最佳的走法的技术。
4）一种评估局面优劣的方法，用以同上面的技术配合做出只能的选择。
5）一个界面，有了它，这个程序才能用。
Alpha-Beta搜索
在极大极小搜索的过程中，存在一定程度的数据冗余。在象棋博弈的过程中，如果某一个节点轮到甲走棋，而甲向下搜索节点时发现第一个子节点就可以将死乙，则剩下的节点就无需再搜索了，甲的值就是第一个字节点的值。这个过程，就可以将大量冗余的节点抛弃。
int AlphaBeta(nPly,nAlpha,nBeta）
{
if(game over)
return Eveluation; //胜负已分，返回估值
if(nPly==0)
return Eveluation; //叶子节点返回估值
if(Is Min Node)
{
//是取极小值的节点
for(each possible move m)
{
make move m; //生产新节点
score=alphabeta(nPly-1,nAlpha,nBeta) //递归搜索子节点
unmake move m; //撤销搜索过的节点
if(score<nBeta)
{
nBeta=score; //取极小值
if(nAlpha >= nBeta)
return nAlpha;
}
}
return nBeta; //返回最小值
}
Else
{
//取极大值的节点
for(each possible move m)
{
make move m; //生产新节点
score =alphabeta(nPly-1,nAlpha,nBeta)
unmake move m;
if(score>nAlpha)
{ //取极大值
nAlpha =score;
if(nAlpah >= nBeta)
return nBeta; //beta剪枝，抛弃后继节点
}
}
return nAlpha; //返回极大值
}
}
| 
转播
