Emulaciona ekvivalencija kombinatornih igara

Abstract

Bavimo se imparcijalnim kombinatornim igrama. Uvešćemo pojam emulacione ekvivalencije dve takve igre: intuitivno govoreći, igre koje su emulaciono ekvivalentne ,,ponašaju se potpuno isto“ sa stanovišta mogućih poteza u odgovarajućim pozicijama. Takođe ćemo uvesti jednu specijalnu igru na grafovima, i pokazaćemo da odgovarajućim odabirom njenih početnih parametara možemo dobiti igre koje su emulaciono ekvivalentne s čitavim nizom poznatih i široko izučavanih kombinatornih igara, kao što su Nim, tzv. igra oduzimanja, Chomp, Notakto itd. Međutim, pokazaćemo da naša igra na grafovima ipak nije ,,svemoćna“, u tom smislu što ćemo za određenu igru (izvesnu modifikaciju igre Nim) pokazati da ona nije emulaciono ekviva- lentna s uvedenom grafovskom igrom (ni za kakav odabir parametara). Ovo je zajednički rad sa Bojanom Bašićem i Nikolom Milosavljevićem.