Difference between revisions of "Hex"

From Chessprogramming wiki
Jump to: navigation, search
(One intermediate revision by the same user not shown)
Line 88: Line 88:
  
 
=Publications=  
 
=Publications=  
<ref>[http://sites.google.com/site/javhar1/hexbibliography Hex bibliography] by [[Jack van Rijswijck]]</ref> <ref>[http://sites.google.com/site/javhar1/javharpublications Javhar publications] by [[Jack van Rijswijck]]</ref>  
+
<ref>https://sites.google.com/site/javhar1/hexbibliography Hex bibliography] by [[Jack van Rijswijck]]</ref> <ref>[https://sites.google.com/site/javhar1/javharpublications Javhar publications] by [[Jack van Rijswijck]]</ref>  
 
==1953==  
 
==1953==  
* [[Claude Shannon|Claude E. Shannon]] ('''1953'''). ''[http://www.jnorman.com/cgi-bin/hss/38411 Computers and Automata]''. Proceedings of the Institute of Radio Engineers Vol. 41, No. 10 <ref>In [[Vadim Anshelevich]] ('''2002'''). ''[http://portal.acm.org/citation.cfm?id=512148.512154&coll=DL&dl=GUIDE&CFID=19278566&CFTOKEN=41682182 A hierarchical approach to computer Hex]''. Artificial Intelligence - Chips challenging champions: games, computers and Artificial Intelligence, [http://home.earthlink.net/~vanshel/VAnshelevich-ARTINT.pdf pdf], [[Vadim Anshelevich]] acknowledged [[Claude Shannon]], who build an analogue Hex-playing machine using electrical [https://en.wikipedia.org/wiki/Resistor resistor] circuits, which was model in Anshelevich's program [https://www.game-ai-forum.org/icga-tournaments/program.php?id=131 Hexy]</ref> <ref>[[Hex]] is a special case of the [https://en.wikipedia.org/wiki/Shannon_switching_game Shannon Switching Game], from [[Jack van Rijswijck]] ('''2003'''). ''Search and evaluation in Hex''. Technical report, [[University of Alberta]], [http://home.fuse.net/swmeyers/y-hex.pdf pdf]</ref> <ref>[http://www.althofer.de/3-hirn-grant--fischer.html Thomas Fischer] ('''2009'''). ''Bridg-It – Beating Shannon’s Analog Heuristic''. [http://www.minet.uni-jena.de/Math-Net/reports/sources/2009/09-07report.pdf pdf]</ref>
+
* [[Claude Shannon|Claude E. Shannon]] ('''1953'''). ''[https://ieeexplore.ieee.org/document/4051186 Computers and Automata]''. [https://en.wikipedia.org/wiki/Institute_of_Radio_Engineers Proceedings of the Institute of Radio Engineers], Vol. 41, No. 10 <ref>In [[Vadim Anshelevich]] ('''2002'''). ''[https://www.sciencedirect.com/science/article/pii/S0004370201001540 A hierarchical approach to computer Hex]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Chips challenging champions: games, computers and Artificial Intelligence, [https://www.cs.auckland.ac.nz/courses/compsci767s2c/resources/VAnshelevich-ARTINT.pdf pdf], [[Vadim Anshelevich]] acknowledged [[Claude Shannon]], who build an analogue Hex-playing machine using electrical [https://en.wikipedia.org/wiki/Resistor resistor] circuits, which was model in Anshelevich's program [https://www.game-ai-forum.org/icga-tournaments/program.php?id=131 Hexy]</ref> <ref>[[Hex]] is a special case of the [https://en.wikipedia.org/wiki/Shannon_switching_game Shannon Switching Game], from [[Jack van Rijswijck]] ('''2003'''). ''Search and evaluation in Hex''. Technical report, [[University of Alberta]], [http://home.fuse.net/swmeyers/y-hex.pdf pdf]</ref> <ref>[http://www.althofer.de/3-hirn-grant--fischer.html Thomas Fischer] ('''2009'''). ''Bridg-It – Beating Shannon’s Analog Heuristic''. [http://www.minet.uni-jena.de/Math-Net/reports/sources/2009/09-07report.pdf pdf]</ref>
 
==1959==  
 
==1959==  
* [[Martin Gardner]] ('''1959'''). ''The Game of Hex''. in ''[http://www.librarything.com/work/5317022 The Scientific American Book of Mathematical Puzzles and Diversions]''. pp 73-83.[https://en.wikipedia.org/wiki/Simon_%26_Schuster Simon & Schuster]
+
* [[Martin Gardner]] ('''1959'''). ''The Game of Hex''. in ''[https://archive.org/details/scientificameric00gard The Scientific American Book of Mathematical Puzzles and Diversions]'', pp. 73-83, [https://en.wikipedia.org/wiki/Simon_%26_Schuster Simon and Schuster]
 
==1977==  
 
==1977==  
 
* [[Mathematician#CBerge|Claude Berge]] ('''1977'''). ''L'Art Subtil du Hex''. (French) Supplied with a version of the game that was marketed in France in 1977
 
* [[Mathematician#CBerge|Claude Berge]] ('''1977'''). ''L'Art Subtil du Hex''. (French) Supplied with a version of the game that was marketed in France in 1977
Line 100: Line 100:
 
* [[Georgy Adelson-Velsky]], [[Vladimir Arlazarov]], [[Mikhail Donskoy]] ('''1988'''). ''Algorithms for Games''. Springer-Verlag, New York, NY. ISBN 3-540-96629-3. [http://www.amazon.com/Algorithms-Games-Georgy-M-Adelson-Velsky/dp/0387966293 amazon.com]
 
* [[Georgy Adelson-Velsky]], [[Vladimir Arlazarov]], [[Mikhail Donskoy]] ('''1988'''). ''Algorithms for Games''. Springer-Verlag, New York, NY. ISBN 3-540-96629-3. [http://www.amazon.com/Algorithms-Games-Georgy-M-Adelson-Velsky/dp/0387966293 amazon.com]
 
==2000 ...==  
 
==2000 ...==  
* [[Vadim Anshelevich]] ('''2000'''). ''[http://www.msri.org/realvideo/ln/msri/2000/gametheory/anshelevich/1/index.html The Game of Hex: The Hierarchical Approach]''. Combinatorial Game Theory Workshop, [https://en.wikipedia.org/wiki/Mathematical_Sciences_Research_Institute MSRI, Berkeley]
+
* [[Vadim Anshelevich]] ('''2000'''). ''[http://www.msri.org/workshops/104/schedules/12860 The Game of Hex: The Hierarchical Approach]''. Combinatorial Game Theory Workshop, [https://en.wikipedia.org/wiki/Mathematical_Sciences_Research_Institute MSRI, Berkeley], [http://library.msri.org/books/Book42/files/anshel.pdf pdf]
 
* [[Cameron Browne]] ('''2000'''). ''[http://www.crcpress.com/product/isbn/9781568811178 Hex Strategy: Making the Right Connections]''. [https://en.wikipedia.org/wiki/A_K_Peters,_Ltd. A K Peters]
 
* [[Cameron Browne]] ('''2000'''). ''[http://www.crcpress.com/product/isbn/9781568811178 Hex Strategy: Making the Right Connections]''. [https://en.wikipedia.org/wiki/A_K_Peters,_Ltd. A K Peters]
 
* [[Jack van Rijswijck]] ('''2000'''). ''Computer Hex: Are Bees better than Fruitflies?'' M.Sc. Thesis, [[University of Alberta]], [http://sites.google.com/site/javhar1/AreBeesBetterThanFruitfliesThesis.pdf pdf]
 
* [[Jack van Rijswijck]] ('''2000'''). ''Computer Hex: Are Bees better than Fruitflies?'' M.Sc. Thesis, [[University of Alberta]], [http://sites.google.com/site/javhar1/AreBeesBetterThanFruitfliesThesis.pdf pdf]
Line 106: Line 106:
 
* [[Jack van Rijswijck]] ('''2000'''). ''Partition Search in Hex''. [[5th Computer Olympiad#Workshop|5th Computer Olympiad Workshop]]  
 
* [[Jack van Rijswijck]] ('''2000'''). ''Partition Search in Hex''. [[5th Computer Olympiad#Workshop|5th Computer Olympiad Workshop]]  
 
* [[Vadim Anshelevich]] ('''2000'''). ''The Game of Hex: The Hierarchical Approach and its Discovery''. [[5th Computer Olympiad#Workshop|5th Computer Olympiad Workshop]]
 
* [[Vadim Anshelevich]] ('''2000'''). ''The Game of Hex: The Hierarchical Approach and its Discovery''. [[5th Computer Olympiad#Workshop|5th Computer Olympiad Workshop]]
* [[Vadim Anshelevich]] ('''2000'''). ''Hexy wins Hex Tournament''. [[ICGA Journal#23_3|ICGA Journal, Vol. 23, No. 3]], [http://home.earthlink.net/%7Evanshel/Ansh-MSO-Results.pdf pdf]
+
* [[Vadim Anshelevich]] ('''2000'''). ''Hexy wins Hex Tournament''. [[ICGA Journal#23_3|ICGA Journal, Vol. 23, No. 3]]
 
* [[Mathematician#IStewart|Ian Stewart]] ('''2000'''). ''Hex Marks the Spot''. [https://en.wikipedia.org/wiki/Scientific_American Scientific American], September 2000
 
* [[Mathematician#IStewart|Ian Stewart]] ('''2000'''). ''Hex Marks the Spot''. [https://en.wikipedia.org/wiki/Scientific_American Scientific American], September 2000
 
'''2001'''
 
'''2001'''
 
* [[Jing Yang]], [[Simon Liao]], [[Mirek Pawlak]] ('''2001'''). ''On a Decomposition Method for Finding Winning Strategy in Hex Game''. ADCOG21, [http://zernike.uwinnipeg.ca/~s_liao/pdf/adcog21.pdf pdf]
 
* [[Jing Yang]], [[Simon Liao]], [[Mirek Pawlak]] ('''2001'''). ''On a Decomposition Method for Finding Winning Strategy in Hex Game''. ADCOG21, [http://zernike.uwinnipeg.ca/~s_liao/pdf/adcog21.pdf pdf]
 
'''2002'''
 
'''2002'''
* [[Vadim Anshelevich]] ('''2002'''). ''[http://portal.acm.org/citation.cfm?id=512148.512154&coll=DL&dl=GUIDE&CFID=19278566&CFTOKEN=41682182 A hierarchical approach to computer Hex]''. Artificial Intelligence - Chips challenging champions: games, computers and Artificial Intelligence, [http://home.earthlink.net/%7Evanshel/VAnshelevich-ARTINT.pdf pdf]
+
* [[Vadim Anshelevich]] ('''2002'''). ''[https://www.sciencedirect.com/science/article/pii/S0004370201001540 A hierarchical approach to computer Hex]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Chips challenging champions: games, computers and Artificial Intelligence, [https://www.cs.auckland.ac.nz/courses/compsci767s2c/resources/VAnshelevich-ARTINT.pdf pdf]
 
* [[Jing Yang]], [[Simon Liao]], [[Mirek Pawlak]] ('''2002'''). ''Another solution for Hex 7x7''. Technical report, [https://en.wikipedia.org/wiki/University_of_Manitoba University of Manitoba]. [http://hex.kosmanor.com/hex/Papers/ylp-TR.pdf pdf]
 
* [[Jing Yang]], [[Simon Liao]], [[Mirek Pawlak]] ('''2002'''). ''Another solution for Hex 7x7''. Technical report, [https://en.wikipedia.org/wiki/University_of_Manitoba University of Manitoba]. [http://hex.kosmanor.com/hex/Papers/ylp-TR.pdf pdf]
 
* [[Jing Yang]], [[Simon Liao]], [[Mirek Pawlak]] ('''2002'''). ''A New Solution for 7x7 Hex Game''. [http://hex.kosmanor.com/hex/Papers/cg02-ylp02.pdf pdf]
 
* [[Jing Yang]], [[Simon Liao]], [[Mirek Pawlak]] ('''2002'''). ''A New Solution for 7x7 Hex Game''. [http://hex.kosmanor.com/hex/Papers/cg02-ylp02.pdf pdf]
Line 169: Line 169:
 
'''2016'''
 
'''2016'''
 
* [[Kenny Young]], [[Ryan Hayward]] ('''2016'''). ''A Reverse Hex Solver''. [[CG 2016]]
 
* [[Kenny Young]], [[Ryan Hayward]] ('''2016'''). ''A Reverse Hex Solver''. [[CG 2016]]
 +
* [[Jakub Pawlewicz]], [[Ryan Hayward]] ('''2016'''). ''[https://www.sciencedirect.com/science/article/pii/S0304397516302729 Conspiracy number search with relative sibling scores]''. [https://en.wikipedia.org/wiki/Theoretical_Computer_Science_(journal) Theoretical Computer Science], Vol. 644
 
'''2017'''
 
'''2017'''
 
* [[Ryan Hayward]], [[Jakub Pawlewicz]], [[Kei Takada]], [[Tony van der Valk]] ('''2017'''). ''MOHEX Wins 2015 Hex 11x11 and Hex 13x13 Tournaments''. [[ICGA Journal#39_1|ICGA Journal, Vol. 39, No. 1]] » [[18th Computer Olympiad#Hex|18th Computer Olympiad]]
 
* [[Ryan Hayward]], [[Jakub Pawlewicz]], [[Kei Takada]], [[Tony van der Valk]] ('''2017'''). ''MOHEX Wins 2015 Hex 11x11 and Hex 13x13 Tournaments''. [[ICGA Journal#39_1|ICGA Journal, Vol. 39, No. 1]] » [[18th Computer Olympiad#Hex|18th Computer Olympiad]]
Line 190: Line 191:
 
* [http://senseis.xmp.net/?Hex Sensei's Library: Hex]
 
* [http://senseis.xmp.net/?Hex Sensei's Library: Hex]
 
* [https://www.game-ai-forum.org/icga-tournaments/game.php?id=7 Hex (ICGA Tournaments)]
 
* [https://www.game-ai-forum.org/icga-tournaments/game.php?id=7 Hex (ICGA Tournaments)]
* [http://ilk.uvt.nl/icga/games/hex/ ICGA: Hex] by [[Vadim Anshelevich]]
+
* [https://icga.org/icga/games/hex/ ICGA: Hex] by [[Vadim Anshelevich]]
 
* [http://webdocs.cs.ualberta.ca/%7Ehayward/hex/ University of Alberta Computer Hex Research Group]
 
* [http://webdocs.cs.ualberta.ca/%7Ehayward/hex/ University of Alberta Computer Hex Research Group]
 
* [http://sites.google.com/site/javhar1/hex hex - javhar1] by [[Jack van Rijswijck]]
 
* [http://sites.google.com/site/javhar1/hex hex - javhar1] by [[Jack van Rijswijck]]

Revision as of 11:08, 2 February 2020

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. https://sites.google.com/site/javhar1/hexbibliography 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