Reversi 게임 제작하기 - 3

이제 컴퓨터가 돌을 놓기 위해서 게임트리를 작성하고 그에 따라서 돌을 놓는 로직이다. 이 부분의 로직은 매우 복잡하고, 알파-베타 가지치기를 효율적으로 사용하기 위해서 자기호출 함수를 사용치 않았다.

 

#define	MINVAL (-1000)
#define	MAXVAL (1000)
#define	MAXDEPTH	(20)
unsigned GetOptimal(Gameboard &board, unsigned turn, unsigned maxdepth, unsigned method)
{
	unsigned nodenum = 0;
	<파트 1 : 오직 한가지 경우만 존재할 때 처리>
	Gameboard boards[MAXDEPTH];
	unsigned slot[MAXDEPTH];
	unsigned optindex[MAXDEPTH];
	int score[MAXDEPTH];
	unsigned depth = 0;
	int nodescore;

	boards[0] = board;
	slot[0] = 0;
	score[0] = (turn == 1)? MINVAL : MAXVAL;	
	for( ; ; )
	{
		<파트 2 : 힌트값에 의해서 다음에 놓을 위치 찾기>
		<파트 3 : 노드 점수값 결정>
		<파트 4 : 미니맥스 알고리즘>
		<파트 5 : 알파-베타 가지치기>
		slot[depth]++;
	}
	return optindex[0];
}

 

<파트 1>에서는 힌트의 갯수가 0인 경우에는 64를 반환해줌으로써 해당 플레이어 턴을 지나가도록 한다. 힌트의 갯수가 1인 경우에는 보드에서 0인 값을 찾아서 반환한다.

 

	if(!board.hint) return 64;
	if(board.hint == 1)
	{
		for( unsigned ui = 0 ; ui < 64 ; ++ui)
			if(board.board[ui] == 0)
				return ui;
	}

<파트 2>에서는 놓을 수 있는 곳을 찾도록 한다.

 

	while(slot[depth] < 64)
	{
		if(boards[depth].board[slot[depth]] == 0) break
		slot[depth]++;
	}

<파트 3>에서는 <파트 2>에서 찾은 곳에 돌을 넣고 마지막 노드인 경우 점수를 계산한다.

 

if(slot[depth] < 64 || (boards[depth].hint == 0 && slot[depth] == 64))
{
	boards[depth+1] = boards[depth];
	PutBoard(boards[depth+1], slot[depth], turn);
	depth++; turn ^= 3;
	score[depth] = (turn == 1)? MINVAL : MAXVAL;
	slot[depth] = 0;
	nodenum++;
	if(depth != maxdepth) continue;
	if(method == USE_SCOREBOARD)
	{
		nodescore = 0;
		for(unsigned r = 0 ; r < 64 ; r++)
		{
			if(boards[depth].board[r] == 1)
				nodescore += ScoreBoard[r];
			else if(boards[depth].board[r] == 2)
				nodescore -= ScoreBoard[r];
		}
	}
	else nodescore = boards[depth].score[1]-boards[depth].score[2];
}
else if(depth == 0) break;
else nodescore = score[depth];

<파트 4>에서는 계산된 점수값을 가지고 상위 노드들의 점수를 기록한다. 여기서 미니맥스 알고리즘을 적용한다.

 

	//	upward pass
	bool bFlag = false;
	if(turn == 2)	//	max check
	{
		if(score[depth-1] >= nodescore) bFlag = true;
	}
	else	//	min check
	{
		if(score[depth-1] <= nodescore) bFlag = true;
	}
	//	up a step
	depth--;
	turn ^= 3;

<파트 5>에서는 알파-베타 가지치기를 한다. 알파-베타 가지치기에서는 상위노드에서 얻어진 최적값을 가지고 계산한다. 가지치기에 성공한 경우는 다른 노드들을 계산할 필요가 없기 때문에 두단계를 위로 점프하게 된다.

 

	if(!bFlag)
	{
		score[depth] = nodescore;
		optindex[depth] = slot[depth];
		if(depth > 0)
		{
			if(turn == 2)	//	max check
			{
				if(score[depth-1] >= nodescore)	bFlag = true;
			}
			else	//	min check
			{
				if(score[depth-1] <= nodescore)	bFlag = true;
			}
			if(bFlag)
			{
				depth--;
				turn ^= 3;
			}
		}
	}

<파트 4>에서 오델로의 점수값을 계산하기 위해서는 오델로의 돌 위치에 따라 가중치를 두었다. 어느 정도 수가 진행되면 실제 돌의 갯수로 점수 계산을 하도록 하였다. 가중치 계산도 어느 정도는 경험에 의해서 작성해야한다. 여기서는 대부분의 오델로 게임자가 느끼는 심리적 가중치를 적용하였다. 오델로 점수값에서 실제 돌의 갯수로 점수 계산을 바꾸는 시점도 경험에 의해서 적용하였다.

 

static int ScoreBoard[64] =
{
	10,  1,  3,  2,  2,  3,  1, 10,
	 1, -5, -1, -1, -1, -1, -5,  1,
	 3, -1,  0,  0,  0,  0, -1,  3,
	 2, -1,  0,  0,  0,  0, -1,  2,
	 2, -1,  0,  0,  0,  0, -1,  2,
	 3, -1,  0,  0,  0,  0, -1,  3,
	 1, -5, -1, -1, -1, -1, -5,  1,
	10,  1,  3,  2,  2,  3,  1, 10
};