조합게임

난 항상 이런 문제가 싫었다.

- 현재 상태에서 두 선수가 최선을 다했을때 승자는 누가 될 것인가.

여기서 두 선수가 최선을 다한다는 문제의 조건이 항상 마음에 들지 않았다. 도대체 두 선수가 최선을 다한다는 것을 어떻게 정의한다는 것인가? 어떤 경우가 최선을 다하는 것이고 어떤 경우는 최선을 다하지 않는 것인가?

하지만 알고리즘 문제해결전략 책을 탐독한 결과 이런 경우는 현재 상태로부터 가능한 모든 상태를 수를 고려했을때(컴퓨터의 빠른 연산 능력을 이용해) 내가 이길 수 있는지 없는지를 판독해내는 과정이다.

책에서 나온 예제로는 Tic Tac Toc가 있었다.

여기서 책에서 큰 깨달음을 얻은 부분이

"현재의 참가자는 모든 수를 둬 보면서 다음 상태 board에 대해서 이길 수 있는 수가 있으면 무조건 그 수를 선택하고 없으면 비기는쪽 아니면 지는 쪽을 선택해야" 한다는 것이다.

 
int canWin(char turn) {
	int i, j, ret;
	int state = retState();

	if (isFinished('o' + 'x' - turn)) return -1;
	if (memo[state] != -2) return memo[state];

	ret = 2;
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) {
			if (board[i][j] == '.') {
				board[i][j] = turn;
				ret = MIN(ret, canWin('o' + 'x' - turn));
				board[i][j] = '.';
			}
		}
	}

	if (ret == 2 || ret == 0) 
		return memo[state] = 0;

	return memo[state] = -ret;
}

즉 다음에 두는 수가 발생시키는 경우들에 대한 return값들 중에서 최대한 이기거나 지는 쪽으로 선택해야한다는 것이다.

이렇게 가정을 세우고 나면 각 참가자가 최선을 다해 경기를 한다는 조건이 만족할 수 있다.

중복되는 상태들은 메모마이제이션을 통해서 간단히 해결 할 수 있다.

이러한 개념은 중요한것 같다. 잘 참고해야겠다.