BOOK Beograd
Član broj: 9769 Poruke: 117 *.108.EUnet.yu
Jabber: BOOK@elitesecurity.org
|
Ovo je jedna od prvih igara sa kojom sam počeo programiranje. Bio sam napisao program u Paskalu koji primenjuje uslovnu optimalnu strategiju i može uvek da pobedi igrača (još uvek imam program koga interesuje, voleo bi da mu ga dam). Međutim, da bi igranje sa kompjuterom bilo zanimljivo, dopustio sam da u svakom nivou igrač odabere ko prvi igra. Kao što ćete videti dole, to je vrlo važno za dalji tok igre. Pametnim izborom ko igra prvi, igrač može da pobedi kompjutera uvek.
Igra kao što je neko rekao ima uslovnu optimalnu strategiju, koja je matematički jako, jako lepa. NAPOMENA: originalna verzija je da POBEĐUJE onaj koji poslednji kamenčić uzme i ovde ću se ja toga držati ne umanjujući opštost (prostom inverzijom svake reči KOMPLETAN u NEKOMPLETAN i obrnuto, stvar se namešta i za slučaj kada gubi onaj koji poslednju uzme). Pokušaću da objasnim optimalnu strategiju:
Brojeve kamenčića u svakoj hrpi predstavite u binarnom sistemu i zapišite ih jedan ispod drugog. Zatim stavite (na primer) plus ispod svake kolone koja ima paran broj jedinica, a minus ispod kolona koje imaju neparan broj jedinica. Na primer, za gornju partiju (1, 3, 5, 7) imamo (OPET PAŽNJA: Analiziram partiju imajući u vidu napomenu da POBEĐUJE onaj koji uzima poslednji):
0 0 1 = 1
0 1 1 = 3
1 0 1 = 5
1 1 1 = 7
-----------------
+ + +
U prvoj koloni (0, 0, 1, 1) imamo dva keca i stavljamo plus ispod nje, jer je dva paran broj. U drugoj koloni (0, 1, 0, 1) imamo takođe dva keca i stavljamo plus. U trećoj koloni (1, 1, 1, 1) imamo četiri keca i opet stavljamo plus, jer je četiri paran broj.
Nazovimo poziciju gomila u kojoj su svi plusevi "KOMPLETNOM", a svaku drugu poziciju u kojoj ima bar jedan minus "NEKOMPLETNOM".
U ovoj igri je početna pozicija KOMPLETNA. Optimalna strategija kaže da tada igrač treba velikodušno da prepusti prvi potez svom protivniku. Matematička teorija nam dokazuje da će protivnik, ŠTA GOD IGRAO, poziciju učiniti NEKOMPLETNOM. Vi zatim, u vašem prvom potezu NEKOMPLETNU poziciju učinite KOMPLETNOM (Matematička teroija takođe kaže da je ovo UVEK moguće). Sada će vaš protivnik, šta god igrao, učiniti poziciju NEKOMPLETNOM. Vi je opet učinite kompletnom, i tako dalje i tako bliže. Prateći ovu strategiju, vaš poslednji potez će biti uzimanje svih kamenčića iz poslednjeg preostalog reda, čime ćete konačno učiniti situaciju KOMPLETNOM (biće sve nule, tj. biće u svakoj koloni paran broj kečeva, tj. situacija će biti KOMPLETNA). Na taj način ste pobedili.
Ukoliko je početna pozicija NEKOMPLETNA (što nije u slučaju (1,3,5,7)), vi treba da igrate prvi i situciju učiniter KOMPLETNOM. onda je vaš protivnik učini NEKOMPLETNOM i u'vatili ste ga u šemu. Vaš je do kraja.
Ova strategija je uslovno optimalna, zato što naravno morate da odlučujete ko igra prvi. Dakle, postoji uslov ko igra prvi. Zbog ovoga, ne možete uvek pobeđivati a da protivnik ne posumnja.
...
Da bi razjasnili samu strategiju, hajde da razmotrimo vašu igru. noviKorisnik je igrao prvi, a početna situacija je KOMPLETNA. Dakle, on je već sada izgubio ukoliko ima za protivnika igrača koji zna optimalnu strategiju. Šta god igra, poziciju čini NEKOMPLTENOM. Situacija nakon njegovog poteza (iz prve gomile uzima jedan kamenčić) je:
0 0 0 = 0 (prazne redove ubuduće nećemo pisati)
0 1 1 = 3
1 0 1 = 5
1 1 1 = 7
-------------
+ + -
Kao što vidimo, postoje tri načina da poziciju učinimo kompletnom: možemo uzeti iz drugog, trećeg ILI četvrtog reda (potpuno svejedno) jedan kamenčić i na taj način obrisati jedan bit koji je kvario parnost. Zaista, srki se odlučuje za jedan kamenčić poslednjeg reda. Napomenimo da je kojim slučajem igrao BILO ŠTA različito od tri navedena poteza koji namešteju KOMPLETNOST, prepustio bi novomKorisniku NEKOMPLETNU situaciju, te bi on korigujući je mogao da uzme konce u svoje ruke i pravilnom igrom do kraja pobedi. Dakle, JEDNA GREŠKA I STVAR SE PREOKREĆE U RUKE PROTIVNIKA. Međutim, srki namešta parnost i čini KOMPLETNOST:
0 1 1 = 3
1 0 1 = 5
1 1 0 = 6
-------------
+ + +
noviKorisnik šta god sad da igra, kvari nameštenu KOMPLETNOST i čini poziciju NEKOMPLTENOM. Odlučuje se za pet kamečića iz trećeg reda:
0 1 1 = 3
1 0 1 = 5
0 0 1 = 1
-------------
- - -
Sada srki ima samo jedan izbor: da "1 0 1" napravi da bude "0 1 0". Ako odigra bilo šta drugo puko je, pod pretpostavkom da je noviKorisnik korisni nesvesno ovu strategiju. Srki se odlučuje za navedeni izbor:
0 1 1 = 3
0 1 0 = 2
0 0 1 = 1
-------------
+ + +
Iskusni igrači znaju napamet neke bitne KOMPLETNE pozicije. Svakako najvažnija je (1,2,3). Od ostalih nabrojmo samo (1,4,5), (3,5,6) i (1,6,7). Sada je noviKorisnik, kao i uostalom od samog početka igre, u beznadežnoj poziciji. Jedina šansa mu je da srki negde u toku igre pogreši. noviKorisnik se ovde odlučuje za dva kamenčića iz prvog reda.
0 0 1 = 1
0 1 0 = 2
0 0 1 = 1
-------------
+ - +
Srki sada greši: NE igra jedini pravilan potez, tj. ne briše bit iz drugog reda. MEĐUTIM, vi ste igrali sve naopako tako da on ustvari po vašoj verziji pobeđuje, a srki ovde i nije pogrešio nego je grešio za sve prethodne partije! (Ko razume shvatiće.) Dakle:
0 0 1 = 1
0 0 1 = 1
0 0 1 = 1
-------------
+ + -
Neka sada noviKorisnik fiktivno igra...
0 0 0 = 0
0 0 1 = 1
0 0 1 = 1
-------------
+ + +
... nameštajući parnost. Srki sada kvari parnost:
0 0 0 = 0
0 0 0 = 0
0 0 1 = 1
-------------
+ + -
... i noviKorisnik ga najzad namešta i pobeđuje:
0 0 0 = 0
0 0 0 = 0
0 0 0 = 0
-------------
+ + +
Ponavljam, kod vas je sve naopako, pa ustvari srki pobeđuje.
...
Sigurno se pitate kako to sve sa silnim nulama i jedinicama da izvedete bez papira i olovke. Posle mnogo partija, ceo se proces u glavi odvija, te protivnik uopšte ne zna ništa o nulama i jedinicama. Ukoliko znate napamet neke važne KOMPLETNE kombinacije (navedene gore), igru činite još jednostavnijom.
Pozdrav svima.
|