20.500.12556/RUL-91238 Kombinatorična igra filozofov nogomet Philosopher's football 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. 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. kombinatorična igra računska zahtevnost filozofov nogomet NP-polnost 3-izpolnljivost spletna aplikacija. combinatorial game computational complexity Philosopher's football NP-completeness 3-SAT web application. true false false Slovenski jezik Angleški jezik Diplomsko delo 2017-03-27 12:55:32 2017-03-27 12:55:34 2022-08-09 21:21:49 0000-00-00 00:00:00 2016 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 17742 Drevensek_Marko_-_Kombinatoricna_igra_filozofov_nogomet.pdf Drevensek_Marko_-_Kombinatoricna_igra_filozofov_nogomet.pdf 1 2E5582554E8A5EEDC97E9375F30443DE e53c604207c3a5fd256da4b85ee5fd44d560a1676ba064352c8739d4abc26f4b 60bf0ffd-a1b2-11eb-a523-00155dcfd717 20.500.12556/rul/ac71a937-8901-4257-8070-a714c4590951 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=95424 Fakulteta za računalništvo in informatiko 0 0 0