you're reading...

SACT Seminar: On the Complexity of Connection Games

Time: 12:00 noon Tuesday, 6th September 2016.

Location: SIT 459

Speaker: Abdallah Saffidine, UNSW

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 the first part of 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. Back to Hex, we adopt a parameterized complexity perspective and establish that while Short Hex is FPT, Short Generalized Hex is W[1]-complete. In doing so, we disprove a 1999-conjecture by Downey and Fellows in the most influential textbook in parameterized complexity.

This talk is based on joint work with Édouard Bonnet and Florian Jamain appearing in the journal “Theoretical Computer Science” as well as ongoing work with Serge Gaspers, Antonin Lambilliotte, and Stefan Rümmele.

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.



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: