Here is a pdf that explains how to win at the hex game :
Apply Heuristic Search to Discover a New Winning Solution in 8 × 8 Hex Game
Jing Yang, Simon Liao, Mirek Pawlak
ABSTRACT
In certain games such as Hex, human experts are still much
stronger than the best existing computer programs. By
combining human Hex experts’ excellent “sense” of good
and bad opening moves and our newly developed search
algorithms, knowledge representations, and detailed rules,
this paper describes a new Hex solver.
As the result, a new winning solution on 8×8 Hex
board has discovered with the first move at F3.
1. INTRODUCTION
Hex is a two-player strategy board game. A Hex board is
composed of hexagons that form a parallelogram shape
shown in Figure 1. Sometimes, the Hex board is also
described as a diamond shape illustrated in Figure 2. In
fact, these two Hex boards are identical and each board is
merely a rotated version of the other. In this paper, we use
the parallelogram version of the Hex board. The size of a
Hex board, denoted by n×n that indicates n rows and n
columns, can vary. The larger the Hex board is, the more
complex and difficult the game will be. As shown in
Figure 1, corresponding to their location on the
parallelogram, four borders of the Hex board are referred
to as “top”, “bottom”, “left”, and “right”, respectively,
Two players take turns placing black and white game
pieces on empty hexagons. The player playing black color
pieces will start the game. The player with black pieces
begins the game. The player playing black pieces tries to
make a connected chain from “top” to “bottom”, and the
player playing white pieces tries to make a connected
chain from “left” to “right”. The first player to make a
connected chain from one border to another wins the game.
For example, Figure 3 illustrates the middle stage of a Hex
game and it is black’s turn. If the player plays a black
piece at hexagon “A”, the player playing black will win the
game. However, if a black piece is placed at any empty
hexagon other than “A”, the other player will play a white
piece at hexagon “A” and win the game.
Since Hex was invented independently by Piet Hein
and John Nash in 1940’s [3], several important research
papers have been published. Shannon and Moore
developed a Hex playing machine in 1953 [8], and their
electrical charge distribution approach still is applied in
Figure 1: An 8x8 Hex board
Figure 2: A diamond shape 8x8 Hex board
Figure 3: The first player plays at cell “A” wins the game
Hexy, one of the strongest computer Hex programs
nowadays [2]. Since a white connected chain and a black
connected chain cannot co-exist, there is no draw in Hex.
A strict mathematical proof was given by David Gale in
late 1970’s [4]. Based on this fact and strategy stealing
proof technique, John Nash proved that the first player will
win, if optimal moves are made [5], though he did not
provide a detailed solution on how to win. Usually, solving
a game means that a detailed account of achieving the
optimal result is provided. Stefan proved that Hex is a
Fourth International Conference on Fuzzy Systems and Knowledge Discovery (FSKD 2007)
0-7695-2874-0/07 $25.00 © 2007
PSPACE-complete game [6], which indicates that
searching for a winning strategy in an arbitrary game state
can be a computation-consuming task. By John Tromp’s
estimation of possible game states for Hex games [3],
when the Hex board is 8×8, 9×9, 11×11, and 14×14, the
possible game states are 4.18×1029, 2.4×1037, 2.38×1056,
and 1.14×1092. Performing a brute force search on such
search spaces with the existing technologies and computers
will be impossible. Therefore, finding winning strategies
for larger Hex boards is a very challenging task to
researchers. In 2001, a winning strategy for a 7×7 Hex
board was first accomplished [9]. Then, the winning
strategies for 8×8 and 9×9 Hex boards were also conducted
[11][12]. In 2003, a team of researchers from the
University of Alberta solved all first moves on a 7×7 Hex
board [7].
In this paper, we will describe a Hex solver that
discovers a new winning strategy on an 8×8 Hex board.
헥스 게임에서 승리하는 방법을 설명하는 PDF가 있습니다:휴리스틱 검색을 적용하여 8 × 8 헥스 게임에서 승리하는 새로운 솔루션 발견하기징 양, 사이먼 리아오, 미렉 파울락초록헥스와 같은 특정 게임에서 인간 전문가는 여전히 현존하는 최고의 컴퓨터 프로그램보다 훨씬현존하는 최고의 컴퓨터 프로그램보다 더 강합니다. 왜냐하면인간 헥스 전문가의 뛰어난 "감각"을 결합하여좋은 수와 나쁜 수에 대한 뛰어난 "감각"과 새로 개발된 검색알고리즘, 지식 표현 및 세부 규칙을 결합하여,이 논문에서는 새로운 헥스 솔버에 대해 설명합니다.그 결과, 8×8 Hex보드에서 F3의 첫 번째 수로 새로운 승리 솔루션을 발견했습니다.1. 소개헥스는 2인 전략 보드 게임입니다. 헥스 보드는평행 사변형 모양을 이루는 육각형으로 구성되어 있습니다.육각형으로 구성됩니다. 때때로 헥스 보드는그림 2에 표시된 다이아몬드 모양으로 묘사되기도 합니다. In사실, 이 두 개의 헥스 보드는 동일하며 각 보드는다른 보드의 회전된 버전일 뿐입니다. 이 백서에서는평행 사변형 버전의 헥스 보드를 사용합니다. 정육각형의 크기는행과 열의 개수를 나타내는 n×n으로 표시되는 헥스 보드의 크기는로 표시되는 헥스 보드의 크기는 다양할 수 있습니다. 헥스 보드가 클수록게임이 더 복잡하고 어려워집니다. 그림 1에서 볼 수 있듯이그림 1과 같이 평행 사변형의 위치에 따라평행 사변형에서 육각형 보드의 네 테두리는각각 "위", "아래", "왼쪽", "오른쪽"이라고 합니다,두 명의 플레이어가 번갈아 가며 빈 육각형에 흑백 게임조각을 빈 육각형에 놓습니다. 검은 색을 플레이하는 플레이어가조각을 가진 플레이어가 게임을 시작합니다. 검은색 조각을 가진 플레이어가게임을 시작합니다. 검은색 조각을 가진 플레이어는"위"에서 "아래"로 연결된 사슬을 만들려고 합니다.흰색 조각을 가진 플레이어는 "왼쪽"에서 "오른쪽"으로 연결된사슬을 만들려고 합니다. 가장 먼저 한 테두리에서 다른 테두리로연결된 사슬을 먼저 만드는 플레이어가 게임에서 승리합니다.예를 들어 그림 3은 헥스 게임의 중간 단계를 보여줍니다.게임의 중간 단계를 보여줍니다. 플레이어가 검은색조각을 플레이하면 검은색을 플레이한 플레이어가 승리합니다.게임에서 승리합니다. 하지만 검은색 말이 "A"가 아닌 다른 빈빈 육각형에 검은색 조각을 놓으면 상대 플레이어는 흰색조각을 놓으면 게임에서 승리합니다.헥스는 1940년대에 피에트 하인과 존 내쉬가와 존 내쉬가 1940년대[3]에 독립적으로 개발한 이후, 몇 가지 중요한 연구논문이 발표되었습니다. 섀넌과 무어는 1953년에 헥스 게임기를 개발했으며[8], 그들의전하 분배 접근 방식은 여전히그림 1: 8x8 헥스 보드그림 2: 다이아몬드 모양의 8x8 헥스 보드그림 3: 셀 "A"에서 먼저 플레이하는 플레이어가 게임에서 승리합니다.오늘날 가장 강력한 컴퓨터 헥스 프로그램 중 하나인 Hexy는게임에서 승리합니다 [2]. 흰색으로 연결된 체인과 검은색으로 연결된연결된 체인은 공존할 수 없기 때문에 헥시에서는 무승부가 발생하지 않습니다.이에 대한 엄격한 수학적 증명은 1970년대 후반 데이비드 게일(David Gale)에 의해1970년대 후반 [4]. 이 사실과 전략 훔치기증명 기법을 바탕으로, 존 내쉬는 최적의 수를 두는 경우 첫 번째 플레이어가최적의 수를 두면 승리할 수 있다는 것을 증명했습니다[5].승리하는 방법에 대한 자세한 솔루션을 제공하지는 않았습니다. 일반적으로 게임을 푼다는 것은게임을 푼다는 것은 최적의 결과를 얻기 위해최적의 결과가 제공됩니다. 스테판은 헥스가제4회 퍼지 시스템 및 지식 발견에 관한 국제 컨퍼런스 (FSKD 2007)0-7695-2874-0/07 $25.00 © 2007PSPACE-완성 게임 [6]에서 다음을 나타냅니다.임의의 게임 상태에서 승리 전략을 찾는 것은계산이 많이 필요한 작업일 수 있습니다. 존 트롬프의헥스 게임의 가능한 게임 상태 추정 [3],헥스 보드가 8×8, 9×9, 11×11, 14×14일 때, 가능한 게임 상태는가능한 게임 상태는 4.18×1029, 2.4×1037, 2.38×1056,그리고 1.14×1092입니다. 이러한 검색 공간에 대해 무차별 대입 검색을 수행하면무차별 대입 검색을 수행하는 것은불가능합니다. 따라서 더 큰 헥스 보드에서 승리하는 전략승리 전략을 찾는 일은매우 어려운 작업입니다. 2001년에 7×7 Hex보드에 대한 승리 전략이 처음으로 달성되었습니다[9]. 그 후, 8×8 및 9×98×8 및 9×9 헥스 보드에 대한 전략도 수행되었습니다.[11][12]. 2003년에 앨버타 대학교의 연구팀이앨버타 대학교 연구팀이 7×7 헥스 보드에서 모든 첫 수를 풀었습니다.보드에서 모든 첫 수를 풀었습니다 [7].이 논문에서는 다음과 같은 헥스 솔버에 대해 설명합니다.8×8 헥스 보드에서 새로운 승리 전략을 발견합니다.