Википедија

Genijalac (društvena igra)

Genijalac je igra pogađanja kombinacija za dva igrača. Modernu igru sa čiodama izmislio je, 1970. godine, Mordecai Meirowitz, izraelski upravnik pošte i ekspert u oblasti telekomunikacija.[1][2] Podseća na igru zvanu Bikovi i krave, koja je nastala pre jednog veka ili više.

Odigrana partija Genijalca

Pravila igre

uredi

Igra se pomoću:

  • table za igru, sa štitom sa jedne strane koji pokriva red sa četiri velike rupe, i dvanaest (ili deset, ili osam, ili šest) dodatnih redova koji sadrže četiri velike rupe, a pored njih još četiri manje rupe;
  • kodne čiode u šest (ili više, pogledaj Varijacije dole) različitih boja, okruglih glava, koje će biti raspoređene u velike rupe na tabli; i
  • čiode za dekodiranje, neke su bele, neke su crne, imaju ravne glave i manje su od kodnih čioda; one će biti raspoređene u manje rupe na tabli.

Igrači unapred određuju koliko će partija odigrati, a broj partija mora biti paran. Jedan igrač zadaje kombinaciju (zovimo ga prvi igrač), a drugi je pogađa pogađa (zovimo ga drugi igrač). Prvi igrač bira četiri kodne čiode. Dozvoljeno je ponavljanje boja, tako da igrač može da izabere sve čiode iste boje. Izabranu kombinaciju postavlja u četiri velike rupe, iza štita, tako da drugi igrač ne može da je vidi.[3]

Drugi igrač pokušava da pogodi kombinaciju, isti poredak, u dvanaest (deset, osam ili šest) pokušaja. Pogađa tako što postavlja kodne čiode u red na tabli za igru. Nakon što je drugi igrač postavio sve četiri čiode, prvi igrač postavlja od nula do četiri čiode za dekodiranje u manje rupe, kako bi mu potvrdio tačnost kombinacije. Crne čiode ukazuju na to da je za neku od čioda pogođena i boja i mesto. Bela čioda ukazuje na to da je za neku od čioda pogođena boja, ali joj treba promeniti mesto.[4]

Ako drugi igrač u svom pokušaju stavi više od jedne čiode iste boje, i takva čioda se pojavljuje u zadanoj kombinaciji ali samo jednom, prvi igrač neće za svaku od njih stavljati crnu ili belu čiodu, nego samo onoliko koliko ih se pojavljuje u rešenju. Na primer, ako je zadana kombinacija crvena-crvena-plava-plava, a drugi igrač pokušava sa crvena-crvena-crvena-plava, prvi igrač mu daje dve crne čiode za pogođene dve crvene čiode, i još jednu crnu čiodu za pogođenu plavu. Za treću crvenu ne dobija ništa jer ne postoji tri crvene u rešenju. Nema nagoveštaja da u kombinaciji postoji još jedna plava čioda. Što se tiče drugog igrača na to mesto može doći bilo koja od preostalih boja, osim crvene.[5]

Nakon što je prvi igrač postavio čiode za dekodiranje, ako kombinacija nije pogođena, drugi igrač pokušava ponovo; to se ponavlja dok drugi igrač ne pogodi kombinacju ili dok ne iskoristi sve pokušaje. Kada se to dogodi, igrači menjaju uloge.

Prvi igrač dobija jedan poen za svaki pokušaj drugog igrača. Dobija dodatni poen ako drugi igrač ne pogodi kombinaciju u poslednjem pokušaju. (Alternativa je da se boduje na osnovu broja iskorišćenih čioda za dekodiranje). Pobednik je onaj igrač koji ima više poena, nakon što odigraju onoliko partija koliko su se dogovorili na početku.

Postoji mogućnost izmene pravila.[6]

Istorijat

uredi

Od 1971, autorska prava na igru držala je Invicta Plastics iz Oadby-ja, blizu Leicestershire-a, Ujedinjeno Kraljevstvo. Originalno su je sami proizvodili, ali su posle dali licencu za proizvodnju Hasbro za svetsko tržište, sa izuzetkom Pressman Toys i Orda Industries koji imaju prava za proizvodnju za Američko i Izraelsko tržište.[7]

Počevši od 1973. godine, na kutiji je bila fotografija gospodina koji sedi na čelu, sa istočno-azijskom ženom koja stoji iza njega. Dva amaterska modela (Bill Woodward i Cecilia Fung) ujedinili su se u junu 2003. godine da poziraju za još jednu sliku za javnost.[8]

Algoritmi

uredi

Sa četiri čiode i šest boja, postoji 6 4 = 1296 različitih kombinacija (uključujući i one u kojima se neka boja ponavlja više puta).

Algoritam Pet pokušaja

uredi

Godine 1977, Donald Knut demonstrirao je da igrač koji pogađa kombinaciju to može učiniti u pet ili manje pokušaja, koristeći algoritam koji postepeno smanjuje broj mogućih kombinacija. Algoritam radi na sledeći način:[9]

  1. Napravi skup S od 1296 kombinacija, 1111, 1112, .. 6666. (svaki broj predstavlja jednu od boja)
  2. Počni sa inicijalnim pokušajem 1122 (Knut je dao primer koji pokazuje da algoritam neće uvek rešiti u pet pokušaja za svaku zadatu kombinaciju, ako se za prvi pokušaj izabere kombinacija kao što je 1123 ili 1234)
  3. Probaj kombinaciju kako bi dobio odgovor da crnim i belim čiodama
  4. Ako je odgovor četiri crne čiode, kombinacija je pogođena, algoritam se završava
  5. u suprotnom, iz skupa S izbaci sve kombinacije koje ne bi dale isti odgovor kai kad bi to (pokušaj) bila kombinacija. (Primer: Ako je pokušaj 1212 i odgovor je prazan tj. nema pogodaka, iz skupa treba izbaciti sve kombinacije koje sadrže boje 1 i 2)
  6. Upotrebi tehniku minimaks da bi našao sledeći pokušaj: Za svaki mogući pokušaj, koji je bilo koja od neiskorišćenih kombinacija od mogućih 1296, ne mora d abude iz skupa S, izračunaj koliko bi kombinacija bilo isključeno za svaku moguću crnu/belu čiodu. Rezultat pokušaja je najmanji broj mogućnosti koji će on eliminisati iz skupa. Jednim prolaskom kroz skup S za svaku neiskorišćenu kombinaciju od 1296 će uvećati rezultat za svaku pronađenu crnu/belu čiodu; najveći rezultat će eliminisati najmanje kombinacija; izračunaj rezultat koristeći formulu: "namanji izbačeni" = "broj elemenata skupa S" - (minus) "najveći rezultat". Iz skupa kombinacija sa najvećim rezultatom, izabrati jednu za sledeći pokušaj, pritom birati član skupa S kad god je to moguće. (Knut prati konvenciju biranja kombinacije sa najmanjom numeričkom verdsti, na primer 2345 jr manje od 3456. Takođe, Knut daje primer koji pokazuje da u nekim slučajevima ni jedan član skupa S neće biti među onim sa najvećim rezultatima i sledi da ta kombinacija ne može pobediti u sledećem pokušaju, a ipak je neophodno obezbediti pobedu u pet koraka).
  7. Ponovi korak 3.

Matematičari su tražili različite algoritme koji umanjili prosečan broj pokušaja koji su potrebni za rešavanje kombinacije: 1993, Kenji Koyama i Tony W. Lai pronašli su metod kome je u proseku potrebno 5625/1296 = 4.340 pokušaja da pogodi kombinaciju, a u najgorem slučaju potrebno je šest pokušaja.[10] Vrednost minimax-a u smislu teorije igre je 5600/1296 = 4.321. [11]

Genetski algoritam

uredi

Novi algoritam sa ugrađenim genetskim algoritmom, u kom se veliki skup prihvatljivih kombinacija sakuplja kroz različite generacije. Kvalitet svakog od ovih kombinacija određuje se na osnovu poređenja sa izborom elemenata iz prihvatljivog skupa.[12]

Algoritam radi na sledeći način:

  1. Postavi i = 1
  2. Odigraj fiksiran inicijalni pokušaj G1
  3. Pogodi odgovor X1 i Y1
  4. Ponavljaj dok je Xi ≠ P:
    1. Uvećaj i
    2. Postavi Ei = ∅ i h = 1
    3. Inicijalizuj populaciju
    4. Ponavljaj dok je h ≤ maxgen i |Ei| ≤ maxsize:
      1. Generiši novu populaciju koristeći prelaske, mutacije, inverzije i permutacije
      2. Izračunaj fitnes
      3. Dodaj prihvatljivu kombitaciju u Ei
      4. Uvećaj h
    5. Odigraj pokušaj Gi koji pripada skupu Ei
    6. Pogledaj odgovor Xi i Yi

Studije o složenosti Genijalca i Problem zadovoljstva

uredi

U novembru 2004. godine, Michiel de Bondt je dokazao da je rešavanje Genijalca NP-kompletan problem kada se igra sa n čioda po redu i dve boje, tako što je pokazao kako predstaviti bilo koje jedan-u-tri #SAT problema na njemu. On je takođe pokazao isto to za Doslednog Genijalca (igra se tako da je svaki pokušaj, koji je dosledan sa odgovorima iz prethodnih pokušaja, kandidat za skrivenu kombinaciju).

Problem zadovoljstva Genijalca je problem odlučivanja koji pita, "Dat je skup pokušaja i broj crnih i belih čioda sa rezultatima za svaki pokušaj, da li postoji makar jedna kombinacija koja generiše baš te rezultate?" (Ako ne, onda je igrač, koji je zadao kombinaciju, pogrešno odgovorio za bar jedan pokušaj). U decembru 2005, Jeff Stuckman i Guo-Qiang Zhang pokazali su u člankuArXiv da je Problem zadovoljstva Genijalca NP-komletan.

Varijacije

uredi

Menjanje broja boja i broja rupa u igri menja težinu. Još jedna česta varijacija je da se podrži različit broj igrača koji zadaju kombinacije i koji ih pogađaju. U tabeli su primeri igre Genijalac proizvedeni od strane Invicta, Parker Brothers, Pressman, Hasbro, i drugih:

Igra Godina Boje Rupe Komentari
Genijalac 1972 6 4 Originalna verzija
Genijalac Rojal 1972 5 boja × 5 oblika 3
Genijalac44 1972 6 5 Za četiri igrača
Veliki genijalac 1974 5 boja × 5 oblika 4
Super Genijalac (poznat i kao Napredni Genijalac) 1975 8 5
Genijalac sa rečima 1975 26 letters 4 Samo postojeće reči se mogu koristiti kao kombinacija i kao pokušaji.
Genijalac sa brojevima 1976 6 cifara 4 Koristi brojeve umesto boja. Igrač koji pravi kombinaciju, kao pomoć, može reći zbir iskorišćenih cifara.
Elektronski Genijalac (Invicta) 1977 10 cifara 3, 4, ili 5 Koristi brojeve umesto boja. Ručna elektronska verzija. Jedan ili više igrača protiv računara.
Volt Dizni Genijalac 1978 5 3 Koristi Diznijeve likove umesto boja.
Mini Genijalac (poznat i kao Genijalac za put) 1988 6 4 Tabla je manje veličine, prilagođena za putovanja. Igrač ima šest pokušaja.
Genijalac izazov 1993 8 5 Oba igrača istovremeno igraju obe uloge.
Parker Genijalac 1993 8 4
Genijalac za decu 1996 6 3 Sa životinjama.
Genijalac tajno istraživanje 1997 26 slova 3-6 Samo reči koje postoje; odgovori se daju slovo po slovo koristeći strelicu nagore/strelicu nadole što predstavlja da je slovo pre/posle tog slova u abecedi.
Ručni elektronski Genijalac (Hasbro) 1997 6 4
Novi Genijalac 2004 8 4 Za do pet igrača
Mini Genijalac 2004 6 4 Tabla je manje veličine, prilagođena za putovanja. Igrač ima osam pokušaja.
Genijalac 2013 6 4 digitalna verzija

Težina bilo koje od gorenavedene verzije može se povećati, ako se "prazno" tretira kao dodatna boja, ili smanjiti, ako je dovoljno pogoditi boje koje ulaze u kombinaciju, ali ne i njihove tačne pozicije.

Napravnjene su računarske verzije ove igre., ponekad i sa varijacijama broja i vrste delova koji su uključeni i često se različito nazivaju da bi se izbegle povrede žiga. Genijalac se može igrati i na papiru.

Postoje i verzije u kojima se pogađa kombinacija četiri cifre.

Klonovi

uredi

Postoje bar četiri implementacije koncepta ove igre:

  • obojene kombinacije koristi Qt[13]
  • gnom-genijalac koristi GTK+[14]
  • GGenijalac koristi GNUstep[15]
  • Pokušaj je deo Prenosive kolekcije puzli Simona Tathama[16]

Reference

uredi
  1. ^ Nelson, Toby (9. 3. 2000). „A Brief History of the Master Mind Board Game”. Arhivirano iz originala 12. 08. 2007. g. Pristupljeno 6. 8. 2014. 
  2. ^ „Mastermind Board Game”. Board Game Geek. Pristupljeno 6. 8. 2014. 
  3. ^ „Industrious”. Pristupljeno 7. 7. 2014. 
  4. ^ „Wolfram”. Pristupljeno 9. 7. 2012. 
  5. ^ „Archimedes”. Pristupljeno 7. 10. 2012. 
  6. ^ „Bulls and Cows & co.”. Pristupljeno 7. 7. 2012. 
  7. ^ „Invicta Toy History page”. Arhivirano iz originala 12. 08. 2007. g. Pristupljeno 7. 8. 2012. 
  8. ^ „Landmark Reunion for Mastermind Box Models”. Pristupljeno 5. 10. 2006. 
  9. ^ Knuth, Donald (1976—77). „The Computer as Master Mind” (PDF). J. Recr. Math. (9): 1—6. Arhivirano iz originala (PDF) 29. 04. 2011. g. Pristupljeno 31. 05. 2015. 
  10. ^ Koyama, Kenji; Lai, Tony (1993). „An Optimal Mastermind Strategy”. Journal of Recreational Mathematics (25): 230—256. 
  11. ^ Knuth 2011, str. 226.
  12. ^ Berghman, Lotte (2007—2008). „Efficient solutions for Mastermind using genetic algorithms” (PDF). K.U.Leuven. (1): 1—15. 
  13. ^ Debian - Details of package colorcode in jessie
  14. ^ Debian - Details of package gnome-mastermind in jessie
  15. ^ "GMastermind - GNUstep Mastermind Implementation", GNUstep Application Project, 15 July 2011.
  16. ^ Simon Tatham's Portable Puzzle Collection

Literatura

uredi
  • Knuth, Donald (2011). Selected papers on fun and games. Center for the Study of Language and Information. str. 226. ISBN 9781575865843. 
 
Genijalac na Vikimedijinoj ostavi.
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Генијалац_(друштвена_игра)&oldid=27753790”