Difference between revisions of "Equivalent patterns"

Revision as of 15:14, 31 January 2008

We say that two hex patterns (subsets of a board) are equivalent patterns if, when one of them occurs embedded in any hex board, it could be replaced by the other and the side who has winning strategy does not change.

Example 1

For example (using '*' for holes), the two patterns below are equivalent, and an example of what is known as the Useless triangle.

If Vertical was the last to move in the left pattern, he has captured the opponent stone in b2, an both players should regard it as another stone of Vertical.

The knowledge of equivalent patterns turns out to be very useful to play Hex, because it allows to disregard some pieces in the board, or prunes the analysis tree. In my opinion, some patterns lead to positions much more clear than other equivalent patterns. My intention here is to write always in second place such pattens, and the use that I make of equivalent patterns is that in my games, mentally I always replace the first patterns by the equivalent counterparts.

Here are several examples of pairs of equivalent positions, and a short explanation on the way to prove them so.

Example 2

The equivalence is obtained by applying two times the example 1.

Both examples before are instances of the following rule to produce equivalence pairs. Given a chain G, let the neighborhood of G, neigh(G), be the set of cells next to one of those in G but not belonging to it. In a given pattern P₁, suppose that G is a chain owned by the player A, and that C is a cell in neigh(G) such that any cell of A next to C belongs to G. Let P₂ be the pattern that results when A occupies C (removing an opponent stone, if necessary), therefore P₂ contains a chain G' containing G and C. If neigh(G')=neigh(G) then P₁ and P₂ are equivalent.

This rule justifies the following equivalent pairs:

Example 3

Example 4

Another rule producing equivalent patterns: If there are two empty cells C₁ and C₂ in a pattern, such that if the opponent of the player A occupies one of them, A can occupy the other capturing the latter, then an equivalent position is obtained if both C₁ and C₂ are occupied by A.

Equivalent pairs obtained with such rule:

Example 5

Example 6

Example 7

Using both rules together:

Example 8

Example 9

(generalization of the Example 5, for any horizontal length)

Third rule for equivalent patterns (rather obvious) rule: Any area surrounded by a single chain of each enemy may be randomly filled. This happens because the outcome of the game does not depend on it at all.

Practical example

Let us see a practical example. In game #206040 at Little Golem, the situation after 55. m2 is shown in the board below.

Clearly, m2 is strongly connected to the top, because the stone in f4 is a ladder escape. On the other hand, it is strongly connected to the bottom exactly if blue cannot connect k3 with the right, using j6 and maybe the group in h8-h9-f10 as a ladder escape. In fact he cannot do it, and it is much clearer if some patterns are locally replaced by other equivalent ones, rendering:

The changes have been:

• f6 and h5 swap color, as in Example 1.

• The horizontal group from d8 to l11 is completely wrapped by a strongly connected group belonging to the opponent, except for a narrow section (typically, 2 cells). This kind of groups typically are captured, exactly in the same reason as in Example 1.

• If blue moves to i7, red moves to i9 and conversely, in both cases enclosing the blue group h8-h9-f10 as before. So, we can use the second rule for detecting equivalent patterns, capturing it.

• The equivalence in Example 5 can be used for the stone in c12.

• The equivalence in Example 4 can be used, adding a stone for vertical at m11.

• The area in the bottom of the board is now surrounded by a red chain and a blue chain. Therefore, it may be filled as we please.

The blue stone in j6 remained, completely alone and too near to the red group to be of any use in such a small region, so it is obvious that vertical has won.