Piškvorky

Tic-tac-toe [1] je logická hra mezi dvěma protivníky na čtvercovém poli o velikosti 3 x 3 buňky nebo větším (až do "nekonečného pole"). Jeden z hráčů hraje s "křížkami", druhý - s "ne". Tradiční čínská hra ( Gomoku ) používá černé a bílé kameny.

Klasická verze

Pravidla hry

Hráči střídavě vkládají 3×3 znaky na volná políčka pole (jeden je vždy křížky, druhý je vždy nula). Vyhrává ten, kdo jako první postaví 3 své dílky vertikálně, horizontálně nebo diagonálně. První tah provede hráč umístěním křížků.

Obvykle vítězná strana na konci hry přeškrtne čarou své tři znaky (nula nebo křížek), které tvoří souvislou řadu.

Analýza

Pro každou ze stran jsou známé algoritmy, které zaručují remízu v jakékoli hře soupeře, a pokud udělá chybu, umožní vám vyhrát. Hra je tedy ve stavu „ mrtvá mrtvá “.

Níže jsou uvedeny některé z těchto strategií. Předpokládá se, že hráč vždy respektuje dvě pravidla, která mají přednost před všemi ostatními:

Pravidlo 1. Může-li hráč vyhrát okamžitě, udělá tak.
Pravidlo 2. Pokud hráč nemůže okamžitě vyhrát, ale jeho soupeř by mohl okamžitě vyhrát tahem na pole, hráč sám provede tah na toto pole, čímž zabrání okamžité prohře.

Pro kříže

Udělejte první pohyb do středu. Zbývající tahy, pokud pravidla 1-2 nelze použít, se provedou na tah volných rohů, který je nejdále od předchozího tahu nul , a pokud to není možné, na kteroukoli buňku.


	X
	Ó

Dokažme, že tato strategie vede k výhře nebo remíze. Pokud nula jde do strany, bude poloha (až do symetrie) následující:

	Ó
	X
X

Poté pravidla 1 a 2 povedou k pozici:

X	Ó	Ó
	X
X

vyhrát .

Pokud se nula dostane do rohu, pozice (až do symetrie) bude následující:

Ó
	X
		X

V závislosti na dalším pohybu nuly vznikne jedna ze tří pozic:

Ó	Ó
	X
		X

Ó
	X	Ó
		X

Ó		Ó
	X
		X

Křížky vítězí na prvních dvou pozicích . Ve třetím - remíza .

Pro nuly

Pamatujte, že pravidla 1-2, pokud jsou relevantní, mají přednost před vším níže uvedeným.

Pokud křížky provedly první pohyb do středu, přejděte do konce hry do libovolného rohu, a pokud to není možné, do libovolné buňky.

		Ó
	X

Pokud křížky provedly první pohyb do rohu, odpovězte pohybem do středu.

		X
	Ó

Při dalším tahu vezměte roh naproti prvnímu tahu křížků, a pokud to není možné, jděte do strany.

		X
	Ó
Ó	X

Pokud křížky provedly první pohyb do strany, odpovězte pohybem do středu.
Pokud je další pohyb křížků do rohu, vezměte opačný roh:

	X	Ó
	Ó
X

Pokud je další pohyb křížků na opačné straně, přejděte do libovolného rohu:

Ó	X
	Ó
	X

Pokud je další tah X na stranu vedle jejich prvního tahu, jděte do rohu vedle obou X

Ó	X
X	Ó

Strom herních situací

Strom herních situací pro hru piškvorky, kde hráč za piškvorky jde první a jedná podle výše uvedeného algoritmu a hráč za piškvorky si může dělat, co chce ( navíc je dán jeden vrchol pro racionální a pro iracionální akt, tedy jakýkoli jiný), sestává z 50 uzlů.

Počítačové řešení

Pro řešení tohoto druhu her je na počítači vytvořen strom herních situací v souladu s metodou minimax . Celkový počet uzlů v takovém stromě je 255168 [2] . Toto číslo se získá jako součet všech možných tahů - 9 možností v prvním kroku, 8 - pro každou z 9 ve druhém kroku, 7 - pro každou ze 72 možností ve třetím kroku atd., mínus situace předčasný konec hry (výhra).

Příklad jednodušší implementace nalezení vítězného hráče: https://github.com/evgnor86/XO_game.git

Zobecnění

Delší řádky

Můžeme uvažovat o hře, ve které vyhrává hráč, který jako první postavil identická znamení na obdélníkovém poli dostatečně velkém k tomu. V tomto případě můžete pole omezit na určitou velikost (počínaje ), nebo jej neomezovat vůbec (v tomto případě se mluví o „nekonečném“ poli) $n\geqslant 3$ $n\krát n$

Hraní až 4 stejných znaků na nekonečném poli není zajímavé, protože začátečník postaví „vidličku“ poměrně rychle a vyhraje. Hra na je také nezajímavá kvůli "remízové smrti". Existují strategie, které brání nepříteli v budování požadované linie. Když se však hra stává mnohem smysluplnější. Tato možnost má speciální název - piškvorky . Gomoku se původně hrálo na desce 19×19, později zmenšené na 15×15 polí. $n\geqslant 6$ $n=5$

Hlavní vítěznou taktikou při hře na nekonečném poli je stavba křižovatek ("forks"), které nedávají nepříteli možnost zablokovat všechny možné způsoby, jak postavit pětku. Aby nedošlo ke ztrátě, je nutné včas přerušit linie nepřítele o délce tří a více kusů.

Praxe ukázala, že při rovných pravidlech pro hráče má ten, kdo udělá první tah, výhodu, která mu umožňuje vyhrát dostatečně kvalifikovanou hrou, což bylo následně přísně prokázáno [3] [4] . Pro udržení zájmu o hru byly navrženy různé možnosti úpravy pravidel hry.

Takže se zavedením faulů (zakázaných tahů) pro hráče, který začíná jako první - má zakázáno stavět vidličky 3 × 3, 4 × 4, stejně jako stavět „dlouhou řadu“ svých figurek - nová hra tzv. renju bylo získáno s širokou škálou herních strategií a stejnými šancemi hráčů.

Úprava pole

Zvětšení velikosti pole již bylo diskutováno výše. Nejjednodušší, ale nejvíce taktickou bohatostí hry je přidat jedno pole podél jedné strany desky 3x3.

Další možností je změna topologie pole. Například lze uvažovat protilehlé strany pole, které mají být přilepeny, čímž se vytvoří buď povrch válce nebo torusu , nebo projektivní rovina . Můžete také zvětšit rozměr, například hrát v krychli 4x4x4, v hyperkrychli a tak dále.

Výměna ikon

Pravidlo, které říká hráčům, aby vkládali pouze svůj vlastní druh ikon, můžete zrušit.

Například varianta hry může být: hráči dají křížek nebo nulu (co chtějí); první vyhrává, pokud ze stejných ikonek postaví řadu požadované délky, druhý vyhrává, pokud se tak nestane před vyplněním pole.

Další možnost: ikona "vlastní" se mění s každým pohybem.

Výherní podmínky se mění

Místo abyste hru ukončili postavením první řady požadované délky, nemůžete se tam zastavit a pokračovat, dokud není pole zcela zaplněno. Například na jakémkoli poli můžete hrát o to, kdo ze svých znaků postaví nejvíce „čtyřek“.

Existuje také varianta Silvermanova tic-tac-toe . Využívá herní pole 4x4 buněk. Křížky vyhrávají, pokud je řada 4 stejných ikon (křížků nebo nul), jinak vítězí nuly.

K dispozici je i varianta hry s klasickým polem 3×3, ve které je pro výhru nutné vytvořit dvě řady, přičemž protichůdnému algoritmu stačí jedna. [5] [6]

Prodloužení tahu

Další možností, jak hru upravit, je dát na každý tah ne jedno ze svých znamení, ale dvě nebo více. Taková je hra Connect6 , ve které černý udělá první tah odkrytím jednoho znamení, poté hráči střídavě vystaví dvě znamení, vítězí ten, kdo jako první postaví řadu 6 nebo více svých znamení.

Piškvorky v kultuře

Této hře jsou věnovány tři písně.

Píseň „Tic Tac Toe“ od skladatele Veniamina Basnera na verše Michaila Matusovského v podání Taisiya Kalinchenko se stala laureátem „Songs-74“ [7] . Později ji nazpíval Eduard Khil [8]
Katya Lel zpívala další píseň se stejným názvem [9]
Třetí píseň nazpívali Viktor Rybin a Natalya Senchukova [10] jako duet .

Viz také

Gomoku
Renju
Hra s dokonalými informacemi
Smrt nikoho
Hexapawn
Konečný tic-tac-toe
Kvantové tic-tac-toe

Poznámky

↑ V 19. století se spolu s názvem „tic-tac-toe“ (viz N. A. Leikin , „Školní den v německé škole“, 1871) používalo také „heriki-oniki“ nebo „heriki“ - podle starý název ruských písmen abecedy "X" - "dick" a "O" - "it" ( "Dahl" v archivní kopii Dictionary of Dahl ze dne 14. června 2011 na Wayback Machine ), "nuly" ( N. P. Gilyarov-Platonov , „Ze zkušenosti“, 1886
↑ Kolik her Tic-Tac-Toe (nuly a křížky)? . www.se16.info. Získáno 16. srpna 2019. Archivováno z originálu 15. února 2020. (neurčitý)
↑ Allis, L. V. (1994). Hledání řešení ve hrách a umělé inteligenci, Ph.D. Diplomová práce, Univerzita Limburg, Maastricht.
↑ Allis, LV, Herik, HJ van den a Huntjens, MPH (1996). Go-Moku vyřešeno novými vyhledávacími technikami. Computational Intelligence, sv. 12.
↑ Dvakrát křížky-kruhy | videohra | VideoGameGeek
↑ Dvakrát křížem krážem: bezplatné stahování, půjčování a streamování: internetový archiv
↑ Taisiya Kalinchenko "Tic-tac-toe" (1974) . Získáno 17. ledna 2022. Archivováno z originálu dne 17. ledna 2022. (neurčitý)
↑ Eduard Khil, - Piškvorky . Získáno 17. ledna 2022. Archivováno z originálu dne 17. ledna 2022. (neurčitý)
↑ Káťa Lel - Piškvorky . Získáno 17. ledna 2022. Archivováno z originálu dne 17. ledna 2022. (neurčitý)
↑ Viktor Rybin a Natalya Senchukova - Tic-Tac-Toe . Získáno 17. ledna 2022. Archivováno z originálu dne 17. ledna 2022. (neurčitý)

Literatura

Gardner M. Piškvorky. —M.: Mir, 1988. ISBN 5-03-001234-6 .