Difference between revisions of "Equivalent patterns"

From HexWiki
Jump to: navigation, search
(Converted more diagrams.)
(Converted remaining diagrams.)
Line 104: Line 104:
 
=== Example 5b (Opening A1+B1 loses) ===
 
=== 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>
+
<hexboard size="4x3"
 +
  float="inline"
 +
  coords="top left"
 +
  edges="top left"
 +
  contents="R a1 b1 B b2"
 +
  /> and <hexboard size="4x3"
 +
  float="inline"
 +
  coords="top left"
 +
  edges="top left"
 +
  contents="B a1 b1 B b2 a2 a3"
 +
  />
  
So, in response to A1+B1 by Red, Blue can play at B2, reaching a position equivalent to just blue stones at A1, A2, A3, B1 & B2. This includes the cells A1 & A2, so the original position is lost for Red by a strategy stealing argument.
+
So, in response to a1+b1 by Red, Blue can play at b2. This captures a2 and a3 by Example 5, and then a1 and b1 by applying Example 1 twice. Thus, the left position is equivalent to the right one. This includes the cells a1 and a2, so the original position is losing for Red 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]]).
+
In fact, making the opening play b2 is equivalent to playing 5 stones at a1, a2, b1, b1, and c1. However this is known to produce a losing position on boards of size 4, 7 & 8 (see [[small boards]]).
 +
 
 +
This example also shows that the opening moves a1 and b1 should never be swapped. Playing at b2 is always at least as good for Blue as swapping (but there are even better moves for Blue available elsewhere on the board).
  
 
=== Example 6 ===
 
=== Example 6 ===
<hex>R3 C5 Va3 Va1 Vb1 Vb3 Ve1 Vd1 Vd2 Vd3 Ve2 Ve3 Sc2 Sc3 Sc1</hex>
+
<hexboard size="3x2"
 +
  float="inline"
 +
  coords="none"
 +
  edges="none"
 +
  contents="R a1 a3 b1 b3"
 +
  /> and <hexboard size="3x2"
 +
  float="inline"
 +
  coords="none"
 +
  edges="none"
 +
  contents="R a1 a2 a3 b1 b2 b3"
 +
  />
  
 
=== Example 7 ===
 
=== Example 7 ===
<hex>R2 C9 Va2 Vb1 Vc1 Vd1 Vd2 Sa1 Se1 Se2 Sf1 Vf2 Vg1 Vg2 Vh1 Vh2 Vi1 Vi2</hex>
+
<hexboard size="2x4"
 
+
  float="inline"
 +
  coords="none"
 +
  edges="none"
 +
  visible="-a1"
 +
  contents="R a2--b1--d1--d2"
 +
  /> and <hexboard size="2x4"
 +
  float="inline"
 +
  coords="none"
 +
  edges="none"
 +
  visible="-a1"
 +
  contents="R all"
 +
  />
 
Using both rules together:
 
Using both rules together:
  
 
=== Example 8 ===
 
=== 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>
+
<hexboard size="3x4"
 +
  float="inline"
 +
  coords="none"
 +
  edges="none"
 +
  visible="area(a2,b3,d2,c1)"
 +
  contents="R c1 b3 B a2 d2"
 +
  /> and <hexboard size="3x4"
 +
  float="inline"
 +
  coords="none"
 +
  edges="none"
 +
  visible="area(a2,b3,d2,c1)"
 +
  contents="R c1 b3 B a2 d2 R b2 c2"
 +
  />
  
 
=== Example 9 ===
 
=== Example 9 ===
 
''(generalization of the Example 5, for any horizontal length)''
 
''(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>
+
<hexboard size="3x5"
 +
  float="inline"
 +
  coords="none"
 +
  edges="none"
 +
  visible="area(a3,e3,e1,c1)"
 +
  contents="R a3--e3 c1--e1 B c2 d2"
 +
  /> and <hexboard size="3x5"
 +
  float="inline"
 +
  coords="none"
 +
  edges="none"
 +
  visible="area(a3,e3,e1,c1)"
 +
  contents="R all"
 +
  />
  
 
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.
 
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.
Line 135: Line 192:
  
 
The following two patterns are equivalent:
 
The following two patterns are equivalent:
<hexboard size="3x9"
+
<hexboard size="3x4"
  coords="hide"
+
  float="inline"
  contents="E *:e1 *:e2 *:e3
+
  coords="none"
  E *:a1 *:a2 *:b3 *:c3 *:d3 R b1 c1 d1 d2 B a3 B b2 E a:c2
+
  edges="none"
  E *:f1 *:f2 *:g3 *:h3 *:i3 R g1 h1 i1 i2 B f3 B h2 E a:g2"
+
  visible="-a1 a2 b3--d3"
  />
+
  contents="R b1--d1 d2 B a3 c2 E a:b2"
This is easily seen by noticing that if the cells marked "a" are both blue, the patterns become equal, whereas if the cells marked "a" are both red, then the blue piece next to each of them is dead and therefore the patterns become equivalent. So whenever one player's strategy calls for playing in the cell marked "a" in one of these two patterns, the same player can play in the cell marked "a" in the other pattern.
+
  /> and <hexboard size="3x4"
 +
  float="inline"
 +
  coords="none"
 +
  edges="none"
 +
  visible="-a1 a2 b3--d3"
 +
  contents="R b1--d1 d2 B a3 b2 E a:c2"
 +
  />
 +
This is easily seen by noticing that if the cells marked "a" are both blue, the patterns become equal, whereas if the cells marked "a" are both red, then the blue piece next to each of them may as well be red by Examples 1 and 3, respectively, so the patterns are equivalent. So whenever one player's strategy calls for playing in the cell marked "a" in one of these two patterns, the same player can play in the cell marked "a" in the other pattern.
  
 
== Practical examples ==
 
== Practical examples ==

Revision as of 02:30, 8 December 2020

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.

Equivalence by capture

Cells that are captured by one player can be filled in with stones of that player's color.

Example 1

For example, the two patterns below are equivalent, and an example of what is known as the useless triangle.

and

The blue stone in the left pattern is captured by Red. Therefore, the position is equivalent to one where this stone is actually red.

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

and

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

and

Example 4

and

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

and

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 Red loses on a board 3x3 or bigger:

Example 5b (Opening A1+B1 loses)

abc1234
and
abc1234

So, in response to a1+b1 by Red, Blue can play at b2. This captures a2 and a3 by Example 5, and then a1 and b1 by applying Example 1 twice. Thus, the left position is equivalent to the right one. This includes the cells a1 and a2, so the original position is losing for Red by a strategy stealing argument.

In fact, making the opening play b2 is equivalent to playing 5 stones at a1, a2, b1, b1, and c1. However this is known to produce a losing position on boards of size 4, 7 & 8 (see small boards).

This example also shows that the opening moves a1 and b1 should never be swapped. Playing at b2 is always at least as good for Blue as swapping (but there are even better moves for Blue available elsewhere on the board).

Example 6

and

Example 7

and

Using both rules together:

Example 8

and

Example 9

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

and

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.

Equivalence for reasons other than capture

Capture is not the only way in which equivalent patterns arise. The following is an example of this.

Example 10

The following two patterns are equivalent:

a
and
a

This is easily seen by noticing that if the cells marked "a" are both blue, the patterns become equal, whereas if the cells marked "a" are both red, then the blue piece next to each of them may as well be red by Examples 1 and 3, respectively, so the patterns are equivalent. So whenever one player's strategy calls for playing in the cell marked "a" in one of these two patterns, the same player can play in the cell marked "a" in the other pattern.

Practical examples

First example game

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 blue 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 Red 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 Red has won.

Second example game

In the following game, Red's c9 is connected to the top edge via edge template V-2a. A 3rd row ladder is about to form along the bottom edge. Red wonders whether his other stones are enough to escape the ladder.

abcdefghijk1234567891011

The analysis of this position seems complicated at first. It can be simplified by using the equivalence in Example 10 to shift the blue stone from f6 to e6.

abcdefghijk1234567891011

The key observation is that the single stone i6 on the 6th row is enough for a 3rd-to-6th row switchback (see B6 switchback) or even for a 3rd-to-5th row switchback (see C6 switchback). The resulting ladder is then escaped by g6 via interior ziggurat. Specifically, if Red pushes the ladder all the way to g9, the red stone at g6 will be connected to this ladder by an interior ziggurat:

abcdefghijk123456789101113572468

Now Red can play the 3rd-to-6th row switchback by breaking the ladder and playing one more piece. Note how i6 becomes the ladder stone for a 3rd row ladder in the opposite direction, which the ziggurat escapes. Therefore, Red is connected.

abcdefghijk123456789101111109

One may wonder whether it would have helped Blue to yield to a 2nd row ladder. This would not have helped here. For example:

abcdefghijk123456789101113135121124710986

This time, Black's 13 acts as a ladder stone for a 2nd row ladder stone in the opposite direction, which the ziggurat again escapes.