m,n,k-게임은 게임 이론에서 다루는 추상 게임으로, 오목이나 틱택토 등의 게임을 일반적으로 확장한 것이다.[1]
m,n,k-게임은 m×n 크기의 바둑판에서 두 명이 번갈아가면서 각자의 돌을 하나씩 놓아, 자신의 돌이 가로, 세로, 혹은 대각선으로 한 줄에 k개가 놓여져 있으면 이기는 규칙을 가진다. 오목은 15,15,5-게임이며, 틱택토는 3,3,3-게임이다.
m,n,k-게임은 게임판 위에 자신의 돌을 추가적으로 놓는 것에 있어 부정적인 결과를 발생하지 않는다. 이러한 성질은 두 번째 참여자가 이기는 전략이 존재하지 않는다는 것을 의미하는데, 만약 두 번째 참여자가 이기는 전략이 존재한다고 하면, 첫 번째 참여자는 돌을 아무데나 둔 다음 다음부터는 그 전략을 이용할 수 있기 때문이다(strategy-stealing argument). 따라서 m,n,k-게임은 첫 번째 참여자가 이기거나, 혹은 비기는 결과만이 존재한다.[1]
특별한 결과
- k = 1 또는 k = 2 일 때는 자명하게 이긴다. (1,1,2) 와 (2,1,2)는 예외이다. 이 때에는 비긴다.
- k = 3 일 때는 (3,3,3) 일 때(틱택토) 또는 m이나 n이 3 미만일 때 비긴다. 다른 경우는 첫 번째 참여자가 이긴다.
같이 보기
각주
- ↑ 가 나 H. Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence.
