[이산수학] 님(nim) 게임

<< 이산수학 9주차 >>

(게임 규칙)
- 여러 그룹이 존재
- '나'부터 시작
- 1개 혹은 전부를 제거 가능
- 최소 하나 이상의 돌이 제거
- 마지막 돌 제거하는 사람이 진다.

(게임은? Botton-up 방식으로 진행)          // 단말노드에서 루트 노드로
1단계 : 단말 노드에 값 배정
2단계 : Min-Max 적용을 위해 위 노드의 값을 반복하여 정한다.
3단계 : 루트 노드가 +1이면 승리, -1이면 패배
4단계 : 1에 기여한 경로가 승리 전략이다.

(예제 1)

님(nim) 게임 예제

위 그림은 앞서 이야기했던 게임 규칙을 적용해 (221)개의 돌이 있을 때, 트리를 그린 것이다. 이것을 보면서 (221)개의 돌이 있을 때 게임의 승리 전략을 알아보자. 트리에서 네모(나), 동그라미(상대방)를 의미한다. 마지막 노드가 내 차례라면, 돌이 1개 남아있고 그 마지막 돌을 제거하는 사람이 '나'이므로 내가 게임에서 지는 case를 의미한다. 그에 반해 마지막 노드가 상대방의 차례라면, 마지막 돌을 제거하는 사람이 '상대방'이므로 내가 이기는 case에 속한다. 

이렇게 내가 지는 case에 -1, 상대방이 지는 case에 +1을 넣어주면서 루트 노드부터 확인했다. 이제 루트 노드로 올라가야 할 텐데 -1, +1 중에서 어떠한 case를 따라야 할까? 쉽게 생각하면 각각의 대상이 이길 수 있는 case로 가는 것을 생각하면 된다. 내 차례가 돌아왔다. 자식 노드에 -1 -1 +1의 케이스가 있다면 나는 어떠한 케이스를 선택할까? 당연히 +1일 것이다. 그리고 상대방의 차례일 때는 아래 자식 노드에 +1 +1 -1의 케이스가 존재한다면, 당연히 -1(상대방이 이기는) case를 선택할 것이다.
 >> 따라서 이것이 상대방 차례일 때는 min값(-1), 내 차례일 때는 max값(+1)을 초이스 하는 방식을 따른다고 말할 수 있다. 

(예제 2)

전의 예제는 마지막 남은 돌의 수량을 1까지 나타냈다면, 남은 돌의 수량을 0으로 나타내 보자. 그러면 마지막 노드가 내 차례라면 이기는 case, 상대방 차례라면 지는 case에 속한다. 여기서는 이기는 case를 1, 지는 case를 0으로 나타냈다.

 

Tic-Tac-Toe 게임

tic-tac-toc 게임

빙고 게임의 승리 전략을 이해해보자. 먼저 위쪽의 빙고 트리에서 각각의 빙고의 현재 값을 알아야 한다. 현재 값은 무얼 의미하는 것인가? (X가 이길 수 있는 케이스) - (O가 이길 수 있는 케이스)를 의미한다. '나(=X)'를 기준 계산이 이뤄지기 때문에 현재 값이 양수면 승리, 음수면 패배, 0이면 무승부의 결과가 난다. 따라서 각각의 빙고 트리를 아래쪽의 숫자 트리로 표현할 수 있다. 결국 양수의 초이스를 하게 되면 내가 이기는 승리 전략을 이해할 수 있다. 

현재 값을 구하는 법을 위의 그림에서 이해할 수 있을 것이다.

 

정점 평가
: '내'가 자식 노드에서 초이스 하는 수는 큰 값, '상대방'이 자식 노드에서 초이스 하는 수는 적은 값이다.

가지치기
: 트리의 일부분을 잘라내는 것이다.     // 승리 전략에 영향을 미치지 않는 부분을 잘라내어 속도를 높인다. 
 예제를 보면서 이해하자.