[Game of Chomp] (0)Game of Chomp!
Discrete Mathematics 수업 때 접하게 된 Game of Chomp.
처음에 rule을 몰랐을 때는 그냥 31게임의 외국 버전인가?라고 생각했는데, 닮아있는 듯 약간의 차이가 있다.
Game of Chomp의 rule을 아래 그림과 함께 살펴보자.
Rule
1. 두 명의 플레이어가 한 번씩 번갈아가며 플레이한다.
2. 각 플레이어는 자신의 차례가 오면 하나의 버섯을 선택하고, 그 버섯을 기준으로 오른쪽과 아래쪽 사각형 바운드 내의 버섯을 모두 가져간다. (그림 1 참조)
3. 가장 왼쪽 위의 버섯은 독버섯이고, 이를 먹는 자는 게임에 패배한다. 패배의 결말은 죽음
nim game이나 tic-tac-toe 처럼 한판이 엄청나게 짧다. 그냥 가볍게 생각 없이 하기 괜찮은 게임인 듯하다.
이런 단순함에도 불구하고, 이에 대해 글을 쓰게 된 것은 이 게임의 필승전략에 대한 흥미로운 이론을 접했기 때문이다.
!!두번째 플레이어는 항상 필승전략이 존재하지 않는다는 사실!!
두번째 플레이어의 winning strategy가 존재하지 않는다는 사실도 흥미로웠지만, 이를 증명하는 과정이 더 신기했다.
조합론적 게임이론(Combinatorial Game Theory)에서의 Strategy-stealing argument의 논리로 이를 증명하는데,
이는 큰 범주에서의 Non-constructive Existence Proof와 유사하다는 느낌을 받았다.
낯선 용어들의 갑작스러운 등장에 당황스럽겠지만, 그게 정상이다! 차근차근 이어지는 포스팅에서 다뤄보고자 한다.