Býci a krávy

Býci a krávy

Snímek obrazovky PC verze hry. Vyhraná partie v sedmi tazích
Hráči 2
Délka party 5-30 minut
Složitost pravidel Nízký
Úroveň strategie Nízký
Vliv náhody Nízký
Rozvíjí dovednosti logické myšlení, počítání, paměť

Býci a krávy  je logická hra, ve které musí jeden z hráčů po několika pokusech zjistit, na čem je druhý. Možnosti hry mohou záviset na typu uhodnuté sekvence – mohou to být čísla, barvy, piktogramy nebo slova. Po každém pokusu počatý hráč umístí „skóre“, uvádějící počet tipů, aniž by odpovídaly jejich pozici (počet „kráv“) a kompletních shod (počet „býků“). Role účastníků hry nejsou rovnocenné - hádající musí analyzovat provedené pokusy a obdržené skóre, to znamená, že jeho role je aktivní. Jeho partner pouze porovnává další variantu s plánovanou a hodnotí podle formálních pravidel, tedy jeho role je pasivní. Pro vyvážení rolí hrají současně dvě protilehlé strany.

Zpočátku byla hra koncipována pro dva hráče, ale s příchodem počítačových verzí se stala populární možnost, kdy hráč uhodne číslo koncipované programem, to znamená, že hraje sám. Ke společné hře stačí mít papír a tužku. V elektronických verzích hru na dálku proti nepříteli zajišťuje funkce hry pro více hráčů (multiplayer).

Pravidla hry

V klasické verzi je hra určena pro dva hráče. Každý z hráčů počne a zapíše tajné 4místné číslo s neopakujícími se čísly [1] . Hráč, který zahájí hru losem, se jako první pokusí uhodnout číslo. Pokus je 4-místné číslo s neopakujícími se číslicemi hlášené soupeři. Oponent v odpovědi hlásí, kolik čísel bylo uhodnuto, aniž by odpovídalo jejich pozicím v tajném čísle (tj. počet krav) a kolik bylo uhodnuto až do pozice v tajném čísle (tj. počet býků). Například:

Tajné číslo „3219“ je vymyšleno.

Pokus: "2310".

Výsledek: dvě „krávy“ (dvě čísla: „2“ a „3“ byla uhodnuta na nesprávných pozicích) a jeden „býk“ (jedno číslo „1“ bylo uhodnuto až na pozici).

Hráči se střídají v hádání soupeřova čísla. Vyhrává ten, kdo jako první uhodne číslo za předpokladu, že hru nezačal. Pokud hádající zahájil hru, jeho soupeř má poslední šanci uhodnout sekvenci.

Při hře proti počítači hráč zadává kombinace jednu po druhé, dokud neuhodne celou sekvenci.

Varianty hry

Ve hře "mastermind" ( angl.  Mastermind , možný překlad: "Intellectual, smart guy") se uhodne sekvence 4 barevných žetonů a barvy se mohou opakovat. Ve složitější verzi lze použít sekvenci 5, 6 nebo více žetonů [2]

Existuje varianta slovní hry [3] [4] [5] . To znamená, že hráč vymyslí slovo, obvykle o 5 písmenech (v nominativu jednotného čísla podle pravidel hry „ balda “), a úkolem soupeře je uhodnout je pomocí stejných správných slov z ruského slovníku jako pokusy. Existuje však i možnost, kdy je možné použít libovolnou kombinaci písmen. S rozšířením osobních počítačů se objevily softwarové implementace hry „Býci a krávy“ se slovy [6] . Hra se využívá ve speciální pedagogice [7] a ve výuce informatiky [8] . V roce 2021 se počítačová implementace hry s pětipísmennými slovy anglického jazyka Wordle rozšířila po celém světě a přitáhla pozornost tisku.

Algoritmus

Obecně platí, že počet možností pro k-místné číslo v N-ární číselné soustavě bez opakování se bude rovnat počtu umístění : .

V případě varianty s opakováním bude počet variant roven .

Většina známých algoritmů jsou variacemi algoritmu hrubé síly s určitou heuristikou . Vzhledem k tomu, že počet možností není tak velký a schéma přímého výčtu je elementárně implementováno, počítač hraje býky a krávy mnohem silnější než člověk. Čím více znaků v čísle, tím větší je rozdíl v síle hry mezi člověkem a počítačem.

Jak ukázal Donald Knuth , pro hru Mastermind (6 4 možnosti) se strategií, kterou navrhl, není potřeba více než 5 pokusů uhodnout jakoukoli kombinaci a v průměru 4 321 pokusů uhodnout [9] [10] .

Knuthův strategický algoritmus je následující:

  1. Sestrojte množinu S z 6 4 = 1296 možných kódů (1111, 1112, ..., 6666).
  2. Udělejte první tah s kódem dvou odpovídajících čísel, například 1122 (Knuth uvádí příklad, který ukazuje, že jiné počáteční odhady, jako je 1123 nebo 1234, nemohou vždy uhodnout kombinaci na 5 pokusů).
  3. Pokud je kombinace uhodnuta, algoritmus končí.
  4. V opačném případě odstraňte z S všechny kódy, které by vzhledem k tomu, že jsou tajné, poskytly jiný výsledek, než jaký byl přijat.
  5. Proveďte následující pohyb podle pravidla minimax :
    • Pro jakoukoli kombinaci původních 1296 (včetně těch, které nejsou v S) vypočítejte, kolik možných kódů bude odstraněno z S v případě jakéhokoli výsledku tahu. Počet bodů udělených za možný tah se rovná minimálnímu počtu prvků, které lze odstranit z S.
    • Jeden průchod sadou S pro každou nevyužitou kombinaci 1296 možných dá určitý počet krav a býků; kombinace býků a krav s největším počtem shod odstraní ze sady nejméně možností; počet bodů udělených za tah se bude rovnat počtu prvků v S mínus nejvyšší počet zápasů.
    • Ze všech tahů s maximálním počtem bodů má přednost tah, který je v S. Pokud je takových možností více, můžete si vybrat kteroukoli z nich. Pro zjednodušení postupu výběru varianty Knuth navrhuje zvolit tah s nejmenší číselnou hodnotou (například 2345 je menší než 3456).
    • Pokud se nejlepší tah nezapočítá do S, pak hra rozhodně nekončí dalším tahem.
  6. Opakujte od kroku 3.

Implementace

Existuje mnoho možností pro elektronickou implementaci hry, včetně mobilních telefonů a mobilních počítačů.

Deskové hry Mastermind jsou populární po celém světě. Nejběžnější varianty jsou:

V kultuře

Viz také

Poznámky

  1. ↑ Hra Bulls and Cows v aplikaci Microsoft Excel Archivováno 1. února 2009 na Wayback Machine . Do světa informatiky , č. 78.
  2. ↑ Vyšetřování deskové hry Master MindTM . Datum přístupu: 21. září 2013. Archivováno z originálu 28. října 2013.
  3. ↑ D. W. Lubich, Lingvistické hry , 1998, s. 47
  4. ↑ Aleph, ne. 1990, strana 45
  5. ↑ T. N. Obraztsova, Logické hry pro děti , 2005
  6. ↑ G. E. Senkevich, Počítač pro osoby se zdravotním postižením , 2014, s. 218
  7. ↑ Zh. M. Glozman, A. E. Soboleva (ed.), Komplexní náprava poruch učení ve škole , 2014, s. 242
  8. ↑ L. Bosová, N. Natelauri (ed.), Aktuální problémy metod výuky informatiky v moderní škole , 2020
  9. ↑ Strategie Mastermind Optimal Archivováno 14. září 2008 na Wayback Machine  
  10. ↑ Knuth, Donald. Vybrané referáty o zábavě a  hrách . - Centrum pro studium jazyka a informací, 2011. - S. 226. - ISBN 9781575865843 .
  11. ↑ "Hackování terminálu" . Získáno 12. června 2022. Archivováno z originálu 19. ledna 2019.

Odkazy