Difference between revisions of "Small boards"

From HexWiki
Jump to: navigation, search
(Size 7: add proof tree link from the top of the page)
(Link to KataHex)
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
Playing [[Hex]] on [[board]]s of size smaller than 10 × 10 is not very interesting, since many players will be able to play almost perfectly. However it may still be intersting for theoretical studies, and for making [[Puzzles|problems]].
+
Playing [[Hex]] on [[board]]s of size smaller than 10 × 10 is not very interesting, since many players will be able to play almost perfectly. However it may still be interesting for theoretical studies, and for making [[Puzzles|problems]].
  
The boards of size up to five can be solved by hand. Hex on 6 × 6 has been solved by [[Queenbee]].
+
The boards of size up to five can be solved by hand. Hex on 6 × 6 has been solved by [[Queenbee]]. The board sizes 7 to 9 have been solved with computer programs, too.
  
Here are the winning first moves on the small boards. [[Red (player)|Red]] is vertical and plays first. The [[Hex (board element)|cells]] containing a red [[Piece|stone]] are winning moves for red, while those containing a blue stone are losing. For more details, visit Queenbee's own  [http://www.cs.ualberta.ca/~queenbee/openings.html opening page].
+
Here are the winning first moves on the small boards. [[Red (player)|Red]] is vertical and plays first. The [[Hex (board element)|cells]] shaded red are winning moves for red, while those shaded blue are losing.
 
+
''Update:'' The 7 × 7 board has been solved by [[Ryan Hayward|R. Hayward]], et.al. For more details, visit http://www.cs.ualberta.ca/~hayward/hex7trees/
+
  
 
== Winner depending on the first move ==
 
== Winner depending on the first move ==
 
The following boards can help you decide where you should [[swap]] when playing on small boards, and it might give you ideas of patterns for bigger boards.
 
The following boards can help you decide where you should [[swap]] when playing on small boards, and it might give you ideas of patterns for bigger boards.
<hex>R2 C2 Q1 Vb1 Va2 Ha1 Hb2</hex>
 
  
<hex>R3 C3 Q1 Va2 Va3 Hb1 Vb2 Hb3 Vc1 Vc2 Ha1 Hc3</hex>
+
<hexboard size="2x2"
 +
  coords="show"
 +
  contents="S red:all blue:(a1 b2)"
 +
  />
  
<hex>R4 C4 Q1 Va4 Vb3 Vc2 Vd1 Ha1 Ha2 Ha3 Hb1 Hb2 Hb4 Hc1 Hc3 Hc4 Hd2 Hd3 Hd4</hex>
+
<hexboard size="3x3"
 +
  coords="show"
 +
  contents="S red:all blue:(a1 b1 b3 c3)"
 +
  />
  
<hex>R5 C5 Q1 Ve1 Vb2 Vc2 Vd2 Ve2 Vb3 Vc3 Vd3 Va4 Vb4 Vc4 Vd4 Va5 Ha1 Ha2 Ha3 Hb1 Hc1 Hd1 Hb5 Hc5 Hd5 He5 He4 He3</hex>
+
<hexboard size="4x4"
 +
  coords="show"
 +
  contents="S blue:all red:(a4 b3 c2 d1)"
 +
  />
  
<hex>R6 C6 Q1 Ve1 Vb2 Vc2 Vd2 Ve2 Vb3 Vc3 Vd3 Va4 Vb4 Vc4 Vd4 Va5 Ha1 Ha2 Va3 Hb1 Hc1 Hd1 He1 Vb5 Vc5 Vd5 Ve5 Ve4 Ve3 Vf1 Vf2 Vf3 Vf4 Hf5 Hf6 He6 Hd6 Hc6 Hb6 Va6</hex>
+
<hexboard size="5x5"
 +
  coords="show"
 +
  contents="S red:all blue:(a1--d1 a2 a3 b5--e5 e4 e3)"
 +
  />
 +
 
 +
<hexboard size="6x6"
 +
  coords="show"
 +
  contents="S red:all blue:(a1--e1 a2 b6--f6 f5)"
 +
  />
  
 
=== Size 7 ===
 
=== Size 7 ===
  
Size 7 was first solved by [[Ryan Hayward]] using [[domination]]. The proof tree can be found at http://www.cs.ualberta.ca/~hayward/hex7trees/
+
Size 7 was first solved by [[Ryan Hayward]] using [[dominated cell|domination]]. The proof tree can be found at http://www.cs.ualberta.ca/~hayward/hex7trees/
  
<hex>R7 C7 Q1 Ha1 Hb1 Hc1 Hd1 He1 Hf1 Vg1 Ha2 Hb2 Vc2 Hd2 Ve2 Vf2 Vg2 Ha3 Vb3 Vc3 Vd3 Ve3 Vf3 Hg3 Va4 Vb4 Vc4 Vd4 Ve4 Vf4 Vg4 Ha5 Vb5 Vc5 Vd5 Ve5 Vf5 Hg5 Va6 Vb6 Vc6 Hd6 Ve6 Hf6 Hg6 Va7 Hb7 Hc7 Hd7 He7 Hf7 Hg7</hex>
+
<hexboard size="7x7"
 +
  coords="show"
 +
  contents="S red:all blue:(a1--f1 a2 b2 a3 d2 a5 b7--g7 g6 f6 g5 d6 g3)"
 +
  />
  
 
=== Size 8 ===
 
=== Size 8 ===
Line 29: Line 46:
 
The outcomes for size 8 were computer generated by [[Javerberg]]. The solution was independently computer generated by Hayward et al. and appeared in [[INJCAI|IJCAI09]].
 
The outcomes for size 8 were computer generated by [[Javerberg]]. The solution was independently computer generated by Hayward et al. and appeared in [[INJCAI|IJCAI09]].
  
<hex>
+
<hexboard size="8x8"
R8 C8 Q1
+
  coords="show"
Ha1 Hb1 Hc1 Hd1 He1 Hf1 Hg1 Vh1
+
  contents="S red:all blue:(a1--g1 a2--f2 a3 a4 a6 b8--h8 c7--h7 h6 h5 h3)"
Ha2 Hb2 Hc2 Hd2 He2 Hf2 Vg2 Vh2
+
  />
Ha3 Vb3 Vc3 Vd3 Ve3 Vf3 Vg3 Hh3
+
Ha4 Vb4 Vc4 Vd4 Ve4 Vf4 Vg4 Vh4
+
Va5 Vb5 Vc5 Vd5 Ve5 Vf5 Vg5 Hh5
+
Ha6 Vb6 Vc6 Vd6 Ve6 Vf6 Vg6 Hh6
+
Va7 Vb7 Hc7 Hd7 He7 Hf7 Hg7 Hh7
+
Va8 Hb8 Hc8 Hd8 He8 Hf8 Hg8 Hh8
+
</hex>
+
  
 
=== Size 9 ===
 
=== Size 9 ===
Line 45: Line 55:
 
The outcomes for size 9 by Jakub Pawlewicz and Ryan Hayward.
 
The outcomes for size 9 by Jakub Pawlewicz and Ryan Hayward.
  
<hex>
+
<hexboard size="9x9"
R9 C9 Q1
+
  coords="show"
Ha1 Hb1 Hc1 Hd1 He1 Hf1 Hg1 Hh1 Vi1
+
  contents="S red:all blue:(a1--h1 d2--g2 a3 a7 b9--i9 c8--f8 i7 i3)"
Va2 Vb2 Vc2 Hd2 He2 Hf2 Hg2 Vh2 Vi2
+
  />
Ha3 Vb3 Vc3 Vd3 Ve3 Vf3 Vg3 Vh3 Hi3
+
 
Va4 Vb4 Vc4 Vd4 Ve4 Vf4 Vg4 Vh4 Vi4
+
=== Size 10 ===
Va5 Vb5 Vc5 Vd5 Ve5 Vf5 Vg5 Vh5 Vi5
+
 
Va6 Vb6 Vc6 Vd6 Ve6 Vf6 Vg6 Vh6 Vi6
+
The 10 &times; 10 board has not been solved, though one can make educated guesses from the swap maps of strong bots. In particular, according to the [https://pic1.zhimg.com/v2-43e07696b00949bb8ae177d3ddfd61c8_r.jpg swap map] of [[KataHex]], the outcomes for size 10 are as follows:
Ha7 Vb7 Vc7 Vd7 Ve7 Vf7 Vg7 Vh7 Hi7
+
 
Va8 Vb8 Hc8 Hd8 He8 Hf8 Vg8 Vh8 Vi8
+
<hexboard size="10x10"
Va9 Hb9 Hc9 Hd9 He9 Hf9 Hg9 Hh9 Hi9
+
  coords="show"
</hex>
+
  contents="S red:all blue:(a1--i1 a2--h2 a3 a8 b10--j10 c9--j9 j8 j3)
 +
            E *:(a1 b1 b9 f5 e6 i2 i10 j10)"
 +
  />
 +
 
 +
Only the cells marked "*" have been proven (by humans) to be winning or losing; the other cells are not completely certain. [[KataHex]] assigns a winning probability of at least 94.4% (in self-play) for every cell it believes is winning, and at most 2.6% for every cell it believes is losing. Note this does '''not''' mean that the bot is at least 94.4% sure of each cell's outcome, only that it thinks it has a 94.4% win rate with the winning side in self-play. However, the probabilities being so close to 0 and 1 suggest the bot is quite confident in its assessment.
  
 
== Reference ==
 
== Reference ==
* [[Queenbee]]'s opening [http://www.cs.ualberta.ca/~queenbee/openings.html page] is a reference for sizes under 6x6.
 
 
* This [http://www.ru.is/faculty/yngvi/pdf/HaywardBJKPR05.pdf article] by Ryan Hayward ''et al.'' is a reference for 7x7.
 
* This [http://www.ru.is/faculty/yngvi/pdf/HaywardBJKPR05.pdf article] by Ryan Hayward ''et al.'' is a reference for 7x7.
 
* This [[Little Golem]]'s forum [http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=338 thread] is a reference for size 8x8.
 
* This [[Little Golem]]'s forum [http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=338 thread] is a reference for size 8x8.
Line 67: Line 80:
  
 
* [[Board size]]
 
* [[Board size]]
* [[Jing Yang]] designed a [[decomposition method]] to find winning strategy in Hex. [http://www.ee.umanitoba.ca/~jingyang/index.html Home Page].
+
* Yang, Liao, and Pawlak designed a [https://webdocs.cs.ualberta.ca/~hayward/papers/yang7.pdf decomposition method] to find a winning strategy for Hex on small boards.
 
* For corresponding information on the game of Y, please visit [[Where to swap (y)]].
 
* For corresponding information on the game of Y, please visit [[Where to swap (y)]].
  
 
[[Category: Theory]]
 
[[Category: Theory]]

Latest revision as of 14:54, 18 November 2023

Playing Hex on boards of size smaller than 10 × 10 is not very interesting, since many players will be able to play almost perfectly. However it may still be interesting for theoretical studies, and for making problems.

The boards of size up to five can be solved by hand. Hex on 6 × 6 has been solved by Queenbee. The board sizes 7 to 9 have been solved with computer programs, too.

Here are the winning first moves on the small boards. Red is vertical and plays first. The cells shaded red are winning moves for red, while those shaded blue are losing.

Winner depending on the first move

The following boards can help you decide where you should swap when playing on small boards, and it might give you ideas of patterns for bigger boards.

ab12
abc123
abcd1234
abcde12345
abcdef123456

Size 7

Size 7 was first solved by Ryan Hayward using domination. The proof tree can be found at http://www.cs.ualberta.ca/~hayward/hex7trees/

abcdefg1234567

Size 8

The outcomes for size 8 were computer generated by Javerberg. The solution was independently computer generated by Hayward et al. and appeared in IJCAI09.

abcdefgh12345678

Size 9

The outcomes for size 9 by Jakub Pawlewicz and Ryan Hayward.

abcdefghi123456789

Size 10

The 10 × 10 board has not been solved, though one can make educated guesses from the swap maps of strong bots. In particular, according to the swap map of KataHex, the outcomes for size 10 are as follows:

abcdefghij12345678910

Only the cells marked "*" have been proven (by humans) to be winning or losing; the other cells are not completely certain. KataHex assigns a winning probability of at least 94.4% (in self-play) for every cell it believes is winning, and at most 2.6% for every cell it believes is losing. Note this does not mean that the bot is at least 94.4% sure of each cell's outcome, only that it thinks it has a 94.4% win rate with the winning side in self-play. However, the probabilities being so close to 0 and 1 suggest the bot is quite confident in its assessment.

Reference

  • This article by Ryan Hayward et al. is a reference for 7x7.
  • This Little Golem's forum thread is a reference for size 8x8.
  • This article by Jakub Pawlewicz and Ryan Hayward is a reference for size 9x9.

See also