hemisphere1357   9달 전

어떤 문제집에서 '게임의 전략 찾기' 문제를 쭉 풀어보았습니다. (https://www.acmicpc.net/workbo...)

이 문제들의 공통점은 A, B 두 사람이 최선을 다해, 또는 최적의 방법으로 게임을 진행한다는 거였습니다.

문제를 처음 풀었을 때는 이게 잘 와닿지 않았고, 사실 지금도 완전히 이해한 건 아닙니다.

제가 이해한 거는 다음과 같습니다.

A, B 두 사람이 게임을 하고 있다고 합시다.

예를 들어, 이 문제의 예제를 생각해보면

2 2 (N = 2, A = 2)

A가 1을 골라서 지운다면, B는 2를 지워서 이기게 되므로 이 선택은 하지 않습니다.

A가 2를 골라서 지운다면, B는 1을 못 지우므로 (2/2=1) 이 선택을 무조건 합니다.

따라서 A는 2를 고를 거고, A가 이깁니다.

4 2 (N = 4, A = 2)

A가 1을 골라서 지운다면

(1) B는 2를 지웁니다. 그렇다면 A는 3, B는 4 (혹은 A는 4, B는 3)을 지우므로 B가 이깁니다. 

(2) B는 3을 지웁니다. 그렇다면 A가 4를 고른다면 B는 2를 지울 수 없으므로 (4/2 = 2) A가 이깁니다. 물론 A가 2를 고른다면 B는 4를 지우므로 B가 이깁니다. 확실히 이기지는 않습니다.

(3) B는 4를 지웁니다. 그렇다면 A는 2를 못 고르므로 3을 무조건 고릅니다. B는 남은 수인 2를 고를 거고 B가 이깁니다.

A가 2를 골라서 지운다면 (이 이후로는 간략하게 설명하겠습니다)

(1) B는 1을 지웁니다. 그렇다면 4 3이 남으므로 B가 이깁니다.

(2) B는 3을 지웁니다. 그렇다면 1 4가 남으므로 B가 이깁니다.

(3) B는 4를 지웁니다. 그렇다면 1 3이 남으므로 B가 이깁니다.

A가 3을 골라서 지운다면

(1) B는 1을 지웁니다. 2 4가 남으므로 A가 4를 지운다면 A가 이깁니다. 이길 가능성이 있습니다.

(2) B는 2를 지웁니다. 1 4가 남으므로 B가 이깁니다.

(3) B는 4를 지웁니다. 1 2가 남으므로 A가 2를 지운다면 A가 이깁니다. 이길 가능성이 있습니다.

A가 4를 골라서 지운다면

(1) B가 1을 고르면 B가 이깁니다.

(2) B가 2를 고르면 B가 이깁니다.

(3) B가 3을 고르면 A가 2를 고를 때만 A가 이깁니다. 이길 가능성이 있습니다.

따라서 A는 2를 제외한 수를 고를 겁니다.

그러나 B도 최선의 전략으로 게임을 할 거기에 A가 이기는 걸 가만두지는 않을 겁니다.

예를 들어, A가 1을 골라서 지웠다면, B는 3을 절대 고르지 않을 거에요. A가 4를 고른다면 지니까요.

결국 이 예제에서는 모든 경우의 수에 대해서 B가 이깁니다.

설명이 매우 길었습니다.

한 마디로 말하면, 최선의 방법으로 플레이한다는 게 결국은 A, B가 이 모든 경우의 수를 탐색하고 이길 가능성이 있는 선택지를 고르는 건가요? 다시 말해서, 게임 이론이라는 건 A 또는 B가 모든 경우에 대해 이길 가능성이 있을 때까지를 찾는 문제라고 생각하면 될까요?

게임 이론을 처음 접해보는 사람이라 설명이 미숙합니다. 양해 부탁드립니다.

lcr7324   9달 전

체르멜로 정리에 의해,

1) 두 명이 번갈아가며 플레이 하며

2) 게임 상태의 수가 유한하고

3) 행동에 따른 게임 상태의 변화가 운에 의해 결정되지 않고 확정적이며 (주사위를 굴리거나 동전을 던지지 않아야 합니다)

4) 게임의 모든 상태가 양쪽 플레이어에게 알려져 있는 게임이라면 (포커처럼 내 손패를 나만 볼 수 있으면 안됩니다)

반드시 둘 중 한 명은 반드시 지지 않는 전략을 가집니다. 이제 게임에 무승부가 존재하지 않고 반드시 승자와 패자가 결정된다면 둘 중 한 명은 반드시 이기는 필승전략을 가진다는 뜻이죠.

그 "필승전략"을 두 명 모두가 사용한다고 생각했을 때 누가 이기는 지를 구하라는 것이 문제입니다.

쉽게 생각해, 속된 말로 상대가 "암만 날고 기어도" 최선의 방법으로 플레이하기만 하면 반드시 이기는 사람이 존재하는데 그 사람을 찾아야 합니다.

hemisphere1357   9달 전

제가 사실 헷갈렸던 부분이

어느 경우에는 A가 확정적으로 이기고, 다른 경우에는 B가 확정적으로 이기면 어떻게 생각해야 하나였거든요.

근데 체르멜로 정리라는 것을 처음 알았습니다.

체르멜로 정리에 의하면 위의 의문이 해결되겠네요.

감사합니다. 여러 가지 게임 이론 문제를 접해보겠습니다.

댓글을 작성하려면 로그인해야 합니다.