7-4. 동적 계획법 예제 문제 - #3. Tic-Tac-Toe(틱택토)

1. Tic-Tac-Toe (틱택토)

3 x 3 사이즈의 보드에서 X 또는 O의 표시로 가로 or 세로 or 대각선으로 한 줄을 이으면 승리하는 게임이다.

 

2. 코드 분석

#include <iostream>
#include <windows.h>
#include <vector>
using namespace std;

// Tic-Tac-Toe
// 특정 상태의 보드판 상태에서 승리 여부를 판단하기

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;
}

vector<vector<char>> board;
int cache[19683];

bool IsFinished(const vector<vector<char>>& board, char turn)
{
	// 좌우
	for (int i = 0; i < 3; i++)
		if (board[i][0] == turn && board[i][1] == turn && board[i][2] == turn)
			return true;
	// 상하
	for (int i = 0; i < 3; i++)
		if (board[0][i] == turn && board[1][i] == turn && board[2][i] == turn)
			return true;
	// 대각
	if (board[0][0] == turn && board[1][1] == turn && board[2][2] == turn)
			return true;

	if (board[0][2] == turn && board[1][1] == turn && board[2][0] == turn)
			return true;

	return false;
 }

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

// 문제가 요구하는 정답을 반환한다
int CanWin(vector<vector<char>>& board, char turn)
{
	// 1. 예외 사항 파악 - 내 차례인데 이미 상대방이 승리했을 경우
	if (IsFinished(board, 'o' + 'x' - turn))
		return LOSE;

	// 2, 캐시 확인 - 모든 칸에 대한 경우의 수 확인하기
	// 각 칸에 o, x, . 이 들어가는 경우의 수는 3^9 = 19683
	int key = HashKey(board);
	int& ret = cache[key];
	if (ret != DEFAULT)
		return ret;

	// 3. 정답 도출
	//  [.][.][.]
	//	[.][O][X]
	//	[.][.][O]
	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; // 승리 여부 => 상대방의 결과의 반대
}


int main()
{
	board = vector<vector<char>>
	{
		{'.', '.', '.'},
		{'.', '.', '.'},
		{'.', '.', '.'}
	};

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

	int win = CanWin(board, 'o');

	switch (win)
	{
	case WIN:
		cout << "Win" << endl;
		break;
	case DRAW:
		cout << "Draw" << endl;
		break;
	case LOSE:
		cout << "Lose" << endl;
		break;
	}

}