Difference between revisions of "Theorems about templates"

From HexWiki
Jump to: navigation, search
(Re-numbered the theorems.)
(fixed typo)
 
(5 intermediate revisions by one other user not shown)
Line 206: Line 206:
 
=== Corner bending ===
 
=== Corner bending ===
  
The idea of corner bending is similar to that of corner clipping. We again start with an observation about two positions. This time, we claim that B is at least at good for Red as A.
+
The idea of corner bending is similar to that of corner clipping. We again start with an observation about two positions. This time, we claim that B is at least as good for Red as A.
 
A: <hexboard size="2x2"
 
A: <hexboard size="2x2"
 
   float="inline"
 
   float="inline"
Line 361: Line 361:
 
=== Alternative connection up ===
 
=== Alternative connection up ===
  
Some templates, such as [[Tom's move]], have an "alternative connection up". There is a general theorem about this. We begin by observing that B is at least at good for Red as A:
+
Some templates, such as [[Tom's move]], have an "alternative connection up". There is a general theorem about this. We begin by observing that from Red's point of view, C is at least as good as B, and B is at least as good as A:
  
 
A: <hexboard size="3x4"
 
A: <hexboard size="3x4"
Line 368: Line 368:
 
   coords="none"
 
   coords="none"
 
   visible="area(a2,b3,d1,c1)"
 
   visible="area(a2,b3,d1,c1)"
   contents="R c1 b2 b3 B a2 d1 E w:c2"
+
   contents="R c1 b2 b3 B a2 d1 E c2"
 
   /> B: <hexboard size="4x4"
 
   /> B: <hexboard size="4x4"
 +
  float="inline"
 +
  edges="none"
 +
  coords="none"
 +
  visible="area(a2,b3,d1,c1)"
 +
  contents="R c1 b3 B a2 R b2 B w:c2 E z:d1"
 +
  /> C: <hexboard size="4x4"
 
   float="inline"
 
   float="inline"
 
   edges="none"
 
   edges="none"
Line 377: Line 383:
 
   />
 
   />
  
Indeed, if Red is first to play in the region, then Red plays z in B, which captures the whole region and is therefore at least as good as anything Red could do in A. Now suppose Blue plays first. If Blue plays x or z in B, Red responds with y, [[dead cell|killing]] x and leaving B at least as good for Red as A with no moves played. If Blue plays y, Red responds at x. We claim that B with these two moves played is still at least as good for Red as A with no moves played. Indeed, if Blue plays next, A and B become identical, and if Red plays next, Red z captures the whole region and is therefore at least as good as anything Red could do in A.
+
To see that B is at least as good for Red as A, note that if Red plays first in the region, then Red plays z in B, which [[dead cell|kills]] w and is at least as good as anything Red could do in A. If Blue plays first in the region, A and B become identical. To see that C is at least as good for Red as B, note that Red can get at least one of x and y by defending the [[bridge]]. No matter which way the bridge goes, the result is identical or better for Red than B.
  
 
'''Theorem 5 (alternative connection up).''' Suppose some (edge or interior) template has a piece of boundary of the form
 
'''Theorem 5 (alternative connection up).''' Suppose some (edge or interior) template has a piece of boundary of the form
<hexboard size="4x4"
+
 
 +
A: <hexboard size="4x4"
 
   float="inline"
 
   float="inline"
 
   edges="none"
 
   edges="none"
Line 387: Line 394:
 
   contents="S blue:all none:b4,c3 R arrow(12):b4"
 
   contents="S blue:all none:b4,c3 R arrow(12):b4"
 
   />
 
   />
Here, as usual, the blue-shaded cells are not part of the template, but the stone marked "↑" must of course be connected up. Then the pattern where this area has been replaced by
+
 
<hexboard size="4x4"
+
Here, as usual, the blue-shaded cells are not part of the template, but the stone marked "↑" must of course be connected up. Then the patterns where this area has been replaced by
 +
 
 +
B: <hexboard size="4x4"
 +
  float="inline"
 +
  edges="none"
 +
  coords="none"
 +
  visible="area(a3,b4,d2,d1,c1)"
 +
  contents="S blue:all none:b4,c3,b3,d2,c2 R b4 arrow(12):c2 R b3 B c3"
 +
  /> or C: <hexboard size="4x4"
 
   float="inline"
 
   float="inline"
 
   edges="none"
 
   edges="none"
Line 395: Line 410:
 
   contents="S blue:all none:b4,c3,b3,d2,c2 R b4 arrow(12):c2"
 
   contents="S blue:all none:b4,c3,b3,d2,c2 R b4 arrow(12):c2"
 
   />
 
   />
is also connected. (It may fail to be a template only because it may fail to be minimal).
 
  
'''Proof.''' Since the shaded hexes are outside the carrier, they may as well be blue stones, except that we need to connect the stone marked "↑" to something, which we can without loss of generality do like this:
+
are also connected. (They may fail to be templates only because they may fail to be minimal).
 +
 
 +
'''Proof.''' Consider the template containing A. Since the shaded hexes are outside the carrier, they may as well be blue stones, except that we need to connect the stone marked "↑" to something, which we can without loss of generality do like this:
 
<hexboard size="4x4"
 
<hexboard size="4x4"
 
   float="inline"
 
   float="inline"
Line 405: Line 421:
 
   contents="B a3 b2 d1 d2 R a:b4 b:b3 c:c2 arrow(12):c1"
 
   contents="B a3 b2 d1 d2 R a:b4 b:b3 c:c2 arrow(12):c1"
 
   />
 
   />
The fact that the stones "b" and "c" are potentially next to cells in the template does not matter, because "a" neighbors those cells anyway. Due to the above observation, the following is at least at good for Red, and therefore also connected:
+
The fact that the stones "b" and "c" are adjacent to cells in the template does not matter, because "a" is adjacent to the same cells anyway. By the above observation, each of the following is at least as good for Red, and therefore also connected:
 
<hexboard size="4x4"
 
<hexboard size="4x4"
 +
  float="inline"
 +
  edges="none"
 +
  coords="none"
 +
  visible="area(a3,b4,d2,d1,c1)"
 +
  contents="B a3 b2 d1 R b4 c2 arrow(12):c1 R b3 B c3"
 +
  /> and <hexboard size="4x4"
 
   float="inline"
 
   float="inline"
 
   edges="none"
 
   edges="none"
Line 413: Line 435:
 
   contents="B a3 b2 d1 R b4 c2 arrow(12):c1"
 
   contents="B a3 b2 d1 R b4 c2 arrow(12):c1"
 
   />
 
   />
This proves the theorem. □
+
Therefore, the patterns using B and C are connected, proving the theorem. □
  
 
'''Example'''  
 
'''Example'''  
Line 424: Line 446:
 
   contents="R arrow(12):b2 a3 a4 B b3"
 
   contents="R arrow(12):b2 a3 a4 B b3"
 
   />
 
   />
By Theorem 5, the following is therefore also connected:
+
By Theorem 5, the following are therefore also connected:
 
<hexboard size="6x8"
 
<hexboard size="6x8"
 +
  float="inline"
 +
  edges="bottom"
 +
  coords="none"
 +
  visible="-g2 h2 h3 f1--h1 -area(a1,a6,c1)"
 +
  contents="R b4 b5 c3 B a6 c4 R arrow(12):d1 R c2 B d2"
 +
  /> and  <hexboard size="6x8"
 +
  float="inline"
 
   edges="bottom"
 
   edges="bottom"
 
   coords="none"
 
   coords="none"

Latest revision as of 05:51, 21 April 2024

There are a number of theorems about templates, some of which can be useful in play. Some of these theorems concern how to construct new templates from existing ones. Others concern how to play when templates overlap. Others explain why templates tend to have particular shapes.

New templates from old

When we have theorems that allow us to construct new templates from known ones, there are fewer templates to memorize.

Corner clipping

We begin by observing that the following two positions are strategically equivalent:

A:
xyz
B:
w

Indeed, if Red plays first in the region, then x captures the entire triangle (x,y,z) in A, and w captures the corresponding triangle in B. Therefore, under optimal play, Red achieves exactly the same thing in A as in B. Similarly, if Blue plays first in the region, y captures the whole triangle in A and w kills the red stone and therefore captures the whole triangle in B. Therefore, under optimal play, Blue achieves the same thing in A as in B. It follows that A and B are equivalent.

Then we have the following theorem about edge templates:

Theorem 1 (corner clipping). Suppose an edge template has a corner of the form

A:

Here, the blue-shaded cells must not be part of the template, i.e., they must be outside of its carrier. Then the pattern where this corner has been replaced by

B:

is also an edge template. The converse is also true, i.e., if some template has a corner of shape B, the corresponding pattern with shape A is also a template.

Proof. Since the shaded hexes are outside the carrier, they may as well be blue stones. Then by the above observation, A and B are completely equivalent, so if some pattern containing A is connected, then so is the corresponding pattern containing B. Moreover, it is easy to see that if removing one cell from the carrier of A would yield a connected shape, then the same could be achieved by removing one cell or the red stone from B, and vice versa. Therefore, the template containing A is minimal if and only if the template containing B is minimal. □

Examples

Corner clipping shows that the ziggurat is equivalent to edge templates III2b and III2g, as well as a very compact 3-stone template:

Edge template IV2a:

Remark. For the clipped corner theorem to hold, the corner must be of this shape

and not merely that one:

In other words, the cell on the 3rd row should not be part of the carrier. However, if the corner is merely of the latter form, the clipped template is still valid. It may not be minimal. For example, consider edge template IV2b:

Clipping the right corner is no problem. If we clip the left corner, the resulting pattern is connected, but not minimal:

The three hexes marked "*" could be removed from the carrier while still remaining connected.

Large corner clipping

Observe that the following positions are equivalent:

A:
B:

Indeed, if Red moves in the region, A and B become identical. If Blue moves in the region, Blue kills Red's stone, so again A and B also become identical.

Then we have the following theorem about edge templates:

Theorem 2 (large corner clipping). Suppose an edge template has a corner of the form

A:

Here, the blue-shaded cells must not be part of the template, i.e., they must be outside of its carrier. Then the pattern where this corner has been replaced by

B:

is also an edge template. The converse is also true, i.e., if some template has a corner of shape B, the corresponding pattern with shape A is also a template.

Proof. By ordinary corner clipping, A is equivalent to

which is in turns equivalent to B by the above observation. □

Examples

Large corner clipping shows that the ziggurat is equivalent to edge template III2a:

Similarly, we can construct several new templates from edge template IV2a:

There are of course additional possibilities, such as clipping both corners, combining large and ordinary corner clipping, etc.

Corner bending

The idea of corner bending is similar to that of corner clipping. We again start with an observation about two positions. This time, we claim that B is at least as good for Red as A.

A:
x
B:
y

Indeed, if Red plays first in B, then y kills the blue stone and therefore captures the whole region, which is certainly at least as good as anything that Red could achieve in A. On the other hand, if Blue plays first in A, then Blue occupies the whole region, which is certainly at least as bad for Red as anything Blue could achieve in B. Therefore, if any position containing A is winning for Red, then so is the corresponding position containing B.

We obtain the following theorem:

Theorem 3 (corner bending). Suppose an edge template has a corner of the form

A:
x

Here, the blue-shaded cell must not be part of the template, i.e., it must be outside of its carrier. Then the pattern where this corner has been replaced by

B:
y

is still connected. (It may fail to be an edge template only because it may fail to be minimal).

Proof. Since the shaded hexes are outside the carrier, they may as well be blue stones. Then by the above observation, B is at least as good for Red as A, so if some region containing A is connected for Red, then so is the same region containing B. □

Examples

The following is a ziggurat, followed by ziggurats with one or two bent corners.

Crescenting

We begin by observing that the following three positions are strategically equivalent:

A:
xyzw
B:
xyzw
C:
xyzw

Indeed, A and B are equivalent because x, y, and w are dead, and B and C are equivalent because z and w are captured. We then have the following theorem about templates:

Theorem 4 (crescenting). Suppose some (edge or interior) template has a piece of boundary of the form

Here, as usual, the blue-shaded cells are not part of the template. Then the pattern where this area has been replaced by

is also a template. Moreover, the converse also holds. (Caveat: the construction preserves minimality with respect to empty cells in the carrier. In some boundary cases, it is possible that some of the red stones are not actually necessary in one or the other template).

Proof. Since the shaded hexes are outside the carrier, they may as well be blue stones. Then the equivalence follows by the above observation. □

Examples

Many templates with two adjacent stones have crescented versions. Indeed, the crescent itself is such a template:

Here is a crescented version of edge template IV2a. Note that crescenting can also be applied recursively, resulting in templates that resemble a long crescent.

Often, the crescent-like shape can be more generally replaced with any capped flank. See also edge templates from capped flanks.

Alternative connection up

Some templates, such as Tom's move, have an "alternative connection up". There is a general theorem about this. We begin by observing that from Red's point of view, C is at least as good as B, and B is at least as good as A:

A:
B:
zw
C:
zxy

To see that B is at least as good for Red as A, note that if Red plays first in the region, then Red plays z in B, which kills w and is at least as good as anything Red could do in A. If Blue plays first in the region, A and B become identical. To see that C is at least as good for Red as B, note that Red can get at least one of x and y by defending the bridge. No matter which way the bridge goes, the result is identical or better for Red than B.

Theorem 5 (alternative connection up). Suppose some (edge or interior) template has a piece of boundary of the form

A:

Here, as usual, the blue-shaded cells are not part of the template, but the stone marked "↑" must of course be connected up. Then the patterns where this area has been replaced by

B:
or C:

are also connected. (They may fail to be templates only because they may fail to be minimal).

Proof. Consider the template containing A. Since the shaded hexes are outside the carrier, they may as well be blue stones, except that we need to connect the stone marked "↑" to something, which we can without loss of generality do like this:

cba

The fact that the stones "b" and "c" are adjacent to cells in the template does not matter, because "a" is adjacent to the same cells anyway. By the above observation, each of the following is at least as good for Red, and therefore also connected:

and

Therefore, the patterns using B and C are connected, proving the theorem. □

Example

Tom's move ensures that the following is connected:

By Theorem 5, the following are therefore also connected:

and

This is exactly the "alternative connection up" of Tom's move.

Ladder creation templates from templates

By an argument similar to the first observation above, we observe that the following three positions are strategically equivalent:

A:
xyz
B:
w
C:
xyz

Indeed, whoever plays first in each region captures the entire region: Red by playing at x or w, and Blue by playing at y or w.

An interesting application of this is getting a 2nd row ladder creation template from an ordinary template.

Theorem 6 (ladder creation template from template). Suppose an edge template has a corner of the form

A:

where as usual, the blue-shaded cells are not part of the template. Then the pattern where this corner has been replaced by either one of

B:
C:

is a 2nd row ladder creation template. The converse is also true, i.e., if some pattern with a corner of shape B or C is a 2nd row ladder creation template, then the corresponding pattern with shape A is an edge template.

Proof. For the equivalence of A and B, note that by the above observation, A is connected if and only if B' is connected:

B':

By essentially Theorem 1 of the article on the theory of ladder escapes, B' is connected if and only if B creates a 2nd row ladder. Finally, since it is an "if and only if", it follows that if A is minimal, so is B, and vice versa. The argument for the equivalence of A and C is analogous. □

Example

From the ziggurat, we get the following ladder creation templates:

What we learn from this is that a Blue intrusion into the very corner of Red's template, or the cell right next to the corner, is not usually a good idea. Red can reconnect by creating a 2nd row ladder escape, potentially far away. This will often allow Red to play a minimaxing response. In particular, if Red already has a 2nd row ladder escape, the intrusion is not even valid (it does not even threaten to disconnect Red).

It is worth remarking that if the edge template's corner is merely of this shape,

then the left-to-right direction of Theorem 6 is still valid: Given an edge template, we still obtain a ladder creation template in two different ways. However, in this case, the latter may not be minimal.

Overlapping templates

When templates overlap, they are usually not both valid. However, there are some exceptions where templates can overlap and still be valid. It is useful to know them.

Edge template II in the overlap

Theorem 7. If the region in which two edge templates overlap is edge template II, then both templates remain valid.

Proof. The two empty hexes in edge template II are captured, and therefore they can be replaced by red stones without changing the strategic value.

Overlapping templates are only invalid if there are empty cells in the overlap. □

Example

+
=

Both templates remain valid, i.e., all three red stones can be connected to the edge simultaneously.

The ziggurat theorem

The following theorem is due to Eric Demer.

Theorem 8 (ziggurat theorem). Consider a ziggurat.

1zxy

If the ziggurat overlaps another edge template in the cell x, and/or overlaps another edge template in the cell y, all templates (i.e., the ziggurat itself and its neighboring templates) remain valid. If Blue plays in the overlap at x or y, Red can restore all templates by playing at z. Moreover, this even remains true if the ziggurat has not been completed yet (i.e., if the template stone 1 has not yet been played).

Proof. If Blue plays at x or y (or both), clearly Red playing at z defends the ziggurat. What we must show is that it defends the neighboring templates as well. But if Red plays at z, then the two hexes just below z are captured.

1zxy

Then the neighboring templates are valid by Theorem 3 above (the corner bending theorem).

The other thing we must show is that if Blue starts by playing in the ziggurat anywhere other than at x or y, then Red can always reconnect in a way that either captures or no longer needs x and y. Indeed, if Blue plays anywhere on the right, Red can play like this:

1xy

which captures x and no longer needs y. And if Blue plays on the left, Red responds like this, which captures y and no longer needs x:

1xy

Example

The classic application of the ziggurat theorem is edge template IV2c:

abc

Red is threatening to play at a or b, getting a ziggurat each way. Blue's only hope is to play in the overlap. Alas, by the ziggurat theorem, this does not work. Red knows that she should play at 2 (the symmetric move would of course also have worked):

21

Now Blue is sure to lose:

348657

There are other ways for Red to connect here; for one, Red's moves 2, 4, 6 could have been played in a different order. But by using the ziggurat theorem, Red can easily know what to do without having to think hard, and can concentrate on other trickier areas of the board.

Generalizations. There are many other edge templates (besides the ziggurat) for which a version of the ziggurat theorem holds, but it is not known whether it holds for all templates of the appropriate shape. Perhaps a list of such templates could be added here at some point.

The shape of templates

You may have noticed that many edge templates resemble each other: their boundaries tend to follow a relatively small number of possible shapes. This is not a coincidence. Some of it is due to the following theorems.

Observation: the two empty cells in the following pattern are captured by Blue.

Indeed, if Red plays in one of these cells, Blue can play in the other, killing Red's stone. From this, we immediately get the following theorem:

Theorem 9. There is no edge template with an empty corner of height 2, i.e., with a corner of this shape:

Here, as in previous theorems, the blue-shaded cells indicate the outside of the template, i.e., they are not part of the carrier.

Proof. Since the shaded hexes are outside the carrier, they may as well be blue stones. But then the two empty cells are captured by the previous observation, which means they can also be filled in with blue stones, contradicting the minimality of the template. □

We note that the theorem only says that the corner of an edge template cannot be of height 2 if that corner is empty. When there are stones in the corner, height 2 is possible, as in the following examples:

Observation: The following two regions are equivalent:

x
yx

To see why, first assume that Blue plays first in the region. Then Blue x captures the entire region, so the stone at y no longer matters. Next, assume that Red plays first in the region. If Red plays anywhere other than x, then Blue x kills the red stone. If Red plays at x, then y is dead, so the stone at y no longer matters. As a consequence, we get the following theorem:

Theorem 10. There is no edge template with a piece of boundary of this shape:

y

Here, as in previous theorems, the blue-shaded cells indicate the outside of the template, i.e., they are not part of the carrier.

Proof. Since the shaded hexes are outside the carrier, they may as well be blue stones. Then by the previous observation, y might as well be blue, contradicting the minimality of the template. □

Once again, we remark that Theorem 10 presupposes that there are no stones in the relevant portion of the template. For example, the ziggurat is an edge template that ends in two columns of height 3, but this does not contradict Theorem 10 due to the presence of a red stone in one of these columns.

Theorem 11. There is no edge template with a corner of this shape:

y

As always, the blue-shaded cells indicate the outside of the template, i.e., they are not part of the carrier.

Proof. This is very similar to Theorem 10. By the previous observation, y might as well be blue, contradicting the minimality of the template. □

Theorems 7–9 explain why the rightmost few columns of edge templates frequently have one of these shapes

and never one of these, unless the template contains stones in those regions: