Difference between revisions of "Parallelogram boards"
(→Size of minimal virtual connection on parallelogram boards: Fixed typo and added a data point) |
(Added a paragraph on conventions for specifying board dimension.) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | Hex is usually played on a rhombic ''n''×''n'' board, but one can also try playing it on ''n''×'' | + | Hex is usually played on a rhombic ''n''×''n'' board, but one can also try playing it on ''n''×''k'' parallelogram boards, where ''n'' is the number of columns, ''k'' the number of rows, and ''n'' ≠ ''k''. For example, here is a board of size 7×3: |
<hexboard size="3x7" | <hexboard size="3x7" | ||
coords="none" | coords="none" | ||
edges="all" | edges="all" | ||
/> | /> | ||
| − | The problem with playing on such parallelogram boards is that the player with the shorter distance between her sides has a simple [[Hex_theory#Winning_strategy_for_non-square_boards|winning strategy]], even when she moves second. To mitigate this, one can permit the player with the greater distance between his sides to place a certain number of stones on the board prior to the game. In particular, it has been found that Hex on a | + | The problem with playing on such parallelogram boards is that the player with the shorter distance between her sides has a simple [[Hex_theory#Winning_strategy_for_non-square_boards|winning strategy]], even when she moves second. To mitigate this, one can permit the player with the greater distance between his sides to place a certain number of stones on the board prior to the game. In particular, it has been found that Hex on a 9×7 board is a rather fair game, when Blue may start the game with two stones at once. |
| + | |||
| + | == Conventions for specifying the board dimensions == | ||
| + | |||
| + | When discussing ''n''×''k'' Hex, there is no standard convention for whether ''n'' represents the number of columns or rows. This page and other areas of the Wiki use the convention that ''n'' represents the number of columns and ''k'' represents the number of rows. This is consistent with the way coordinates are specified, such as in "b3" where the column "b" is listed before the row "3". The columns-before-rows convention is also used for specifying board sizes in the [[GTP]] protocol and in the [[Smart Game Format|SGF]] file format. | ||
| + | |||
| + | However, it's worth noting that this convention is not universally accepted, and in some cases, the opposite convention is used. Notably, on this Wiki, the [[New board diagrams|<code><hexboard></code>]] tag uses the opposite convention. To avoid confusion, it's best to clarify the meaning when discussing Hex with non-square dimensions. | ||
== Size of minimal virtual connection on parallelogram boards == | == Size of minimal virtual connection on parallelogram boards == | ||
| − | On a board of size ''n''×'' | + | On a board of size ''n''×''k'', one may ask what is the minimum number of stones Blue must place on the board prior to the game to guarantee a Blue win. Equivalently, one can ask what is the size of the minimal [[virtual connection]] between Blue's edges on an otherwise empty board. |
| − | The answer is known for certain small values of ''n'' and/or '' | + | The answer is known for certain small values of ''n'' and/or ''k'': |
{| class="wikitable" style="text-align: center;" | {| class="wikitable" style="text-align: center;" | ||
! × | ! × | ||
| − | ! scope="column" | 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || Formula (if known) | + | ! scope="column" | n=1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || Formula (if known) |
|- | |- | ||
| − | ! scope="row" | 1 | + | ! scope="row" | k=1 |
| − | | 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || '' | + | | 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || ''n'' |
|- | |- | ||
! scope="row" | 2 | ! scope="row" | 2 | ||
| − | | 0 || 1 ||2 || 2 || 3 || 4 || 4 || 5 || 6 || 6 || 7 || 8 || ⌈⅔'' | + | | 0 || 1 ||2 || 2 || 3 || 4 || 4 || 5 || 6 || 6 || 7 || 8 || ⌈⅔''n'' − ⅔⌉ |
|- | |- | ||
! scope="row" | 3 | ! scope="row" | 3 | ||
| − | | 0 || 0 || 1 || 2 || 3 || 3 || 4 || 5 || 5 || 6 || 7 || 7 || ⌈⅔'' | + | | 0 || 0 || 1 || 2 || 3 || 3 || 4 || 5 || 5 || 6 || 7 || 7 || ⌈⅔''n'' − 1⌉ |
|- | |- | ||
! scope="row" | 4 | ! scope="row" | 4 | ||
| − | | 0 || 0 || 0 || 1 || 2 || 2 || 3 || 4 || 4 || 5 || 6 || 6 || ⌈⅔'' | + | | 0 || 0 || 0 || 1 || 2 || 2 || 3 || 4 || 4 || 5 || 6 || 6 || ⌈⅔''n'' − 2⌉ |
|- | |- | ||
! scope="row" | 5 | ! scope="row" | 5 | ||
| − | | 0 || 0 || 0 || 0 || 1 || 2 || 2 || 3 || 3 || | + | | 0 || 0 || 0 || 0 || 1 || 2 || 2 || 3 || 3 || 4 || 5 || 5 || ⌈⅔''n'' − 3⌉, n ≥ 7 |
|- | |- | ||
! scope="row" | 6 | ! scope="row" | 6 | ||
| Line 42: | Line 48: | ||
== Examples of minimal virtual connections == | == Examples of minimal virtual connections == | ||
| − | === Boards of size | + | === Boards of size ''n''×1 === |
| − | For boards of size | + | For boards of size ''n''×1, it is obvious that Blue's virtual connection requires ''n'' stones, because if any cell is left empty, Red will win in one move. |
<hexboard size="1x7" | <hexboard size="1x7" | ||
edges="all" | edges="all" | ||
| Line 51: | Line 57: | ||
/> | /> | ||
| − | === Boards of size | + | === Boards of size ''n''×2 === |
| − | For boards of size | + | For boards of size ''n''×2, the size of Blue's minimal virtual connection is ⌈⅔''n'' − ⅔)⌉. Here, ⌈''x''⌉ denotes the ''ceiling'' of ''x'', i.e., the smallest integer ≥ ''x''. Examples of such minimal virtual connections are shown for ''n'' = 2, 3, 4, 5, 6, 7. The pattern continues for larger ''n''. |
<hexboard size="2x2" | <hexboard size="2x2" | ||
float="inline" | float="inline" | ||
| Line 86: | Line 92: | ||
/> | /> | ||
| − | === Boards of size | + | === Boards of size ''n''×3 === |
| − | For boards of size | + | For boards of size ''n''×3, where ''n'' ≥ 3, the size of Blue's minimal virtual connection is ⌈⅔''n'' − 1⌉. Examples of such minimal virtual connections are shown for ''n'' = 3, 4, 5, 6, 7. The pattern continues for larger ''n''. |
<hexboard size="3x3" | <hexboard size="3x3" | ||
float="inline" | float="inline" | ||
| Line 116: | Line 122: | ||
/> | /> | ||
| − | === Boards of size | + | === Boards of size ''n''×4 === |
| − | For boards of size | + | For boards of size ''n'', where ''n'' ≥ 4, the size of Blue's minimal virtual connection is ⌈⅔''n'' − 2⌉. This is proved, using tools from combinatorial game theory, in the paper [https://arxiv.org/abs/2101.06694 "On the combinatorial value of Hex positions"]. Examples of such minimal virtual connections are shown for ''n'' = 4, 5, 6, 7, 8, 9. The pattern continues for larger ''n''. |
<hexboard size="4x4" | <hexboard size="4x4" | ||
float="inline" | float="inline" | ||
| Line 150: | Line 156: | ||
contents="B c2 d3 f2 g3" | contents="B c2 d3 f2 g3" | ||
/> | /> | ||
| − | Interestingly, in addition to a virtual connection by [[bridge]]s, there is another pattern of such minimal connections when '' | + | Interestingly, in addition to a virtual connection by [[bridge]]s, there is another pattern of such minimal connections when ''k'' = 4. It uses the same number of stones, but has a larger [[carrier]]. |
<hexboard size="4x4" | <hexboard size="4x4" | ||
float="inline" | float="inline" | ||
| Line 185: | Line 191: | ||
== References == | == References == | ||
| − | * P. Selinger, [https://arxiv.org/abs/2101.06694 | + | * P. Selinger, "On the combinatorial value of Hex positions", [http://math.colgate.edu/~integers/vol22.html#g3 Integers 22:G3], 2022. Also available from [https://arxiv.org/abs/2101.06694 arxiv:2101.06694] |
[[category: Theory]] | [[category: Theory]] | ||
Latest revision as of 14:39, 25 January 2023
Hex is usually played on a rhombic n×n board, but one can also try playing it on n×k parallelogram boards, where n is the number of columns, k the number of rows, and n ≠ k. For example, here is a board of size 7×3:
The problem with playing on such parallelogram boards is that the player with the shorter distance between her sides has a simple winning strategy, even when she moves second. To mitigate this, one can permit the player with the greater distance between his sides to place a certain number of stones on the board prior to the game. In particular, it has been found that Hex on a 9×7 board is a rather fair game, when Blue may start the game with two stones at once.
Contents
Conventions for specifying the board dimensions
When discussing n×k Hex, there is no standard convention for whether n represents the number of columns or rows. This page and other areas of the Wiki use the convention that n represents the number of columns and k represents the number of rows. This is consistent with the way coordinates are specified, such as in "b3" where the column "b" is listed before the row "3". The columns-before-rows convention is also used for specifying board sizes in the GTP protocol and in the SGF file format.
However, it's worth noting that this convention is not universally accepted, and in some cases, the opposite convention is used. Notably, on this Wiki, the <hexboard> tag uses the opposite convention. To avoid confusion, it's best to clarify the meaning when discussing Hex with non-square dimensions.
Size of minimal virtual connection on parallelogram boards
On a board of size n×k, one may ask what is the minimum number of stones Blue must place on the board prior to the game to guarantee a Blue win. Equivalently, one can ask what is the size of the minimal virtual connection between Blue's edges on an otherwise empty board.
The answer is known for certain small values of n and/or k:
| × | n=1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | Formula (if known) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| k=1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | n |
| 2 | 0 | 1 | 2 | 2 | 3 | 4 | 4 | 5 | 6 | 6 | 7 | 8 | ⌈⅔n − ⅔⌉ |
| 3 | 0 | 0 | 1 | 2 | 3 | 3 | 4 | 5 | 5 | 6 | 7 | 7 | ⌈⅔n − 1⌉ |
| 4 | 0 | 0 | 0 | 1 | 2 | 2 | 3 | 4 | 4 | 5 | 6 | 6 | ⌈⅔n − 2⌉ |
| 5 | 0 | 0 | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 4 | 5 | 5 | ⌈⅔n − 3⌉, n ≥ 7 |
| 6 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 2 | 3 | ≤5 | |||
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 2 | ||||
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 2? |
Examples of minimal virtual connections
Boards of size n×1
For boards of size n×1, it is obvious that Blue's virtual connection requires n stones, because if any cell is left empty, Red will win in one move.
Boards of size n×2
For boards of size n×2, the size of Blue's minimal virtual connection is ⌈⅔n − ⅔)⌉. Here, ⌈x⌉ denotes the ceiling of x, i.e., the smallest integer ≥ x. Examples of such minimal virtual connections are shown for n = 2, 3, 4, 5, 6, 7. The pattern continues for larger n.
Boards of size n×3
For boards of size n×3, where n ≥ 3, the size of Blue's minimal virtual connection is ⌈⅔n − 1⌉. Examples of such minimal virtual connections are shown for n = 3, 4, 5, 6, 7. The pattern continues for larger n.
Boards of size n×4
For boards of size n, where n ≥ 4, the size of Blue's minimal virtual connection is ⌈⅔n − 2⌉. This is proved, using tools from combinatorial game theory, in the paper "On the combinatorial value of Hex positions". Examples of such minimal virtual connections are shown for n = 4, 5, 6, 7, 8, 9. The pattern continues for larger n.
Interestingly, in addition to a virtual connection by bridges, there is another pattern of such minimal connections when k = 4. It uses the same number of stones, but has a larger carrier.
References
- P. Selinger, "On the combinatorial value of Hex positions", Integers 22:G3, 2022. Also available from arxiv:2101.06694
