Hex

From Chessprogramming wiki
Jump to: navigation, search

Home * Games * Hex

A rendering of a Hex game on a 19x19 board [1]

Hex,
a two-player zero-sum and perfect information abstract strategy, connection board game played on a hexagonal grid composed of hexagons [2] 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 [3] .

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 [4] .

Computer Olympiads

Photos

WolveTeam2.JPG

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

HexKrigerWolve.JPG

Hex Programs

[6]

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

[7] [8]

1953

1959

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 ...

2000 ...

2001

2002

2003

2004

2005 ...

2006

2007

2008

2009

2010 ...

2011

2012

2013

2015 ...

2016

2017

2018

Forum Posts

External Links

References

  1. Hex (board game) from Wikipedia
  2. Honeycomb from Wikipedia
  3. History of Hex - HexWiki
  4. 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
  5. Ryan Hayward (2006). Six Wins Hex Tournament. ICGA Journal, Vol. 29, No 3, pdf
  6. Hex (ICGA Tournaments)
  7. Hex bibliography by Jack van Rijswijck
  8. Javhar publications by Jack van Rijswijck
  9. In Vadim Anshelevich (2002). A hierarchical approach to computer Hex. Artificial Intelligence - Chips challenging champions: games, computers and Artificial Intelligence, pdf, Vadim Anshelevich acknowledged Claude Shannon, who build an analogue Hex-playing machine using electrical resistor circuits, which was model in Anshelevich's program Hexy
  10. Hex is a special case of the Shannon Switching Game, from Jack van Rijswijck (2003). Search and evaluation in Hex. Technical report, University of Alberta, pdf
  11. Thomas Fischer (2009). Bridg-It – Beating Shannon’s Analog Heuristic. pdf
  12. PSPACE from Wikipedia
  13. PSPACE-complete from Wikipedia
  14. AAAI-2000 Outstanding Paper Awards
  15. Philip Henderson's Research Page

Up one Level