Equivalent patterns

From HexWiki
Revision as of 16:05, 6 July 2012 by Tompo (Talk | contribs)

Jump to: navigation, search

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.

abcdefg12

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 you to disregard some pieces in the board, or prune the analysis tree. In my opinion, some patterns lead to positions that are 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 P1, 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 P2 be the pattern that results when A occupies C (removing an opponent stone, if necessary), therefore P2 contains a chain G' containing G and C. If neigh(G')=neigh(G) then P1 and P2 are equivalent.

This rule justifies the following equivalent pairs:

Example 3

Example 4

Another rule producing equivalent patterns: If there are two empty cells C1 and C2 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 C1 and C2 are occupied by A.

Equivalent pairs obtained with such rule:

Example 5

This is a very instructive pattern because it shows that playing 2 rows out from a friendly edge with 2 free cells on the first row below the play is equivalent to playing at all three cells simultaneously, and hence at least as good as playing at either cell on the first row. So as a rule, never play on the first row in such a situation. We can see this by viewing the 3 upper red stones as part of a friendly edge.

This pattern, along with Example 4 can be used to show that the two move start A1 + B1 (or either single move) for vertical loses on a board 3x3 or bigger:

Example 5b (Opening A1+B1 loses)

So, in response to A1+B1 by vertical, horizontal can play at B2, reaching a position equivalent to just horizontal stones at A1, A2, A3, B1 & B2. This includes the cells A1 & A2, so the original position is lost for vertical by a strategy stealing argument.

In fact, making the opening play B2 is equivalent to playing 5 stones at A1, A2, B1, B2 & C1, however this is known to produce a losing position on boards of size 4, 7 & 8 (see small boards).

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.

abcdefghijklm12345678910111213

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:

abcdefghijklm12345678910111213

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.