[Seminar] Solving 10×10 Hex

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
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.
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.
https://webdocs.cs.ualberta.ca/~hayward/hexcoupon.pdf

Ryan lives in Edmonton where he commutes year-round by recumbent bike.

[Seminar] Agents with internal models

On Wednesday 6th February 2019 the Game AI Group will host a seminar by Theophane Weber from DeepMind.

Title: Agents with internal models
Speaker: Theophane Weber
Time: 4pm to 5pm, Feb 6, 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
I will present recent work that studies agents endowed with an internal model of the world. This will include agents that learn world models by predicting the future, and learn to interpret those predictions in order to act better without suffering from model inaccuracies; agents with neural analogues of search algorithms such as Monte Carlo Tree Search; agents that learn temporally abstract models of the world in order to compute representations of their belief about the state of the world, agents that use their models to evaluate counterfactual scenarios and learn from those synthetic experiences, and agents with only implicit models of the world that still exhibit planning-like behavior.

Biography

I am a staff research scientist at DeepMind. My research interests span deep reinforcement learning, model-based RL and planning, probabilistic modeling and modeling of uncertainty. Prior to DeepMind, I worked at Lyric Labs, a skunkworks team of Analog Devices, working on applications of machine learning to the physical world. I hold an M.S. and Ph.D from MIT in Operations Research and an M.S. from Ecole Centrale Paris in Applied Mathematics.

Theophane’s Google Scholar profile.

[Seminar] Advancing Video Game AI With Intrinsically Motivated Reinforcement Learning

On Friday 7th December the Game AI Group will host a seminar by Christian Guckelsberger from QMUL.

Title: Advancing Video Game AI With Intrinsically Motivated Reinforcement Learning
Speaker:Christian Guckelsberger
Time: 2pm-3pm (GMT), Dec 6, 2018
Room: BR 3.02, Bancroft Road Teaching Rooms, QMUL Mile End Campus
Abstract
Modern video games come with increasingly large and complex worlds to satisfy players’ demands for a rich and long-lasting playing experience. This development brings new challenges: designing robust believable characters that players can engage with in an open-ended way, and also with respect to evaluating content, especially when procedurally generated. In this talk, I will motivate the use of intrinsically motivated reinforcement learning to address the challenges of next-generation video games, a technique which currently gains strong momentum in the search for artificial general intelligence. I will give a comprehensive, interdisciplinary introduction to the concept of intrinsic motivation. I will motivate the development of computational models of intrinsic motivation, point out the opportunities they hold for game AI, and discuss the new challenges such models come with. My research on coupled empowerment maximisation for more believable non-player characters will illustrate the potential of such models, and motivate their combination with reinforcement learning. The use of intrinsically motivated reinforcement learning for video game AI is still in its infancy, and I will consequently finish with a set of open questions and interesting research projects.

[Seminar] “Computational Creativity and Videogame Design ” by Prof. Simon Colton

Title: Computational Creativity and Videogame Design 

Speaker: Prof. Simon Colton, Digital Games Technologies (Falmouth) and Computational Creativity (Goldsmiths), EPSRC Leadership Fellow Metamakers Institute, Games Academy, Falmouth University Computational Creativity Group, Goldsmiths, University of London.

Time: 5pm-6pm (GMT), Jan 23, 2018
Room: BR3.02, Bancroft Road, School of Electronic Engineering and Computer Science, QMUL

Abstract

In Computational Creativity research, we try to hand over creative responsibilities to software in arts and science projects, so that our systems can become trusted co-creators or autonomous creatives. After describing some recent advances and issues in Computational Creativity, I’ll move on to what is a killer application for the field, namely videogame design. I’ll describe recent work I’ve been involved with that aims to use AI techniques to democratise game design, so that anyone and everyone can make digital games as easily as they can write stories or make videos. I’ll also cover projects in procedural content generation and whole game design, and the idea that we can communicate our lives through play. At the end of the talk, I’ll come back to Computational Creativity research in general and look at high-level issues such as software showing intentionality, which we’ve addressed through The Painting Fool project. I’ll then describe what I believe is the biggest issue facing the field, namely authenticity, and I’ll provide some suggestions for how we can start to address this issue.

 

Bio

Simon Colton is a Professor of Digital Games Technology, holding an ERA Chair at Falmouth University, and a part-time Professor of Computational Creativity at Goldsmiths, University of London. He was previously a reader in Computational Creativity at Imperial College, London, and held an EPSRC Leadership Fellowship until mid-2017. An AI researcher for 20 years, he is one of the founding members of the Computational Creativity movement, with nearly 200 publications and national and international awards for his research. At Falmouth, he co-leads the MetaMakers Institute (www.metamakersinstitute.com) applying Computational Creativity techniques to the democratisation of game design and the cultural appreciation of videogames. At Goldsmiths, he co-leads the Computational Creativity group (ccg.doc.gold.ac.uk), addressing issues of creative behaviour in various application domains. He is also involved in the EPSRC IGGI doctoral training centre and the DC Labs Next Step Digital Economy centre. He is best known for his work on software such as the HR mathematical discovery system, The Painting Fool (www.thepaintingfool.com), the What-If Machine (http://ccg.doc.gold.ac.uk/research/whim) and the Wevva iOS game design system (https://itunes.apple.com/gb/app/wevva/id1322519841 and www.wevvagame.com). He has recently co-founded up a company called Imaginative AI Ltd., to pursue commercial applications of Computational Creativity.

Useful links: metamakers.falmouth.ac.ukccg.doc.gold.ac.ukmetamakersinstitute.comwevvagame.com