[STAT155] Rim Game 정리

Chapter 1.1.3

Rim game이란 Nim game의 변형으로, Impartial game에 속합니다. 이번 장에선 이 Rim game에 대해서 알아보겠습니다.

 

 

---

Rims에서는 플레이어들이 평면에 놓인 유한한 수의 점들과 서로 교차하지 않는 유한한 수의 loop를 시작으로 둡니다.

각 loop는 최소한 하나의 점을 지나야 하며(선이 점을 가르는 형태), 플레이어는 기존의 루프와 교차하지 않는 새로운 루프를 그려야 합니다.

목표는 마지막 루프를 그리는 플레이어가 되는 것입니다.

---

 

Two Equivalent Dots (Equivalence Classs)

Uncovered dots and continuous path exists that is connexting them without passing any loops.

어느 루프에도 속하지 않은 두 점이 루프에 가로막히지 않고 연결되는 경로가 존재한다면, 이를 동등하다고 정의합니다.

이 Rim game은 Nim game으로 연결될 수 있는데요. Equivalence class의 각 점들을 pile of chips로 개념화하는 겁니다.

Rim에서 플레이어가 최소한 하나의 점을 제거하며 루프를 그리는 행위는, Nim에서 플레이어가 한 pile로부터 칩을 가져가는 행위와 같다고 볼 수 있죠. 루프를 그리고 남아있는 점들은, 파일에서 칩을 가져가고 남은 칩들의 개수와 동일합니다.

 

흥미로운 점은, Nim에서는 단일 pile에서만 칩을 제거하는 반면, Rim에선 플레이어가 자신의 턴에 특정 pile의 점 구성을 재구성할 수 있다는 점입니다. 이게 무슨 말이냐면:

Rim에서는 dots만 충분하고 루프간 교차하지만 않는다면, 루프 안에 루프를 그릴 수 있습니다. 그렇게 되면, 특정 pile에서 칩을 꺼내가고 해당 pile에 남겨진 칩들을 이용해서  2개의 pile로 쪼갤 수 있습니다.

---

환 웅,  B.A. in Statistics & Minor in Data Science at University of California, Berkeley