푸트볼

Phutball
몬티 파이톤 스케치는 철학자 축구 경기를 참조하십시오.
남자 5명이 투입된 후 퍼트볼 경기(공은 아직 움직이지 않았다)

푸트볼(Phutball:철학자 축구의 줄임말)은 엘윈 베를캄프, 존 호튼 콘웨이, 리처드 K에 묘사된 2인용 추상 전략 보드 게임이다. 수학 연극을 위한 '가이'의 승리 방법.[1]

규칙.

푸트볼은 19×15 격자의 교차점에서 백석 1개와 필요한 만큼의 검은 돌을 사용하여 연주된다.[1]이 글에서 두 선수의 이름은 Ohs (O)와 Eks (X)이다.이 판자는 왼쪽에서 오른쪽으로 A에서 P까지 (Omating I)라고, 오즈의 관점에서 아래쪽에서 위쪽으로 1에서 19로 라벨이 붙여져 있다.0열과 20열은 각각 1열과 19열 이상의 "기판 밖에서"를 나타낸다.

특화된 퍼트볼 보드는 구하기 어렵기 때문에 보통 19×19 바둑 보드에서 경기가 진행되는데, 축구는 흰색 돌이, 남자는 검은색 돌로 표현된다.

남자(검은 돌)를 이용해 축구(백석)를 상대 골라인(1열이나 19열) 위로 이동시켜 골을 넣는 게 목표다.Ohs는 축구를 19열이나 20열로, Eks는 1열이나 0열로 옮기려고 한다.한 선수가 다른 선수에게 핸디캡을 주지 않는 한,[1] 경기가 시작될 때 축구는 중앙 지점에 놓이게 되며, 이 경우 공은 한 선수의 골에 가까워진다.

선수들은 번갈아 가며 움직인다.이동은 보드의 어떤 빈자리에 사람을 추가하거나 공을 이동시키는 것이다.오스가 연기하는 남자들과 Eks가 연기하는 남자들 사이에는 차이가 없다.[1]

점프

축구는 인접한 남자들을 넘어가는 일련의 점프에 감동한다.각 점프는 한 명 이상의 남자 위에 가로, 세로 또는 대각선으로 일직선으로 첫 번째 빈자리에 위치한다.그런 다음 점프한 남성은 보드에서 제거된다(이후 점프 발생 전).이 과정은 점프할 수 있는 사람이 남아 있고 선수가 원하는 한 반복된다.점프는 선택 사항이다: 점프를 할 필요가 없다.체커와는 대조적으로 일렬로 늘어선 여러 명의 남자가 집단으로 점프를 하고 제거된다.[1]

오른쪽의 도표는 점프를 보여준다.

  • 오스는 K6-G9-G11-J11에서 축구를 움직인다.
  • J7, H8, G10, H11의 남자는 제거된다.
  • K6–G9–J9–G7에서의 점프는 합법적이지 않을 것이며, 이는 H8에 있는 사람을 두 번 점프시킬 것이기 때문이다.

축구에서 상대 골라인 위나 위로 이동하면 골이 터진다.축구는 골선을 통과했지만 추가 점프로 인해 다른 곳으로 귀결되면 경기는 계속된다.

, 전략

  • 점프의 세심하게 설정된 순서는 중요한 순간에 점프를 연장하여 "스포밍"할 수 있다.
  • 왼쪽이나 오른쪽 가장자리로의 점프는 빈 지점을 남겨두지 않아 막을 수 있다.
  • 점프할 때 상대가 자신의 진보를 '해제'할 수 있도록 쉽게 사용한 복귀 경로를 남겨두는 것이 보통 나쁘다.

계산 복잡성

경기는 (m×n 보드 위에서) 1승이 있는지 확인하는 것이 NP-완전일 정도로 충분히 복잡하다.[2]출발지점에서는 승리 전략이 있는 선수가 있는지, 아니면 두 선수 모두 드로잉 전략이 있는지는 알 수 없지만, 두 선수 모두 드로잉 전략이 있는 다른 구성이 존재한다.[3]

처음에는 백석이 중앙에 배치되는 임의의 보드 포지션을 주어, 현재 플레이어가 승리 전략을 가지고 있는지 여부를 결정하는 것은 PSPACE-hard이다.[4]

참조

  1. ^ a b c d e Schmittberger, R. Wayne (1992). New Rules for Classic Games. John Wiley & Sons Inc. pp. 112–14. ISBN 978-0471536215.
  2. ^ Demaine, Erik D.; Demaine, Martin L.; Eppstein, David (2002). "Phutball endgames are hard" (PDF). More Games of No Chance. MSRI Publications 42, Cambridge Univ. Press. pp. 351–360.
  3. ^ Sarkar, Sucharit (2019). "Phutball draws". Games of No Chance 5. MSRI Publications 70, Cambridge Univ. Press. pp. 439–446.
  4. ^ Dereniowski, Dariusz (2010). "Phutball is PSPACE-hard". Theoretical Computer Science. 411 (44–46): 3971–3978. arXiv:0804.1777. doi:10.1016/j.tcs.2010.08.019. S2CID 14975402.

추가 읽기

  • Grossman, J.P.; Nowakowski, Richard J. (2002). "One-Dimensional Phutball" (PDF). More Games of No Chance. MSRI Publications 42, Cambridge Univ. Press. pp. 361–367.