Fakulta informatiky Masarykovy univerzity

Počítač hraje šachy

(historie i budoucnost)

Brno 1999 Pavel Řehulka


Contents

Úvod

Šachová hra vznikla přibližně v druhé polovině šestého století v severozápadní Indii. Je pravděpodobné, že byla vynalezena jedinou osobou v krátkém časovém období. Hra se řídila tehdy běžnými pravidly při bitvách: každá z obou armád měla pěchotu (pěšci), slony (dnešní střelci), jezdectvo (jezdci), velké bojové vozy (věže) a vezíra (dámu). Hru později převzali Peršané a Arabové, kteří ji v osmém století přinesli do Evropy. V průběhu času se pravidla částečně pozměnila a měnily se i názvy šachových figur. Ve své podstatě hra přetrvala stejná dodnes.

V současné době se šachovou hrou zabývá půl miliardy lidí. Existují desetitisíce šachových oddílů, více než 130 národních federací a mezinárodní svaz. A díky existenci počítačové techniky se zkoumáním šachové hry zabývají různé výzkumné ústavy, univerzity a programátorské firmy.

Dějiny počítačových strojů však nezačaly až ve dvacátém století. První pokus o počítačový stroj se objevil už v osmnáctém století. Nebyl to šachový stroj v pravém slova smyslu; nutno však podotknout, že vzbudil mimořádný ohlas.

První šachové stroje

Kempelenův Turek

V roce 1769 pověřila rakouská císařovna Marie Terezie pětatřicetiletého barona Wolfganga von Kempelena zvláštní zakázkou: měl jí postavit velkolepý stroj, který by předčil vše, co doposud viděla. Baron tuto výzvu přijal a zkonstruoval něco překvapivého. Vytvořil stroj, který hrál šachy, a to velmi výborně.

Stroj měl podobu orientálně oděného muže sedícího před dřevnou skříňkou. Tento stroj byl před každým představením vždy pečlivě zkontrolován. Postupně byla otevřena všechna dvířka a vnitřní mechanika byla prosvětlena svící. Podobně byla zkontrolována i postava muže. Zdálo se téměř nemožné, aby uvnitř seděl člověk.

Při představení byl přístroj nejprve natažen pomocí klíče. Po natažení se pohnula pravá ruka muže a vykonala první tah. Protivníkovy tahy rozeznal přístroj sám. Turek - jak se postavě říkalo - pohyboval hlavou a očima, přičemž zjišťoval pozici na šachovnici. Přitom bylo slyšet vrzání ozubených koleček a pák. Občas bylo nutné přístroj opět natáhnout. V naprosté většině případů stroj vyhrál. Jen vyjímečně se stalo, že návštěvník stroj porazil. To se ovšem nestalo slavnému Napoleonovi, který sehrál s Turkem tři partie a všechny prohrál.

V tehdejší době prožívala svůj vrchol výroba různých automatů, které chodily, tančily, skákaly apod. Proto většina lidí viděla v šachovém přístroji jen nutnost použití lepší a dokonalejší mechaniky nebo podvod. Např. Edgar Alan Poe si myslel, že pokud by byl vynalezen způsob jak naučit hrát stroj šachy, pak by bylo jen otázkou času, kdy se přístroj zdokonalí natolik, aby porazil každého protihráče. Protože přístroj dělal chyby, byl přesvědčen, že ve stroji je ukryt člověk. Poněkud jinak uvažoval Poeův současník, Angličan Robert Willis, který napsal o Kempelenově stroji knihu. V ní mimo jiné uvádí, že šachová hra obsahuje poněkud jiný rozměr, který nemůže zvládnout žádná mechanika světa. Počet nepředvídatelných situací je natolik velký, že přesahuje možnosti stroje. Proto v přístroji musí být člověk, který hraje šachy. Willis v knize popisuje, jak asi celé představení probíhalo a co bylo třeba udělat, aby přítomnost člověka v Kempelenově stroji zůstala divákům utajena.

Tajemství Turka nebylo nikdy zveřejněno. Ví se asi jen tolik, že stroj obsluhovali nejlepší z šachových mistrů Evropy. Byli mezi nimi Mouret, Allgaier (který porazil Napoleona) a Francouz Schlumberger, který byl s přístrojem na turné ve Spojených státech po dobu deseti let a jehož smrt v roce 1838 náhle ukončila aktivní dráhu šachového stroje.

Babbage a analytický stroj

Další pokus o sestrojení šachového stroje se konal v Anglii počátkem 19. století. Nejednalo se vlastně přímo o šachový stroj, ale o Analytical Engine, který měl být velmi univerzálním strojem. Jeho autorem byl Charles Babbage.

Tento stroj měl za úkol počítat logaritmické tabulky a také je tisknout. Řízení stroje mělo probíhat na principu děrných štítků. A jako ukázku výkonnosti tohoto stroje chtěl Babbage sestrojit testovací verzi, která by byla určena pro šachovou hru. Tento plán ztroskotal stejně jako celý plán sestrojení Analytical Engine. Důvod ztroskotání byl jednoduchý: Babbage předběhl svou dobu velmi výrazně a projekt, který si předsevzal, byl příliš rozsáhlý.

Nicméně strategie, které Babbage pro svůj šachový stroj vymyslel, se zachovaly a některé z nich se používají v šachových programech ještě dodnes. Babbageův šachový stroj měl v každé pozici klást následující otázky a z odpovědí vyvodit svou reakci:

Předchozí strategie ve své době velmi vyspělé. Při podrobnější analýze však dospějeme ke zjištění, že se zde vyskytují logické chyby a nebyla správně odhadnuta složitost celého problému.

Torresův automat

První pravý šachový stroj zkonstruoval Torres Y Quevedo v roce 1890. Tento Španěl byl specialistou na elektromechanické řídící systémy, které se používaly například při námořní navigaci. Při vývoji automatické regulace hloubky ponoření torpéd ho napadlo, aby inteligenci tohoto zařízení využil pro sestrojení mnohem složitějšího mechanismu, který by ovládal strategickou hru.

Torres si pro tento účel vybral omezenou část šachu: koncovku král a věž proti králi. Automat, který sestrojil, byl velmi zdařilý. Pomocí mechanického pohybu a nejjednoduších magnetických relé skutečně dokázal sehrát koncovku. Tento stroj dosud existuje a je vystaven v Polytechnické univerzitě v Madridu.

Papírový stroj Alana Turinga

V roce 1939 založilo britské ministerstvo zahraničí v městečku Bletchley zvláštní oddělení, které se mělo zabývat dešifrováním německých rádiových depeší. V tomto oddělení pracoval také mladý matematik Alan Mathieson Turing. Ten se už tehdy začal zabývat myšlenkou umělé inteligence strojů. Protože sám byl nadšeným šachistou, chtěl také vytvořit stroj, který by dovedl hrát šachovou hru. Neví se, zdali experimentoval s výpočetními automaty v tomto oddělení, ale je jisté, že už tehdy začal vyvíjet první program pro šachovou hru.

Tento program na šesti stranách popisoval přesné instrukce pro výpočet tahů. Protože tehdy ještě nebyl k dispozici žádný počítač, na kterém by se Turingem navržený algoritmus realizoval, musel Turing počítat tahy ručně. Program fungoval takto:

Protože ovšem, zejména při zahájení, dávala většina v úvahu přicházejících tahů stejný výsledek (), zavedl Turing také některá kritéria pro vyhodnocení pozice:

Podle Turingových algoritmů je tedy nejlepší zahájení: 1.e4 Jc6 2.d4.

V roce 1952 se uskutečnila první partie mezi Turingovým papírovým strojem a kolegou Alickem Glenniem, který hrál šachy jen rekreačně. Hra byla vyrovnaná, stroj mohl v 22. tahu vyhrát. Výpočty však vedly k jinému konci a protože papírový stroj nezná vazbu, Glennie vyhrál. Zde se ukázalo, že celý problém tvorby šachového stroje je podstatně složitější.

První vítězství počítače

V roce 1950 byl v laboratoři v Los Alamos pod vedením Johna von Neumanna sestrojen počítač MANIAC I. Ten byl schopný provést 10 000 operací za sekundu a bylo jej možné volně programovat.

Toto byl nový průlom. Naskytlo se mnoho nových možností a jeden z experimentů bylo programování šachové hry. Aby se úloha zjednodušila, byla šachovnice zmenšena na polí (byly odstraněni oba střelci a oba pěšci). Na jeden tah potřeboval počítač asi 12 minut. S regulerní šachovnicí by jeden tah počítal asi tři hodiny.

Program byl dokončen v polovině padesátých let a sehrál celkem tři partie. První sehrál sám proti sobě (bílý vyhrál), druhou proti silnému hráči, který počítači daroval dámu. Tato partie trvala 10 hodin a skončila vítězstvím šachového mistra. Třetí partii hrál proti jedné člence výzkumného týmu, která se naučila hrát šachy asi týden před vlastní partií. A stalo se - poprvé v dějinách prohrál člověk šachovou partii s počítačem.

Vývoj v posledních letech

Od poloviny 60. let nabral vývoj nové obrátky. Díky novým technologiím se počítače staly výkonnějšími. Daly se lépe programovat a tak mohly začít vznikat lepší a kvalitnější programy. V následujících odstavcích si stručně shrneme další vývoj tvorby počítačových strojů.

MacHack a Dreyfusova aféra

První programem, který se zúčastnil lidského turnaje, byl MacHack, vyvinutý v roce 1966 Richardem Greenblattem a dvěma jeho kolegy na známém Massachusetts Institute of Technology (MIT). Jednalo se o program, který v sobě obsahoval jak metodu selektivní, tak i metodu hrubé síly. Program byl vysoce selektivní, což mělo za následek časté přehlédnutí jednoduchých kombinací. Proto autor postavil doplňující stroj, který pracoval souběžně s MacHackem a oceňoval jen materiál.

V lednu 1967 hrál MacHack na amatérském mistrovství ve státě Massachusetts a z pěti partií uhrál v jedné remízu. Za to obdržel americké hodnocení 1240 (asi 1040 bodů ELO), které v průběhu let vzrostlo až na 1529 bodů.

V tehdejší době probíhal ostrý spor v oblasti umělé inteligence. Temperamentní profesor filosofie Hubert Dreyfus ostře napadl umělou inteligenci a celý obor odbyl jako fantazii. Doslechl se o tom Seymour Papert z MIT a ihned jej vyzval, aby si zahrál proti programu svého studenta Greenblatta. Dreyfus, který neznal MacHack, souhlasil. Během partie neustále vysvětloval, proč počítač nemůže nikdy dobře hrát šachy - až najednou zjistil, že mu hrozí porážka. Začal bojovat, ale v 37. tahu dostal mat. Odborníci na umělou inteligenci jásali, ale sám Papert se vyjádřil ve smyslu, že ani počítač ani Dreyfus neuměli hrát pořádně šachy.

Chess a Levyho sázka

V letech 1967 až 1970 došlo ke skutečnému boomu v programování šachu. Bylo napsáno nejméně osm nových programů a v roce 1970 bylo vyhlášeno první mistrovství v počítačovém šachu. Konalo se v rámci počítačové konference, kterou pořádala Association for Computing Machinery (ACM).

První turnaj tehdy vyhrál Chess 3.0, který vytvořili David Slate, Larry Atkin a Keith Gorlen. Tento program zvítězil celkem na čtyřech turnajích a na počítačovém mistrovství světa. Tento program byl ale také velmi úspěšný na lidských šachových soutěžích. V roce 1976 se zúčastnil renomovaného turnaje v Saratoze a porazil všech pět lidských protivníků.

Koncem 60. let byl spor o intelektuální schopnosti počítačů ještě v plném proudu. Sebevědomý mladý šachista, skotský mistr David Levy, patřil ke kritikům, kteří se o výkonnosti šachových programů rádi vyjadřovali hanlivě. V srpnu 1968 tak učinil na konferenci, jíž se zúčastnili dva odborníci počítačového šachu a umělé inteligence. John McCarthy a Donald Michie, profesoři na univerzitách ve Stanfordu a Edinburghu rozhodně odporovali. Levy jim nato nabídl sázku: v průběhu deseti let se žádnému počítači na světě nepodaří, aby jej v soutěži porazil. Každý z vědců vsadil 250 liber a zakrátko přidali Seymour Papert z MIT a Ed Kozdrowicki taktéž po 250 librách, zatímco Michie zvýšil svůj vklad na 500 liber. Celkem tedy hrál Levy o 1250 liber.

Tento Skot byl tehdy silným hráčem, který navíc velmi dobře rozuměl způsobu hry počítačů. Devět let porážel všechny počítače, většinou při simultánních hrách. V srpnu 1978 sehrál Levy závěrečný souboj o šesti partiích s tehdy nejlepším šachovým programem světa Chess 4.7 v Torontu. Hned v první partii byl zaskočen, ale nakonec vyhrál 3,5:1,5 a tím definitivně vyhrál svoji sázku.

Speciální stroj Belle

Koncem 70. let stálo programování šachu před problémem: jak zlepšit dále výkony šachových počítačů? Nejlepší programy tehdy dosáhly úroveň mistrovských hráčů, ale další pokrok byl v nedohlednu. Inteligentní šachové programy nebyly schopné hrát ani na úrovni šachových programů střední síly. A programy používající algoritmu hrubé síly potřebovaly na zvýšení herní síly několikanásobné zvýšení výkonu počítačů. Co s tím?

Objevilo se malé překvapení: v roce 1980 se objevil speciální přístroj nazvaný Belle. Jeho autoři - Ken Thompson a Joe Condon - si dali za cíl 1 000 000 pozic za sekundu, ale museli se uskromnit na asi 150 000 až 180 000 pozic za sekundu. Pro srovnání: tehdy nejlepší program Chess 4.8 na superpočítači Cyber 176 dokázal rovných 5 000. Belle byla práce dvou nadšených vědců, kteří se rozhodli napevno zadrátovat algoritmus hrubé síly do jednoho stroje. Úspěch jejich práce byl vskutku velký a Belle sklidila mnoho úspěchů.

Výkony, které na šachovnicích Belle odvedla v letech 1980 až 1983, byly pozoruhodné. Tento stroj vyhrál všechno, co se v počítačovém šachu vyhrát dalo. Dokázal zcela potřít konkurenci a na žádném počítačovám turnaji neobsadil horší než první místo. Ještě během čtvrtého mistrovtví světa v počítačovém šachu v New Yorku (říjen 1983) mu šachová federace USA propůjčila oficiální titul národního mistra - to bylo poprvé, co byl takto poctěn počítač.

Šachy na počítači Cray

V roce 1975 začal Robert Hyatt z univerzity v Mississippi vyvíjet nový program Blitz. Brzy se k němu přidal Al Gower a v roce 1979 se pak obrátili na vývojové oddělení firmy Cray. Ta jim přislíbila pro jejich pokusy špičkový počítač.

Cray 1 tehdy dovedl za sekundu provést až 80 miliónů aritmetických operací. S tímto výkonem a programem Blitz v roce 1981 vyhrál otevřené mistrovství státu Mississippi. Spolu s Belle se Cray Blitz zúčatnili několika turnajů, ale malá mašinka Belle se nedala porazit. Očekávaného vítězství se počítač Cray dočkal až v roce 1983. Mistrovství světa v počítačovém šachu se tehdy účastnil úplně nový Cray I X-MP. Navíc program Blitz byl optimalizován na strojový kód počítače Cray. S výkonem 210 000 000 operací za sekundu se poprvé tedy podařilo zdolat tisíckrát levnější stroj.

Deep Thought

Na univerzitě Carnegie-Mellon v Pittsburgu se sešla skupina těchto studentů: Feng-Hsiung Hsu, elektroinženýr z Taiwanu, Thomas Anantharaman z Hindu univerzity v Benares (Indie), Murray Campbell z univerzity v Albertě (Kanada), turnajový hráč šachu, a Andreas Nowatzyk, fyzik a informatik z univerzity v Hamburku. Všichni chtěli napsat své doktorandské práce na univerzitě v Carnegie-Mellon.

Hsu jako první přišel s myšlenkou implementovat kompletní generátor tahů za pomoci technologie VLSI na jediný čip. Po deseti měsících se mu podařilo rozdělit algoritmy na 39 925 tranzistorů. Tento procesor vygeneroval 2 000 000 tahů za sekundu.

Po jejich částečném úspěchu s nehotovým strojem na mistrovství v počítačovém šachu se dali do práce s vysokým nasazením. Vylepšili algoritmus, mikrokód a svůj projekt nazvali Deep Thought. Počítač v ceně součástek 5 000 dolarů vyhrál v roce 1987 Severoamerické mistrovství světa.

V roce 1989 přešli tři členové týmu Deep Thought do výzkumného ústavu patřícího firmě IBM. Stroj byl rozšířen a vylepšen. Na zásuvných kartách se zhruba 250 čipy byly umístěny vždy dva šachové procesory, které pracoval paralelně: Deep Thought II používal celkem 16 až 24 procesorů (na 8 až 12 zásuvných kartách) a dosahoval rychlosti zkoumání až 7 000 000 pozic za sekundu. To stačilo na spodní úroveň velmistrů a opravdu bylo také zdoláno několik velmistrů za regulerních turnajových podmínek: (zhruba tři minuty na tah).

Dalším projektem (tehdy do budoucna) byl Deep Blue, který by překonal hranici jedné miliardy uzlů za sekundu. Jednalo se v plánu o 1 000 paralelně spojených čipů, kde každý by měl výkon asi 3 000 000 pozic za sekundu.

Programy pro PC

Nutno podotknout, že v současné době je stav počítačových strojů z velké části soustředěn na oblast programů pro PC. Dnešní PC disponují již takovým výkonem, že běžné hrací automaty zaměřené čistě jen na šachovou hru jim nestačí. V oblasti programů pro PC jsou špičkové programy již na úrovni velmistrů. Proto se této oblasti v současné době věnuje hodně firem, neboť je zde potenciálně vysoká možnost prodeje. Namátkou si uveďme pár programů, které jsou v současnosti na trhu: Mephisto Chess Genius, MChess Pro, Fritz, Chessmaster, Chessica atd.

Perspektivy do budoucna

Ano, perspektivy jsou zajímavé. Není tomu tak dávno, co už zůstával pouze mistr světa Garri Kasparov, který nebyl počítačem v regulerním turnajovém zápase poražen. Když v roce 1996 nastoupil proti Deep Blue, vyhrál a čest lidstva byla prozatím zachráněna. O rok později, 11. května 1997, byl však udolán a prohrál poměrem 3,5:2,5. Znamená to totální porážku lidstva? Těžko říct.

Garri Kasparov se někdy kolem roku 1995 vyjádřil, že počítač porazí člověka asi v roce 2010 nebo také nikdy. Pravděpodobně tehdy netušil, co jej čeká za dva roky.

Je však lidstvo již úplně poraženo? To se asi nedá tvrdit. Jsou totiž hráči, kteří by proti mistru světa dlouho neobstáli, ale počítač porazí relativně snadno. Např. bulharský supervelmistr Kiril Georgijev bez problému porazil program Fritz2, který krátce předtím porazil na turnaji i samotného Kasparova a s ním i všechy ostatní velmistry. Dá se tedy očekávat, že proti počítači budou bojovat počítačoví specialisté. Ti dobře vědí o slabinách počítačů, hlavně těch strategických, a toho se budou snažit vyžívat. Naproti tomu ale stojí mnoho programátorů počítačového šachu a mnoho dalších lidí, kteří táhnou vývoj dále dopředu. Nechejme se překvapit!

Závěr

Tento článek byl jakousi rekapitulací dlouhodobého pokusu lidstva naučit stroj hrát šachy. Nyní jsme v době, kdy se můžeme s podivem dívat na téměř dokonale hotové dílo. Je sice pravda, že téměř všichni obyčejní šachisté jsou počítačem porazitelní. To nám však nemusí odebírat chuť nadále se svými přáteli hrát tu hezkou hru, která se jmenuje šachy.