m,n,k-game

m,n,k게임은 두 선수가 번갈아 가며 자신의 색깔의 돌을 m-by-n 보드에 올려놓는 추상 보드게임으로, 승자는 먼저 자신의 색깔의 kstone을 일렬로, 수평으로, 수직으로, 또는 대각선으로 받는 선수다.^[1][2]따라서 틱택토(tic-tac-toe)는 3,3,3게임이고 프리스타일 고모쿠는 15,15,5게임이다.m,n,k게임은 또한 m-by-n 보드에서 k-in-a-row 게임이라고도 불린다.

m,n,k-games는 주로 수학적인 흥미가 있다.완벽한 플레이로 게임의 결과물인 게임테오르틱 가치를 찾으려 한다.이것은 게임을 해결하는 것으로 알려져 있다.

전략 도용 논쟁

콤비네이터 게임 이론의 주장을 가로채는 표준 전략은 어떤 m,n,k 게임에서도 두 번째 선수가 승리할 것이라고 확신하는 전략이 있을 수 없다는 것을 보여준다.어떤 포지션에서든 어느 선수에게나 주어진 추가 돌은 그 선수의 기회를 향상시킬 수 있기 때문이다.전략 도용 논쟁은 두 번째 선수가 승리 전략을 가지고 있고 첫 번째 선수의 승리 전략을 보여준다고 가정한다.첫 번째 선수는 우선 제멋대로 움직인다.이후 선수는 자신이 두 번째 선수인 척하며 두 번째 선수의 승리 전략을 채택한다.전략이 이미 점령한 '임의' 광장에 돌을 놓을 것을 요구하지 않는 한, 그들은 이것을 할 수 있다.하지만 이렇게 되면 다시 자의적인 움직임을 보이며 두 번째 선수의 승리 전략으로 이전과 같은 행보를 이어갈 수 있다.여분의 돌은 그들을 다치게 할 수 없기 때문에, 이것은 첫 번째 선수에게는 승리 전략이다.그 모순은 원래의 가정이 거짓이라는 것을 암시하며, 두 번째 선수는 승리 전략을 가질 수 없다.

이 주장은 특정 경기가 무승부인지 첫 번째 선수의 승리인지에 대해서는 아무 것도 말하지 않는다.또한, 그것은 실제로 첫 번째 선수에게 전략을 주지 않는다.

다른 보드 크기에 결과 적용

유용한 개념은 '취약(m,n,k) 게임'으로, 두 번째 선수의 연승으로 경기가 끝나지 않는다.

약점(m,n,k)이 무승부일 경우 m 또는 n이 감소하거나 k가 증가하면 추첨 경기도 발생한다.

반대로 약하거나 정상(m,n,k)이 승리라면 더 큰 약자(m,n,k)는 승리다.

페어링 전략을 사용한 추첨 증명서는 약한 버전과 모든 작은 버전에 대해서도 추첨을 증명한다는 점에 유의하십시오.

일반결과

다음 진술은 두 선수 모두 최적의 전략을 구사한다고 가정할 때 약한 경기의 첫 번째 선수를 가리킨다.

• 특정(m₀, n₀, k₀)이 무승부라면 k ≥ k를₀ 가진 (m₀, n₀, k)는 무승부, m ≤ m과₀ n ≤ n을₀ 가진 (m, n, k₀)는 무승부다.마찬가지로 (m₀, n₀, k₀)가 승리라면 (m₀, n₀, k) k with k가₀ 승리, (m, n, k₀) m ≥ m과₀ n ≥ n이₀ 승리다.
• k ≥ 9는 무승부다: k = 9와 보드가 무한할 때, 두 번째 플레이어는 "무승부 전략"을 통해 무승부를 할 수 있다.무한보드 위에서 무승부를 기록한다는 것은 완벽한 플레이로 게임이 영원히 진행된다는 것을 의미한다.페어링 전략에는 보드의 모든 사각형을 한 쌍으로 나누어 항상 첫 번째 플레이어의 사각형에서 플레이함으로써 두 번째 플레이어가 한 줄로 k를 얻을 수 없도록 하는 방법이 포함된다.무한 보드의 페어링 전략은 어떤 한정된 보드에도 적용될 수 있다 – 만약 전략이 보드 밖에서 움직여야 한다면, 두 번째 플레이어는 보드 내부에서 임의적인 움직임을 한다.
• k ≥ 8은 무한대 위에서 무승부다.이 전략이 어떤 한정된 보드 크기에 적용되는지는 명확하지 않다.^[2]무한보드에서 k가 6이나 7일 때 두 번째 선수가 무승부를 강요할 수 있는지는 알 수 없다.
• k ≥ 3과 k > m 또는 k > n 중 하나는 추첨으로, 또한 k보다 작지 않은 치수에서의 페어링 전략(또는 둘 다 작을 경우 사소한 승부가 불가능함)에 의해서도 추첨한다.

구체적인 결과

• k = 1과 k = 2는 (1,1,2,2)와 (2,1,2)를 제외하고 사소한 승리다.
• (3,3,3)은 무승부(Tic-tac-toe 참조), (m,n,3)는 m < 3 또는 n < 3. (m,n,3)은 m ≥ 3과 n ≥ 4 또는 m ≥ 4와 n ≥ 3이면 승이다.
• (5,5,4) is a draw, which means that (m,n,4) is a draw for m ≤ 5 and n ≤ 5, and (6,5,4) is a win, which means that (m,n,4) is a win for m ≥ 6 and n ≥ 5 or m ≥ 5 and n ≥ 6. (m,4,4) is a win for m ≥ 30 (Lustenberger, 1967) and a draw for m ≤ 8.^[1](m, 4,4)가 9㎛ for 29의 승인지 무승부인지는 알 수 없다.
• 위위안슈와 고추링의 컴퓨터 검색 결과, (7,7,5)와 (8,8,5)가 모두 추첨된 것으로 나타났는데,^[3] 이는 (m,n,5)가 m ≤ 8과 n ≤ 8을 추첨한 것임을 의미한다.L의 컴퓨터 검색. 빅터 앨리스는 고모쿠의 제한적인 규칙 중 하나라도 (15,15,5)가 승리라는 것을 보여주었다.
• (9,6,6)과 (7,7,6)은 쌍을 통한 추첨이다.

다차원 변종

입체 보드 대신 다차원 보드에서 재생되는 변형을 고려할 수 있다.

보드가 길이가 k인 모든 모서리를 가진 n차원 하이퍼큐브인 k-in-a-row의 경우 핼레스와 Jujett은 k가 홀수일 경우 무승부임을 증명했다^[4].

k ≥ 3ⁿ − 1

또는 만약 k가 짝수라면

kⁿ⁺¹ ≥ 2 - 2

셀 수가 최소한 줄의 2배 이상일 때 경기가 무승부라고 추측하는데, 이는 만약의 경우, 그리고 만약의 경우에 한해서 일어나는 현상이다.

2k^{n n}≥ (k + 2)

참고 항목

참조