완전 정보 게임
- 게임의 정보가 참가자 모두에게 공개된 게임
- 누가 먼저 하는가에 따라서 이미 승부가 결정되어 있다.
- 예시) 바둑, 오목, 체스
불완전 정보 게임
- 확률적으로 정보가 주어진다.
- 모든 정보가 공개되어 있지는 않다.
바둑돌 가져가기
- 바둑돌이 K개 있다.
- 두 사람이 번갈아가며 자신의 차례에 1개, 2개 돌을 가져갈 수 있다.
- 자신의 차례에 동작을 할 수 없으면 그 사람이 진다.
D[i] = 돌의 개수가 i개 일 때, 이기는 방법이 있는 경우 O, 아니면 X
i=0 일 때 가져갈 수 있는 돌이 없음
i=1 일 때 1개 가져갈 수 있음
i=2 일 때 2개 가져갈 수 있음
i=3 일 때부터 중요한데
- 1칸 앞, 2칸 앞의 값을 확인한다
- 둘 중 하나라도 X가 있으면 내가 이긴다.
만약 1칸 앞을 봤는데 X라면 내가 돌을 1개 가져갔을 때 상대가 진다는 것이다. - 3은 왜 X이냐면, 내가 1개를 가져가든, 2개를 가져가든 상대가 남은 바둑돌을 다 가져갈 수 있어서 내 차례에 동작을 할 수 없기 때문이다.
i=4 로 예를 들어보면,
한 칸 앞인 i=3일 때는 X이다.
내가 1개를 가져가면 3개가 남을텐데 이 때 상대가 바둑돌 1개를 가져가든, 2개를 가져가든 남는 바둑돌이 있어서 내 차례에 동작을 할 수 있다.
그래서 i=4일 때 내가 1개를 가져가면 내가 이길 수 있다.
반면, 두 칸 앞인 i=2일 때는 O이다.
내가 2개를 가져가면 2개가 남고 상대가 충분히 똑똑하면 당연히 남은 2개를 다 가져갈 것이기 때문에 내가 다음에 할 동작이 없다. 그래서 i=4일 때 내가 2개를 가져가면 이길 수 없다.
또 다른 예시
- 다음은 위와 똑같은데 자신의 차례에 1개, 3개, 4개의 바둑돌을 가져갈 수 있다.
위에서 i=5인 경우를 보면 다음과 같이
X가 하나 있기 때문에 내가 3개를 가져가면 이길 수 있는 게임이 된다.
D[i-1] = D[4] = O
D[i-3] = D[2] = X
D[i-4] = D[1] = O
Game Programmer