Difference between revisions of "Equivalent patterns"

Latest revision as of 02:17, 9 May 2023

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.

Edge equivalence

Edges are equivalent to edge-connected rows of pieces on a larger board.

Example 0

Any position on an nxm board is equivalent to the same position on the interior (i.e. the cells non-adjacent to the edges) of an (n+2)x(m+2) board with the first rows next to each edge filled with friendly pieces and dead cells at the vertex cells (or equivalently either red or blue pieces at any of the vertex cells)

This allows the examples below to be applied at the edges: either formally, by converting to the larger board, applying the equivalence in the example, then converting back to the smaller board; or informally, by considering an edge to be a row of friendly pieces.

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.

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 for playing Hex, because it allows the player to disregard some pieces in the board, or prune the analysis tree. Some positions are much clearer than other equivalent positions. In the examples below, the simpler pattern is usually written on the right. One can make use of these equivalent patterns by mentally always replacing the left pattern with the right one.

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 example 1 twice.

Both above examples 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 that are adjacent to G but do not belong to it. In a given pattern P₁, suppose that G is a red chain, and that C is a cell in neigh(G), which may be empty or occupied by Blue. Let P₂ be the result of placing a red piece in C (removing a blue stone, if necessary). Therefore P₂ contains a chain G' containing G and C. If neigh(G')=neigh(G) then P₁ and P₂ are equivalent. Of course the dual argument also holds for blue chains.

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 Blue occupies one of them, Red can occupy the other capturing the former, then an equivalent position is obtained if both C₁ and C₂ are occupied by Red.

Equivalent pairs obtained with this 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, one should 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 2-move opening a1 + b1 (or either single move) for Red loses on a board 3x3 or bigger:

Example 5a (Opening a1+b1 loses)

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 4 twice (use of these examples at the edges is justified by Example 0 above). 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, 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 7

Using both rules together:

Example 8

Example 9

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

Here is a third (rather obvious) rule for equivalent patterns: Any area surrounded by a single chain of the opponent 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:

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.

Clearly, m2 has a virtual connection to the top, because the stone at f4 is a ladder escape. On the other hand, m2 is connected to the bottom exactly if Blue cannot connect k3 to the right, using j6 and maybe the group at h8-h9-f10 as a ladder escape. In fact, Blue cannot do this. This becomes much clearer when some patterns are locally replaced by other equivalent ones, yielding:

The changes are:

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

• The blue group from d8 to l11 is completely wrapped by a virtually connected group belonging to Red, except for a narrow section (typically, 2 cells). These kinds of groups are typically captured, for exactly the same reason as in Example 1.

• If Blue moves at i7, Red moves at i9 and vice versa. In both cases, the blue group h8-h9-f10 will be enclosed. So we can use the second rule for detecting equivalent patterns, capturing it.

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

• The equivalence in Example 4 can be used to add a stone for Red at m11.

• The area near the bottom of the board is now surrounded by a red chain and a blue chain. Therefore, the cells in this area are dead and can be filled with any color.

The blue stone at j6 remains, but is completely isolated and too close to the red group to be of any use in such a small region. Therefore, it is now 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.

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.

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:

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.

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

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