Sprague-Grundyjeva teorija nepristranih kombinatornih igara

Ovaj rad daje kratki pregled teorije nepristranih kombinatornih igara. Osnovni obrađeni koncepti i rezultati su: klasifikacija pozicija kao pobjedničkih za prvog, odnosno drugog igrača, definicija Sprague-Grundyjeve funkcije, dokaz istoimenog teorema, primjena teorije na rješavanje igara Nim i Hackenbush te analiza igre Chomp korištenjem računala. Općenita teorija je detaljno ilustrirana na velikom broju primjera kombinatornih igara, od nekih dobro poznatih i često igranih do onih izmišljenih samo za potrebe ovog rada.This paper gives a brief overview of impartial combinatorial games. The main concepts and results are as follows: classification of positions as winning for the first, and second player, definition of Sprague-Grundy’s function, the proof of homonymous theorem, application of theory on solving Nim and Hackenbush games and the analysis of the game of Chomp by using the computer. The basic theory is illustrated in detail on a variety of examples of combinatorial games, ranging from some well known and often used to the ones invented for the purpose of this paper