Here is the continuation of the article :
2. THE SEARCH ALGORITHMS
Hex is one of the a few games that human experts are
still much stronger than the best existing computer
programs. The human Hex experts are “smarter” in two
perspectives: they can apply general problem solving
techniques to reduce the search space significantly, and
human players have an excellent “sense” of good and bad
moves, which leads to limit the search space to good
moves only.
A greedy decomposition method was introduced in
2001 [9], which lead to the discovery of the first winning
strategy to solve the 7×7 Hex game. The decomposition
method divides a Hex game into several “local games”
with sub-goals. After all sub-goals are achieved, the
original game will be solved. A sub-goal is associated with
several empty positions called the “influence region” or
“carrier”. When the opponent’s move is not played within
the influence region, the sub-goal is secured. A Hex game
can often be decomposed in this way. One of the benefits
of the decomposition method is that the influence regions
can lead to cut-offs in a search. For example, in Figure 4, if
white’s 1 is not played among positions A through N and
position black 2, black can play at 2 to win the game.
Other moves for white would not be further searched
because they are worse than or equal to the previous move
1.
In a depth first search, the region cut-off takes effect
when the search process has reached a leaf of the tree. In
Figure 5, assume node L is a leaf, and the score of this
node is 1 (black wins). In step 1, the influence region,
marked as IA, can be calculated. Then, in step 2, IA is used
to cut white’s nodes on the above level (nodes A, B, C, D,
...). These nodes A, B, C, D, …, may not be further
explored if they are located outside of the influence region.
Assume that nodes A, B, and C have not been cut, then,
Figure 4: Positions A to N and black 2 form an influence
region for black’s win.
Figure 5: Region cut-off details
step 3 will search down the node B. If the result of
searching down node B is also a black’s win, the step 4
will be conducted, in which a new influence region IB is
calculated again and used to cut rest of nodes similar to
that of step 2. If there is no more node to be cut further,
step 5 will be carried out is to search down node C.
Assume the score of node C is also 1 and the new
influence is IC, since all nodes on this level are either
checked or cut, the score of node N will be 1 (black wins)
and the influence region is the union of IA, IB, and IC.
This bottom-up process can further propagate to the upper
levels.
During the process of searching for a winning
solution, all of the opponent’s possible moves should be
considered. Although the region cut-off idea can greatly
reduce the number of defense moves to consider, however,
it is still not enough to lead to a winning strategy on an
8×8 Hex board. Human Hex experts can understand a
Fourth International Conference on Fuzzy Systems and Knowledge Discovery (FSKD 2007)
0-7695-2874-0/07 $25.00 © 2007
board situation with logical insights. These insights will
tell them that playing a certain move may lead to a win and
playing another move will make a win impossible. Based
on this advantage, Hex experts only need to consider a few
moves on each level of a search. They may make a mistake
sometimes, but for the most part this insight will lead to
the desire result.
Searching a subset of possible moves is called a
selective search, which is a popular technique in computer
game programs. If one applies this approach to solving a
game when the heuristics are not perfect, the solution
maybe missed. There is an interesting concept named
symmetric property in Hex game, which indicates that a
winning opening may reveal some losing openings. This
idea was applied in our previous work to find losing
openings in a 7×7 Hex board [10]. The same idea was also
utilized in the process of finding a winning strategy on an
8×8 Hex board [11]. Figure 6 shows black’s first move in
this winning strategy for 8×8 Hex. Based on the region
cut-off algorithm, the positions marked by a cross in
Figure 6 do not have any effect to disallow black 1 to win
the game. Due to the symmetric property, if black’s first
move is played at anyone of the positions shown in Figure
7, white can play at 2 and use the same winning strategy to
win.
The selective search attempt will not be able to find a
winning solution if there is no winning strategy for the
player under the current game situation. The symmetric
property can further be used to determine the reason of not
being able to find a winning move. To do this, a symmetry
game needs to be created and the move against black’s
solving in the original game will be the testing move in the
symmetry game. Figure 8 shows the symmetry game of an
original game displayed in Figure 9 by changing original
position (x,y) to (y,x) and swapping the color. If the
symmetry game is solvable, there will be no winning
solution for the original game. If the symmetry game is not
solvable, it will lead to the conclusion that the heuristic set
needs to be improved further. For example, the proposed
Hex solver did not find a solution for the original game
shown in Figure 9, but solved the symmetry game
displayed in Figure 8. Therefore, the final conclusion is
that there is no winning solution for black in the case.
기사의 연속입니다:2. 검색 알고리즘헥스는 인간 전문가가 현존하는 최고의 컴퓨터보다현존하는 최고의 컴퓨터보다 훨씬 강력합니다.프로그램. 인간 Hex 전문가는 두 가지 측면에서 "더 똑똑합니다".두 가지 측면에서 "더 똑똑하다"고 할 수 있습니다.기술을 적용하여 검색 공간을 크게 줄일 수 있고인간 플레이어는 선과 악에 대한 뛰어난 '감각'을 가지고 있습니다.움직임에 대한 "감각"이 뛰어나기 때문에 검색 공간을 좋은움직임으로만 제한합니다.탐욕스러운 분해 방법은 2001년에 도입되었습니다.2001 [9], 최초의 승리 전략 발견으로 이어져전략이 최초로 발견되었습니다. 분해방법은 헥스 게임을 여러 개의 "로컬 게임"으로 나누고하위 목표가 있습니다. 모든 하위 목표가 달성되면원래 게임이 해결됩니다. 하위 목표는 다음과 연관됩니다."영향력 영역"이라고 불리는 여러 개의 빈 위치 또는"캐리어". 상대방의 이동이 영향력 영역 내에서 이루어지지 않으면상대방의 이동이 없으면 서브 목표가 확보됩니다. 헥스 게임은 종종 이런 식으로 분해될 수 있습니다. 분해 방법의 장점 중 하나는분해 방법의 장점 중 하나는 영향력 지역이검색에서 컷오프로 이어질 수 있다는 것입니다. 예를 들어, 그림 4에서백의 1번이 위치 A부터 N까지 중 플레이되지 않고위치가 검은색 2라면, 검은색은 2에서 플레이하여 게임에서 이길 수 있습니다.백의 다른 수들은 더 이상 검색되지 않습니다.이전 수보다 나쁘거나 같기 때문입니다.1.깊이 우선 검색에서 영역 컷오프는 검색 프로세스가 잎사귀에 도달하면검색 프로세스가 나무의 잎에 도달했을 때 적용됩니다. 에서그림 5에서 노드 L이 리프이고 이 노드의 점수가 1이라고 가정합니다.노드의 점수가 1이라고 가정합니다(검은색이 승리). 1단계에서 영향 영역(을 계산할 수 있습니다. 그런 다음 2단계에서 IA를 사용하여를 사용하여 위 레벨에서 흰색의 노드를 잘라냅니다(노드 A, B, C, D...,...). 이 노드 A, B, C, D, ...는 더 이상 탐색되지 않을 수 있습니다.더 이상 탐색할 수 없습니다.그러면 노드 A, B, C가 절단되지 않았다고 가정합니다,그림 4: 위치 A부터 N까지와 검은색 2는 검은색의 승리를 위한 영향력영역을 형성합니다.그림 5: 지역 컷오프 세부 정보3단계에서는 노드 B를 검색합니다.노드 B를 탐색한 결과 역시 흑의 승리인 경우, 단계 4단계가 진행되며, 여기서 새로운 영향력 지역 IB가를 다시 계산하여 2단계와 유사하게 나머지 노드를노드를 잘라냅니다. 더 이상 잘라낼 노드가 없는 경우,5단계가 수행되어 노드 C를 탐색합니다.노드 C의 점수도 1이고 새로운 노드의영향력은 IC라고 가정합니다. 이 레벨의 모든 노드가 체크되거나체크되거나 절단되면 노드 N의 점수는 1이 됩니다(검은색이 승리).그리고 영향력 영역은 IA, IB, IC의 합이 됩니다.이 상향식 프로세스는 상위 레벨로 더 전파될 수 있습니다.레벨로 전파될 수 있습니다.승리하는 솔루션을 찾는 과정에서솔루션을 찾는 과정에서 상대방의 모든 가능한 수를고려해야 합니다. 지역 컷오프 아이디어는 고려해야 할 방어 수를고려해야 할 방어 수를 크게 줄일 수 있지만,8×8 헥스 보드에서 승리하는 전략으로 이어지기에는 여전히 충분하지 않습니다.8×8 헥스 보드. 인간 헥스 전문가는제4회 퍼지 시스템 및 지식 발견에 관한 국제 컨퍼런스(FSKD 2007)0-7695-2874-0/07 $25.00 © 2007보드 상황을 논리적 통찰력으로 파악할 수 있습니다. 이러한 통찰력은 다음과 같습니다.특정 수를 두면 승리로 이어질 수 있음을 알려주고다른 수를 두면 승리가 불가능하다는 것을 알려줍니다. 기반이러한 이점을 바탕으로 Hex 전문가는 검색의 각 레벨에서 몇 가지수만 고려하면 됩니다. 가끔 실수를 할 수도 있지만실수를 할 수도 있지만, 대부분의 경우 이러한 통찰력은원하는 결과로 이어집니다.가능한 기보의 하위 집합을 검색하는 것을선택적 검색이라고 하며, 컴퓨터 게임 프로그램에서 널리 사용되는게임 프로그램. 이 접근 방식을 게임 해결에 적용하면휴리스틱이 완벽하지 않은 게임에서 이 접근법을 적용하면 솔루션을을 놓칠 수도 있습니다. 흥미로운 개념이 있습니다.대칭 속성이라는 흥미로운 개념이 있습니다.이기는 오프닝은 지는 오프닝을 드러낼 수 있습니다. 이아이디어는 이전 작업에서 7×7 헥스 보드에서 패배하는7×7 헥스 보드 [10]에서 잃어버린 개구부를 찾기 위해 적용되었습니다. 같은 아이디어가에서 승리 전략을 찾는 과정에서도 활용되었습니다.8×8 헥스 보드 [11]. 그림 6은 흑의 첫 번째 수를 보여줍니다.8×8 헥스에서 승리한 전략을 보여줍니다. 영역에 따라컷오프 알고리즘에 따르면, 그림 6에서 십자로 표시된 위치는그림 6에서 십자로 표시된 위치는 흑 1의 승리를 허용하지 않는 효과가 없습니다.게임에서 이길 수 없습니다. 대칭 속성으로 인해, 만약 흑의 첫 번째수가 그림 7에 표시된 위치 중 어느 곳에서든 놓인다면7에 표시된 위치에서 첫 수를 두면 백은 2에서 동일한 승리 전략을 사용하여승리할 수 있습니다.선택적 검색 시도는 이기는 전략이 없으면선택적 검색 시도는 현재 게임 상황에서 플레이어가 이길 수 있는플레이어가 이길 수 있는 전략을 찾을 수 없습니다. 대칭속성을 사용하여 이기는 수를 찾을 수 없는 이유를 결정할 수 있습니다.이기는 수를 찾을 수 없습니다. 이를 위해서는 대칭게임을 만들어야 하며, 원래 게임에서 블랙의에 대한 수를 대칭 게임의 테스트 수로 삼아야 합니다.대칭 게임. 그림 8은 그림 9에 표시된 대칭 게임의그림 9에 표시된 원래 게임의 대칭 게임을 보여줍니다.위치를 (x,y)에서 (y,x)로 변경하고 색상을 바꾼 대칭 게임입니다. 만약대칭 게임을 풀 수 있다면, 승자가 없을 것입니다.