Equivalent patterns

2012-07-06T16:05:01Z

Tompo:

We say that two hex [[pattern]]s (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]].

<hex>R2 C7 Q1 Va2 Vb1 Vc1 Vc2 Hb2 Ve2 Vf1 Vg1 Vg2 Vf2 Sa1 Sd1 Sd2 Se1</hex>

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 ==
<hex>R3 C9 Va2 Vb1 Vc1 Vd1 Vd2 Vc3 Hb2 Hc2 Vf2 Vg1 Vh1 Vi1 Vi2 Vh3 Vg2 Vh2 Sa1 Sa3 Sb3 Sd3 Se3 Sf3 Sg3 Si3 Se1 Sf1 Se2</hex>

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 ==
<hex>R3 C6 Va2 Vb1 Vc1 Hb2 Hb3 Vd2 Ve1 Vf1 Ve2 He3 Sa1 Sa3 Sc2 Sc3 Sd1 Sd3 Sf2 Sf3</hex>

== Example 4 ==
<hex>R3 C6 Ha3 Hb3 Vb1 Vc1 Hb2 Hd3 He3 Ve1 Vf1 Ve2 Sa1 Sa2 Sc2 Sc3 Sd1 Sd2 Sf2 Sf3</hex>

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 ==
<hex>R3 C7 Va1 Vb1 Vc1 Va3 Ve1 Vf1 Vg1 Ve3 Ve2 Vf2 Sc2 Sd2 Sb3 Sc3 Sd3 Sf3 Sg2 Sg3 Sd1</hex>

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) ==

<hex>R5 C9 1:*VVV**VVV 2:HVV_*BBB_ 3:H_H_*HHH_ 4:H___*HH__ 5:H****H***</hex>

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 ==
<hex>R3 C5 Va3 Va1 Vb1 Vb3 Ve1 Vd1 Vd2 Vd3 Ve2 Ve3 Sc2 Sc3 Sc1</hex>

== Example 7 ==
<hex>R2 C9 Va2 Vb1 Vc1 Vd1 Vd2 Sa1 Se1 Se2 Sf1 Vf2 Vg1 Vg2 Vh1 Vh2 Vi1 Vi2</hex>

Using both rules together:

== Example 8 ==
<hex>R3 C9 Vc1 Vb3 Ha2 Hd2 Vh1 Vg3 Vg2 Vh2 Hf2 Hi2 Sa1 Sb1 Sd1 Se1 Sf1 Sg1 Si1 Se2 Sa3 Sc3 Sd3 Se3 Sf3 Sh3 Si3</hex>

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

<hex>R3 C11 Va3 Vb3 Vc3 Vd3 Ve3 Vc1 Vd1 Ve1 Hc2 Hd2 Vg3 Vh2 Vh3 Vi1 Vi2 Vi3 Vj1 Vj2 Vj3 Vk1 Vk2 Vk3 Sa1 Sa2 Sb1 Sf1 Sf2 Sf3 Sg1 Sg2 Sh1</hex>

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 [http://www.littlegolem.net/jsp/game/game.jsp?gid=206040&nmove=55 #206040] at [[Little Golem]], the situation after 55. m2 is shown in the board below.

<hex>R13 C13 Q1 Hc1 Hd6 Hd8 Hd9 Hd10 Hd11 Hd12 He6 He12 Hf5 Hf10 Hf12 Hg5 Hg6 Hg12 Hh6 Hh8 Hh9 Hh12 Hi5 Hi11 Hj4 Hj6 Hj11 Hk3 Hk11 Hl11 Vc8 Vc9 Vc10 Vc11 Vc12 Vd7 Ve7 Ve8 Ve10 Ve11 Vf4 Vf6 Vf8 Vf11 Vg11 Vh5 Vh7 Vh11 Vi6 Vi8 Vi10 Vj5 Vj10 Vk4 Vk10 Vl10 Vm2</hex>

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:

<hex>R13 C13 Q1 Hc1 Hd6 Vd8 Vd9 Vd10 Vd11 Vd12 He6 Ve12 Hf5 Vf10 Vf12 Hg5 Hg6 Vg12 Hh6 Vh8 Vh9 Vh12 Hi5 Vi11 Hj4 Hj6 Vj11 Hk3 Vk11 Vl11 Vc8 Vc9 Vc10 Vc11 Vc12 Vd7 Ve7 Ve8 Ve10 Ve11 Vf4 Hf6 Vf8 Vf11 Vg11 Hh5 Vh7 Vh11 Vi6 Vi8 Vi10 Vj5 Vj10 Vk4 Vk10 Vl10 Vm2 Ve9 Vf7 Vf9 Vg7 Vg8 Vg9 Vg10 Vh10 Vi7 Vi9 Vb13 Vc13 Vm10 Vm11 Vi12 Vj12 Vk12 Vl12 Vm12 Vd13 Ve13 Vf13 Vg13 Vh13 Vi13 Vj13 Vk13 Vl13 Vm13</hex>

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.

[[Category: Strategy]]
[[Category: Computer Hex]]
[[Category: Theory]]

HexWiki - User contributions [en]

Equivalent patterns