Piškvorky - Tic-tac-toe

Piškvorky
Tic tac toe.svg
Dokončená hra tic-tac-toe
Ostatní jména
Žánry Hra na papír a tužku
Hráči 2
Čas na přípravu Minimální
Hrací čas ~ 1 minuta
Náhodná šance Žádný
Požadované dovednosti Strategie , taktika, pozorování

Tic-tac-toe ( americká angličtina ), noughts and crosses ( Commonwealth English ) nebo Xs and Os ( irská angličtina ) je hra na papír a tužku pro dva hráče, kteří se střídají při označování mezer ve hře tři na tři mřížka s X nebo O . Vyhrává hráč, který uspěje v umístění tří svých značek do horizontální, vertikální nebo diagonální řady. Je to vyřešená hra s nucenou remízou, která předpokládá nejlepší hru od obou hráčů.

Hratelnost

Tic-tac-toe hrají na mřížce tři na tři dva hráči, kteří střídavě umisťují značky X a O do jednoho z devíti polí v mřížce.

V následujícím příkladu první hráč ( X ) vyhrává hru v sedmi krocích:

Hra Tic-tac-toe, kterou vyhrál X

Neexistuje univerzálně dohodnuté pravidlo, kdo hraje jako první, ale v tomto článku se používá konvence, že X hraje první.

Hráči brzy zjistí, že nejlepší hra z obou stran vede k remíze . Tic-tac-toe proto často hrají malé děti, které možná neobjevily optimální strategii.

Vzhledem k jednoduchosti tic-tac-toe je často používán jako pedagogický nástroj pro výuku konceptů dobrého sportovního chování a odvětví umělé inteligence, které se zabývá hledáním stromů zvěře . Je jednoduché napsat počítačový program tak, aby perfektně hrál tic-tac-toe, nebo vyjmenovat 765 v podstatě různých pozic ( složitost stavového prostoru ) nebo 26 830 možných her až po rotace a odrazy ( složitost herního stromu ) v tomto prostoru. Pokud je oba hráči hrají optimálně, hra vždy skončí remízou, takže tic-tac-toe je marná hra .

Incidenční struktura pro tic-tac-toe

Hru je možné zobecnit na m , n , k -game , ve kterém dva hráči alternativní vestavby kamenů své vlastní barvy na M -by- n palubě s cílem získání K jejich vlastní barvy v řadě. Tic-tac-toe je hra 3,3,3. Hararyho generalizovaný tic-tac-toe je ještě širší generalizace tic-tac-toe. Lze ji také zobecnit jako hru n d , konkrétně hru , ve které n se rovná 3 a d se rovná 2. Lze ji zobecnit ještě dále hraním na libovolnou strukturu dopadu , kde řádky jsou čáry a buňky body . Struktura dopadu tic-tac-toe se skládá z devíti bodů, tří vodorovných čar, tří svislých čar a dvou diagonálních čar, přičemž každá čára se skládá alespoň ze tří bodů.

Dějiny

Hry hrané na deskách typu tři v řadě lze vysledovat až do starověkého Egypta , kde byly takové herní desky nalezeny na střešních taškách z doby kolem roku 1300 př. N. L.

Časná variace tic-tac-toe byla hrána v římské říši , kolem prvního století před naším letopočtem. Říkalo se tomu terni lapilli ( tři oblázky najednou ) a místo toho, aby měl libovolný počet figurek, měl každý hráč pouze tři; proto je museli přesunout do prázdných prostor, aby mohli dál hrát. Herní mřížkové značení bylo nalezeno křídou po celém Římě. Další úzce související starověká hra je morris tří mužů, která se také hraje na jednoduchém roštu a k dokončení vyžaduje tři figurky v řadě, a Picaria , hra Puebloans .

Různé názvy hry jsou novější. První tisková zmínka o „noughts and crosses“ ( nic není alternativní slovo pro „nulu“), britský název, se objevila v roce 1858 ve vydání Notes and Queries . První tisková zmínka o hře s názvem „tick-tack-toe“ se objevila v roce 1884, ale odkazovala na „dětskou hru hranou na břidlici, která spočívala v pokusu se zavřenýma očima přinést tužku na jedno z čísel nastaven, počet dosažených zásahů “. „Tic-tac-toe“ může také pocházet z „tick-tack“, názvu staré verze vrhcábu, který byl poprvé popsán v roce 1558. V USA došlo k přejmenování „noughts and crosses“ na „tic-tac-toe“ 20. století.

V roce 1952 se OXO (neboli Noughts and Crosses ), vyvinutá britskou počítačovou vědkyní Sandy Douglasovou pro počítač EDSAC na University of Cambridge , stala jednou z prvních známých videoher . Počítačový hráč mohl hrát dokonalé hry tic-tac-toe proti lidskému soupeři.

V roce 1975 použili studenti MIT také tic-tac-toe k demonstraci výpočetní síly prvků Tinkertoy . Počítač Tinkertoy, vyrobený z (téměř) pouze Tinkertoys, dokáže perfektně hrát tic-tac-toe. V současné době je vystaven v Muzeu vědy v Bostonu .

Kombinatorika

Když vezmeme v úvahu pouze stav desky a po zohlednění symetrií desky (tj. Rotace a odrazy), existuje pouze 138 pozic svorkovnice. Kombinatorika studium hry ukazuje, že když „X“ je první krok pokaždé, herní výsledky jsou následující:

  • 91 odlišných pozic získává (X)
  • 44 odlišných pozic získává (O)
  • Jsou vylosovány 3 různé pozice (často se jim říká „hra s kočkami“)

Strategie

Optimální strategie pro hráče X, pokud začíná v rohu. V každé mřížce stínovaná červená X označuje optimální tah a umístění dalšího tahu O dává další subgrid k prozkoumání. Všimněte si toho, že pouze dvě sekvence tahů O (obě začínající středem, vpravo nahoře, vlevo uprostřed) vedou k remíze, přičemž zbývající sekvence vedou k výhrám od X.
Optimální strategie pro hráče O. Hráč O si může vynutit výhru nebo remízu pouze hraním nejprve ve středu.

Hráč může hrát dokonalou hru tic-tac-toe (vyhrát nebo alespoň remizovat), pokud si pokaždé, když je na řadě, vybere první dostupný tah z následujícího seznamu, jak byl použit v Newellově a Simonově 1972 program tic-tac-toe.

  1. Výhra: Pokud má hráč dva v řadě, může umístit třetí, aby získal tři v řadě.
  2. Blok: Pokud má soupeř dva v řadě, musí hráč sám zahrát třetí, aby zablokoval soupeře.
  3. Vidlička: Způsobte scénář, kde má hráč dva způsoby, jak vyhrát (dva neblokované řady po 2).
  4. Blokování soupeřovy vidlice: Pokud existuje pouze jedna možná vidlice pro soupeře, hráč by ji měl zablokovat. V opačném případě by měl hráč zablokovat všechny vidlice jakýmkoli způsobem, který jim současně umožní udělat dvě za sebou. V opačném případě by měl hráč udělat dvojku v řadě, aby donutil soupeře k obraně, pokud to nevede k tomu, že vytvoří vidličku. Pokud má například „X“ dva protilehlé rohy a „O“ střed, „O“ nesmí hrát rohovým tahem, aby vyhrál. (Zahráním tahu na roh v tomto scénáři vytvoříte vidličku pro „X“ k vítězství.)
  5. Střed: Hráč označí střed. (Pokud se jedná o první tah hry, hraní rohových tahů dává druhému hráči více příležitostí k chybě a může být proto lepší volbou; mezi dokonalými hráči však není žádný rozdíl.)
  6. Opačný roh: Pokud je soupeř v rohu, hráč zahraje opačný roh.
  7. Prázdný roh: Hráč hraje v rohovém čtverci.
  8. Prázdná strana: Hráč hraje ve středním poli na kterékoli ze čtyř stran.

První hráč, který bude označen jako „X“, má během prvního kola tři možné strategicky odlišné pozice. Povrchně by se mohlo zdát, že existuje devět možných pozic, odpovídajících devíti čtvercům v mřížce. Otáčením desky však zjistíme, že v první zatáčce je každá značka rohu strategicky ekvivalentní každé jiné značce rohu. Totéž platí pro každou značku hrany (boční střed). Ze strategického hlediska tedy existují pouze tři možné první značky: roh, hrana nebo střed. Hráč X může vyhrát nebo vynutit remízu z kterékoli z těchto počátečních značek; zahrání rohu však dává soupeři nejmenší výběr polí, která musí být zahrána, aby se předešlo ztrátě. To by mohlo naznačovat, že roh je nejlepším otevíracím tahem pro X, ale jiná studie ukazuje, že pokud hráči nejsou dokonalí, je pro X nejlepší otevírací tah ve středu.

Druhý hráč, který bude označen „O“, musí na úvodní značku X reagovat tak, aby se vyhnul vynucené výhře. Hráč O musí vždy reagovat na rohový otvor středovou značkou a na středový otvor rohovou značkou. Na okrajový otvor je třeba odpovědět buď středovou značkou, rohovou značkou vedle X nebo hranovou značkou naproti X. Jakékoli jiné reakce umožní X vynutit výhru. Jakmile je zahájení dokončeno, úkolem O je postupovat podle výše uvedeného seznamu priorit, aby si vynutil remízu, nebo jinak získal výhru, pokud X odehraje slabou hru.

Podrobněji, aby zaručil remízu, O by měl přijmout následující strategie:

  • Hraje -li X tah otevíráním rohu, O by měl zaujmout střed a poté hranu, což donutí X zablokovat v dalším tahu. Tím se zabrání všem vidličkám. Když jsou X i O dokonalí hráči a X se rozhodne začít vyznačením rohu, O vezme střed a X zaujme roh naproti originálu. V takovém případě si O může jako druhý tah vybrat libovolnou hranu. Pokud však X není dokonalým hráčem a zahrál roh a poté hranu, O by neměl hrát opačnou hranu jako svůj druhý tah, protože pak X není nucen blokovat v dalším tahu a může rozdvojit.
  • Pokud X hraje pohyb otevíráním hran, O by měl mít střed nebo jeden z rohů sousedících s X a poté se řídit výše uvedeným seznamem priorit, hlavně dávat pozor na blokové vidlice.
  • Pokud X hraje pohyb otevírání centra, O by měl zahnout za roh a poté se řídit výše uvedeným seznamem priorit, hlavně věnovat pozornost blokovacím vidlím.

Když X nejprve zahraje roh a O není dokonalý hráč, může dojít k následujícímu:

  • Pokud O odpoví středovou značkou (nejlepší tah pro ně), perfektní hráč X vezme roh naproti originálu. Pak by O měl hrát o hranu. Pokud však O hraje jako druhý tah roh, perfektní hráč X označí zbývající roh, zablokuje O 3 v řadě a vytvoří si vlastní vidličku.
  • Pokud O odpoví rohovou značkou, X je zaručeno, že vyhraje jednoduše tím, že vezme kterýkoli z dalších dvou rohů a poté poslední, vidličku. (protože když X vezme třetí roh, O může zaujmout pouze pozici mezi dvěma X. Pak X může vzít jediný zbývající roh, aby vyhrál)
  • Pokud O odpoví hranou značkou, X je zaručeno, že vyhraje tím, že vezme střed, pak O může vzít pouze roh naproti rohu, který X hraje jako první. Nakonec si X může vzít roh a vytvořit vidličku a pak X vyhraje v dalším tahu.

Další detaily

Zvažte desku s devíti pozicemi očíslovanými následujícím způsobem:

1 2 3
4 5 6
7 8 9

Když X hraje 1 jako úvodní tah, pak O by mělo trvat 5. Potom X bere 9 (v této situaci by O neměl brát 3 nebo 7, O by měl vzít 2, 4, 6 nebo 8):

  • X1 → O5 → X9 → O2 → X8 → O7 → X3 → O6 → X4, tato hra bude remízou.

nebo 6 (v této situaci by O neměl vzít 4 nebo 7, O by měl vzít 2, 3, 8 nebo 9. Ve skutečnosti je nejlepší tah 9, protože nedokonalý hráč X může vzít 4, pak O může vezměte 7 a vyhrajte).

  • X1 → O5 → X6 → O2 → X8, pak O by neměl brát 3, nebo X může trvat 7, aby vyhrál, a O by neměl vzít 4, nebo X může vzít 9, aby vyhrál, O by měl vzít 7 nebo 9.
    • X1 → O5 → X6 → O2 → X8 → O7 → X3 → O9 → X4, tato hra bude remízou.
    • X1 → O5 → X6 → O2 → X8 → O9 → X4 (7) → O7 (4) → X3, tato hra bude remízou.
  • X1 → O5 → X6 → O3 → X7 → O4 → X8 (9) → O9 (8) → X2, tato hra bude remízou.
  • X1 → O5 → X6 → O8 → X2 → O3 → X7 → O4 → X9, tato hra bude remízou.
  • X1 → O5 → X6 → O9, pak by X neměl brát 4 nebo O může vyhrát 7, X by měl vzít 2, 3, 7 nebo 8.
    • X1 → O5 → X6 → O9 → X2 → O3 → X7 → O4 → X8, tato hra bude remízou.
    • X1 → O5 → X6 → O9 → X3 → O2 → X8 → O4 (7) → X7 (4), tato hra bude remízou.
    • X1 → O5 → X6 → O9 → X7 → O4 → X2 (3) → O3 (2) → X8, tato hra bude remízou.
    • X1 → O5 → X6 → O9 → X8 → O2 (3, 4, 7) → X4/7 (4/7, 2/3, 2/3) → O7/4 (7/4, 3/2, 3/ 2) → X3 (2, 7, 4), tato hra bude remíza.

V obou těchto situacích (X bere 9 nebo 6 jako druhý tah), X má a 1/3 majetek vyhrát.

Pokud X není dokonalý hráč, může X jako druhý tah zabrat 2 nebo 3. Pak bude tato hra nerozhodná, X nemůže vyhrát.

  • X1 → O5 → X2 → O3 → X7 → O4 → X6 → O8 (9) → X9 (8), tato hra bude remízou.
  • X1 → O5 → X3 → O2 → X8 → O4 (6) → X6 (4) → O9 (7) → X7 (9), tato hra bude remízou.

Pokud X hraje 1 úvodní tah a O není dokonalý hráč, může dojít k následujícímu:

Ačkoli O zaujímá jedinou dobrou pozici (5) jako první tah, ale O má špatnou pozici jako druhý tah:

  • X1 → O5 → X9 → O3 → X7, pak X může vyhrát 4 nebo 8.
  • X1 → O5 → X6 → O4 → X3, pak X může vyhrát 7 nebo 9.
  • X1 → O5 → X6 → O7 → X3, pak X může vyhrát 2 nebo 9.

Ačkoli O zaujímá dobré pozice jako první dva tahy, ale O zaujímá špatnou pozici jako třetí tah:

  • X1 → O5 → X6 → O2 → X8 → O3 → X7, pak X může vyhrát 4 nebo 9.
  • X1 → O5 → X6 → O2 → X8 → O4 → X9, pak X může vyhrát 3 nebo 7.

O vezme špatnou pozici jako první tah (kromě 5, všechny ostatní pozice jsou špatné):

  • X1 → O3 → X7 → O4 → X9, pak X může vyhrát 5 nebo 8.
  • X1 → O9 → X3 → O2 → X7, pak X může vyhrát 4 nebo 5.
  • X1 → O2 → X5 → O9 → X7, pak X může vyhrát 3 nebo 4.
  • X1 → O6 → X5 → O9 → X3, pak X může vyhrát 2 nebo 7.

Variace

Mnoho deskových her sdílí prvek snahy být první, kdo získá n - in -a-row, včetně tří pánských morrisů , devíti pánských morrisů , pente , gomoku , Qubic , Connect Four , Quarto , Gobblet , Order and Chaos , Toss Across a Mojo . Tic-tac-toe je příkladem hry m, n, k , kde se dva hráči střídají na desce m × n, dokud jeden z nich nedostane k za sebou. Hararyho generalizovaný tic-tac-toe je ještě širší generalizace. Hru lze ještě zobecnit hraním na libovolném hypergrafu , kde řádky jsou hyperhrany a buňky vrcholy .

Mezi další variace tic-tac-toe patří:

  • 3-dimenzionální tic-tac-toe na desce 3 × 3 × 3. V této hře má první hráč snadné vítězství tím, že hraje ve středu, pokud hrají 2 lidé.

Lze hrát na desce čtverců 4x4 a vyhrávat několika způsoby. Výhra může zahrnovat: 4 v přímce, 4 v diagonále, 4 v kosočtverci nebo 4 na vytvoření čtverce.

Další varianta, Qubic , se hraje na desce 4 × 4 × 4; byl vyřešen tím, Oren Patashnik v roce 1980 (první hráč může vynutit vítězství). Jsou také možné větší rozměrové variace.

  • V misère tic-tac-toe hráč vyhrává, pokud soupeř získá n v řadě. Hra 3 × 3 je remíza. Obecněji řečeno, první hráč může kreslit nebo vyhrát na jakékoli desce (jakéhokoli rozměru), jejíž délka strany je lichá, a to tak, že nejprve hraje v centrální buňce a poté zrcadlí tahy soupeře.
Magicsquareexample.svg
  • Ve „divokém“ tic-tac-toe si hráči mohou zvolit umístění buď X nebo O při každém tahu.
  • Number Scrabble nebo Pick15 je izomorfní až tic-tac-toe, ale na povrchu vypadá úplně jinak. Dva hráči zase řeknou číslo mezi jednou a devíti. Konkrétní číslo se nesmí opakovat. Hru vyhrává hráč, který řekl tři čísla, jejichž součet je 15. Pokud jsou použita všechna čísla a nikdo nezíská tři čísla, jejichž součet je 15, pak je hra remízou. Vynesení těchto čísel na magický čtverec 3 × 3 ukazuje, že hra přesně odpovídá tic-tac-toe, protože tři čísla budou uspořádána do přímky právě tehdy, pokud jich bude celkem 15.
r a n  i n o n e →  n
a s r i s e  s o →  s
t e a  t r o t →  t
 ↙

E  

A

 ↓

 

 ↓

 Ó

  r

  • Další izomorfní hra používá seznam devíti pečlivě vybraných slov, například „zkusit“, „nebo“, „být“, „zapnuto“, „libovolné“, „loď“, „podle“, „deset“ a „ucho“ . Každý hráč si postupně vybere jedno slovo a pro vítězství musí hráč vybrat tři slova se stejným písmenem. Slova mohou být vynesena na mřížku tic-tac-toe takovým způsobem, že vítězí řada tři v řadě.
  • Numerical Tic Tac Toe je variace vynalezená matematikem Ronaldem Grahamem . V této hře se používají čísla 1 až 9. První hráč hraje s lichými čísly, druhý hraje se sudými čísly. Všechna čísla lze použít pouze jednou. Vyhrává hráč, který v řadě položí 15 bodů (součet 3 čísel).
  • V sedmdesátých letech minulého století byla hra pro dva hráče vytvořená společností Tri-ang Toys & Games s názvem Check Lines , ve které se deska skládala z jedenácti jamek uspořádaných v geometrickém vzoru dvanácti přímých linií, z nichž každá obsahovala tři otvory. Každý hráč měl přesně pět žetonů a hrál postupně tak, že do každé jamky umístil jeden žeton. Vítězem se stal první hráč, jehož žetony byly uspořádány ve dvou řadách po třech (což byly podle definice čáry protínající se ). Pokud ani jeden hráč nevyhrál do desátého tahu, následující tahy spočívaly v přesunutí jednoho z vlastních žetonů do zbývající prázdné díry s omezením, že tento tah může být pouze ze sousední jamky.
  • Quantum tic tac toe umožňuje hráčům umístit na desku kvantovou superpozici čísel, tj. Pohyby hráčů jsou „superpozicemi“ her v původní klasické hře. Tuto variantu vynalezl Allan Goff z Novatia Labs.

Anglická jména

Tato hra má různá anglická jména, včetně:

Někdy jsou tic-tac-toe (kde hráči stále přidávají „figurky“) a morris tří mužů (kde se figurky začínají pohybovat po umístění určitého počtu) navzájem zaměňovány.

V populární kultuře

Různé herní show byly založeny na tic-tac-toe a jeho variantách:

  • Na hollywoodských náměstích zaplnilo cely mřížky tic-tac-toe devět osobností; hráči vkládají symboly na tabuli správným souhlasem nebo nesouhlasem s odpovědí celebrity na otázku. Variace přehlídky zahrnují čtverce pohádek a čtverce hip hopu . Britská verze byla Celebrity Squares . Austrálie měla různé verze pod názvy Celebrity Square, Personality Squares a All Star Squares .
  • Ve hře Tic-Tac-Dough si hráči vykládají symboly na tabuli odpovídáním na otázky v různých kategoriích, které se zamíchají poté, co oba hráči provedou obě tahy.
  • Ve hře Beat the Teacher soutěžící odpovídají na otázky, aby zvítězili a ovlivnili mřížku tic-tac-toe.
  • Na webu The Price Is Right je v několika národních variantách k dispozici hra s cenami s názvem „Secret X“, ve které hráči musí uhodnout ceny dvou malých cen, aby mohli vyhrát X (navíc k jednomu bezplatnému X) a umístit je na prázdnou desku. Musí umístit X do polohy, aby uhádly umístění titulárního „tajného X“ ukrytého ve středním sloupci desky a vytvořily tic-tac-toe čáru vodorovně (napříč) nebo diagonálně (svislé čáry nejsou povoleny). V této variantě hry nejsou žádní Os.
  • Na minutu k vítězství , hra Ping Tac Toe má jednoho soutěžícího, který hraje hru s devíti sklenicemi naplněnými vodou a bílými a oranžovými míčky na ping-pong a snaží se získat tři v řadě z každé barvy. Po každém úspěšném přistání musí střídat barvy a musí dávat pozor, aby se nezablokovali.

Viz také

Reference

externí odkazy