Генијалац (друштвена игра)

Одиграна партија Генијалца

Генијалац је игра погађања комбинација за два играча. Модерну игру са чиодама измислио је, 1970. године, Mordecai Meirowitz, израелски управник поште и експерт у области телекомуникација.[1][2] Подсећа на игру звану Бикови и краве, која је настала пре једног века или више.

Правила игре

Игра се помоћу:

  • табле за игру, са штитом са једне стране који покрива ред са четири велике рупе, и дванаест (или десет, или осам, или шест) додатних редова који садрже четири велике рупе, а поред њих још четири мање рупе;
  • кодне чиоде у шест (или више, погледај Варијације доле) различитих боја, округлих глава, које ће бити распоређене у велике рупе на табли; и
  • чиоде за декодирање, неке су беле, неке су црне, имају равне главе и мање су од кодних чиода; оне ће бити распоређене у мање рупе на табли.

Играчи унапред одређују колико ће партија одиграти, а број партија мора бити паран. Један играч задаје комбинацију (зовимо га први играч), а други је погађа погађа (зовимо га други играч). Први играч бира четири кодне чиоде. Дозвољено је понављање боја, тако да играч може да изабере све чиоде исте боје. Изабрану комбинацију поставља у четири велике рупе, иза штита, тако да други играч не може да је види.[3]

Други играч покушава да погоди комбинацију, исти поредак, у дванаест (десет, осам или шест) покушаја. Погађа тако што поставлја кодне чиоде у ред на табли за игру. Након што је други играч поставио све четири чиоде, први играч поставља од нула до четири чиоде за декодирање у мање рупе, како би му потврдио тачност комбинације. Црне чиоде указују на то да је за неку од чиода погођена и боја и место. Бела чиода указује на то да је за неку од чиода погођена боја, али јој треба променити место.[4]

Ако други играч у свом покушају стави више од једне чиоде исте боје, и таква чиода се појављује у заданој комбинацији али само једном, први играч неће за сваку од њих стављати црну или белу чиоду, него само онолико колико их се појављује у решењу. На пример, ако је задана комбинација црвена-црвена-плава-плава, а други играч покушава са црвена-црвена-црвена-плава, први играч му даје две црне чиоде за погођене две црвене чиоде, и још једну црну чиоду за погођену плаву. За трећу црвену не добија ништа јер не постоји три црвене у решењу. Нема наговештаја да у комбинацији постоји још једна плава чиода. Што се тиче другог играча на то место може доћи било која од преосталих боја, осим црвене.[5]

Након што је први играч поставио чиоде за декодиранје, ако комбинација није погођена, други играч покушава поново; то се понавља док други играч не погоди комбинацју или док не искористи све покушаје. Када се то догоди, играчи мењају улоге.

Први играч добија један поен за сваки покушај другог играча. Добија додатни поен ако други играч не погоди комбинацију у последњем покушају. (Алтернатива је да се бодује на основу броја искоришћених чиода за декодирање). Победник је онај играч који има више поена, након што одиграју онолико партија колико су се договорили на почетку.

Постоји могућност измене правила.[6]

Историјат

Од 1971, ауторска права на игру држала је Invicta Plastics из Oadby-ја, близу Leicestershire-а, Уједињено Краљевство. Оригинално су је сами производили, али су после дали лиценцу за производњу Hasbro за светско тржиште, са изузетком Pressman Toyс и Orda Industries који имају права за производњу за Америчко и Израелско тржиште.[7]

Почевши од 1973. године, на кутији је била фотографија господина који седи на челу, са источно-азијском женом која стоји иза њега. Два аматерска модела (Bill Woodward и Cecilia Fung) ујединили су се у јуну 2003. године да позирају за још једну слику за јавност.[8]

Алгоритми

Са четири чиоде и шест боја, постоји 6 4 = 1296 различитих комбинација (укључујући и оне у којима се нека боја понавља више пута).

Алгоритам Пет покушаја

Године 1977, Доналд Кнут демонстрирао је да играч који погађа комбинацију то може учинити у пет или мање покушаја, користећи алгоритам који постепено смањује број могућих комбинација. Алгоритам ради на следећи начин:[9]

  1. Направи скуп С од 1296 комбинација, 1111, 1112, .. 6666. (сваки број представља једну од боја)
  2. Почни са иницијалним покушајем 1122 (Кнут је дао пример који показује да алгоритам неће увек решити у пет покушаја за сваку задату комбинацију, ако се за први покушај изабере комбинација као што је 1123 или 1234)
  3. Пробај комбинацију како би добио одговор да црним и белим чиодама
  4. Ако је одговор четири црне чиоде, комбинација је погођена, алгоритам се завршава
  5. у супротном, из скупа С избаци све комбинације које не би дале исти одговор каи кад би то (покушај) била комбинација. (Пример: Ако је покушај 1212 и одговор је празан тј. нема погодака, из скупа треба избацити све комбинације које садрже боје 1 и 2)
  6. Употреби технику минимакс да би нашао следећи покушај: За сваки могући покушај, који је било која од неискоришћених комбинација од могућих 1296, не мора д абуде из скупа С, израчунај колико би комбинација било искључено за сваку могућу црну/белу чиоду. Резултат покушаја је најмањи број могућности који ће он елиминисати из скупа. Једним проласком кроз скуп С за сваку неискоришћену комбинацију од 1296 ће увећати резултат за сваку пронађену црну/белу чиоду; највећи резултат ће елиминисати најмање комбинација; израчунај резултат користећи формулу: "намањи избачени" = "број елемената скупа С" - (минус) "највећи резултат". Из скупа комбинација са највећим резултатом, изабрати једну за следећи покушај, притом бирати члан скупа С кад год је то могуће. (Кнут прати конвенцију бирања комбинације са најмањом нумеричком вердсти, на пример 2345 јр мање од 3456. Такође, Кнут даје пример који показује да у неким случајевима ни један члан скупа С неће бити међу оним са највећим резултатима и следи да та комбинација не може победити у следећем покушају, а ипак је неопходно обезбедити победу у пет корака).
  7. Понови корак 3.

Математичари су тражили различите алгоритме који умањили просечан број покушаја који су потребни за решавање комбинације: 1993, Kenji Koyama и Tony W. Lai пронашли су метод коме је у просеку потребно 5625/1296 = 4.340 покушаја да погоди комбинацију, а у најгорем случају потребно је шест покушаја.[10] Вредност minimax-а у смислу теорије игре је 5600/1296 = 4.321. [11]

Генетски алгоритам

Нови алгоритам са уграђеним генетским алгоритмом, у ком се велики скуп прихватљивих комбинација сакупља кроз различите генерације. Квалитет сваког од ових комбинација одређује се на основу поређења са избором елемената из прихватљивог скупа.[12]

Алгоритам ради на следећи начин:

  1. Постави i = 1
  2. Одиграј фиксиран иницијални покушај G1
  3. Погоди одговор X1 и Y1
  4. Понављај док је Xi ≠ P:
    1. Увећај i
    2. Постави Ei = ∅ и h = 1
    3. Иницијализуј популацију
    4. Понављај док је h ≤ maxgen и |Ei| ≤ maxsize:
      1. Генериши нову популацију користећи преласке, мутације, инверзије и пермутације
      2. Израчунај фитнес
      3. Додај прихватљиву комбитацију у Ei
      4. Увећај h
    5. Одиграј покушај Gi који припада скупу Ei
    6. Погледај одговор Xi и Yi

Студије о сложености Генијалца и Проблем задовољства

У новембру 2004. године, Michiel de Bondt је доказао да је решавање Генијалца НП-комплетан проблем када се игра са н чиода по реду и две боје, тако што је показао како представити било које један-у-три #САТ проблема на њему. Он је такође показао исто то за Доследног Генијалца (игра се тако да је сваки покушај, који је доследан са одговорима из претходних покушаја, кандидат за скривену комбинацију).

Проблем задовољства Генијалца је проблем одлучивања који пита, "Дат је скуп покушаја и број црних и белих чиода са резултатима за сваки покушај, да ли постоји макар једна комбинација која генерише баш те резултате?" (Ако не, онда је играч, који је задао комбинацију, погрешно одговорио за бар један покушај). У децембру 2005, Jeff Stuckman и Guo-Qiang Zhang показали су у чланкуArXiv да је Проблем задовољства Генијалца НП-комлетан.

Варијације

Мењање броја боја и броја рупа у игри мења тежину. Још једна честа варијација је да се подржи различит број играча који задају комбинације и који их погађају. У табели су примери игре Генијалац произведени од стране Invicta, Parker Brothers, Pressman, Hasbro, и других:

Игра Година Боје Рупе Коментари
Генијалац 1972 6 4 Оригинална верзија
Генијалац Ројал 1972 5 боја × 5 облика 3
Генијалац44 1972 6 5 За четири играча
Велики генијалац 1974 5 боја × 5 облика 4
Супер Генијалац (познат и као Напредни Генијалац) 1975 8 5
Генијалац са речима 1975 26 letters 4 Само постојеће речи се могу користити као комбинација и као покушаји.
Генијалац са бројевима 1976 6 цифара 4 Користи бројеве уместо боја. Играч који прави комбинацију, као помоћ, може рећи збир искоришћених цифара.
Електронски Генијалац (Invicta) 1977 10 цифара 3, 4, или 5 Користи бројеве уместо боја. Ручна електронска верзија. Један или више играча против рачунара.
Волт Дизни Генијалац 1978 5 3 Користи Дизнијеве ликове уместо боја.
Мини Генијалац (познат и као Генијалац за пут) 1988 6 4 Табла је мање величине, прилагођена за путовања. Играч има шест покушаја.
Генијалац изазов 1993 8 5 Оба играча истовремено играју обе улоге.
Паркер Генијалац 1993 8 4
Генијалац за децу 1996 6 3 Са животињама.
Генијалац тајно истраживање 1997 26 слова 3-6 Само речи које постоје; одговори се дају слово по слово користећи стрелицу нагоре/стрелицу надоле што представља да је слово пре/после тог слова у абецеди.
Ручни електронски Генијалац (Hasbro) 1997 6 4
Нови Генијалац 2004 8 4 За до пет играча
Мини Генијалац 2004 6 4 Табла је мање величине, прилагођена за путовања. Играч има осам покушаја.
Генијалац 2013 6 4 дигитална верзија

Тежина било које од горенаведене верзије може се повећати, ако се "празно" третира као додатна боја, или смањити, ако је довољно погодити боје које улазе у комбинацију, али не и њихове тачне позиције.

Направњене су рачунарске верзије ове игре., понекад и са варијацијама броја и врсте делова који су укључени и често се различито називају да би се избегле повреде жига. Генијалац се може играти и на папиру.

Постоје и верзије у којима се погађа комбинација четири цифре.

Клонови

Постоје бар четири имплементације концепта ове игре:

  • обојене комбинације користи Qt[13]
  • гном-генијалац користи GTK+[14]
  • GГенијалац користи GNUstep[15]
  • Покушај је део Преносиве колекције пузли Симона Татхама[16]

Референце

  1. ^ Nelson, Toby (9. 3. 2000). „A Brief History of the Master Mind Board Game”. Архивирано из оригинала 12. 08. 2007. г. Приступљено 6. 8. 2014. 
  2. ^ „Mastermind Board Game”. Board Game Geek. Приступљено 6. 8. 2014. 
  3. ^ „Industrious”. Приступљено 7. 7. 2014. 
  4. ^ „Wolfram”. Приступљено 9. 7. 2012. 
  5. ^ „Archimedes”. Приступљено 7. 10. 2012. 
  6. ^ „Bulls and Cows & co.”. Приступљено 7. 7. 2012. 
  7. ^ „Invicta Toy History page”. Архивирано из оригинала 12. 08. 2007. г. Приступљено 7. 8. 2012. 
  8. ^ „Landmark Reunion for Mastermind Box Models”. Приступљено 5. 10. 2006. 
  9. ^ Knuth, Donald (1976—77). „The Computer as Master Mind” (PDF). J. Recr. Math. (9): 1—6. Архивирано из оригинала (PDF) 29. 04. 2011. г. Приступљено 31. 05. 2015. 
  10. ^ Koyama, Kenji; Lai, Tony (1993). „An Optimal Mastermind Strategy”. Journal of Recreational Mathematics (25): 230—256. 
  11. ^ Knuth 2011, стр. 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

Литература

  • Knuth, Donald (2011). Selected papers on fun and games. Center for the Study of Language and Information. стр. 226. ISBN 9781575865843. 
Генијалац на Викимедијиној остави.