Týden od 3. května vstoupí do dějin šachu - úřadující mistr světa Garry Kasparov se utkal v šesti partiích se šachovým superpočítačem DeepBlue firmy IBM a podlehl mu rozdílem jediné prohrané partie 3.5:2.5. Momentálně nejlepší světový hráč se tak poprvé musel sklonit před počítačovým programem. Cenu pro vítěze - obnos ve výši 700 000 dolarů, věnovaných firmou IBM - si odnesl vývojový tým IBM a bude investována do dalšího výzkumu technologií, na kterých je DeepBlue založen. Dějištěm utkání byla speciálně zařízená místnost v New Yorku, kam mělo přístup pouze vybrané publikem, ale průběh zápasu mohli sledovat nejen diváci ve větším sále s obrazovkami, a to včetně komentářů šachových odborníků, mezinárodních velmistrů a členů týmů obou soupeřů, ale díky stenografům a Internetu mohli být u této události lidé na celém světě.

Než se pustíme do popisu průběhu zápasu a hodnocení jeho výsledku, dovolte mi nejprve několik slov o tom, jak je možné naučit stroj hrát šachy na úrovni velmistra. Nejsem šachový odborník ani dobrý šachista (za svůj nejlepší výsledek považuji, že jsem byl schopen zvítězit nad šachovým programem na svém starém dobrém Spectru - GNUChess mne naprosto bez zábran pravidelně poráží), nicméně mám jakési vzdělání v oboru umělé inteligence a četl jsem velmi zasvěcené komentáře šachového velmistra Yassera Seirawana, který rozebíral jednotlivé partie. Zde vám tedy předkládám stručný souhrn takto získaných informací, který můžete přeskočit a dostat se rovnou k zápasu samotnému.

DeepBlue dosáhl kvality velmistra

Jak vlastně počítače hrají šachy? Představte si nějakou pozici na šachovnici. Jak vybrat ten správný tah? Počítače k tomuto problému přistupují "metodou hrubé síly". Stroj postupně probere všechny možné tahy, všechny možné odpovědi soupeře, všechny své další tahy, všechny další možné odpovědi soupeře a tak dále. Pokud bychom dali šachovému programu dostatek času, vyhodnotil by všechny možné pozice na šachovnici až do konce hry. Bohužel počet pozic vzrůstá geometrickou řadou s počtem tahů a dostatek času v tomto případě znamená nekonečně dlouhou dobu, takže se musíme spokojit pouze s omezeným pohledem dopředu. Takto vygenerované pozice nyní počítač posoudí (přiřadí jim nějaké číslo reprezentující jeho názor na danou pozici), aby zjistil, která z nich je pro něj nejvýhodnější. Poté si zapamatuje posloupnost tahů, které k této pozici vedou (samozřejmě včetně tahů protihráče), a zahraje první tah z této posloupnosti. Odborníci říkají, že počítač prohledává graf hry zadaný implicitně pravidly šachu a hledá dosažitelný vrchol (pozici na šachovnici) s nejlepším ohodnocením. DeepBlue dokáže takto vypočítat 200 milionů pozic za sekundu, což představuje průměrně sedm (!) tahů dopředu v limitu na tah (ten činil v zápase tři minuty). Podle názoru šachových odborníků je díky tomu schopen hrát šach na úrovni velmistra.

Uvedená strategie má ovšem několik nedostatků. Především je zcela závislá na volbě ohodnocovací (heuristické) funkce, neboli schopnosti programu zjistit, jestli a jak je pro něj situace na šachovnici výhodná. Nejjednodušší taková funkce má pouze tři hodnoty: výhra, remíza a prohra - to ale samozřejmě nestačí. O něco lepší je počítat se stavem figur - má-li šachista o jednu více, bývá na tom zpravidla lépe. Ani tím jsme však problém nepostihli celý, nicméně stav materiálu bývá základem pro hodnocení pozice - proto se o počítačích říká, že jsou materialistické. Pokud mají možnost získat převahu v počtu nebo kvalitě kamenů, využijí ji, přestože to někdy vede k horší nebo dokonce prohrané pozici. Pro posouzení stavu na šachovnici jsou důležité i další faktory - počet polí kontrolovaných vlastními kameny, volnost pohybu (neboli počet polí kontrolovaných kameny protivníka), s tím související stav vývinu, struktura pěšců (zvláště postoupilých), postavení krále a mnoho jiných těžko definovatelných vztahů. Špičkoví šachisté získávají schopnost analýzy dlouholetou praxí a nemalou součástí této schopnosti je intuice. Problémy nastávají v okamžiku, kdy chceme tuto vysoce individuální zkušenost převést do jazyka stroje. Volba kvalitní ohodnocovací funkce je jedním ze základních předpokladů pro dobrou hru.

Dalším problémem je, že počítač se na každou pozici dívá, jako by ji viděl poprvé. Není schopen si předem vypracovat nějaký plán, strategii, a ten potom dodržovat. To občas vede ke zvláštním tahům, které jsou pro počítače typické - jsou to vyčkávací tahy v situaci, kdy si stroj neví rady - například pohyb krále tam a zase zpět. Schopnost dívat se na každou pozici zvlášť a nezaujatě může ale být i výhodou - pokud se situace změní, stroji nedělá problémy se přizpůsobit a opustit dosavadní záměr (žádný nemá).

Spíše technickým problémem je způsob prohledávání možných pozic, respektive otázka, kdy toto prohledávání ukončit. Lze si představit různá kritéria, například omezení na počet tahů dopředu, které počítač zkoumá, dosažení jisté hodnoty ohodnocení (tedy kritérium typu "najdeš-li dostatečně dobrý tah, použij jej") nebo jednoduše časové omezení - "použij nejlepší tah, který jsi schopen najít během tří minut".

K překonání uvedených nedostatků slouží několik metod. Jednou z hlavních jsou knihovny tahů, zejména zahájení. DeepBlue má údajně ve své databázi všechna zahájení, jaká kdy byla hrána významnějšími hráči. Znalost posloupnosti úvodních tahů samozřejmě nestačí - počítač musí také vědět, které tahy jsou dobré a které nikoliv, musí mu být řečeno, kdy zahájení opustit a hrát své vlastní tahy. Jednou z možností je špatné tahy z databáze zahájení vynechat, o něco lepší je přidat k tahům expertní hodnocení - počítač tak předem ví čemu se vyhnout. Jednou ze strategií hry proti počítači je snažit se zahrát neortodoxní tahy a donutit protivníka, aby hrál vlastní hru, dostat ho "ven z knihy". Později uvidíme, že Kasparov tuto strategii používal, i když ne s velkým úspěchem (a nakonec mu byla také osudná).

Kromě knihovny zahájení má počítač k dispozici také knihovnu koncovek. Pokud na šachovnici zbude pouze pět kamenů, nemusí se už DeepBlue namáhat s vyhodnocováním situace - všechny takovéto koncovky má spočteny předem a hraje je tedy naprosto bezchybně. Během práce na koncovkách se dokonce ukázalo, že některé z pozic, které byly dříve považovány za remízové, vedou ve skutečnosti k vynucené výhře jedné ze stran - většinou ovšem v mnoha tazích (kolem padesáti). Toto je dobrá ukázka způsobu, jakým mohou počítače obohatit šachovou teorii.

Další metodou, jak vybrat správný tah, může být použití expertních pravidel. Jedna z klasických pouček, s níž se setká každý začínající šachista, je netáhnout v zahájení dvakrát tou samou figurou. Tato pravidla mohou být jakýmsi doplňkem ohodnocovací funkce, případně mohou být začleněna přímo do ní.

Stručně řečeno, počítače při hře v šachy prokazují málo vlastní inteligence - jediná inteligence, která v nich je, je ta, jíž do ní vložili jejich tvůrci.

Jak hrají šachy lidé, respektive šachoví velmistři? I oni se pokoušejí odhadnout situaci na několik tahů dopředu, používají přitom ale takzvané selektivní prohledávání. Ze všech možných tahů, které mají k dispozici, si vyberou několik málo nejlepších - tento výběr je založen na přijaté strategii, na intuici, na zkušenosti ze sehraných partií a na spoustě dalších těžko definovatelných faktorů (z nichž ne nevýznamným je i vlastní psychický stav) - a u takto vybraných tahů zkoušejí odhadnout, jaké budou mít důsledky. Lidský mozek je zatím nepřekonaný v rozeznávání vzorů. Co lidem chybí na schopnosti počítat dopředu možné kombinace, nahrazují uměním posoudit situaci na šachovnici a vypracovat si strategický plán postupu.

Vlastnosti hry u počítačů jsou dostatečně známé a to dovoluje formulovat "protipočítačovou" strategii hry. Jednu ze zásad této strategie jsem již uváděl - snažit se počítač vyvést z knihovny známých zahájení nějakým novým prvkem. Mezi další zásady patří hrát uzavřené pozice, a tak získat poziční výhodu, i na základě obětí materiálu. O počítačích je známo, že špatně zvládají uzavřené pozice, kdy nemají dost prostoru k manévrování. Jejich ohodnocovací funkce nejsou dokonalé, což se projevuje zejména v situacích, kdy záleží na postavení figur víc než na materiálních výhodách.

Dosti ale obecných úvah, pojďme se nyní podívat, jak se výše řečené uplatnilo v zápase úřadujícího mistra světa v šachu proti superpočítači DeepBlue.

Stroj překvapil soupeře i celý svět

První partie, kterou vyhrál Kasparov s bílými kameny, se zdá být dokonalou ilustrací výše uvedených zásad hry proti počítači. Kasparov během partie postupně získával a stále zvětšoval poziční převahu, která však byla pod mezí rozlišovacích schopností DeepBlue. Počítač se v průběhu hry dopustil několika strategických chyb a potvrzoval tak teorii o špatné poziční hře. Když se ovšem dostal do úzkých, prokázal chladnou hlavu (jak jinak) a schopnost agresivní obrany - nicméně už bylo pozdě.

Druhá hra měla pro vývoj zápasu rozhodující význam a zřejmě bude ještě dlouhou dobu zdrojem mnoha spekulací a nejasností. Zdá se, že DeepBlue zde bez poskvrnky prošel šachovým Turingovým testem a prokázal vlastní inteligenci a hloubku porozumění šachové hře.

Turingův test je považován za jedno z rozlišovacích kritérií umělé inteligence. Představte si, že máte před sebou terminál, jehož prostřednictvím se můžete bavit se svým jinak neviditelným partnerem. Máte za úkol rozhodnout, zda na opačném konci terminálu sedí člověk nebo stroj. Pokud se stroji podaří vás oklamat, prošel Turingovým testem a musí mu být přiznána inteligence. (Zajímalo by mne co s lidmi, kteří Turingovým testem neprojdou.) Šachový Turingův test je obdobný - máte před sebou zápis odehrané partie a musíte rozhodnout, zda a kdo z hráčů byl ve skutečnosti stroj.

Druhá partie, ve které měl bílé DeepBlue, začala španělskou hrou. Hra se dostala do uzavřené, blokované pozice, ve které měl DeepBlue teoreticky mít potíže a "trpět". Nicméně počítač si s přehledem poradil a dokonalou poziční hrou si vynutil převahu, která vedla až k rezignaci Kasparova ve 45. tahu. Co je vlastně na této partii tak zvláštního? Především DeepBlue zde předvedl výkon, o kterém málokdo věřil, že by ho byl nějaký počítač schopen. V průběhu hry dokonce odmítl tah, který by vedl k zisku materiálu a možná k vynucené výhře, ve prospěch jiného, čistě pozičního manévru. (Sám Kasparov prohlásil, že jen velmi málo šachových velmistrů by zahrálo tento tah.)

Pravá senzace však vypukla, když se během analýz ukázalo, že v pozici, kterou Kasparov vzdal, si mohl během pěti tahů vynutit remízu věčným šachem! (K tomuto objevu ironicky přispěly analýzy provedené pomocí dalších šachových programů i návrhy uživatelů Internetu.) Garry si podle vlastních slov nepamatuje, že by někdy vzdal partii, kterou mohl zremizovat. Chyby se zde ovšem dopustil i DeepBlue, který remízu vlastním tahem umožnil - z nějakých důvodů ji prostě "přehlédl". Na tiskové konferenci druhý den panovala velmi vzrušená atmosféra - Garry vznesl oprávněnou otázku jak je možné, že počítač schopný zahrát tak skvělé tahy (a dokonce odmítnout zisk materiálu) během partie na závěr přehlédne pětitahový věčný šach? Ač je to divné, zdá se, že tento problém půjde vyřešit velmi obtížně - podle tvrzení IBM totiž není možné partii jednoduše zopakovat.

Tahy DeepBlue vybírá do jisté míry nedeterministicky - za stejné situace může DeepBlue zahrát jiný tah - takže jsou k dispozici pouze výtisky analýz DeepBlue během hry. Nedeterminismus může být způsoben náhodnými rušivými vlivy ve víceprocesorovém systému, jakým DeepBlue je, i když podle mého názoru by tento nedeterminismus neměl mít až tak velký význam. IBM odmítlo dát výsledky rozboru k dispozici během zápasu, ale uvolnilo je po jeho skončení - bude tedy následovat velmi podrobný rozbor a máme se jistě na co těšit.

Tato prohra Garryho velmi ovlivnila a projevila se na stylu jeho hry. Jednak si nebyl jistý, co vlastně může od DeepBlue očekávat (představa, že má proti sobě stroj nejenom schopný dokonale počítat kombinace, ale i hrát dobře pozičně, mu jistě nedávala spát), jednak ho jistě mrzela prohra v remízové pozici.

Další tři partie skončily remízou po téměř stejném průběhu - Garry zvolil netradiční zahájení, získal výhodu, kterou ale nedokázal dovést do vítězného konce. Ve hře DeepBlue se už neobjevil onen záblesk génia z druhé partie, nicméně počítač dokázal odrážet Garryho útoky a vyrovnat hru. Toto se zejména projevilo v páté partii, kde hrál Garry bílými kameny - přes velkou převahu ho DeepBlue dotlačil do věčného šachu a partii zremizoval. Zde hrál velkou roli psychologický faktor - lidský protivník by se za stejné situace vzdal.

Šestá, poslední partie skončila překvapivým vítězstvím DeepBlue už v 19. tahu. Kasparov, který opět zvolil netradiční zahájení, se zřejmě spletl a přehodil pořadí tahů - upadl tak do známé léčky a DeepBlue zvítězil, aniž by musel příliš spoléhat na vlastní výpočetní sílu. Na tiskové konferenci se Garry omluvil za svou hru a prohlásil, že neměl sílu dále bojovat.

Zápas rozhodla odolnost vůči stresu

Tento zápas po sobě zanechává mnohé nevyřešené otázky. Přišla už doba, kdy budou počítače porážet šachové mistry? Byl výkon DeepBlue v druhé partii náhodný nebo je schopen ho zopakovat? Jaká je vlastně vhodná strategie hry proti počítači? Přes všechny nesporné přednosti DeepBlue si myslím, že Kasparov je stále nejlepším šachistou na této planetě. Jeho porážku způsobily především faktory stojící mimo samotnou hru. S trochou zjednodušení se dá říci, že se Kasparov porazil sám - zvolenou strategií vyváděl z konceptu nejen DeepBlue, ale především sebe. Projevila se zde nesporná výhoda všech strojů - odolnost vůči stresu, schopnost hrát svoji (i když ne dokonalou) hru za jakýchkoliv okolností a nenechat se ovlivnit děním mimo šachovnici. Garry Kasparov, překvapený a zdrcený porážkou ve druhé partii, zahrál pod své možnosti a dopustil se chyb, které by za jiných okolností v jiném, méně prestižním a sledovaném zápase byly nemyslitelné. Těžko říci, zda zvítězila inteligence - tou rozhodující silou v zápase byla chladnokrevnost. Nicméně už teď se můžeme těšit na zajímavé události - Garry požaduje, aby se DeepBlue začal účastnit normálního šachového dění a možná se uskuteční i další vzájemný zápas, hraný tentokrát podle standardních pravidel (t.j. na deset partií). Nechme se tedy překvapit a držme Garrymu palce.