Difference between revisions of "Equivalent patterns"
m (→Example 5a (Opening a1+b1 loses): Typo) |
(Some copy-editing.) |
||
(3 intermediate revisions by one other user not shown) | |||
Line 65: | Line 65: | ||
The equivalence is obtained by applying example 1 twice. | 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<sub>1</sub>, 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<sub>2</sub> be the result of placing a red piece in C (removing a | + | 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<sub>1</sub>, 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<sub>2</sub> be the result of placing a red piece in C (removing a blue stone, if necessary). Therefore P<sub>2</sub> contains a chain G' containing G and C. If neigh(G')=neigh(G) then P<sub>1</sub> and P<sub>2</sub> are equivalent. Of course the dual argument also holds for blue chains. |
This rule justifies the following equivalent pairs: | This rule justifies the following equivalent pairs: | ||
Line 235: | Line 235: | ||
<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> | <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 | + | 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: |
<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> | <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 | + | The changes are: |
− | * f6 and h5 swap | + | * f6 and h5 swap colors, as in Example 1. |
− | * The blue group from d8 to l11 is completely wrapped by a | + | * 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 | + | * 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 | + | * The equivalence in Example 5 can be used for the stone at c12. |
− | * The equivalence in Example 4 can be used | + | * The equivalence in Example 4 can be used to add a stone for Red at m11. |
− | * The area | + | * 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 cell|dead]] and can be filled with any color. |
− | The blue stone | + | 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 === | === Second example game === | ||
Line 288: | Line 288: | ||
R 11:h9 B 12:g9 R 13:h7" | R 11:h9 B 12:g9 R 13:h7" | ||
/> | /> | ||
− | This time, | + | 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. |
[[Category: Strategy]] | [[Category: Strategy]] | ||
[[Category: Computer Hex]] | [[Category: Computer Hex]] | ||
[[Category: Theory]] | [[Category: Theory]] |
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.
Contents
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)
andThis 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.
andThe 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
andThe 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 P1, 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 P2 be the result of placing a red piece in C (removing a blue stone, if necessary). Therefore P2 contains a chain G' containing G and C. If neigh(G')=neigh(G) then P1 and P2 are equivalent. Of course the dual argument also holds for blue chains.
This rule justifies the following equivalent pairs:
Example 3
andExample 4
andAnother rule producing equivalent patterns: If there are two empty cells C1 and C2 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 C1 and C2 are occupied by Red.
Equivalent pairs obtained with this rule:
Example 5
andThis 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)
andIn 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
andExample 7
andUsing both rules together:
Example 8
andExample 9
(generalization of the Example 5, for any horizontal length)
andHere 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:
andThis 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.