[알고리즘 문제풀이] TICTACTOE game

1. 문제

 

틱택토는 3x3 크기의 게임판에서 하는 3목 게임입니다. 두 명이 번갈아가며 o와 x를 게임판의 빈 칸에 쓰되, 먼저 같은 글자를 가로, 세로 혹은 대각선으로 3개 쓰이도록 하는 쪽이 이깁니다. 예를 들어, 다음 게임판은 x가 이긴 게임판입니다.

xoo
.x.
..x

게임은 항상 x부터 시작합니다.

틱택토 게임판의 현재 상태가 주어집니다. 두 사람 모두 최선을 다한다고 가정할 때, 어느쪽이 이길지 판단하는 프로그램을 작성하세요.

 

 

 

 

2. 풀이

 

/*

- canWin(board) : 
게임판이 현재 board일 때, 이번 차례인 사람이 
이길 수 있다면 1,
비길 수 있다면 0,
질 수 밖에 없다면 -1을 반환한다.

+ board를 아홉 자리의 3진수로 본다.

- 함수의 반환 값 중 -1이 있으므로,
cache[]를 -2로 초기화해야한다. 

- canWin()에 현재 게임판 상황과 더불어 누구 차례인지를 turn으로 전달한다. 

- canWin()은 모든 수를 시도하며, 반환 값 중 가장 작은 것을 찾는다. 
: 어떤 수를 두었을 때, -1이 반환된다면 내가 이길 수 있다는 뜻이고
  -1 없이 0이 있다면 0이 있다면 비길 수 있다는 뜻이다. 

*/



bool isFinished(const vector<string>& board, char turn);
// turn이 한 줄을 만들었는지 확인한다.


/*

bijection (전단사 함수)
: 두 집합 사이를 중복 없이 모두 일대일로 대응시키는 함수, 일대일 대응.
: 게임판(board)가 주어졌을 때, [0 ~ 19682 ~=3^9 ] 범위의 정수로 변환한다. 

*/

int bijection(const vector <string>&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;
			}
			else if (board[y][x] == 'x') {
				ret += 2;
			}
		}
	}
	return ret;
}


 
int cache[19683];
int canWin(vector<string>& board, char turn) {
	// board 요소 변환이 있기 때문에, const 선언X

	if (isFinished(board, 'o' + 'x' - turn) == true ) {
		return -1;
		// 기저사례: 마지막에 상대가 두어 한 줄이 만들어진 경우 -> -1 반환
		// 내가 x이면 input parameter이 o, 내가 o이면 input parameter이 x! 
	}

	int& ret = cache[bijection(board)];
	if (ret != -2) {
		return ret;
	}

	int minValue = 2;
	for (int y = 0; y < 3; ++y) {
		for (int x = 0; x < 3; ++x) {
			if (board[y][x] == '.') {
				board[y][x] = turn;
				// 빈 칸에 나의 수를 두었을 때, 결과를 임시로 도출해본다.
				// 반복문을 통하여 9가지 경우의 수 모두 순회하며 판별한다. 
				minValue = min(minValue, canWin(board, 'o' + 'x' - turn));
				board[y][x] = '.';
				// 다시 되돌려 놓는 과정!
			}
		}
	}

	if (minValue == 2 || minValue == 0) {
		return ret = -minValue;
		// 플레이 할 수 없거나, 비기는 것이 최선인 경우 
		// 상대가 이기는 것 -> 내가 지는 것
	}
}

 

 

 

 

 

3. impartial game 

 

In combiantional game theory, an impartial game is a game in which the allowable moves depend

only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric.

the only difference between player 1 and player 2 is that player 1 goes first.

The game is played until a terminal position is reached.

A terminal position is one from which no moves are possible.

Then one of the players is declared the winner and the other the loser.

Furthermore, impartial games are played with perfect information and no chance moves, meaning all information about the game and operations for both players are visible to both players.

 

 

 

 

 

4. git-hub

 

- https://github.com/SohyeonKim-dev/AlgorithmicProblem/blob/main/DynamicProgramming_technique/tictactoe.cpp 

 

 

 

 

 

5. 출처

- https://www.algospot.com/judge/problem/read/TICTACTOE