O matematičkim igrama

“Let my playing be my learning, and my learning be my playing”, kaže u svom delu Homo Ludens (“Čovek igrač”) holandski sociolog i istoričar Johan Huizinga (1872.-1945.). Uvodi pojam “teorija igre”, kojim definiše konceptualni prostor u kome se igra odvija, gde se igra vidi kao primarni i potreban (iako ne i dovoljan) uslov za genezu civilizacije. Zašto?

Neminovno, čovek se ostvaruje kroz rad i igru. Dok rad asocira na obaveze i odgovornosti, igra je produkt slobodnog razmišljanja i razonode. Pojam igre se poistovećuje sa radnjom koju obavljamo dobrovoljno, nezavisno od egzistencijalnih potreba, sa ciljem da se kroz nadmudrivanje protivnika dostigne zadovoljstvo slično onom koje se doživljava u procesu stvaranja.

Igra neposredno podstiče čovekovu prirodno urođenu dovitljivost i intuiciju, takmičarski duh i inovativnost, i samim tim, emituje se presudan uticaj na razvitak ljudske kulture. Naime, kako navodi dr Ratko Tošić u svojoj knjizi Matematičke igre, “čovek kroz igru uči da na osnovu određenih postavki i svojih veština shvata određene odnose i stvara nove; deluje logički time što nastoji da dostizanjem zadatog cilja postigne uspeh”. I tako, najsrećniji jeste čovek koji uspeva da u svom svakodnevnom delanju objedini rad i igru.

Sam pojam matematičke igre može se smatrati kontradiktornim. Kada igru podvrgnemo matematičkoj analizi, kroz izračunavanja i dokaze strategija, da li ona prestaje biti igra u klasičnom smislu? Svakako ne. Time je izvršen svojevrsan prelaz iz sfere umetnosti u sferu nauke, a rezultat su novi izazovi.

Godine 1612. Klod de Mezirjak objavio je prvu knjigu koja se može svrstati u žanr tzv. zanimljive matematike. U toj knjizi prvi put se pojavljuje jedan zadatak u obliku igre sa brojevima, kasnije poznate kao Poker Nim. Nemački matematičar Ernst Zermelo je 1921. godine dokazao važna tvrđenja teorije igara o postojanju pobedničkih strategija. Ubrzo zatim, veliki doprinos njenom razvoju dali su matematičari Patrik Grandi, Roland Šprag, Džon fon Nojman, Oskar Morgenštern i Džon Konvej. Danas je matematička teorija igara važna i popularna disciplina, koja nalazi primenu u ekonomiji i mnogim drugim naukama.

Istorija igara

Među staroegipatskim iskopinama pronađene su mnogobrojne istovetne figure koje su korišćene u igrama. U grobnici Regotema u Medumu (2800. godine pre n. e.), pomoću hijeroglifa su predstavljeni predmeti, ostavljeni u grobnici, a među njima i garnitura za igru koja podseća na savremenu igru dame. Na spomeniku u Tebi iz perioda oko 2500. godina pre n. e. predstavljeni su igrači koji igraju ovu drevnu igru; na tabli se jasno raspoznaje 6 figura crne i bele boje. Sama pravila nisu dešifrovana, jer o tome nisu ostali pisani tragovi.

U Rimu je takođe bila popularna igra tipa dame, poznata pod imenom latrunkuli (lat. latro - vojnik). Igra je bila toliko omiljena i opšteprihvaćena u narodu, da su je igrali svuda, na trgovima i ulicama, a prolaznici su se često zaustavljali da bi osmotrili poziciju i komentarisali šanse igrača. Veliki ljubitelj ove igre, pesnik Marcial, zapisao je: "Tablu, figure i nekoliko knjiga, i ustupam ti sve lepote Neronovih termi". Nažalost, nije sačuvan ni jedan do detalja jasan crtež kompleta za latrunkuli, tako da nam pravila ove igre nisu do kraja poznata.

Od igara tzv. ratničkog sadržaja ističu se takođe kineski šah i šatrandž. Kineski šah se prvi put pominje u kineskom leksikonu "More reči", gde se kaže da je igra preneta iz Indije u Kinu u vreme vladavine cara Vu-Di (502.-550.). Šatrandž, preteča šaha, prvi put se pominje u istorijskom romanu "Karnamak" (600. godine).

Od igara tzv. ratničkog sadržaja ističu se takođe kineski šah i šatrandž. Kineski šah se prvi put pominje u kineskom leksikonu "More reči", gde se kaže da je igra preneta iz Indije u Kinu u vreme vladavine cara Vu-Di (502.-550.). Šatrandž, preteča šaha, prvi put se pominje u istorijskom romanu "Karnamak" (600. godine).

Prvi zbornik igara sastavio je španski kralj Alfonso Mudri (1283.), nakon osvajanja Španije od strane Arapa. Opisane su igre "mlin" (arapski alkerk), šah, trik-trak, kao i dve igre na tabli 5 x 5. Vrlo slične igre se kasnije pojavljuju i u Engleskoj i Nemačkoj.

Svoj savremen oblik igra dame dobija u Rusiji. U Moskvi su u 17. veku igre bile toliko popularne i rasprostranjene, da je car Aleksej Mihailovič (1645.-1675.) zabranio zakonom ne samo igre na sreću, već i izradu kocki.

Danas je Teorija igara ozbiljna naučna disciplina i aktuelan predmet matematičkih istraživanja. Smatra se primenjenom algebrom i kombinatorikom, a posebno veliki uticaj prima iz Teorije brojeva, i Teorije grafova.

Teorija igara ima primenu u tehnici, ekonomiji, i mnogim drugim naukama, čak i u vojnim operacijama, za "nalaženje optimalnog načina izvršavanja zadataka u kompetativnom okruženju". Takođe, matematičke igre su sve zastupljeniji predmet pažnje sa aspekta programiranja i algoritamskih rešenja.

Pojam matematičke igre i osnovne klasifikacije

Deni Didro (1713.-1784.), u svom delu Zakoni prirode, navodi: “Nisam siguran da li postoji veza između nadarenosti za igru i genija matematičara; međutim, između igre i matematike postoje brojne veze. Kad je reč o igri, ako ne uzmemo u obzir nesigurnosti koje stvara slučaj, ili ako uporedimo igru sa netačnošću koju apstrakcija unosi u matematiku, tada možemo partiju neke igre posmatrati kao neodređeni niz problema, koji se pod uobičajnim uslovima mogu rešiti. Nema matematičkog problema na koji se ove reči ne bi mogle primeniti; pa čak ni materija kojom se bavi matematika, u prirodi isto tako ne postoji kao predmet što ga ima pred očima igrač. To je i sa jedne i sa druge strane stvar dogovora.”

Igra je normalna ukoliko je pobednik onaj koji svojim potezom igru prevodi u završnu poziciju. Igra je obrnuta (misère play) ukoliko igrač koji prevede igru u završnu poziciju gubi. Igra je beskonačna ukoliko u njoj može doći do beskonačnog broja ponavljanja pozicija, odnosno skup završnih pozicija je prazan. U suprotnom je konačna.

Može se govoriti o igrama između dva lica, kao što su šah i go, i o igrama više lica, kao što su poker i bridž. Postoje igre u kojima učestvuje samo jedno lice, kao što je soliter. Ako je broj igrača bar tri, pojavljuje se mogućnost stvaranja koalicija. Igre se takođe mogu podeliti spram prisustva elementa slučajnosti.

Element slučajnosti je naročito izražen u hazardnim igrama (sa kartama i kockom). Treći kriterijum za klasifikaciju igara zasniva se na tome da li igrači imaju potpunu informaciju o poziciji igre, kao i o mogućim potezima u svakoj poziciji - svojim i svog protivnika. Šah je igra sa potpunom informacijom. Sa druge strane, bridž je igra dva igrača, pri čemu je svaki igrač tim od dve osobe, i interesantan je po tome što čak ni članovi tima između sebe nemaju potpunu informaciju o sopstvenim pozicijama.

Igrač može igrati pametno i seriju poteza apstrahovati po nekom principu – strategiji, koja predviđa odgovor u svakoj od pozicija. Ukoliko strategija vodi do pobede bez obzira kako protivnik odigrao svoje poteze, onda igrač ima pobedničku strategiju. Teorija igara bavi se analizom pozicija, upravo sa ciljem da se definišu pobedničke strategije. Tada možemo reći da je igra “rešena”.

Kao primer matematičke igre predstavićemo Zelenog Hakenbuša!

“Hasan seckati”

Tvorac igre Hakenbuš je matematičar Džon Konvej, proslavljen zahvaljujući svom izuzetnom doprinosu u raznim oblastima algebre i kombinatorike. Kao autor knjiga On Numbers and Games, i Winning Ways For Your Mathematical Plays, postavlja temelje savremene Teorije igara. U ovim delima analiziran je velik broj matematičkih igara i dati su koncepti i dokazi njihovih rešenja.

Naziv Hakenbuš potiče od nemačke reči hackenbusch, što znači rezanje grana. Takođe su je nazivali i igra Hewitt, Graph and Chopper, ili, ukoliko je je postavka bila nalik na ljudske figure, Lizzie Borden`s Nim. Ova igra je zapravo surogat igre Nim, ali o tome u nekom drugom tekstu. Iznesimo osnovne principe igre, na primeru Zelenog Hakenbuša.

Za igru su potrebni papir, olovka i gumica, ili kreda i tabla, ili kreda i tabla, ili plaža i štap... Na početku igre treba nacrtati nekoliko grafova. Sam Konvej je predložio početnu sliku za igru, tzv. Bašta Hakenbuš:

Uočavamo tri grafa: drvo, kuća i svetiljka. Svaki graf ima svoje postolje. Linija postolja ne pripada ni jednom grafu. Na crtežu je prikazana isprekidanim crticama. Tačke grafova koje se nalaze na toj liniji nazivaju se bazne tačke. Grafovi mogu sadržati petlje (kao što su to jabuke na slici). Igrači naizmenično brišu sa slike po jednu liniju. Pri tom, ako se izbriše linija koja gubi oslonac sa nekom osnovom, onda se briše celi deo crteža koji je držala ta grana grafa.

Ako se izbriše linija označena slovom B na drvetu, onda krošnja više nema oslonac i "pada", odnosno celu krošnju treba izbrisati sa crteža. Slično, ako se izbriše linija A, celo okno sa paukom "pada". Izbriše li se linija C, onda se mora izbrisati i celi pauk, dok okno

ostaje ukoliko se ne briše linija A. Svetiljka ima dva oslonca sa “zemlje". Ako se jedna linija oslonca izbriše, svetiljka i dalje ostaje. Izbriše li se i druga linija oslonca, svetiljka "pada", tj. briše se cela.

Pobednik u ovoj igri je onaj igrač koji izbriše poslednju liniju sa crteža.Ono što razlikuje Zelenog Hakenbuša od npr. Plavo-crvenog, gde je graf podeljen na plave grane za jednog, i crvene za drugog igrača, pravilo je da su oboma dostupne sve grane grafova, odnosno dozvoljen im je isti skup poteza. Jedna od varijacija igre je i, još složeniji, Hotchpotch Hakenbuš, gde se graf deli na plave, crvene i zelene grane, analogno.

Kako pobediti u ovoj igri? Određenim matematičkim dovijanjima, svakoj grani se dodeljuje vrednost. Takođe, graf se može redukovati po određenim pravilima fuzije, tako da bi naša bašta sa prethodne slike sada izgledala ovako (brojevi nad granama označavaju njihove vrednosti):

I konačno, stižemo do pobedničke strategije, koja se duhovito može predstaviti sledećim stihovima:

When it is your turn to play, Bring the value down to 0 if there is a way, If the game has non-0 value, such a move you will find. Stick with this strategy and win every time!

Naravoučenije

Tako da, dečaci i devojčice, igrajte se! Kao što kaže naslov, a i Džek Nikolson u čuvenom Kjubrikovom filmu The Shining:

All work and no play makes Jack a dull boy!

Autorka bi se ovom prilikom zahvalila Marici Stojanov, dr Draganu Mašuloviću i dr Ratku Tošiću – sjajni igrači!