D#8 – Piškvorky
Piškvorky jsou strategická hra, ve které spolu soupeří dva hráči. Nejčastěji se hraje na čtverečkovaném papíře, na kterém se hráči střídají v kreslení křížku/kolečka. Vyhrává hráč, který jako první vytvoří nepřerušenou řadu pěti svých značek.
Historie
Hra, respektive její princip, vznikla pravděpodobně nezávisle na sobě v různých částech světa. První zmínky o obdobě piškvorek pocházejí z oblasti okolí delty řeky Hwang Ho v Číně a jsou datovány do období 2000 let př. Kristem. Japonské slovo gomoku, které se dnes používá mezinárodně, znamená 5 kamenů v řadě (go = 5, moku = průsečík). Údaje o hře byly objeveny i v antickém Řecku a v předkolumbovské Americe.
Matematická a výpočetní řešení
Pro piškvorky na omezené i neomezené hrací ploše existuje neprohrávající strategie pro začínajícího hráče. Plyne to z argumentu o kradení strategie, který platí pro všechny silné poziční hry, jež plyne zhruba následovně:
- Nechť existuje výherní strategie nezačínajícího hráče. Budeme chtít využít (ukradnout) tuto strategii pro hráče začínajícího.
- První piškvorku nechť první hráč zahraje na libovolné pole. Tomuto tahu budeme říkat tah zahozený.
- Každý další tah nechť začínající hraje podle hypotetické vyhrávající strategie druhého hráče pro hru bez zahozeného tahu, tedy pro hru, v ní původně nezačínající hráč začíná (původně až druhým tahem). Pokud mu strategie určí zahrát do zahozeného tahu (který jí byl předložen jako neobsazený), nechť hráč zahraje na libovolné neobsazené pole a tento tah si dále pamatuje jako zahozený (tj. pamatuje si hru, jako by úvodní zbytečný tah zahrál na toto nové místo a původní zahozený tah zahrál až ve chvíli, kdy byl diktován ukradenou strategií).
- Byla-li strategie nezačínajícího hráče vítězná, musí být vítězná také tato pozměněná strategie. Nemůže však existovat vítězná strategie jak pro hráče začínajícího, tak pro nezačínajícího: to je kýžený spor.
Holandský počítačový expert L. Victor Allis dokázal, že na hracím poli 15×15 má začínající hráč vítěznou strategii. Vyhrávající strategie existuje také pro větší rozměry hrací plochy, protože druhý hráč nemůže využít tohoto prostoru k vynucení remízy.
Programy s počítačovým protihráčem, které dokáží obstojně hrát proti člověku nebo jinému programu, jsou zpravidla založený na algoritmu minimax, který je různými postupy (např. alfa-beta ořezávání, killer move) optimalizován pro větší efektivitu. Tento algoritmus se užívá i pro strojově asistované důkazy, jakým je například výše zmiňovaný Allisův.
Zdroj: https://cs.wikipedia.org
Ke kešce:
N48°??.???‘ E017°??.???‘
NEZAPOMĚNTE SI OPSAT BONUSOVÉ ČÍSLO !!!