On Wednesday 20th February 2019 the Game AI Group will host a seminar by Ryan Hayward from the University of Alberta.
Title: Solving 10×10 Hex
Speaker: Ryan Hayward, University of Alberta
Time: 4pm to 5pm, Feb 20, 2019
Room: BR 3.02, Bancroft Road Teaching Rooms, QMUL Mile End Campus
Time: 4pm to 5pm, Feb 20, 2019
Room: BR 3.02, Bancroft Road Teaching Rooms, QMUL Mile End Campus
Followed by drinks in the Informatics Hub.
All welcome (especially students), no pre-booking required.
Abstract
In late winter 1949 John Nash bumped into David Gale in Princeton told him about a game — now called Hex — for which (unlike with chess or Go) he could prove that the first player has a winning strategy. After hearing Nash’s description of the game, Gale built a board that he left in the math department’s common room, where it became popular. Eventually it caught the attention of Claude Shannon, who built 2 Hex-playing machines, and Martin Gardner, who wrote about it in his Mathematical Games column in Scientific American.
Nash’s proof is existential, and gives little information about how to find explicit strategies. You might try this problem for yourself: on nxn boards up to 5×5, finding a first player winning strategy is easy. 6×6 is more challenging, and the problem gets harder as n grows. (Finding particular winning strategies for arbitrary positions is P-space-complete. Finding arbitrary strategies for the empty-board position might be easier.)
In this talk I will summarize the ideas that went into finding an (almost completely) explicit strategy for the first-player on the 10×10 board, and then say a few words about what it would take to solve 11×11.
This is joint work with Broderick Arneson, Phil Henderson, Aja Huang and Jakub Pawlewicz.
Nash’s proof is existential, and gives little information about how to find explicit strategies. You might try this problem for yourself: on nxn boards up to 5×5, finding a first player winning strategy is easy. 6×6 is more challenging, and the problem gets harder as n grows. (Finding particular winning strategies for arbitrary positions is P-space-complete. Finding arbitrary strategies for the empty-board position might be easier.)
In this talk I will summarize the ideas that went into finding an (almost completely) explicit strategy for the first-player on the 10×10 board, and then say a few words about what it would take to solve 11×11.
This is joint work with Broderick Arneson, Phil Henderson, Aja Huang and Jakub Pawlewicz.
Biography
Ryan Hayward received his B.Sc. and M.Sc. in mathematics from Queen’s University (Kingston) in 1981 and 1982 and his Ph.D.in computer science from McGill University in 1987. His doctoral thesis, Two Classes of Perfect Graphs, was supervised by Vasek Chvatal. From 1986 through 1989 he was assistant professor in the Department of Computer Science at Rutgers University, after which he held an Alexander von Humboldt fellowship at the Institute for Discrete Mathematics in Bonn for 1989-90. From 1990 through 1992 he was assistant professor in the Department of Computing Science at Queen’s University. From 1992 he was assistant and then associate professor in the Department of Mathematics and Computer Science at the University of Lethbridge, until in 1999 joining the Department of Computing Science at the University of Alberta, where he was promoted to professor in 2004.
He has supervised 13 graduate and 29 undergraduate students,some of whom later became university professors. His current research interests include algorithms for two-player games. His group (including at times Yngvi Bjornsson, Michael Johanson, Broderick Arneson, Philip Henderson, Jakub Pawlewicz, and Aja Huang — later lead programmer of AlphaGo) has built the world’s strongest computer Hex player, and has solved two 1-move 10×10 Hex openings and all smaller-board openings.
With Bjarne Toft, he wrote “Hex, the full story”, published by Taylor-Francis in 2019.
He has supervised 13 graduate and 29 undergraduate students,some of whom later became university professors. His current research interests include algorithms for two-player games. His group (including at times Yngvi Bjornsson, Michael Johanson, Broderick Arneson, Philip Henderson, Jakub Pawlewicz, and Aja Huang — later lead programmer of AlphaGo) has built the world’s strongest computer Hex player, and has solved two 1-move 10×10 Hex openings and all smaller-board openings.
With Bjarne Toft, he wrote “Hex, the full story”, published by Taylor-Francis in 2019.
https://webdocs.cs.ualberta.ca/~hayward/hexcoupon.pdf
Ryan lives in Edmonton where he commutes year-round by recumbent bike.
Ryan lives in Edmonton where he commutes year-round by recumbent bike.