Y - Revision history

Selinger: /* References */ Added Browne reference

2025-08-27T23:13:51Z

‎References: Added Browne reference

Selinger: /* Embedding Y in Hex */ Added a reference

2025-08-27T23:11:56Z

‎Embedding Y in Hex: Added a reference

Selinger: Added Y as a quotient of Hex

2025-08-27T21:08:55Z

Added Y as a quotient of Hex

Selinger: Copy-editing.

2024-06-20T21:57:16Z

Copy-editing.

Selinger: Crediting Milnor

2024-06-20T20:59:15Z

Crediting Milnor

Bobson8 at 04:26, 20 June 2024

2024-06-20T04:26:15Z

Bobson8: Adding Y-reduction

2024-06-20T04:10:04Z

Adding Y-reduction

Selinger: Converted to new hexboard diagrams, copy-editing.

2020-12-28T22:25:12Z

Converted to new hexboard diagrams, copy-editing.

Isometry: /* On the web */

2016-08-31T05:30:18Z

‎On the web

Zamunda: I had not seen the "where to swap (y)" page :-/

2011-09-20T20:42:52Z

I had not seen the "where to swap (y)" page :-/

@@ Line 134: / Line 134: @@
 * John F. Nash. Some games and machines for playing them. RAND Corporation Report D-1164, February 2, 1952. https://www.rand.org/pubs/documents/D1164.html Credits John Milnor as the inventor of the game.
-* Felix Weilacher, "I guess you can get Y as a quotient of normal Hex by mirroring moves across the short diagonal". In a post on the [[Hex forums|Hex Discord]], August 27, 2025.
+* Cameron Browne, [http://www.amazon.com/Connection-Games-Variations-Cameron-Browne/dp/1568812248/ref=pd_bbs_sr_1/104-1532904-9846317?ie=UTF8&s=books&qid=1177663469&sr=8-1 "Connection Games: Variations on a Theme"]. A K Peters/CRC Press, 2005.
 [[Category: Y]]
 [[Category: Theory]]

@@ Line 85: / Line 85: @@
 The winner of the Y position is also the winner of the Hex position, and vice versa. Proof: to win the Y position, a player must have a [[group]] that is connected to the short diagonal and also to the right and bottom edges. By mirror symmetry, the same stone of the short diagonal is also connected to the left and top edges, so it is a winning path in Hex (either top to bottom for Red, or left to right for Blue). Conversely, consider the winner of the Hex position, say Red. Then Red has a group of stones that connects the top edge to the bottom edge. It must pass through the short diagonal. By symmetry, that same stone on the short diagonal is also connected to the right and left edges, and therefore it is a winning group in Y.
-The fact that a Y board can be seen as a quotient of a Hex board was first observed by Felix Weilacher on the [[Hex_forums|Hex Discord]], following a similar observation by the user Bobson that Y is a quotient of Projective Hex.
+This way of seeing a Y board as a quotient of a Hex board appears in Cameron Browne's book "Connection Games", Figure 7.14.
-−
 == Y-Reduction ==

@@ Line 42: / Line 42: @@
 In Y the [[strategy-stealing argument]] can be applied. It proves that the second player has no winning strategy. The argument is that if the second player had a winning strategy, then the first player could chose a random first move and then pretend that she is the second player and apply the strategy. An important point is that an extra stone is not a disadvantage in Y. Since Y is a perfect information game without draws, there is a winning strategy for one player. The second player has no winning strategy so the first player has one.
-== Extension of [[Hex]] ==
+== Relationship to [[Hex]] ==
-The proof above extends to Hex because a Hex game can be seen as a special case of a Y game.
+=== Embedding Hex in Y ===
-For instance consider the following Y board of size 7.
+Hex game can be seen as a special case of a Y game. For instance consider the following Y board of size 7.
 <hexboard size="7x7"
    coords="none"
@@ Line 52: / Line 52: @@
    visible="area(g1,a7,g7)"
    />
 We can simulate a Hex game of [[size]] 4 on it.
 <hexboard size="7x7"
@@ Line 60: / Line 59: @@
    contents="R area(g1,e3,g3) B area(c5,a7,c7)"
    />
 Now the only way to win for Blue is to cross the board horizontally, whereas the only way for Red to do so is to cross the board vertically.
-Each game of Hex on a board of size ''n'' can be played on a Y board of size 2''n''−1 with the rules of Y. The players just need to place some stones to "construct" the Hex board.
+Each game of Hex on a board of size ''n'' can be played on a Y board of size 2''n''−1 with the rules of Y. The players just need to place
 == Y-Reduction ==
@@ Line 111: / Line 134: @@
 * John F. Nash. Some games and machines for playing them. RAND Corporation Report D-1164, February 2, 1952. https://www.rand.org/pubs/documents/D1164.html Credits John Milnor as the inventor of the game.
 [[Category: Y]]
 [[Category: Theory]]

@@ Line 1: / Line 1: @@
-The game of Y is a [[connection game]] first invented in the early 1950s by John Milnor, and independently discovered in 1953 by Craige Schensted (later known as Ea Ea) and Charles Titus. In its original form, it is played on a triangular grid of hexagons, but Schensted and Titus preferred grids the include some pentagons, see [[#Variations|Variations]] below. There are two [[player]]s, who have one colour each, and a move consists of placing a piece of your colour in one of the hexagons on the board. The winner is the first player to complete a [[chain]] connecting all three sides of the board. Y is a kind of generalisation of [[Hex]], perhaps the one closest to it, but there are some strategic peculiarities, such as [[corner template]]s.
+The game of Y is a [[connection game]] first invented in the early 1950s by John Milnor, and independently discovered in 1953 by Craige Schensted (later known as Ea Ea) and Charles Titus. In its original form, it is played on a triangular grid of hexagons, but Schensted and Titus preferred grids the include some pentagons, see [[#Variations|Variations]] below. There are two [[player]]s, who have one colour each, and a move consists of placing a stone of your colour in one of the hexagons on the board. The winner is the first player to complete a [[chain]] connecting all three sides of the board. Y is a kind of generalisation of [[Hex]], perhaps the one closest to it, but there are some strategic peculiarities, such as [[corner template]]s.
 <hexboard size="7x7"
@@ Line 9: / Line 9: @@
 == No draws ==
-Y cannot end in a draw. That is, once the board is complete there must be one and only one winner.
+Y cannot end in a draw. That is, once the board is completely filled, there must be one and only one winner.
 There cannot be two winners at the same time. If there were, each player would have a region of the board touching all three sides of the triangle as well as the opponent's region. Considering the three sides as regions themselves, this gives a map of five regions, each of which is adjacent to the other four. However, this is impossible, as the graph K5 is non-planar.
 === At least one winner ===
-It can be proved by an algorithm that once a board is complete there is at least one player linking the 3 sides. Let the "state" of a board refer to the answer to the question "Is there at least one winner?" We want to prove that the state of every board is "Yes".
+It can be proved by an algorithm that once the board is completely filled, there is at least one player linking the 3 sides. Let the "status" of a board refer to the answer to the question "Is there at least one winner?" We want to prove that the status of every board is "yes".
-''First step'': if there is a pawn group (red for instance) completely surrounded by the opponent (blue for instance) let's consider the board with this pawn group replaced by opponent's pawns (blue ones). The new board has the same status as the older one as the remote group was not winning and the new big (blue) one is winning iff it was in the former board. Also note that there is still at least one group left.
+''First step'': if there is a group of stones that is completely surrounded by the opponent, let's consider the board with the surrounded group replaced by opponent's stones. The new board has the same status as the old one, as the surrounded group was not winning and the new big group is winning if and only if it was winning on the old board. Also note that there is still at least one group left.
-Repeat this step until there is no completely surrounded group more (of either color). The board obtained has the same state as the original.
+Repeat this step until there are no more completely surrounded groups of either color. The resulting board has the same status as the original.
-''Second step'': if there is a pawn group surrounded by the opponent and a side, removing it does not change the state of the board (for similar reasons as in step 1) and there is still at least one group left.
+''Second step'': if there is a group of stones surrounded by the opponent and an edge, removing it does not change the status of the board (for similar reasons as in step 1), and there is still at least one group left.
 Repeat this step.
-''Third step'': if there is a pawn group surrounded by the opponent and two sides removing it does not change the state of the board (for similar reasons as in step 1) and there is still at least one group left.
+''Third step'': if there is a group of stones surrounded by the opponent and two edges, removing it does not change the status of the board (for similar reasons as in step 1), and there is still at least one group left.
 Repeat this step.
-It is quite clear that after applying this algorithm there is no group connected to more than 1 opponent's groups. No group is connected to zero sides and one opponent's group, no group is connected to one side and one opponent's group, no group is connected to two sides and one opponent's group. No group can be connected to 0 1 or 2 sides without connecting an opponent group. Moreover there is at least one group left. Hence this group left is connected to 3 sides.
+It is quite clear that after applying this algorithm there is no group connected to more than one of the opponent's groups. No group is connected to zero edges and one opponent's group, no group is connected to one egdes and one opponent's group, no group is connected to two edges and one opponent's group. No group can be connected to 0, 1 or 2 edges without connecting to an opponent group. Moreover there is at least one group left. Hence this group left is connected to 3 edges.
-So the state of the board is "yes"; as it is the same as the state of the beginning board, there was a winner to begin with.
+So the status of the board is "yes"; as it is the same as the status of the original board, there was a winner to begin with.
 Note that this algorithm ends because the number of different groups is finite.
-=== Extension to [[Hex]] ===
+For another proof, see [[#Y-Reduction|Y-Reduction]] below.
-The proof above extends to Hex because a Hex game can be seen as a subset of a Y game.
+== The first player wins ==
 For instance consider the following Y board of size 7.
@@ Line 60: / Line 67: @@
 == Y-Reduction ==
-Given a Y board of size n filled with red or blue stones, there is an operation of replacing each of the upper triangle of size 2 with a hex at its center, and with a stone of color representing the majority of the three hexes being replaced. The result would be a Y board of size n-1. This operation is called the Y-reduction, introduced by Craige Schensted.
+Given a Y board of size ''n'' filled with red or blue stones, there is an operation of replacing each of the upper triangles of size 2 with a hex at its center, and with a stone of the color representing the majority of the three hexes being replaced. The result is a Y board of size ''n''−1. This operation is called the '''Y-reduction''', introduced by Craige Schensted.
 <hexboard size="5x24"
    coords="none"
    edges="none"
-   visible="area(e1,a5,e5) area(j2,g5,j5) area(n3,l5,n5) q4 p5 q5 s5"
+   visible="area(e1,a5,e5) area(j2,g5,j5) area(n3,l5,n5) area(q4,p5,q5) area(s5)"
    contents="R b4 c3 c4 d4 d5 e2 e5 h4 i4 j5 i5 m4 m5 n5 p5 q5 s5 B a5 b5 c5 d2 d3 e1 e3 e4 j2 i3 j3 g5 h5 j4 n3 n4 l5 q4"
    />
@@ Line 71: / Line 78: @@
 For example, the above Y board of size 5 can be reduced to size 4, and so on.
-An important property of this operation is that, one color has a winning chain if and only if the color has a winning chain for its Y-reduction. As a consequence, one can repeatedly reduce the board until size 1 to determine the winner. This can also be seen as a proof of exactly one winner for Y.
+An important property of this operation is that one color has a winning [[chain]] if and only if the color has a winning chain for its Y-reduction. As a consequence, one can repeatedly reduce the board until size 1 to determine the winner. This can also be seen as a proof that there is exactly one winner in Y.
-−
-== The first player wins ==
-In Y the [[strategy-stealing argument]] can be applied. It proves that the second player has no winning strategy. The argument is that if the second player had a winning strategy, then the first player could chose a random first move and then pretend that she is the second player and apply the strategy. An important point is that an extra pawn is not a disadvantage in Y. Y is a complete and perfect information game in which no draw can be conceived, so there is a winning strategy for one player. The second player has no winning strategy so the first player has one.
 == Swap ==
-The [[Swap rule]] can be used in Y too, the corner are bad moves to be played so there may well exist average moves to begin with. Further information on [[where to swap (y)|where to swap]].
+The [[swap rule]] can be used in Y. Opening moves in the center are good, and opening moves in the corners are bad, so there may well exist average opening moves. Further information, see [[Where to swap (y)]].
 == Variations ==
-The game is usually played with the [[swap rule]]. Alternatively, one can play Double-move Y, also known as [[Master Y]]: The first player places one piece on the board, and each subsequent move consists of placing two pieces on the board. This is a pretty challenging variant, even on small boards.
+As an alternative to the [[swap rule]]. Alternatively, one can play Double-Move Y, also known as Master Y: The first player places one stone on the board, and each subsequent move consists of placing two stones on the board. This is a pretty challenging variant, even on small boards.
-The inventors tried out a number of alternative playing grids, and eventually concluded that the most suitable one is the following "bent" version. The pieces are placed on the intersections (like in [[Go]]).
+The inventors tried out a number of alternative playing grids, and eventually concluded that the most suitable one is the following "bent" version. The stones are placed on the intersections (like in [[Go]]).
 [[Image:Y93_bent.gif]]
@@ Line 105: / Line 109: @@
 == References ==
-−
 * John F. Nash. Some games and machines for playing them. RAND Corporation Report D-1164, February 2, 1952. https://www.rand.org/pubs/documents/D1164.html Credits John Milnor as the inventor of the game.
 [[Category: Y]]
 [[Category: Theory]]

@@ Line 1: / Line 1: @@
-The game of Y is a [[connection game]] invented by [[Craige Schensted]] and [[Charles Titus]]. In its original form, it is played on a [[triangular grid of hexagons]]. There are two [[Player (general)|players]], who have one colour each, and a move consists of placing a piece of your colour in one of the hexagons on the board. The winner is the first player to complete a [[chain]] connecting all three sides of the board. Y is a kind of generalisation of [[Hex]], perhaps the one the nearest from it, but there are some strategic peculiarities, such as [[corner template]]s
+The game of Y is a [[connection game]] first invented in the early 1950s by John Milnor, and independently discovered in 1953 by Craige Schensted (later known as Ea Ea) and Charles Titus. In its original form, it is played on a triangular grid of hexagons, but Schensted and Titus preferred grids the include some pentagons, see [[#Variations|Variations]] below. There are two [[player]]s, who have one colour each, and a move consists of placing a piece of your colour in one of the hexagons on the board. The winner is the first player to complete a [[chain]] connecting all three sides of the board. Y is a kind of generalisation of [[Hex]], perhaps the one closest to it, but there are some strategic peculiarities, such as [[corner template]]s.
 <hexboard size="7x7"
@@ Line 103: / Line 103: @@
 * http://www.neutreeko.net/y.htm
 * http://www.iggamecenter.com/ ('''igGameCenter''' - play "Y" online with other opponents from your iGoogle homepage)
 [[Category: Y]]
 [[Category: Theory]]

@@ Line 1: / Line 1: @@
 The game of Y is a [[connection game]] invented by [[Craige Schenstead]] and [[Charles Titus]]. In its original form, it is played on a [[triangular grid of hexagons]]. There are two [[Player (general)|players]], who have one colour each, and a move consists of placing a piece of your colour in one of the hexagons on the board. The winner is the first player to complete a [[chain]] connecting all three sides of the board. Y is a kind of generalisation of [[Hex]], perhaps the one the nearest from it, but there are some strategic peculiarities, such as [[corner template]]s
-[[Image:Y-board-straight.gif]]
+<hexboard size="7x7"
 == No draws ==
@@ Line 35: / Line 39: @@
 The proof above extends to Hex because a Hex game can be seen as a subset of a Y game.
-For instance consider the following Y board of size 8. (The star marked hexes are not a part of the board.)
+For instance consider the following Y board of size 7.
-<hex> C8 R8
+<hexboard size="7x7"
-:SSSSSSS_
+  coords="none"
-:SSSSSS__
+  edges="none"
-:SSSSS___
+  visible="area(g1,a7,g7)"
-:SSSS____
+  />
-:SSS_____
-:SS______
-:S_______</hex>
 We can simulate a Hex game of [[size]] 4 on it.
-<hex> C8 R8
+<hexboard size="7x7"
-:SSSSSSSR
+  coords="none"
-:SSSSSSRR
+  edges="none"
-:SSSSSRRR
+  visible="area(g1,a7,g7)"
-:SSSSRRRR
+  contents="R area(g1,e3,g3) B area(c5,a7,c7)"
-:SSSB____
+  />
-:SSBB____
-:SBBB____
-:BBBB____</hex>
-Now the only way to win for Blue is to cross the board horizontally, whereas the only way for Red to do so is to cross the board verticaly.
+Now the only way to win for Blue is to cross the board horizontally, whereas the only way for Red to do so is to cross the board vertically.
-Each game of Hex on size n Hex board can be played on a Y board of size 2n or 2n-1 with the rules of Y, player just need to play some stones to "construct" the Hex board.
+Each game of Hex on a board of size ''n'' can be played on a Y board of size 2''n''−1 with the rules of Y. The players just need to place some stones to "construct" the Hex board.
 == The first player wins ==
-In Y the [[strategy-stealing argument]] can be applied. It proves that the second player has no winning strategy. The argument is that if the second player had a winning strategy, then the first player could chose a random first move and then pretend that she is the second player and apply the stratey. An important point is that an extra pawn is not a disadvantage in Y. Y is a complete and perfect information game in wich no draw can be conceived, so there is a winning strategy for one player. The second player has no winning strategy so the first player has one.
+In Y the [[strategy-stealing argument]] can be applied. It proves that the second player has no winning strategy. The argument is that if the second player had a winning strategy, then the first player could chose a random first move and then pretend that she is the second player and apply the strategy. An important point is that an extra pawn is not a disadvantage in Y. Y is a complete and perfect information game in which no draw can be conceived, so there is a winning strategy for one player. The second player has no winning strategy so the first player has one.
 == Swap ==
@@ Line 69: / Line 67: @@
 == Variations ==
-The game is usually played with the [[swap_rule]]. Alternatively, one can play Double-move Y, also known as [[Master Y]]: The first player places one piece on the board, and each subsequent move consists of placing two pieces on the board. This is a pretty challenging variant, even on small boards.
+The game is usually played with the [[swap rule]]. Alternatively, one can play Double-move Y, also known as [[Master Y]]: The first player places one piece on the board, and each subsequent move consists of placing two pieces on the board. This is a pretty challenging variant, even on small boards.
 The inventors tried out a number of alternative playing grids, and eventually concluded that the most suitable one is the following "bent" version. The pieces are placed on the intersections (like in [[Go]]).

@@ Line 87: / Line 87: @@
 * http://www.gamepuzzles.com/gameofy.htm
 * http://www.gamepuzzles.com/revugy.htm (Games magazine reviews)
-* http://home.flash.net/~markthom/html/the_game_of_y.html
+* http://home.flash.net/~markthom/html/the_game_of_y.html (Dead link?)
 * http://www.iggamecenter.com/ ('''igGameCenter''' - play "Y" online with other opponents from your iGoogle homepage)

← Older revision		Revision as of 20:42, 20 September 2011
Line 74:		Line 74:

	[[Image:Y93_bent.gif]]		[[Image:Y93_bent.gif]]
−
−	~~== Solved? ==~~
−
−	~~No attempts to solve Y (regular and/or Master Y) for specific board sizes are known. On this small bent board, the game appears to be non-trivial, but should be within reach for computers.~~
−
−	~~[[Image:Y27_bent.gif]]~~

	== See also ==		== See also ==