27. 완전 정보 게임 [11 2주차]

27. 완전 정보 게임 [11-2주차]

2024년 1월 14일 일요일

오전 3:10

<완전 정보 게임>

완전 정보 게임

• 게임의 정보가 참가자 모두에게 공개된 게임
• 숨어있는 정보는 없다.
• 양쪽 다 최선의 선택을 할 경우, 누가 먼저 하는지에 따라 승부는 이미 결정되게 된다.
• 최선의 선택이 무엇인지 정확히 정의하는 게 가능하다.
• ex) 바둑, 오목, 체스

불완전 정보 게임

• 확률적으로 정보가 주어진다.
• 모든 정보가 공개되어 있지는 않다.
• 최선의 선택을 정확하게 정의할 수 없다.
• 예) 화투 놀이, 포커, 스포츠배팅

<NIM>

한 턴을 플레이할 때마다 문제의 크기가 줄어든다는 것이 보장된 게임.

문제의 크기가 줄어든다 : 체스에서 말 하나가 죽으면 말의 개수가 줄어드므로 문제 사이즈가 줄어든다.

<NIM의 예 : 바둑돌 가져가기>

바둑돌이 K개 있다. 두 사람이 번갈아가며 자신의 차례에 1개 또는 2개의 돌을 가져갈 수 있다. 자신의 차례에 동작을 할 수 없으면 그 사람이 진다. 두 사람이 최선의 선택을 한다고 가정했을 때, 누가 이기는 지 맞추는 방법은?

바둑돌의 개수를 3의 배수로 맞추고 턴을 넘기는 사람이 무조건 이길 수 있다.

(반대로, 바둑돌의 개수가 3의 배수인 상태에서 턴을 넘겨받으면 상대방이 최선의 선택을 할 때 절대로 이길 수 없다)

즉, 턴을 넘겨받을 때 바둑돌의 개수가 3의 배수만 아니면 무조건 이길 수 있다.

상대방이 3n개를 넘겨받았다면, 다음 턴에 나는 3n-1또는 3n-2개를 넘겨받게 된다.

내가 2개, 1개를 가져가면, 상대방은 3n-3개를 넘겨받는다.

따라서 상대방이 3의 배수를 넘겨받으면, 무조건 다음 턴에도 상대방이 3의 배수를 넘겨받도록 할 수 있다.

상대방이 3개를 넘겨받았다면, 상대방이 몇 개를 가져가든 내 턴에 나머지 바둑돌을 모두 가져갈 수 있으므로 결국 이기게 된다.

<바둑돌 가져가기2>

바둑돌이 K개 있다. 두 사람이 번갈아가며 자신의 차례에 1개, 3개, 4개의 돌을 가져갈 수 있다. 자신의 차례에 동작을 할 수 없으면 그 사람이 진다. 두 사람이 최선의 선택을 한다고 가정했을 때, 누가 이기는지를 구하시오.

D(i)를 다음과 같이 정의한다.

• 바둑돌을 i개 넘겨받은 사람이 무조건 이긴다면, D(i) = 1
• 무조건 진다면, D(i) = 0

(완전 정보 게임이므로 무조건 이기거나 무조건 지는 경우만 존재)

D(i)에 대해 다음 점화식을 세울 수 있다.

D(0) = 0, D(1) = 1, D(2) = 0, D(3) = 1, D(4) = 1 임은 쉽게 알 수 있다.

위 점화식과 초깃값을 이용하여 D배열을 0부터 채우면, 몇 개의 돌을 넘겨받은 사람이 이기는지를 알 수 있다.