search.c

牛角棋的源码

//search.c

#include <assert.h>
#include "horn.h"
#include "evaluation.h"
#include "data.h"

/*
************************************************************************
Search
******************************
功能描述：调用Search()递归地展开博弈树。其算法为固定深度的深度优先的Alpha-beta搜索。
参数：	  depth：深度；alpha：窗口下界；beta：窗口上界；wtm：轮到哪方走棋。
返回值：  局面的估值。
*************************************************************************
*/
int Search(int depth, int alpha, int beta, int wtm)
{
	int i;
	int t;
	int score;	
	int move;
	int piece;
	int from;
	int ply = maxDepth - depth;
	int *pMove = pList[ply];
	int value;

	pList[ply+1] = MoveGen(wtm, pList[ply]);

	if(INFINITEVAL == bestRootMove)
		bestRootMove = *pMove;

	value = GameOver(wtm, stoneIntersection, ply);

	//若胜负已分，或者抵达叶节点，则不再搜索，只是返回胜负分值；
	//否则，继续展开博弈树搜索。
	if ((value <= LOSE + maxDepth)||		//胜负已分
		(WIN - maxDepth <= value)		//胜负已分
		)
	{
		return value;
	}

	if((pList[ply] == pList[ply+1]) ||		//无着法可走
		(depth <= 0)				//叶节点
		)
	{
		return Evaluation(wtm, stoneIntersection, ply);
	}

	//逐一展开各子树
	for ( ; pMove < pList[ply+1]; ++pMove ) 
	{
		move = *pMove;
		piece = move>>4;

		from = MakeMove(piece, move & 15);

		if(HasRepetition(posStack, ply))	//出现循环，和棋
		{
			t = DRAW;
			UnmakeMove(piece, from);
		}
		else					//展开某子树，负极大值形式的alpha-beta搜索
		{
			t = -Search(depth-1, -beta, -alpha, !wtm);	
			UnmakeMove(piece, from); 
		}

		if (alpha < t)				//找到更好的着法
		{
			alpha = t;
			if(!ply)			//若是root move
			{
				bestRootMove = move;	//令最佳的root move更新为当前的root move
			}
		}
		if ( alpha >= beta )			//fail-high，剪枝
		{
			return alpha;
		}
	}

	return alpha;
}