Welcome to the home page of the computer Hex research group. We --- current and former members Chao Gao, Noah Weninger, Kenny Young, Kelly Li, Broderick Arneson, Phil Henderson, Ryan, Jakub, Aja Huang, David Spies, Jack van Rijswijck, Mike Johanson, Morgan Kan, Nathan Po, Maryia, Martha (Lednicky) White, Leah Hackman, 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 Schaeffer. Current projects include MoHex and Solver. Previous projects include Wolve, Mongoose and Queenbee.

For more on these news items, see Ryan's publications page below, or send him email.

news

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). An early version uses the RAVE(all moves as first) heuristic and lock-free parallelization. Versions of MoHex have won gold respectively at every Computer Games Olympiad since 2009. The first version 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. 9x9some.png

8x8 openings   8x8.png
The initial version of Solver was created by Ryan, Yngvi, Mike, Nathan, and Jack. In 2003 it solved all 7x7 openings.

7x7 openings   7x7.png

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.

code

reading

bibliography

feedback? email Ryan Hayward at lastname@ualberta.ca
last modified Tue 18 Jan 2022 02:59:21 PM MST
css style courtesy Gábor Melis; all other content © 2008--2012