Difference between revisions of "User:Selinger"

From HexWiki
Jump to: navigation, search
(Proposed article: Mustplay region: Flipped colors)
(Proposed article: Mustplay region: Finished first complete draft of mustplay)
Line 161: Line 161:
 
* With respect to the chosen set of threats, the ''mustplay region'' is the set of empty cells in that intersection.
 
* With respect to the chosen set of threats, the ''mustplay region'' is the set of empty cells in that intersection.
  
== Properties of the mustplay region ==
+
== Properties ==
  
 
* All moves outside a player's mustplay region are losing. Moves within the mustplay region may be winning or losing.
 
* All moves outside a player's mustplay region are losing. Moves within the mustplay region may be winning or losing.
Line 225: Line 225:
 
   />
 
   />
  
TODO:
+
Red's main threats are:
 +
 
 +
* e4, connecting via [[bridge]]s and a [[ziggurat]]: <hexboard size="7x7"
 +
  coords="show"
 +
  edges="all"
 +
  contents="R c2 b4 f2 f5 B c4 d4 d5 g3
 +
            R *:e4 S red:area(f1,e3,e6,d7,g7,g5,f5,f3,g1)"
 +
  />
 +
* a6, connecting via a 2nd row [[ladder]] and [[ladder escape]]: <hexboard size="7x7"
 +
  coords="show"
 +
  edges="all"
 +
  contents="R c2 b4 f2 f5 B c4 d4 d5 g3
 +
            R *:a6 S red:area(c1,a5,a7,f7,f5,e5,d6,b6,d1)"
 +
  />
 +
* a6, connecting via a 2nd row [[ladder]] and a slightly different [[ladder escape]]: <hexboard size="7x7"
 +
  coords="show"
 +
  edges="all"
 +
  contents="R c2 b4 f2 f5 B c4 d4 d5 g3
 +
            R *:a6 S red:area(c1,a5,a7,g7,g5,f5,e6,b6,d1)"
 +
  />
 +
 
 +
Therefore, Blue's mustplay region consists of the following 5 cells:
 +
<hexboard size="7x7"
 +
  coords="show"
 +
  edges="all"
 +
  contents="R c2 b4 f2 f5 B c4 d4 d5 g3
 +
            S blue:area(e6,f6,d7,e7,f7) E x:e6 y:f6 z:d7 u:e7 v:f7"
 +
  />
 +
Of these, y, z, u, and v are losing: if Blue plays there, Red wins by responding at x. Blue's unique winning move is x. This move is also known as a [[foiling]] move, because it takes away Red's template and Red's ladder escape at the same time.
 +
 
 +
=== Solving Hex puzzles ===
 +
 
 +
Consider the following puzzle, due to Eric Demer. Blue to move and win.
 +
<hexboard size="7x7"
 +
  coords="show"
 +
  edges="all"
 +
  contents="R g3 g2 e5 e3 c5 b5 a2 B d7 e4 d5 c4 b4"
 +
  />
 +
At first, the situation seems confusing here. Blue's central stones neither seem to have a convincing connection to the left edge nor to the right one.
 +
 
 +
Mustplay analysis helps clarify the situation. First, let's note that Red's e3 and g3 are already very strongly conneced to the bottom edge; Blue cannot gain anything by intruding into that connection. (In fact, Red has [[captured cell|captured]] rows 1&ndash;3). We therefore concentrate on the bottom part of the board. Within that region, Red's main threats are:
 +
 
 +
* d4, connecting via [[edge template III2a]]: <hexboard size="7x7"
 +
  coords="show"
 +
  edges="all"
 +
  contents="R g3 g2 e5 e3 c5 b5 a2 B d7 e4 d5 c4 b4
 +
            R *:d4 S red:(area(c7,c5,b5,a6,a7),d4,e3)"
 +
  />
 +
 
 +
* f5, connecting via [[double threat]] of f6 and a 2nd row [[ladder]] at d6, for which b5 and c5 are a [[ladder escape]]: <hexboard size="7x7"
 +
  coords="show"
 +
  edges="all"
 +
  contents="R g3 g2 e5 e3 c5 b5 a2 B d7 e4 d5 c4 b4
 +
            R *:f5 S red:area(g3,g4,f7,e7,e6,d6,c7,a7,a6,b5,c5,d6)"
 +
  />
 +
We therefore see that Blue's mustplay region consists of the following six cells:
 +
<hexboard size="7x7"
 +
  coords="show"
 +
  edges="all"
 +
  contents="R g3 g2 e5 e3 c5 b5 a2 B d7 e4 d5 c4 b4
 +
            S blue:(a6 b6 c6 a7 b7 c7) E x:a6 y:b6 z:c6 u:a7 v:b7 w:c7"
 +
  />
 +
Of these, x, y, u, v, and w are losing: if Blue plays there, Red can respond at z, re-establishing both threats.
 +
The unique winning move for Blue is z. In fact, this is basically a [[foiling]] move.
 +
 
 +
=== Verification of templates ===
 +
 
 +
Mustplay analysis is also useful in the verification of templates. In that context, it is sometimes known as ''template reduction''. For example, consider [[edge template V1a]]:
 +
<hexboard size="5x10"
 +
  visible="area(a5,c3,d3,f1,h1,h2,i2,i3,j3,j5)"
 +
  edges="bottom"
 +
  coords="none"
 +
  contents="R g1"
 +
  />
 +
 
 +
To show that the template is valid, we must show that Blue has no way of disconnecting the template's red stone from the edge. We use mustplay analysis to reduce the number of possiblities. Red's main threats are:
 +
 
 +
* Connecting via [[template IVa]]: <hexboard size="5x10"
 +
  visible="area(a5,c3,d3,f1,h1,h2,i2,i3,j3,j5)"
 +
  edges="bottom"
 +
  coords="none"
 +
  contents="R g1 R *:f2 S red:area(e2,c3,a5,g5,g3,f2)"
 +
  />
 +
 
 +
* Connecting via a [[bridge]] and [[template IVa]]: <hexboard size="5x10"
 +
  visible="area(a5,c3,d3,f1,h1,h2,i2,i3,j3,j5)"
 +
  edges="bottom"
 +
  coords="none"
 +
  contents="R g1 R *:h2 S red:area(h1,d5,j5,j3)"
 +
  />
 +
 
 +
* Connecting via a [[bridge]] and [[edge template III1b|template III-1-b]]: <hexboard size="5x10"
 +
  visible="area(a5,c3,d3,f1,h1,h2,i2,i3,j3,j5)"
 +
  edges="bottom"
 +
  coords="none"
 +
  contents="R g1 R *:f3 S red:area(f2,c5,g5,g2)-e5"
 +
  />
 +
 
 +
* Connecting via [[template IVb]], in two different ways: <hexboard size="5x10"
 +
  visible="area(a5,c3,d3,f1,h1,h2,i2,i3,j3,j5)"
 +
  edges="bottom"
 +
  coords="none"
 +
  contents="R g1 R *:f2 S red:area(e2,c3,a5,h5,h3,g2)-e4"
 +
/> <hexboard size="5x10"
 +
  visible="area(a5,c3,d3,f1,h1,h2,i2,i3,j3,j5)"
 +
  edges="bottom"
 +
  coords="none"
 +
  contents="R g1 R *:g2 S red:area(f2,d3,b5,i5,i3,h2)-f4"
 +
  />
 +
Therefore, Blue's mustplay region consists of only three cells:
 +
<hexboard size="5x10"
 +
  visible="area(a5,c3,d3,f1,h1,h2,i2,i3,j3,j5)"
 +
  edges="bottom"
 +
  coords="none"
 +
  contents="R g1 S blue:(f3 f5 d5)"
 +
  />
 +
To finish verifying the template, it then remains to show that each of these three moves are losing for Blue. See the article on [[edge template V1a]] for the details.
  
* application: foiling
+
=== Computer Hex ===
  
* application: puzzle 20210618-5
+
Mustplay analysis is used in computer Hex to reduce the number of possibilities that must be considered for a player's next move. This drastically reduces the size of the search tree.
  
* application: verification of templates
+
== References ==
  
* example with ladder creation + escape.
+
Hayward, Björnsson, Johanson, Kan, Po, and van Rijswijck: [http://webdocs.cs.ualberta.ca/~hayward/papers/s7x7hex1.pdf "Solving 7x7 Hex with domination, fill-in, and virtual connections"], ''Theoretical Computer Science'' 349;123&ndash;139, 2005.
  
* mustplay region in computer Hex
+
Hayward: [http://webdocs.cs.ualberta.ca/~hayward/papers/s7x7hex1.pdf "A puzzling Hex primer"]. In ''Games of No Chance 3'', Cambridge University Press, 56:151&ndash;162, 2009.
  
* add reference
+
[[category:Theory]]
 +
[[category:Intermediate Strategy]]
 +
[[category:Computer Hex]]

Revision as of 15:30, 5 July 2021

Proposed article: Pivoting template

The problem with this article draft, as currently written, is that the stated condition, "Red can either connect A to the edge, or else occupy and connect B to the edge", is weaker than what many of the templates satisfy. Most templates satisfy the stronger condition "Red can continuously threaten to connect A until Red occupies and connects B to the edge." There are situations where templates satisfying the weaker condition would be losing, but templates satisfying the stronger condition are winning. So one either needs several different notions, or specify the strength of each template. or state the stronger condition and select only templates that satisfy it. All choices seem awkward.

A pivoting template is a kind of edge template that guarantees that the template's owner can either connect the template's stone(s) to the edge, or else can occupy a specified empty hex and connect it to the edge.

Example

AB

This template guarantees that, with Blue to move, Red can either connect A to the edge, or else occupy and connect B to the edge. Its carrier is minimal with this property.

Proof: Red's main threat is to bridge to c and connect to the edge by ziggurat or edge template III1b. Therefore, to prevent Red from connecting to the edge outright, Blue must play in one of the cells a,...,g.

ABabcdefg

If Blue plays at a, Red responds at b and connects outright by edge template IV1a.

If Blue plays at b, Red responds with a 3rd row ladder escape fork:

A82147635

If Blue plays at c, d, or f, Red responds as follows and is connected by edge template V2f. If Blue plays on the right instead of 3, Red responds as if defending template V2f.

A431211

If Blue plays at e or g, Red responds at c and gets a 2nd or 3rd row ladder, which can reach B by ladder escape fork.

Usage

Pivoting templates can be useful in many situations, but are especially useful in connection with flanks.

[Todo: Add an example.]

More examples

AB
AB
AB
AB
AB

See also




Proposed article: Mustplay region

Informally, a mustplay region for a player is a set of cells in which the player must move to avoid losing immediately. Mustplay analysis is an important tool for analyzing Hex positions, because it can help narrow down the number of possibilities a player must consider.

Example

Consider the following position, with Blue to move:

abcdefg1234567

To determine Blue's mustplay region, Blue should consider the possible ways in which Red could make a connection if it were Red's turn. These are called Red's threats. Red has (at least) the following threats:

  • If Red plays at e5, then Red is connected via two copies of edge template II and two bridges, as shown:
    abcdefg1234567
  • Alternatively, if Red plays at e5, Red is also connected via edge template II and edge template III2e, as shown:
    abcdefg1234567
    While the last two connections both use a Blue stone at e5, they have different carriers.
  • If Red plays at d5, Red is connected via a 3rd row ladder, using f6 as a ladder escape. In this case, the carrier consists of the path the ladder will take and the space required for the ladder escape:
    abcdefg1234567

Blue's mustplay region consists of those empty cells that are in the carriers of all of Red's known threats. Therefore, Blue's mustplay region consists of the cells d1, e1, e5, e6, e7, and f7.

abcdefg1234567

Note that this does not mean that all of d1, e1, e5, e6, e7, and f7 are winning moves for Blue, or even that Blue has any winning moves at all. Rather, what it means is that all other moves are losing. In other words, if Blue has any winning moves at all, they must be in Blue's mustplay region. Blue must now consider each of the six moves d1, e1, e5, e6, e7, and f7 and check if any of them are winning, or barring that, which one of them is least likely to be losing.

To help narrow down Blue's choices even further, it helps to consider captured and dominated cells. In the above example, d1, e1, e7, and f7 are captured by Red, and therefore, Blue should not play there. This leaves Blue with e5 and e6 as the only possible moves to consider. It so happens that e5 is winning and e6 is losing. Therefore, considering the mustplay region has helped Blue identify the only possible winning move. Blue will play e5 and win the game.

Definition

From the point of view of a player, a threat is a virtual connection between the opponent's board edges that the opponent can create in a single move. The carrier of the threat is the set of cells (empty or not) that are required for the virtual connection to be valid. The player's mustplay region is determined as follows:

  • Identify as many threats as possible.
  • Determine the intersection of the carriers of all of these threats.
  • With respect to the chosen set of threats, the mustplay region is the set of empty cells in that intersection.

Properties

  • All moves outside a player's mustplay region are losing. Moves within the mustplay region may be winning or losing.
  • If a player's mustplay region is empty, the player is losing.
  • If there are no winning moves in a player's mustplay region, the player is losing.
  • The mustplay region is not unique. By considering more opponent threats, a player may arrive at a smaller mustplay region.

Example: no winning move

If there are no winning moves in a player's mustplay region, the player is losing. To illustrate this, consider the following position, with Blue to move.

abcde12345

Red's main threats are:

The only empty cell in the carrier of all three threats is b5, hence Blue's mustplay region consists of b5. This means that all moves except possibly b5 are losing for Blue.

abcde12345

Unfortunately for Blue, b5 is also losing, because if Blue plays b5, Red can win as follows:

abcde123452431

Therefore Blue has no winning moves at all and is losing the game.

Applications

Foiling

Consider the following situation, with Blue to move:

abcdefg1234567

Red's main threats are:

Therefore, Blue's mustplay region consists of the following 5 cells:

abcdefg1234567xyzuv

Of these, y, z, u, and v are losing: if Blue plays there, Red wins by responding at x. Blue's unique winning move is x. This move is also known as a foiling move, because it takes away Red's template and Red's ladder escape at the same time.

Solving Hex puzzles

Consider the following puzzle, due to Eric Demer. Blue to move and win.

abcdefg1234567

At first, the situation seems confusing here. Blue's central stones neither seem to have a convincing connection to the left edge nor to the right one.

Mustplay analysis helps clarify the situation. First, let's note that Red's e3 and g3 are already very strongly conneced to the bottom edge; Blue cannot gain anything by intruding into that connection. (In fact, Red has captured rows 1–3). We therefore concentrate on the bottom part of the board. Within that region, Red's main threats are:

We therefore see that Blue's mustplay region consists of the following six cells:

abcdefg1234567xyzuvw

Of these, x, y, u, v, and w are losing: if Blue plays there, Red can respond at z, re-establishing both threats. The unique winning move for Blue is z. In fact, this is basically a foiling move.

Verification of templates

Mustplay analysis is also useful in the verification of templates. In that context, it is sometimes known as template reduction. For example, consider edge template V1a:

To show that the template is valid, we must show that Blue has no way of disconnecting the template's red stone from the edge. We use mustplay analysis to reduce the number of possiblities. Red's main threats are:

Therefore, Blue's mustplay region consists of only three cells:

To finish verifying the template, it then remains to show that each of these three moves are losing for Blue. See the article on edge template V1a for the details.

Computer Hex

Mustplay analysis is used in computer Hex to reduce the number of possibilities that must be considered for a player's next move. This drastically reduces the size of the search tree.

References

Hayward, Björnsson, Johanson, Kan, Po, and van Rijswijck: "Solving 7x7 Hex with domination, fill-in, and virtual connections", Theoretical Computer Science 349;123–139, 2005.

Hayward: "A puzzling Hex primer". In Games of No Chance 3, Cambridge University Press, 56:151–162, 2009.