On Wednesday 20th February 2019 the Game AI Group will host a seminar by Ryan Hayward from the University of Alberta.
Time: 4pm to 5pm, Feb 20, 2019
Room: BR 3.02, Bancroft Road Teaching Rooms, QMUL Mile End Campus
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.
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.
Ryan lives in Edmonton where he commutes year-round by recumbent bike.