[STAT155] Chomp Game 정리

Chomp game은 조합 게임중 impartial game(불공정 게임)으로 분류되는 게임입니다. 두 플레이어는 동일한 규칙을 따르며, 초콜릿 바에서 조각을 선택할 때 선택할 수 있는 조각은 다를 수 있지만, 기본적으로 같은 게임 규칙을 적용받습니다.

 

Chomp game은 progressively bounded 게임입니다. Progressively bounded는, 조합 게임에서 게임이 유한한 수의 단계 내에 종료될 수 있음을 나타냅니다. 즉, 한 게임에서 모든 시작 위치로부터 게임이 끝날 때까지의 최대 이동수가 유한하다는 뜻입니다. 

---

 

두 플레이어는 직사각형 초콜릿 바를 두고 경기합니다.

왼쪽 아래 모서리에는 브로콜리가 위치하고 있습니다. 

 

각 플레이어는 자신의 차례에서 초콜릿 조각 하나를 선택합니다.

선택한 조각과 그 위쪽 및 오른쪽에 위치한 모든 조각을 동시에 제거합니다.

모든 초콜릿이 없어지는 상태가 되면, 브로콜리만이 남게 되는데, 제거할 조각이 없는 플레이어가 브로콜리를 먹게 됩니다.

게임의 종료 상태(terminal point)는 초콜릿이 모두 제거된 상태를 의미합니다.

---

Chapter 1.1.6

mxn 직사각형에서 플레이어 1은 항상 승리 전략을 가진다. 우상단 모서리를 제거하면 되는 것.

 

Strategy-Stealing 기법

2x3모양의 초콜릿 바의 경우, 우측 상단 모서리의 조각을 제거하면, Previous Player에게 P position을 안겨줄 수 있습니다. 이 경우, upper-right corner를 제거하는게 winning move가 되는거죠. 하지만 nxn모양의 초콜릿 바에선 upper-right-coner를 제거하는게 winning move가 아닙니다. N-Player가 해당 지점을 제거하고나서 P-Player가 제거하게될 타일의 모양은 N-Player가 첫 움직임에서 똑같은 결과를 만들어낼 수 있는 모양인겁니다. 그런데 이 말은 즉, N-Player에게 winning strategy가 존재한다는걸 증명해주는거죠. 구체적인 전략 제시에는 한계법이 있지만, N-Player에게 확실한 승리 전략이 존재한다는 사실이 중요한겁니다.

 

하단 첨부 링크는 UCLA에서 제작한 Chomp 연습게임입니다. 

https://www.math.ucla.edu/~tom/Games/chomp.html

Chomp

 

n x n 초콜릿 바 유도: 

위 그림처럼 세로 가로의 길이 같은 L자를 유지해주는 N-Position

 

2 x n 초콜릿 바 유도:

첫줄이 n, 그 윗줄이 n-1인 형태를 유지해주는 N-Position