Search and Learning Algorithms for Two-Player Games with Application to the Game of Hex

• Author / Creator

  Gao, Chao

• Two-Player alternate-turn perfect-information zero-sum games have been suggested
  as a testbed for Artificial Intelligence research since Shannon in 1950s. In this thesis,
  we summarize and develop algorithms for this line of research. We focus on the game
  of Hex — a game created by Piet Hein in 1942 and popularized by Jonh Nash in

  1. We continue on previous research, further bringing the strength of machine learning techniques — specifically deep neural networks — to the game of Hex. We develop new methods and apply them to solving and playing Hex. We present state-of-the-art results for Hex and discuss relevant research on other domains. In particular, we develop solving and playing algorithm by combining search and deep learning methods. As a result of our algorithmic innovations, we produce stronger solver and player, winning gold medal at the Computer Olympiad Hex tournaments in 2017 and 2018.

• Subjects / Keywords

  • Computer Hex
  • Search
  • Learning
  • Two-Player Games

• Graduation date

  Spring 2020

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/r3-wwyb-cp31

• License

  Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.