Welcome to the home page of the computer Hex research group. We --- Broderick, Phil, Ryan, Jakub, Aja, David (and previously Jack, Mike, Morgan, Nathan Po, Maryia, Martha, Leah, Yngvi, Geoff Ryan, and Robert Budac) --- build Hex players and solvers. The group informally dates from 1999, when Jack, who wrote Queenbee, started an MSc with Jonathan. Current projects include Wolve, MoHex, and Solver. Previous projects include Mongoose and Queenbee.
- Nov 2011 MoHex and Wolve win gold and silver at the 16th Computer Games Olympiad in Tilburg, ahead of Panoramex.
- Sep 2010 MoHex and Wolve win gold and silver at the 15th Computer Games Olympiad in Kanazawa, ahead of MimHex and Yopt. Our paper "Solving Hex: Beyond Humans" (see Ryan's pub'ns below) wins the CG 2010 Conference best paper award.
- May 2010 Many 9x9 Hex openings are solved, as shown below. Solver enhancements behind this result will be presented at the CG 2010 conference in Kanazawa.
- May 2009 MoHex and Wolve win gold and silver at the 14th Computer Games Olympiad in Pamplona, ahead of Six and Yopt.
- Mar 2009 8x8 Hex is solved. Solver can find the winner of all 8x8 openings in under two weeks.
- Sep 2008 Wolve and MoHex win gold and silver at the 13th Computer Games Olympiad in Beijing ahead of three-time gold medallist Six and by Gábor Melis and newcomer Yopt by Tristan Cazenave and Addallah Saffidine. Here's a photo of the Wolve/MoHex authors.
Wolve is a "traditional" (alpha-beta search) Hex player. At each search tree node, it computes virtual connections using Anshelevich and/or combining rules. It prunes moves that are provably inferior or not in the mustplay. It finds inferior moves by iterated local pattern matching and a generic pattern search. Its evaluation function is based on an electical circuit model similar to that used by Gábor Melis's player Six. The 2008 version uses a truncated 2-ply search, and spends some time each move trying to solve the game. Wolve won silver/silver/gold/silver respectively at the '10/'09/'08/'06 Computer Games Olympiads. Wolve was rewritten in 2007-9 by Broderick with assistance from Philip and Ryan. Wolve 2006, written by Broderick, Phil, Mike, Morgan, Geoff, and Yngvi with assistance from Ryan and Martin Müller, is a revised version of Mongoose.
MoHex is a Monte Carlo UCT Hex player. In the UCT search tree it prunes moves via virtual connection and inferior cell information similar to that used by Wolve; it also handles solved states. In playouts it uses only one local pattern (preserving a threatened bridge analogous to the miai move in Go). It uses the RAVE(all moves as first) heuristic and lock-free parallelization. MoHex won gold/gold/silver respectively at the '10/'09/'08 Computer Games Olympiads. MoHex was written 2007-10 by Philip and Broderick with Ryan.
Solver is our Hex solver, rewritten 2007-10 by Broderick with Philip and Ryan. As of May 2010 Solver can solve many 9x9 openings (see below) in at most one month per opening, all 8x8 openings in 30 hours, and all 7x7 openings in 10 minutes. For more details, see "Solving 8x8 Hex" on Ryan's publications page below.
|9x9 openings. Black opens at each cell. Colour (black/white) shows outcome for Black (win/loss). Empty cells are not yet solved.|
Mongoose is the predecessor of Wolve, created by Mike, Morgan, Nathan, Maryia, and Ryan starting in 2001. Mongoose won silver at each of the Graz 2003, Ramat Gan 2004, and Turin 2006 Computer Games Olympiad.
Queenbee is an alpha-beta search Hex player and solver written by Jack van Rijswijck. Queenbee won silver at the London 2000 CGO. Queenbee's home page includes all winning openings for board sizes up to 6x6.
Hex is the classic two-player connection game invented by Piet Hein in 1942 and independently John Nash in 1948, and popularized by Martin Gardner in his Scientific American Mathematical Games column in 1957. See the reading for more info.
Computer Hex has existed since around 1950 when E.F. Moore and Claude Shannon built an electrical resistance network to play the game. Computer Hex programs have competed at the Computer Games Olympiad since 2000.
The Computer Games Olympiad is the annual competition of the International Computer Games Association (ICGA). There were CGO Hex competitions in London 2000, Graz 2003, Ramat-Gan 2004, Turin 2006, Beijing 2008, Pamplona 2009, Kanazawa 2010, and Tilburg 2011. Here are summaries of the 2003, 2006, 2008, 2009, 2010, and 2011 competitions. See the ICGA Tournament Database for more info.
- benzene @ sourceforge is the repository for our open-source code, including 2011 versions of mohex, wolve, and solver
- hex (board game) @ wikipedia
- hex webpage by Thomas Maarup
- basic, intermediate, and advanced strategy guides
- Hex strategy: making the right connections by Cameron Browne
- connection games by Cameron Browne
- mudcrack Y and poly-Y by Craige Schensted and Charles Titus (still available from kadon games) by Glenn Rhoads
feedback? email Ryan Hayward at firstname.lastname@example.org last modified Fri 19 Oct 2012 14:43:39 MDT
css style courtesy Gábor Melis; all other content © 2008--2012