62. Game Theory

게임 이론(Game Theory)은 상호 의존적이고 이성적인 의사 결정을 다루는 이론이다. 게임(Game)은 각각의 행위자들이 일정한 전략을 가지고 최고의 보상을 얻기 위해 벌이는 행위를 말하며, 알고리즘 문제에 적용할 경우 게임에서 승리하거나 최대한 좋은 결과를 얻기 위해 적절한 전략을 가지고 플레이하는 것을 의미한다고 할 수 있다.

 

게임 이론에서 모든 참가자는 최선의 선택을 하며 다른 참가자들 역시 최선의 선택을 할 것이라는 사실을 알고 있다고 간주한다. 또한 다음과 같은 사항이 존재한다.

• 모든 참가자는 정보를 가지고 있다.
• 게임의 초기 상태가 존재한다.
• 게임의 순서와 정해진 규칙이 존재한다.
• 참가자는 가능한 선택 중 어떤 것이든지 할 수 있다.

대부분의 게임은 다음과 같은 추가적인 제한을 갖는다.

• 게임에는 무작위적인 요소가 없다.

또한 모든 게임은 반드시 끝나는 게임과 끝나지 않을 수 있는 게임으로 구분할 수 있다. 일반적으로 후자가 문제에 등장하는 경우는 많지 않으며 대부분 전자의 상황을 문제로 마주하게 된다. 반드시 끝나는 게임의 경우 더이상 게임을 진행할 수 없는 상태가 존재하며, 이 상태를 '이길 수 있는 상태' 또는 '이길 수 없는 상태' 중 하나로 지정하면 다른 모든 상태들이 각각 두 종류의 상태 중 하나로 결정된다. 어떤 상태에서 '이길 수 없는 상태'로 한번에 이동할 수 있는 경우가 하나로 있다면 그 상태는 '이길 수 있는 상태'이고 그렇지 않다면 그 상태는 '이길 수 없는 상태'이다. 기본적인 문제들은 이 상태를 빠르게 알아내는 것만으로도 문제를 풀 수 있는 경우가 많고, 어떤 문제들은 더 심화된 지식을 요구하기도 한다. 이를 다음 글에서 설명할 예정이다.

 

[연습문제]

 

BOJ 9655. 돌 게임 (Silver V)

한 턴이 지날 때마다 남은 돌 수의 홀짝이 계속 바뀐다. 돌이 없는 상태는 '이길 수 없는 상태'이고 이때 돌 수는 짝수이다. 그러면 돌 수가 홀수인 경우는 '이길 수 있는 상태'가 된다. 따라서 돌 수가 짝수이면 CY, 홀수이면 SK가 답이 된다.

 

CF 1102C. Doors Breaking and Repairing (1200)

$x > y$인 경우 모든 문의 강도를 $0$으로 만들 수 있다. 그렇지 않은 경우, 만약 강도가 $x$보다 큰 문을 선택할 경우 상대 역시 그 문을 선택하면 처음 상태에서 그 문의 강도만 더 늘어나는 것이므로 의미가 없다. 따라서 강도가 $x$ 이하인 문이 있는 경우 항상 그 문을 선택하는 것이 이득이다. 상대 또한 그런 문이 있다면 그 문을 선택할 것이므로 강도가 $x$ 이하인 문의 수의 절반(소수점 올림)이 답이 된다.

 

CF 1370C. Number Game (1400)

$n$이 $1$인 경우 차례를 진행할 수 없으므로 진다. $n$이 $1$보다 큰 홀수인 경우 $n$을 $n$으로 나눌 수 있다. 이렇게 하면 $1$이 되므로 다음 사람이 차례를 진행할 수 없어서 이기게 된다. 따라서 $n$이 홀수인 경우 무조건 이길 수 있다. 또한 $n$이 $2$인 경우도 $1$을 빼면 $1$이 되므로 이길 수 있다.

 

$n$이 $2$보다 큰 짝수일 경우, $1$을 빼면 $1$보다 큰 홀수가 되므로 이래서는 이길 수 없고, 홀수 약수로 나누는 방법으로 차례를 진행해야 한다. 이에 따라 경우를 나누면 다음과 같다.

• $n$이 $2$의 거듭제곱인 경우 $1$보다 큰 홀수 약수가 없으므로 $1$을 뺄 수밖에 없다. 따라서 진다.
• $n$이 홀수 소인수를 $1$개만 갖는 경우 $n$이 소인수 $2$를 $1$개만 가지면 지고, 아니면 이긴다.
• $n$이 홀수 소인수를 $2$개 이상 갖는 경우 항상 이긴다.

 

CF 1451D. Circle Game (1700)

모든 경우는 다음 둘 중 한 가지에 해당한다.

• 점 $(pk, pk)$는 원 내부 또는 경계에 존재하고 점 $(pk, (p+1)k)$는 원 외부에 존재하게 하는 음이 아닌 정수 $p$가 존재한다.
• 점 $(pk, (p+1)k)$는 원 내부 또는 경계에 존재하고 점 $((p+1)k, (p+1)k)$는 원 외부에 존재하게 하는 음이 아닌 정수 $p$가 존재한다.

첫 번째 경우는 Utkarsh가 항상 Ashish와 다른 방향으로 토큰을 옮기면 Utkarsh가 항상 이길 수 있고, 두 번째 경우는 처음에 Ashish가 아무 방향으로 토큰을 옮긴 다음 그 다음부터는 항상 Utkarsh와 다른 방향으로 토큰을 옮기면 Ashish가 항상 이길 수 있다. 따라서 이것을 판별하면 된다.

 

CF 1537D. Deleting Divisors (1700)

처음부터 차례를 진행하지 못해서 지게 되는 경우는 $n$의 약수가 $2$개 이하인 경우이다. 또한 홀수의 약수는 모두 홀수이므로, $n$이 홀수일 경우 다음 차례에는 항상 $n$이 짝수가 된다. 따라서 $n$이 짝수일 경우 홀수 약수를 빼서 홀수로 만들 수 있으면 항상 이길 수 있다. $n$이 $2$의 거듭제곱이 아닌 경우 항상 $1$보다 큰 홀수 약수가 존재하므로 이길 수 있고, $n$이 $2$의 거듭제곱인 경우 $2$의 지수가 홀수면 지고 짝수면 이긴다.

 

CF 1191D. Tokitsukaze, CSL and Stone Game (1800)

처음에 같은 수가 $3$개 이상 입력되거나 같은 수가 $2$개 이상 입력되는 쌍이 $2$개 이상 존재할 경우, 그리고 같은 수가 $2$개 이상 존재하고 그 수보다 $1$ 작은 수가 존재할 경우는 어떻게 해도 첫 턴에 바로 지게 된다. 그렇지 않은 경우 두 플레이어가 최적의 방법으로 차례를 진행할 경우 마지막에 각각의 파일에 남는 돌의 수는 $0, 1, 2, \ldots$이고 그 합은 $\frac{n(n-1)}{2}$이다. 따라서 처음에 입력되는 $n$개의 수의 합에서 $\frac{n(n-1)}{2}$을 뺐을 때 나오는 수의 홀짝으로 누가 이길지를 정할 수 있다.

 

CF 1162E. Thanos Nim (2000)

현재 상태에서 파일에 남아 있는 돌 수의 최솟값을 $k$라고 하면, $k$개의 돌이 남아있는 파일의 수가 $\frac{n}{2}$보다 작을 경우 $k$가 무조건 $1$ 줄어들게 된다. 그렇지 않은 경우 $k$가 줄어들지 않게 할 수 있다. 두 플레이어가 최적의 방법으로 차례를 진행할 경우 두 상황이 번갈아서 나타나게 되므로 처음에 입력되는 수들을 정렬해서 가장 작은 수가 절반보다 많이 나타나는지 확인하면 된다.

 

CF 1191E. Tokitsukaze and Duel (2300)

첫 턴에 Tokitsukaze가 게임을 끝낼 수 있는 경우, 첫 턴에 Tokitsukaze가 게임을 끝낼 수 없고 두 번째 턴에 Quailty가 항상 게임을 끝낼 수 있는 경우, 그렇지 않은 경우 세 가지로 상태가 나누어진다. 마지막 경우는 항상 무승부가 되며, 이대로 출력하면 된다. quailty를 출력할 때 철자에 주의해야 한다(명사 quality가 아님).

 

→ solved.ac tag: game_theory