Speaker: Abdallah Saffidine, University of New South Wales
Title: On the Complexity of Connection Games
Invented in 1942, Hex is a strategy game with a lasting influence in board game design as well as in computer games research. In this talk, we study three related connection games among the most widely played: Havannah, Twixt, and Slither. Drawing inspiration from results on Hex, we examine the complexity of determining the outcome of arbitrary input positions as well as whether non-constructive solutions to the empty starting positions are possible.
This talk is based on joint work with Édouard Bonnet and Florian Jamain. The paper it is based on will appear in the journal "Theoretical Computer Science".
Abdallah Saffidine is an ARC DECRA Fellow and a Research Associate at the University of New South Wales, Sydney, Australia. He works in the Artificial Intelligence and Algorithms groups. He arrived at UNSW in 2013 as a postdoc with Pr. Michael Thielscher and obtained his PhD from the Université Paris-Dauphine, France, under the supervision of Pr. Tristan Cazenave. Abdallah has a wide range of interests from games, planning, and other areas of decision-making to logic, complexity and other areas of theory.