/**//// <summary>
/// ＡｌｐｈａＢｅｔａ剪枝法 /// </summary>
/// <returns></returns>
private int AlphaBetaSearch(int curDepth, int alpha, int beta) ...{ lock (this)
...{ if (curDepth >= Depth || times >= MaxTimes) ...{ times++; //开局或中局对棋盘评分,boardState指定是开局还是中局 MonkeyOthello.BoardFX(boardState); SetNums(0); SetNums(1); //返回估值 return SetScore(boardState);
} else ...{ //if (times < MaxTimes) //{ // StaticObject.ThinkingProgressBar.Value = times; //} if (!MonkeyOthello.CanDown()) ...{ //如果没棋可下,交换对手 MonkeyOthello.CurrentColor = 1 - MonkeyOthello.CurrentColor; if (!MonkeyOthello.CanDown()) ...{ //双方都没棋可下,则不用再往下搜索 MonkeyOthello.CurrentColor = 1 - MonkeyOthello.CurrentColor; //中局就已经结束游戏,获取中局的结果 GameResult result = MonkeyOthello.GetMidGameResult((int)MonkeyOthello.CurrentColor); //中局就已经结束游戏,返回游戏结束的估值 return EvalGameOver(result, beta); } else ...{ //其中一方无棋可下,继续由对方下 return -AlphaBetaSearch(curDepth + 1, -beta, -alpha); //alpha = -beta; beta = -alpha; curDepth++; } } //进栈(当前的所有棋步) AllStepStack.Push(new Stack<Step>(MonkeyOthello.Mobility)); //当前估值 int score; //棋步数量 int Num = MonkeyOthello.MobilityNum[(int)MonkeyOthello.CurrentColor]; for (int i = 0; i < Num; i++) ...{ //获取没有访问过的棋步 Step step = GetNotVisitedStep(); //模拟下一步棋 MonkeyOthello.DownStones(step); // 搜索下一步(递归) score= -AlphaBetaSearch(curDepth + 1, -beta, -alpha); //退一步 MonkeyOthello.Reback(); //搜索到比上次高的估值,替换 if (score > alpha) ...{ alpha = score; //如果认为已经赢定,则可以终止搜索 if (score >= beta) break; } } //退栈(当前的所有棋步) AllStepStack.Pop(); return alpha; } } }
我把它用在开局和中局的思考,当然开局跟中局的评估函数有区别
而当离游戏还有10-12步时,用它来搜索最大赢子数.
|