하바나

Havannah
이 기사는 보드 게임에 관한 것이다.영어마을은 체셔의 하바나를 보라.다른 용도는 Havana(동음이의)를 참조하십시오.
하바나에 있는 3개의 승리한 구조물의 예, 8번 베이스 보드에 있는 것.왼쪽에서 오른쪽으로, 그것들은 포크, 고리 그리고 다리 입니다.

하바나는 크리스천 프릴링이 발명한 2인용 추상 전략 보드 게임이다.그것은 일반적으로 커넥션 게임이라고 불리는 게임 계열에 속한다; 그것의 친척들은 Hex와 TwixT를 포함한다.하바나는 "정밀하고 다양한 전략"을 가지고 있으며 베이스 10 육각형 보드, 한쪽으로 10개의 육각형 셀에서 가장 잘 연주된다.[1]

이 게임은 독일에서 라벤스버거가 한 기간 동안 발행한 것으로 초보자에게 적합한 더 작은 베이스-8 보드를 가지고 있다.요즘은 헥스보드에서만 생산되고 있다.[2]

게임 규칙

한 선수는 흑인으로, 다른 선수는 백인으로 플레이한다.흰색이 시작되고, 그 후에 번갈아 움직인다.규칙은 다음과 같다.

  • 각 플레이어는 턴마다 자신의 색깔의 돌을 보드 위에 놓는다.
  • 돌은 절대 움직이거나, 포획하거나, 다른 방법으로 변하지 않는다.
  • 플레이어는 깨지지 않은 선이나 경로, 연결된 스톤, 모든 색상의 세 가지 구조 중 하나를 완성할 때 승리한다.
    • 링은 하나 이상의 셀 주위의 루프(주변 셀이 플레이어에 의해 점유되거나 비어[3] 있든 상관없이)이다.
    • 보드의 6개 코너 셀 중 2개를 연결하는 브리지
    • 보드의 세 모서리를 연결하는 포크, 모서리 점은 가장자리의 일부로 간주되지 않는다.

세 가지 승리 조합의 예는 모두 위에 나와 있다.널빤지 중앙에 있는 구조물은 고리, 왼쪽에 있는 구조물은 포크, 오른쪽에 있는 구조물은 교량이다.

하바나에서 가장 먼저 이적하는 선수가 뚜렷한 이점을 갖고 있기 때문에 일반적으로 공정성을 위해 파이 규칙이 시행된다.이 규칙은 첫 번째 선수가 먼저 움직인 후에 두 번째 선수가 첫 번째 선수와 포지션 전환 여부를 선택할 수 있도록 한다.[4]

힘이 다른 선수들은 약한 선수(흰색으로)가 첫 번째 턴에 2개 이상의 돌을 놓도록 허용했을 때 여전히 흥미로운 경기를 할 수 있다.

16진수 대비 차이

헥스에서는 보드가 완전히 채워지면 정확히 한 명의 플레이어가 승리 연결을 갖게 되고, 하바나에서는 완전히 채워진 보드가 보통 한 개 이상의 승리 구조를 갖게 된다(그러나 경기는 첫 번째 승리 구조로 끝난다).

Hex에서와 달리 Havannah에서 추첨은 기술적으로 가능한데, 실제로는 극히 드물다.인간 선수들 사이에 한 번의 무승부가 있었던 것으로 알려져 있다.[5]전술은 전략보다 숙달하기 훨씬 쉽고, 경기 수준의 차이도 상당하다.

컴퓨터 하바나

2002년 프릴링은 10경기 중 단 한 경기라도 그를 이길 수 있는 어떤 컴퓨터 프로그램에도 2012년까지 이용할 수 있는 1000유로의 상금을 내걸었다.여러 해 동안, 컴퓨터 프로그램은 인간 선수들보다 훨씬 뒤떨어졌다.그러나 2010년 이후 몇몇 하바나 놀이 프로그램들이 몬테카를로 나무 찾기 기술을 적용하여 경기력이 눈에 띄게 향상되었다.프릴링은 2012년 10월 15일~19일 열린 '하바나 챌린지 2012'에서 이용 가능한 최강의 하바나 플레이 프로그램 3개를 상대로 10경기를 치렀고, (적어도) 흑백 1경기를 치렀다.[6]프릴링은 라지코니크 프로그램을 상대로 백의종목 경기를 포기해야 하는 상황에서 이 경기에서 패했다.

2019년까지 최고의 인간은 여전히 컴퓨터보다 훨씬 강했다.그러나 폴리게임즈[7](Facebook 인공지능 리서치와 여러 대학이[8] 처음 개발한 오픈소스 프로젝트)를 기반으로 한 메타토로는 리틀골렘에서 ELO 1위를 한 휴먼 플레이어를 상대로 규모 8의 보드 위에서 4연승했다.

이 결과는 헥스에서 최고의 인간을 이기기 위해 사용된 것과 같은 프로그램에 의해 달성되었다.알파제로에서와 같이 제로 학습에 기반한 알고리즘이지만, 참신한 알고리즘을 가지고 있다: 완전히 융합된 신경 네트워크(U-Net과 같이)와 글로벌 풀링 덕분에 비침윤성을 보드화한다.이것은 성장하는 구조를 허용하는데, 이것은 프로그램이 작은 보드에서 배운 다음 큰 보드에서 추론할 수 있다는 것을 의미한다.[9]

계산 복잡성

Havannah 해결은 입력 그래프의 크기와 관련하여 PSPACE 완료.[10]그 증거는 일반화된 지리학에서 감소된 것이며 지리 그래프를 나타내기 위해 고리 위협들을 사용하는 것에 기초한다.세부적으로 보면, 리히텐슈타인과 시퍼는 일반화된 지리는 그래프가 초당적이고 최대 3도라고 해도 PSPACE-hard로 유지된다는 것을 증명했으므로, 하바나에 여러 가지 기구를 구축함으로써 달성되는 그러한 그래프에서 동등한 하바나 위치를 구성하기만 하면 된다.

참조

  1. ^ Handscomb, Kerry, ed. (Winter 2002). "Front Cover". Abstract Games. Carpe Diem Publishing (12). ISSN 1492-0492.
  2. ^ 헥스보드
  3. ^ 프릴링에 의해 http://www.mindsports.nl/index.php/arena/havannah/49-havannah-rules;에서 밝힌 바와 같이 슈미트버거의 책은 반지가 적어도 한 개의 빈 감방을 둘러싸야 한다고 잘못 기술하고 있다.
  4. ^ Schmittberger, R. Wayne (1992), "Havannah", New Rules for Classic Games, John Wiley & Sons, Inc., pp. 116–17, ISBN 978-0471536215
  5. ^ "Little Golem".
  6. ^ "Human against Computer: 7-3 - Press release".
  7. ^ facebookincubator/Polygames, Facebook Incubator, 2020-05-28, retrieved 2020-05-29
  8. ^ "Open-sourcing Polygames, a new framework for training AI bots through self-play". ai.facebook.com. Retrieved 2020-05-29.
  9. ^ Cazenave, Tristan; Chen, Yen-Chi; Chen, Guan-Wei; Chen, Shi-Yu; Chiu, Xian-Dong; Dehos, Julien; Elsa, Maria; Gong, Qucheng; Hu, Hengyuan; Khalidov, Vasil; Li, Cheng-Ling (2020-01-27). "Polygames: Improved Zero Learning". arXiv:2001.09832 [cs.LG].
  10. ^ Bonnet, Édouard; Jamain, Florian; Saffidine, Abdallah (14 August 2013). Havannah and TwixT are PSPACE-complete. The 8th Intl. Conf. on Computers and Games. Keio University, Yokohama, Japan. arXiv:1403.6518. doi:10.1007/978-3-319-09165-5_15.

외부 링크