a.cpp

void T3AI::GetBestMove()
{
	Position iList[TOTAL];			/* 현재 게임판에서 놓을 수 있는 좌표 개수, 위치 저장 */
	int	bestValue = -10000;			/* besteval 값 선언 */
	int	possible = 0;				/* 가능한 개수 저장 변수 */
		
	possible = GetPossibleMove(iList);	/*현재 가능한 수 좌표, 개수 저장 */

	for( int i = 0; i < possible; i++ )				/* 가능한 수 만큼 Minimax 알고리즘을 사용하여 수를 계산 */
	{
		root->next[i] = new Node;					/* 새로운 노드 생성 */
		InitNode(root->next[i], (root->depth)+1);	/* 노드 초기화 */
		tttBoard.DoMove(iList[i].x , iList[i].y);	/* 가능한 수를 둠 */
		int newValue = Minimize(root->next[i]);		/* Min함수호출로 값을 구해서 */
		root->next[i]->eval = newValue;				/* 노드에 저장 */
		tttBoard.UndoMove();						/* 두었던 수를 무름 */

		if( newValue > bestValue )		/* 구한 eval값이 best값보다 크다면 */
		{
			bestValue = newValue;		/* 값을 변경하고 해당 수정보를 저장 */
			bestX = iList[i].x;
			bestY = iList[i].y;
			root->eval = bestValue;		/* 노드에 값을 저장 */
		}
	}
	root->childCnt = possible;			/* 자식 노드 수를 저장 */
};

int T3AI::GetPossibleMove(Position* iList)
{
	int	iNum = 0;	/* 가능한 수 개수 저장할 변수 */
	int	check = 0;	/* 대칭성 검사 변수 */
	int k=0;

	GameBoard tempBoard = tttBoard;	/* 게임판 복사 */
		
	for(int i=0; i<ROW; i++ )
	{
		for(int j=0; j<ROW; j++)
		{
			if( tttBoard.board[i][j] == ' ' )
			{
				check = 0;
				for(int k=0; k<iNum; k++)
				{
					tttBoard.DoMove(i, j);
					tempBoard.DoMove(iList[k].x, iList[k].y);
					check =	CheckSymmetric(tempBoard, tttBoard);	/* 대칭성 검사 */
					tempBoard.UndoMove();
					tttBoard.UndoMove();
					if(check == 1)		/* 대칭된다면 스킵 */
						break;
				}
				
				if(!check)				/* 아니라면, */
				{
					iList[iNum].x = i;		/* 현재 x좌표, y좌표 저장 */
					iList[iNum].y = j;
					iNum++;					/* 개수 증가 */				
				}
			}
		}
	}			
	return iNum;	/* 개수 반환 */
};


int T3AI::Minimize(struct treeNode* root)
{
	Position iList[TOTAL];		/* 현재 게임판에서 놓을 수 있는 좌표 개수, 위치 저장 */
	int	possible = 0;			/* 둘수있는 개수 저장 변수 */
	int	bestValue = 10000;		/* besteval 값 선언 */

	possible = GetPossibleMove(iList); /*현재 가능한 수 좌표, 개수 저장 */
		
	if( possible == 0 || CheckEnd() || root->depth == LAlevel ) /* 가능한수 없거나, 게임종료면 eval 값을 계산하여 리턴 */
	{
		return EvaluateBoard(root);
	}		

	for( int i = 0; i < possible; i++ ) /* 가능한 수 만큼 Minimax 알고리즘을 사용하여 수를 계산 */
	{
		root->next[i] = new Node;					/* 노드 생성 후 초기화 */
		InitNode(root->next[i], root->depth+1);

		tttBoard.DoMove(iList[i].x , iList[i].y);	/* 가능한 수를 둠 */
		int newValue = Maximize(root->next[i]);		/* Max함수호출로 값을 구해서 */
		root->next[i]->eval = newValue;				/* 노드에 저장 */
		tttBoard.UndoMove();						/* 두었던 수를 무름 */

		if( newValue < bestValue )	/* 구한 eval값이 best값보다 작다면 */
		{				
			bestValue = newValue;	/* 값을 변경하고 해당값으로 노드값에 저장 */
			root->eval = bestValue;
		}
	}
	root->childCnt = possible;		/* 자식 노드개수 저장 */
	return bestValue;				/* bestValue 값 반환 */
};


int T3AI::Maximize(struct treeNode* root)
{
	Position iList[TOTAL];		/* 현재 게임판에서 놓을 수 있는 좌표 개수, 위치 저장 */
	int	bestValue = -10000;		/* besteval 값 선언 */
	int	possible;				/* 둘수있는 개수 저장 변수 */
		
	possible = GetPossibleMove(iList);	/*현재 가능한 수 좌표, 개수 저장 */
		
	if( possible == 0 || CheckEnd() || root->depth == LAlevel )	/* 가능한수 없거나, 게임종료면 eval 값을 계산하여 리턴 */
	{
		return EvaluateBoard(root);
	}		

	for( int i = 0; i < possible; i++ )	/* 가능한 수 만큼 Minimax 알고리즘을 사용하여 수를 계산 */
	{
		root->next[i] = new Node;					/* 노드 생성 후 초기화 */
		InitNode(root->next[i], root->depth+1);

		tttBoard.DoMove(iList[i].x , iList[i].y);	/* 가능한 수를 둠 */		
		int newValue = Minimize(root->next[i]);		/* Min함수호출로 값을 구해서 */
		root->next[i]->eval = newValue;				/* 노드에 저장 */
		tttBoard.UndoMove();						/* 두었던 수를 무름 */

		if( newValue > bestValue )				/* 구한 eval값이 best값보다 크다면 */
		{				
			bestValue = newValue;				/* 값을 변경하고 해당값으로 노드값에 저장 */
			root->eval = bestValue;	
		}		
	}
	root->childCnt = possible;					/* 자식 노드개수 저장 */
	return bestValue;							/* bestValue 값 반환 */
};