촘프
Chomp | 이 글은 검증을 위해 인용구가 추가로 필요하다.– · · 책· · (2021년 7월)(이 템플릿 하는 |
촘프는 작은 사각 셀로 구성된 직사각형 그리드에서 하는 2인 전략 게임으로 초콜릿 바의 블록으로 생각할 수 있다.플레이어는 한 블록을 차례로 선택하고 그 아래 블록과 오른쪽에 있는 블록과 함께 "먹는다"(보드에서 제거)는 것이다.왼쪽 위 블록은 '독'이고 이것을 먹는 선수는 진다.
촘프의 초코바 제형은 데이비드 게일(David Gale) 덕분이지만, 고정 정수의 디비저를 선택한다는 측면에서 표현된 등가 게임이 앞서 프레데릭 슈(Frederik Schuh)에 의해 출판되었다.
촘프는 게임이 진행되는 부분 주문 세트가 최소 요소(독성 블록)를 제거한 총 주문 상품인 포셋 게임의 특례다.
예시 게임
아래는 5 × 4 바로 시작하는 일반적인 게임에서 동작 순서를 보여준다.
A선수는 오른쪽 하단 모서리에서 두 블록을 먹고, B선수는 맨 아래 줄에서 세 블록을 먹고, A선수는 독이 든 블록의 오른쪽 블록을 골라 11블록을 먹고, B선수는 나머지 기둥에서 세 블록을 먹고 독이 든 블록만 남는다.A선수는 마지막 한 블록을 먹어서 지어야 한다.
5×4바에서 출발할 때 A선수가 승리할 수 있다는 것을 증명할 수 있기 때문에 A선수의 움직임 중 적어도 하나는 실수라는 점에 유의한다.
게임 포지션
m ×n Chomp에서 중간 위치는 정수분할(양수 정수의 비증가 시퀀스) λ11 ≥ λ2 ≥ · · · · n arer with · · · r r r r r n n n n n n n and n n n n n n n n.이들의 숫자는 이항계수+ ) 이며 m과 n과 함께 기하급수적으로 증가한다.[1]
게임 승리
Chomp는 공평한 2인용 완벽한 정보 게임의 범주에 속한다.
1×1 이외의 직사각형 출발 위치에서는 첫 번째 선수가 승리할 수 있다.이것은 전략적인 주장을 사용하여 보여질 수 있다: 두 번째 선수가 첫 번째 선수의 움직임에 대해 승리 전략을 가지고 있다고 가정한다.그렇다면 첫 번째 선수가 오른쪽 아래 사각형만 가져간다고 가정해 보자.우리의 추정에 따르면, 두 번째 선수는 이에 대한 반응을 가지고 있어 승리를 강요할 것이다.그러나 그런 승리 반응이 존재한다면 첫 번째 선수가 첫 동작으로 플레이를 해서 승리를 강요할 수도 있었다.따라서 두 번째 선수는 승리 전략을 가질 수 없다.
컴퓨터는 합리적인 크기의 2차원 보드 위에서 이 게임의 승리 동작을 쉽게 계산할 수 있다.그러나 포지션 수가 기하급수적으로 증가함에 따라, 더 큰 보드의 경우 이를 실현할 수 없다.
정사각형 출발 위치(즉, n × 2의 경우 n × n)의 경우, 승리 전략을 쉽게 명시할 수 있다.첫 번째 플레이어는 독이 있는 광장에 연결된 동일한 길이의 L자 모양과 동일한 길이의 기둥만 사용하여 두 번째 플레이어를 제시해야 한다.그러면 두 번째 선수가 L의 한쪽 팔에 무엇을 하든지, 첫 번째 선수는 두 번째 팔에서 같은 동작으로 답하며, 항상 대칭적인 L자 모양으로 두 번째 선수를 다시 제시한다.결국 이 L은 독이 있는 하나의 광장으로 전락하고, 두 번째 선수는 패하게 된다.
쿰프의 일반화
3차원 촘프에는 (i,j,k)로 색인된 블록의 큐보이드로 된 초기 초콜릿 바가 있다.이동은 선택한 블록의 해당 인덱스와 더 크거나 같은 모든 블록과 함께 블록을 취하는 것이다.동일한 방법으로 Chomp는 어떤 숫자의 차원으로 일반화될 수 있다.
Chomp는 때때로 숫자로 묘사된다.초기 자연수가 주어지고, 플레이어는 초기 숫자의 양수를 번갈아 선택하지만, 이전에 선택한 구분자의 배수를 선택할 수는 없다.이 게임은 초기 자연수가 n개의 주요 인자를 가지고 있고 Chomp 보드의 치수는 그것의 주요 인자화에서 소수점 지수에 의해 주어지는 n차원 Chomp를 모델로 한다.Ordinal Chomp는 일부 치수의 순서형 번호(예: 2 × (Ω + 4) 바)를 가진 무한 보드에서 재생된다.이동은 블럭을 선택하고 선택한 블럭의 해당 지수보다 크거나 같은 두 지수를 가진 모든 블럭을 제거하는 것이다.Ω × Ω × Ω Chomp의 경우는 주목할 만한 공개적인 문제로서, 우승 첫 수를 찾으면 100달러의 보상이 제공되었다[2].
좀 더 일반적으로 Chomp는 최소 요소와 함께 부분적으로 정렬된 세트에서 재생될 수 있다.이동은 모든 더 큰 요소와 함께 모든 요소를 제거하는 것이다.선수는 최소한의 요소만 취하면 진다.
모든 종류의 Chomp도 miserer play convention을 이용하여 독에 의존하지 않고 연주할 수 있다.마지막 초콜릿 블록을 먹는 플레이어는 독이 든 것이 아니라 마지막 플레이어가 된다는 덕택에 간단히 진다.이것은 Chomp를 혼자서 할 때 일반적인 규칙과 동일하지만, 마지막 마지막 초콜릿 블록만 지는 Chomp 게임의 이격 합계를 할 때 다르다.
