Verze z 2. 12. 2011, 15:35 editovat Lukax (diskuse \| příspěvky) 1 164 editací m renju -> rendžu ← Přejít na předchozí porovnání		Verze z 2. 12. 2011, 16:05 editovat zrušit editaci Lukax (diskuse \| příspěvky) 1 164 editací lepší strategy stealing Přejít na další porovnání →
Řádek 8: == Matematická a výpočetní řešení == Na neomezené hrací ploše existuje neprohrávající strategie pro začínajícího hráče. Plyne to z [[Argument o kradení strategie\|argumentu o kradení strategie]], který platí pro všechny silné [[Poziční hra\|poziční hry]], jež plyne zhruba následovně:<ref>József Beck: Combinatorial Games: Tic-Tac-Toe Theory</ref> Lze snadno nahlédnout (uvedenému důkazu se říká [[argument o kradení strategie]] a platí pro všechny [[Poziční hra\|poziční hry]]), že na neomezené hrací ploše existuje neprohrávající strategie pro začínajícího hráče — za předpokladu, že by neexistovala, stačilo by začínajícímu hráči táhnout na libovolné neobsazené pole. Tím se kromě ztráty tahu do budoucna nemůžeme poškodit, naše piškvorka je vždy výhoda (což u her nepozičních platit nemusí, např. u šachů nám vlastní figura může bránit v úniku králem ze šachu). Tím by se dostal do pozice nezačínajícího hráče a v souladu s předpokladem (tj. že hráč, který nezačíná, má vítěznou strategii) by vyhrál, což by byl zároveň spor. Proto musí taková neprohrávající strategie pro začínajícího hráče existovat. * Nechť ([[Důkaz sporem\|pro spor]]) existuje výherní strategie nezačínajícího hráče. Budeme chtít využít (''ukradnout'') tuto strategii pro hráče začínají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]] vytvořil algoritmus<ref>L. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. thesis, University of Limburg, The Netherlands. ISBN 90-900748-8-0.</ref>, který na hracím poli 15×15 zajistí začínajícímu hráči výhru. Předpokládá se, že existuje také vyhrávající strategie pro větší rozměry hrací plochy, protože je nepravděpodobné, že by druhý hráč mohl využít tohoto prostoru k vynucení remízy.

Piškvorky: Porovnání verzí