카일스

카일즈는 1908년 헨리 듀데니가 고안한 조합 게임 이론의 단순한 공평한 게임이다.상상의 볼링핀이 줄지어 있는 상황에서 플레이어는 핀이 모두 없어질 때까지 핀 1개, 즉 인접한 핀 2개를 차례로 두드린다.팔각형 게임의 표기법을 사용하여 카일즈는 0.77로 표기된다.

규칙.

카일은 볼링핀을 나타내는 토큰을 줄지어 가지고 놀이를 한다.행의 길이는 어느 정도일 수 있다.두 선수는 번갈아 가며, 각 선수는 차례대로, 한 핀(그 핀에 직접 휘어지는 공) 또는 두 개의 인접한 핀(둘 다 치기 위해 구부러진 공) 중 하나를 제거할 수 있다.일반적인 플레이 컨벤션에서 선수는 법적 움직임이 없을 때(즉, 핀이 모두 없어졌을 때) 패한다.이 게임은 또한 미시르 규칙을 사용하여 할 수 있다. 이 경우 움직일 수 없는 플레이어가 승리한다.

역사

케일즈는 헨리 두데니에 의해 발명되었다.^[1][2]리차드 가이(Richard Guy)와 세드릭 스미스는 먼저 스프래그-그룬디 이론을 이용하여 정상 플레이 버전을 완전히 분석하였다.^[3][4]미시르 버전은 1973년 윌리엄 시버트가 분석했지만 1989년까지 그의 작품을 발표하지 않았다.^[5]

카일스(Kayles)라는 이름은 프랑스 퀼의 영국식 영어식어로, '볼링(bowling)'을 의미한다.

분석

대부분의 선수들은 줄 길이가 0보다 길어질 때마다 첫 번째 선수가 일반 카일즈에서 확실히 승리한다는 것을 금방 알게 된다.이 승리는 대칭 전략을 사용하여 달성할 수 있다.첫 번째 동작에서 첫 번째 선수는 같은 길이의 두 부분으로 줄이 끊어지도록 움직여야 한다.이것은 미래의 모든 이동을 한 구역 또는 다른 구역으로 제한한다.이제 첫 번째 선수는 반대줄에서 두 번째 선수의 움직임을 흉내낼 뿐이다.

$길이$가 n$${\$displaystyle n}$인 줄의 nim-값이 무엇인지 물어보는 것이 더 흥미롭다$.$이것은 흔히 ${\displaystyle {Kn}_{}}$ ${\$로 표기된다$;$ 숫자가 아니라 민첩하다.스프래그-그룬디 정리에 $의해{\displaystyle {}_{}}$ {\$displaystyle K_{n}}$는 결과 두 부분의 님 값의 가능한 모든 이동에 대한 mex이다.예를 들어,

${\displaystyle K_{5}={\mbox{mex}}\{{K_{0}+K_{4},K_{1}+K_{3},K_{2}+K_{2},K_{0}+K_{3},K_{1}+K_{2},},},},},}$

왜냐하면 5행의 길이로 부터 그 위치로 이동할 수 있기 때문이다.

${\displaystyle K_{0}+K_{4},\quad K_{1}+K_{3},\quad K_{2}+K_{2}+K_{2},\quad K_{0}+K_{3},{\text{}, }},},},}$

값의 재귀 계산($K{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$= ${\displaystyle 0}$ ${\displaystyle K_{0}=0$은 다음 표에 결과를 요약한 것이다.테이블에서$$ ${\displaystyle {Kn}_{}}$ ${\$의 값을 찾으려면 $n{\displaystyle }$ ${\$$displaystyle n}$을(를$)$ ${\displaystyle 12}$ ${\displaystyle a}$+ ${\displaystyle b}$로 $입력$하고$$a 행, b 열:

K ${\displaystyle {83}_{}}$ ${\$을 통한 카일 님 값

${\displaystyle K_{n}}$	0	1	2	3	4	5	6	7	8	9	10	11
0+	0	1	2	3	1	4	3	2	1	4	2	6
12+	4	1	2	7	1	4	3	2	1	4	6	7
24+	4	1	2	8	5	4	7	2	1	8	6	7
36+	4	1	2	3	1	4	7	2	1	8	2	7
48+	4	1	2	8	1	4	7	2	1	4	2	7
60+	4	1	2	8	1	4	7	2	1	8	6	7
72+	4	1	2	8	1	4	7	2	1	8	2	7

이때 님-값 시퀀스는 기간 12와 함께^[5] 주기적이 되므로 표의 추가 행은 모두 마지막 행과 동일하다.

적용들

이 구간은 확장이 필요하다.추가하면 도움이 된다. (2016년 7월)

Dots와 Box의 특정 위치가 Kayles 위치로 줄어들기 때문에 일반적인 Dots와 Box 위치를 분석하기 위해서는 Kayles를 이해하는 것이 도움이 된다.^[6]

계산 복잡성

정상적인 놀이에서 카일은 스프래그그루디 이론을 이용하여 다항식 시간에 풀 수 있다.^[3]

Node Kayles는 Kayles를 각 그릇이 원하는 꼭지점과 그 주변의 모든 꼭지점을 "노크 다운"(제거)하는 그래프에 일반화한 것이다.(대안적으로 이 게임은 두 플레이어가 함께 독립 세트를 찾는 것으로 볼 수 있다.)셰퍼(1978)는 이 게임의 결과를 결정하는 것이 PSPACE-완전이라는 것을 증명했다.^[7]동일한 결과가 각 노드에 대해 특정 노드를 녹다운 대상으로 선택할 수 있는 당파적 노드 Kayles에 대해 적용된다.

참고 항목

• 콤비네이터 게임 이론
• 팔분의 게임
• 도슨스 케일스
• 님버

참조