[알고리즘] 동적 계획법(DP) - TIC-TAE-TOE(3목)

TIC-TAE-TOE는 서양식 오목으로 이해하기 쉽게 말하면 3목이다.

가로든 세로든 대각선으로 든 돌 세 개를 먼저 잇는 사람이 승리한다.

3x3 보드에 각 플레이어의 돌을 'o'와 'x'로 두고 어떤 플레이어가 승리하는지 확인하는 코드를 볼 것이다.

 

	board = vector<vector<char>>
	{
		{'o', 'x', 'x'},
		{'.', 'o', '.'},
		{'o', '.', '.'}
	};

	for (int i = 0; i < 19683; i++)
		cache[i] = DEFAULT;

보드는 2차원 벡터 형태로 만들고 cache를 19683개까지 저장하게 했다. 이 오묘한 숫자의 의미는 3^9이다.

보드 한칸에 빈 경우, o의 돌이 놓여있는 경우, x의 돌이 놓여있는 경우 세가지가 있을 수 있고 총 9칸이기 때문에 

3을 9번 곱하면 전체 경우의 수가된다. 그래서 모든 경우의 수를 0~19682까지 hashKey로 저장하도록 만들 것이다.

 

int HashKey(const vector<vector<char>>& board)
{
	int ret = 0;

	for (int y = 0; y < 3; y++)
	{
		for (int x = 0; x < 3; x++)
		{
			ret = ret * 3;

			if (board[y][x] == 'o')
				ret += 1;
			else if (board[y][x] == 'x')
				ret += 2;
		}
	}

	return ret;
}

보드의 현재 상태를 hashKey로 저장하는 함수다. 이해하기 어렵게 보이지만 3진법처럼 저장하는 것이다.

빈칸이면 0, o의 돌이면 1, x의 돌이면 2로 하고 칸을 지나갈 때마다 3씩 곱해준다. 3진법으로 보면 맨 처음 칸의 0또는 1또는 2가 3씩 계속 곱해져서 앞으로 밀려 날 것이고 마지막 칸의 상태가 맨 뒤 쪽에 저장될 것이다.

 

enum
{
	DEFAULT = 2,
	WIN = 1,
	DRAW = 0,
	LOSE = -1
};

int CanWin(vector<vector<char>>& board, char turn)
{
	// 기저 사례
	if (IsFinished(board, 'o' + 'x' - turn))
		return LOSE;

	// 캐시 확인
	int key = HashKey(board);
	int& ret = cache[key];
	if (ret != DEFAULT)
		return ret;

그러면 이제 누구의 승리인지 가리는 CanWin함를 보자. IsFinished는 o나 x의 승리를 체크하며 turn에 'o'가 들어간다면 IsFinshed는 'x'의 승리라면 true , 'x'가 들어간다면 'o'의 승리일 때 true를 반환한다. 보드의 현재 상태를 HashKey로 변환해 key에 저장하고 cache[key]에 이미 값이 저장되어 있다면 그 값을 반환한다.

 

int minValue = DEFAULT;

	for (int y = 0; y < 3; y++)
	{
		for (int x = 0; x < 3; x++)
		{
			if (board[y][x] != '.')
				continue;

			// 착수
			board[y][x] = turn;

			// 확인
			minValue = min(minValue, CanWin(board, 'o' + 'x' - turn)); // 상대방이 패배하는게 제일 좋은 케이스

			// 취소
			board[y][x] = '.';
		}
	}

	if (minValue == DRAW || minValue == DEFAULT)
		return ret = DRAW;

	return ret = -minValue;
}

보드를 탐색하며 빈 공간이 있을 때 turn인 플레이어가 착수를 하고 그 다음 상대방이 지는 경우의 수가 있다면 

minValue에 Lose(-1)값을 저장한다. 최소값을 저장하는 이유는 내가 이기기 위해서는 상대방이 지는 경우의 수가 있어야 하기 때문이다. 그 후에는 플레이어가 착수한 칸을 다시 빈칸으로 돌려놔 보드를 초기화한다. 백트래킹과 유사하다.

그래서 minValue가 -1(상대방의 패배)라면 1로 승리하고 minValue가 1(상대방의 승리)라면 -1로 패배한다.