Kombinatorična igra filozofov nogomet

DREVENŠEK, MARKO (author), Fijavž, Gašper (mentor)

Kombinatorične igre so igre, kjer igralca izmenično izvajata poteze. Pri igri nimamo nikakršnih pripomočkov, ki bi na igro vplivali naključno. Igralca imata popolno informacijo o preteklih potezah za odločanje, kako igrati naprej. Pravila so takšna, da je igra končna. V delu predstavimo malo znano igro filozofov nogomet oziroma figomet. Predstavimo, zakaj je igra težka, in zakaj je odločiti, ali lahko igralec v dani situaciji zmaga z eno potezo, NP-poln problem. Dokazovanja smo se lotili s prevedbo že znanega NP-polnega problema 3-SAT. Poleg tega smo implementirali igro kot aplikacijo za dva igralca, ki je dostopna preko spletnega brskalnika.

• Language: Slovenian
• Keywords: kombinatorična igra, računska zahtevnost, filozofov nogomet, NP-polnost, 3-izpolnljivost, spletna aplikacija.
• Work type: Undergraduate thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2016
• PID: 20.500.12556/RUL-91238
• Publication date in RUL: 27.03.2017

Secondary language

• Language: English
• Title: Philosopher's football

Abstract

Combinatorial games are games where the players alternately take moves. In the game we do not have any chance devices that could impact on the game randomly. Players have complete information about past moves to decide how to play on. The rules are such that the game must eventually end. Philosopher’s football or Phutball is a not so well-known combinatorial game which is the focus of this work. We present why the game is difficult and why determing whether a player can win in a given situation in one move is an NP-complete problem. We prove it by reducing to an already known NP-complete problem 3-SAT. We have also implemented Phutball application for two players, which is accessible through a web browser.

• Keywords: combinatorial game, computational complexity, Philosopher's football, NP-completeness, 3-SAT, web application.