Hex

Home * Games * Hex

A rendering of a Hex game on a 19x19 board

Hex,
a two-player zero-sum and perfect information abstract strategy, connection board game played on a hexagonal grid composed of hexagons arranged in an n × n orthodiagonal Quadrilateral, most common an 11x11, 13x13 or 19x19 Rhombus. The goal is to connect the opposing sides of own colors with own stones - or to prevent the opponent from doing so, by alternately placing stones on a single cell.

History

Hex was invented by the Danish mathematician Piet Hein called Polygon, appeared in the Danish newspaper Politiken on December 26, 1942, and independently by the American mathematician John Nash in 1947, who, according to the biography A Beautiful Mind, advocated 14x14 as the optimal size. In 1952 Parker Brothers marketed a version called Hex and the name stuck .

Since 2000, Computer Hex is regularly played at the Computer Olympiads. In 2003, 7x7 Hex was solved by Ryan Hayward, Yngvi Björnsson, Michael Johanson, Morgan Kan, Nathan Po, Jack van Rijswijck .

Computer Olympiads

• 5th Computer Olympiad, London 2000
• 8th Computer Olympiad, Graz 2003
• 9th Computer Olympiad, Ramat Gan 2004
• 11th Computer Olympiad, Turin 2006
• 13th Computer Olympiad, Beijing 2008
• 14th Computer Olympiad, Pamplona 2009
• 15th Computer Olympiad, Kanazawa 2010
• 16th Computer Olympiad, Tilburg 2011
• 17th Computer Olympiad, Yokohama 2013
• 18th Computer Olympiad, Leiden 2015
• 20th Computer Olympiad, Leiden 2017

Photos

Members of the Wolve Team at the Computer Olympiad, Turin 2006
Ryan Hayward, Philip Henderson and Broderick Arneson (operating Hex Kriger)

Hex Programs

Programs	Authors	Search Algorithm
Ezo Ezo-CNN	Kei Takada, Masaya Honjo, Hiroyuki Iizuka, Masahito Yamamoto	Alpha-Beta CNN
Hex Kriger	Rune Rasmussen, Cameron Browne, Auden Ellertsen, Ross Hayward, Frédéric Maire	Alpha-Beta
Hex Nash	Jeffrey Vanneste
Hexy	Vadim Anshelevich	Alpha-Beta
MIMHex	Jakub Pawlewicz	MCTS, RAVE UCT
MoHex	Philip Henderson, Broderick Arneson, Ryan Hayward Aja Huang, Jakub Pawlewicz, Noah Weninger, Kenny Young	MCTS, UCT, Solver
MoHex-CNN	Chao Gao, Philip Henderson, Broderick Arneson, Ryan Hayward Aja Huang, Jakub Pawlewicz, Noah Weninger, Kenny Young	MCTS, UCT, CNN, Solver
Mongoose	Ryan Hayward, Yngvi Björnsson, Michael Johanson	Alpha-Beta
Queenbee	Jack van Rijswijck	Alpha-Beta
Six	Gábor Melis	Alpha-Beta
Wolve	Ryan Hayward, Broderick Arneson, Philip Henderson, Michael Johanson, Morgan Kan, Martin Müller, Geoff Ryan	Alpha-Beta, Solver
Yopt	Abdallah Saffidine, Tristan Cazenave	MCTS, RAVE UCT

Publications

1953

• Claude E. Shannon (1953). Computers and Automata. Proceedings of the Institute of Radio Engineers, Vol. 41, No. 10

1959

• Martin Gardner (1959). The Game of Hex. in The Scientific American Book of Mathematical Puzzles and Diversions, pp. 73-83, Simon and Schuster

1977

• Claude Berge (1977). L'Art Subtil du Hex. (French) Supplied with a version of the game that was marketed in France in 1977

1980 ...

• Claude Berge (1981). Some remarks about the Hex problem. in David A. Klarner (ed): The Mathematical Gardner, pages 25-27. Wadsworth International, amazon.com
• Stefan Reisch (1981). Hex ist PSPACE-vollständig. Acta Informatica Vol. 15, No. 2 (German)
• Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (1988). Algorithms for Games. Springer-Verlag, New York, NY. ISBN 3-540-96629-3. amazon.com

2000 ...

• Vadim Anshelevich (2000). The Game of Hex: The Hierarchical Approach. Combinatorial Game Theory Workshop, MSRI, Berkeley, pdf
• Cameron Browne (2000). Hex Strategy: Making the Right Connections. A K Peters
• Jack van Rijswijck (2000). Computer Hex: Are Bees better than Fruitflies? M.Sc. Thesis, University of Alberta, pdf
• Vadim Anshelevich (2000). The Game of Hex: An Automatic Theorem Proving Approach to Game Programming. Proceedings of the Seventeenth National Conference on Artificial Intelligence, pdf
• Jack van Rijswijck (2000). Partition Search in Hex. 5th Computer Olympiad Workshop
• Vadim Anshelevich (2000). The Game of Hex: The Hierarchical Approach and its Discovery. 5th Computer Olympiad Workshop
• Vadim Anshelevich (2000). Hexy wins Hex Tournament. ICGA Journal, Vol. 23, No. 3
• Ian Stewart (2000). Hex Marks the Spot. Scientific American, September 2000

2001

• Jing Yang, Simon Liao, Mirek Pawlak (2001). On a Decomposition Method for Finding Winning Strategy in Hex Game. ADCOG21, pdf

2002

• Vadim Anshelevich (2002). A hierarchical approach to computer Hex. Artificial Intelligence, Chips challenging champions: games, computers and Artificial Intelligence, pdf
• Jing Yang, Simon Liao, Mirek Pawlak (2002). Another solution for Hex 7x7. Technical report, University of Manitoba. pdf
• Jing Yang, Simon Liao, Mirek Pawlak (2002). A New Solution for 7x7 Hex Game. pdf
• Jing Yang, Simon Liao, Mirek Pawlak (2002). New Winning and Losing Positions for 7x7 Hex. CG 2002, pdf

2003

• Jack van Rijswijck (2003). Search and evaluation in Hex. Technical report, University of Alberta, pdf
• Ryan Hayward, Yngvi Björnsson, Michael Johanson, Morgan Kan, Nathan Po, Jack van Rijswijck (2003). Solving 7x7 Hex: Virtual Connections and Game-state Reduction. Advances in Computer Games 10, pdf
• Gábor Melis, Ryan Hayward (2003). Six wins Hex Tournament (8th Computer Olympiad 2003 Graz). ICGA Journal, Vol. 26, No. 4, pdf » 8th Computer Olympiad
• Stefan Kiefer (2003). Die Menge der Virtuellen Verbindungen im Spiel Hex ist PSPACE-vollständig. Studienarbeit Nr. 1887, University of Stuttgart, pdf (German)

2004

• Rune Rasmussen, Frédéric Maire (2004). An Extension of the H-Search Algorithm for Artificial Hex Players. AI'2004, pdf
• Jan Willemson, Yngvi Björnsson (2004). Six wins hex tournament. ICGA Journal, Vol. 27, No. 3 » 9th Computer Olympiad

2005 ...

• Kohei Noshita (2005). Union-Connections and Straightforward Winning Strategies in Hex. ICGA Journal, Vol. 28, No. 1, companion document 2006 as pdf
• Ryan Hayward, Yngvi Björnsson, Michael Johanson, Morgan Kan, Nathan Po, Jack van Rijswijck (2005). Solving 7x7 Hex with domination, fill-in, and virtual connections. Theoretical Computer Science, 349(2):123–139, 2005. pdf
• Thomas Maarup (2005) Everything You Always Wanted to Know About Hex But Were Afraid to Ask. Masters thesis, University of Southern Denmark, pdf

2006

• Yngvi Björnsson, Ryan Hayward, Michael Johanson, Jack van Rijswijck (2006). Dead Cell Analysis in Hex and the Shannon Game. In Graph Theory in Paris: Proceedings of a Conference in Memory of Claude Berge (CT'04 Paris), pp. 45–60, 2006. zipped ps
• Ryan Hayward, Jack van Rijswijck (2006). Hex and Combinatorics. Discrete Math 306, pdf
• Rune Rasmussen, Frédéric Maire, Ross Hayward (2006). A Move Generating Algorithm for Hex Solvers. pdf
• Jack van Rijswijck (2006). Set Colouring Games. Ph.D. thesis, University of Alberta, pdf
• Ryan Hayward (2006). Six Wins Hex tournament. ICGA Journal, Vol. 29, No 3, pdf » 11th Computer Olympiad
• Ryan Hayward, Broderick Arneson, Philip Henderson (2006). Automatic Strategy Verification for Hex. CG 2006, pdf

2007

• Rune Rasmussen (2007). Algorithmic Approaches for Playing and Solving Shannon Games. Ph.D. thesis, University of Queensland, pdf
• Rune Rasmussen, Frédéric Maire, Ross Hayward (2007). A Template Matching Table for Speeding-Up Game-Tree Searches for Hex. 20th Australian Joint Conference on Artificial Intelligence
• Jing Yang, Simon Liao, Mirek Pawlak (2007). Apply Heuristic Search to Discover a New Winning Solution in Hex Game. Proceedings of the Fourth International Conference on Fuzzy Systems and Knowledge Discovery - Volume 04

2008

• Philip Henderson, Ryan Hayward (2008). Probing the 4-3-2 Edge Template in Hex. CG 2008, pdf

2009

• Broderick Arneson, Ryan Hayward, Philip Henderson (2009). Wolve 2008 wins Hex tournament. ICGA Journal, Vol. 32, No. 1 » 13th Computer Olympiad
• Philip Henderson, Broderick Arneson, Ryan Hayward (2009). Solving 8×8 Hex. IJCAI-09, pdf
• Broderick Arneson, Ryan Hayward, Philip Henderson (2009). MoHex wins Hex tournament. ICGA Journal, Vol. 32, No. 2, pdf » 14th Computer Olympiad

2010 ...

• Philip Henderson, Broderick Arneson, Ryan Hayward (2010). Hex, Braids, the Crossing Rule, and XH-Search. Advances in Computer Games 12, pdf
• Tristan Cazenave, Abdallah Saffidine (2010). Monte-Carlo Hex. pdf
• Broderick Arneson, Ryan Hayward, Philip Henderson (2010). MoHex wins Hex Tournament. ICGA Journal, Vol. 33, No. 3, pdf » 15th Computer Olympiad
• Broderick Arneson, Ryan Hayward, Philip Henderson (2010). Solving Hex: Beyond Humans. CG 2010, pdf
• Broderick Arneson, Ryan Hayward, Philip Henderson (2010). Monte Carlo Tree Search in Hex. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 2, No. 4, pdf
• Philip Henderson (2010). Playing and Solving the Game of Hex. (Ph.D. thesis under committee review ), pdf

2011

• Henry Brausen, Ryan Hayward, Martin Müller, Abdul Qadir, David Spies (2011). Blunder Cost in Go and Hex. Advances in Computer Games 13

2012

• Ryan Hayward (2012). MoHex wins Hex Tournament. ICGA Journal, Vol. 35, No. 2 » 16th Computer Olympiad

2013

• Ryan Hayward, Broderick Arneson, Shih-Chieh Huang, Jakub Pawlewicz (2013). MOHEX Wins Hex Tournament. ICGA Journal, Vol. 36, No. 3, pdf » 17th Computer Olympiad
• Shih-Chieh Huang, Broderick Arneson, Ryan Hayward, Martin Müller, Jakub Pawlewicz (2013). MoHex 2.0: a pattern-based MCTS Hex player. CG 2013, pdf

2015 ...

• Xi Liang (2015). Job-Level Search for Solving Hex. Master's thesis, National Chiao Tung University, advisor I-Chen Wu
• Xi Liang, Ting-Han Wei, I-Chen Wu (2015). Job-level UCT search for solving Hex. CIG 2015
• Kei Takada, Masaya Honjo, Hiroyuki Iizuka, Masahito Yamamoto (2015). Developing Computer Hex using Global and Local Evaluation based on Board Network Characteristics. Advances in Computer Games 14
• Kei Takada, Masaya Honjo, Hiroyuki Iizuka, Masahito Yamamoto (2015). Developing Evaluation Function of Hex using Board Network Characteristics and SVM. Transactions of the Japanese Society for Artificial Intelligence, Vol. 30, No. 6
• S. Ali Mirsoleimani, Aske Plaat, Jaap van den Herik, Jos Vermaseren (2015). Scaling Monte Carlo Tree Search on Intel Xeon Phi. CoRR abs/1507.04383 » MCTS, Parallel Search, x86-64
• S. Ali Mirsoleimani, Aske Plaat, Jaap van den Herik, Jos Vermaseren (2015). Parallel Monte Carlo Tree Search from Multi-core to Many-core Processors. TrustCom/BigDataSE/|ISPA 2015, pdf
• Xi Liang, Ting-Han Wei, I-Chen Wu (2015). Solving Hex Openings Using Job-Level UCT Search. ICGA Journal, Vol. 38, No. 3
• Jakub Pawlewicz, Ryan Hayward (2015). Sibling Conspiracy Number Search. SoCS 2015

2016

• Kenny Young, Ryan Hayward (2016). A Reverse Hex Solver. CG 2016
• Jakub Pawlewicz, Ryan Hayward (2016). Conspiracy number search with relative sibling scores. Theoretical Computer Science, Vol. 644

2017

• Ryan Hayward, Jakub Pawlewicz, Kei Takada, Tony van der Valk (2017). MOHEX Wins 2015 Hex 11x11 and Hex 13x13 Tournaments. ICGA Journal, Vol. 39, No. 1 » 18th Computer Olympiad
• Ryan Hayward, Noah Weninger (2017). Hex 2017: MoHex wins the 11x11 and 13x13 tournaments. ICGA Journal, Vol. 39, Nos. 3-4 » 20th Computer Olympiad 2017
• Kei Takada, Hiroyuki Iizuka, Masahito Yamamoto (2017). Reinforcement Learning for Creating Evaluation Function Using Convolutional Neural Network in Hex. TAAI 2017
• Kei Takada, Hiroyuki Iizuka, Masahito Yamamoto (2017). Computer Hex Algorithm Using a Move Evaluation Method Based on a Convolutional Neural Network. CGW@IJCAI 2017
• Chao Gao, Martin Müller, Ryan Hayward (2017). Focused Depth-first Proof Number Search using Convolutional Neural Networks for the Game of Hex. IJCAI 2017

2018

• Kei Takada, Hiroyuki Iizuka, Masahito Yamamoto (2018). Computer Hex Algorithm Using a Move Evaluation Method Based on a Convolutional Neural Network. Communications in Computer and Information Science
• Chao Gao, Siqi Yan, Ryan Hayward, Martin Müller (2018). A transferable neural network for Hex. CG 2018, ICGA Journal, Vol. 40, No. 3
• François Bonnet (2018). Winning strategies in DarkHex: Hex with hidden stones. CG 2018, ICGA Journal, Vol. 40, No. 3

2019

• Chao Gao, Kei Takada, Ryan Hayward (2019). Hex 2018: MoHex3HNN over DeepEzo. ICGA Journal, Vol. 41, No. 1 » 21st Computer Olympiad 2018
• Nicolas Fabiano, Ryan Hayward (2019). New Hex Patterns for Fill and Prune. Advances in Computer Games 16

Forum Posts

• bitboard algorithm needed by Daniel Shawul, CCC, July 08, 2011
• Re: Possible Search Algorithms for GPUs? by Daniel Shawul, CCC, January 07, 2012 » GPU, Flood Fill Algorithms

External Links

• Hex (board game) from Wikipedia
• HexWiki
• Sensei's Library: Hex
• Hex (ICGA Tournaments)
• ICGA: Hex by Vadim Anshelevich
• University of Alberta Computer Hex Research Group
• hex - javhar1 by Jack van Rijswijck
• Hex by Thomas Maarup
• About Hex from MazeWorks - Java Games and Puzzles
• The abstract board game Hex by Tijs Krammer
• HEX: Answers to common questions by David Boll
• Answers to infrequently asked questions about the game of Hex by Bert Enderton
• Kwaku Ananse: Hex by Ralf Poschmann (German)
• Little Golem - online board games by Richard Malaschitz
• Little Golem - FAQ by Edward D. Collins
• Sechseckpflaster (German) a little off topic, may be for outdoor Hex ...
• Hexagonal chess from Wikipedia
• Sannin shogi from Wikipedia

References

Up one Level