Student World

***pravidelné páteční „přetištění“ staršího článku

Dáma se dnes ve světě hraje v celé řadě variant, popsaný důkaz se týká verze převažující i u nás, tedy té, která se hraje na ploše 8 * 8 (šachovnice), kde jsou kameny obou stran na začátku ve třech řadách. Jde o anglickou, nikoliv tzv. mezinárodní dámu.

Důkaz provedl Jonathan Schaeffer z univerzity v kanadské Albertě a zabral mu 18 let hrubé počítačové práce. V této variantě dámy může vzniknout až 10 na 20 pozic. Schaeffer postupoval podobně jako u šachů, kde také postupně přibývají totálně propočítané n-kamenové koncovky. Nejprve hrubou silou prošel prostor koncovek s méně než 10 kameny, což obnášelo cca 39 bilionů pozic. Posléze dokázal, že pokud žádný z hráčů neudělá chybu, vede z každého zahájení cesta do pozice z této databáze, která končí remízou. Během 18letého počítání Schaeffer samozřejmě využíval četných symetrií, které znamenají, že určité pozice jsou si ekvivalentní.
Výpočet běžel od roku 1989 na 200 osobních počítačích, přičemž bylo samozřejmě třeba se úzkostlivě vyvarovat chyb – v takovém případě by mnohaletá práce vyšla nazmar.

Spolu s důkazem Schaeffer představil také novou verzi svého programu Chinook, který je nyní opravdu neporazitelný – samozřejmě v případě, že důkaz/provedený postup je opravdu bezchybný, o čemž ale nepanují pochybnosti. Původní oznámení vyšlo v časopisu Science.
Chinook ještě před svou neporazitelností již v roce 1994 zvítězil v zápase s mistrem světa Mariono Tinsleyho, který je považován za nejlepšího lidského hráče dámy všech dob. Program nyní funguje tak, že neprohledává kompletně celý stavový prostor – stačí mu vždy například najít jedinou cestu k výhře.
Chinook je on-line k dispozici na http://www.cs.ualberta.ca/~chinook.

Zdroje:
New Scientist
Nature

Poznámky:
– Ačkoliv je v článcích používán výraz „umělá inteligence“, člověku přichází na mysl spíše rčení „nenamáhej se, vezmi si větší kladivo“. V důkazu samozřejmě ale nejde jen o bezduché počítání, ale i o mnoho optimalizací. Jonathan Schaeffer proto svůj algoritmus nepokládá za hříčku, ale domnívá se, že by se mohl uplatnit i při řešení problémů z reálného světa, třeba při práci s rozsáhlými databázemi biologických dat.
– V článku na Nature je citován názor, že podobného výsledku pro šachy bychom se mohli někdy v letech 2060-2070.
– Hráči dámy přijali podaný důkaz pozitivně. Tvrdí, že na jejich zájmu hrát dámu to ale nic nemění, i když je otázka, zda nyní bude někoho lákat se postavit proti Schaefferovu programu.

autor Pavel Houser