| Popis: |
V magistrskem delu obravnavamo izbrane vsebine s področja kombinatorične teorije iger. V uvodnih poglavjih predstavimo primere preprostih kombinatoričnih iger ter navedemo nekatere osnovne definicije in trditve, na katerih temelji teorija kombinatoričnih iger. Predstavimo dokaz Zermelovega izreka in podamo več primerov osnovnih strategij, ki jih igralca uporabljata pri igranju. Glavni poudarek je na igrah normalnega tipa, pri katerih zmaga tisti igralec, ki napravi zadnjo potezo. Ob tem obravnavamo pojme kot so: položaj in njegov tip, vsota položajev in ekvivalenca položajev, na katerih temelji kombinatorična teorija iger. V drugem delu predstavimo kombinatorično teorijo nepristranskih iger ob pomoči igre Nim in dokažemo Sprague-Grundyev izrek, ki nam omogoča celostno razumevanje ekvivalence pri nepristranskih igrah. Podobno predstavimo tudi njegovo različico za pristranske igre ob pomoči igre Hackenbush. Skozi celotno magistrsko delo povezujemo in odkrivamo zveze med obravnavanimi vsebinami, ki jih dopolnjujemo z rešenimi praktičnimi primeri. In this master's thesis, we discuss chosen topics of combinatorial game theory. In the opening section we introduce some simple combinatorial games and give some basic definitions and theorems on which the theory of combinatorial games is based. We present a proof of Zermelo's theorem, and provide some examples of basic strategies that can be used by players while playing. The main emphasis is on the normal-play games, in which the player that makes the last move wins. Along the way we study the conccepts such as position in the game and its type, sum of positions and equivalence of positions, on which the combinatorial game theory is based. In the second part we present combinatorial theory of impartial games with the help of the Nim game. We prove the Sprague-Grundy's theorem, which enables us to comprehensively understand the equivalence in impartial games. Similarly, we also present a version for partizan games with the help of the Hackenbush game. Through the entire master's thesis, we connect and discover the relations between the discussed contents, which are supplemented with the solved practical examples. |
