Algoritmy hrají piškvorky

Šachy patří mezi deskové hry srovnatelné třeba s různými variantami dámy, s go či piškvorkami. Computerworld je př...


Šachy patří mezi deskové hry srovnatelné třeba s různými variantami dámy, s go
či piškvorkami. Computerworld je přitom mediálním partnerem soutěže, kterou pro
vývojáře připravil český Microsoft. V rámci této akce budou oceněni nejlepší
programy schopné hrát piškvorky.
Jan Stoklasa z divize .Net Developer Group Microsoft ČR říká o srovnání
algoritmů pro šachovou hru a piškorky: "Podobně jako v případě šachů se ani
současné programy pro hraní piškvorek nesnaží o nic na způsob umělé
inteligence. Piškvorky jsou algoritmizovatelné zřejmě snáze než šachy, v
některých konkrétních případech (hra na malé ploše) je možné dokonce zkoušet
řešení výčtem všech možností. Na rozdíl od šachů kladou vývojáři programů pro
piškvorky důraz především na propočet, ohodnocovací funkce je naopak poměrně
jednoduchá. Mimochodem, dosavadní vývoj ukázal, že začínající strana má
nezanedbatelnou výhodu. V naší soutěži se proto zápasy mezi programy odehrají
vždy na dvě partie, pokud výsledek bude nerozhodný, přihlédne se ke
spotřebovanému času. Vyhraje tedy algoritmus efektivnější a tedy i rychlejší."

Šachové počítačeTriumf hrubé síly
Počátky šachových "automatů" z 19. století jsou poměrně úsměvnou kapitolou v
dějinách královské hry. Proslulým se stal především stroj zvaný Turek, v jehož
útrobách se skrýval a figurkami hýbal šachista-lilipután. Doba se změnila a
dnes se již dostáváme do etapy, kdy šachové programy patří k nejsilnějším
hráčům světa. Jedná se o historický mezník: Vždyť ještě před 20 lety převládaly
názory v tom smyslu, že šachová hra na velmistrovské úrovni vyžaduje lidský
intelekt. Ukazuje se tedy, jak ošidné jsou předpovědi stylu "počítače na rozdíl
od člověka nikdy nedokážou...".
Jak už bylo uvedeno na titulní straně, na drtivou většinu rekreačních šachistů
již dnes stačí i program schovaný v útrobách mobilního telefonu nebo PDA.
Počítače s převahou triumfují v dalším oboru původně výhradně lidské činnosti.
Vývoj šachových programů však nabral úplně jiný směr, než očekávali vizionáři
oboru. Tehdejší mistr světa Botvinik, který se začal šachovými počítači
podrobněji zaobírat krátce po druhé světové válce, si představoval, že
výsledkem jeho úsilí bude jakýsi samoučící se program uvažující lidským
způsobem. V konkurenci umělé inteligence se však naopak prosadila metoda hrubé
síly (brute force). Dnešní šachové programy královské hře na rozdíl od člověka
nijak nerozumějí, postačí jim však dostatečně výkonný hardware. Programy se
samy od sebe nijak nezlepšují, jejich tvůrci pouze neustále doplňují databáze a
zjemňují algoritmy sloužící k hodnocení pozice.Šachový program dnes sestává
především z následujících částí: databáze zahájení, databáze koncovek,
prohledávání stromu hry a vyhodnocovací funkce.
Základem současných šachových počítačů je prohledávání stromu hry. Jedná se
prostě o výčet všech možností (samozřejmě tedy takových, která připouštějí
šachová pravidla) hrubou silou. Program od stávající pozice počítá všechny své
možnosti a všechny možnosti soupeře v neustále se větvícím stromě až tam, kam
"dopočítá". Tato hloubka propočtu se obvykle udává jako celkový počet půltahů.

Hodnotící funkce
Výsledkem prohledávání stromu hry je množina pozic, které je nyní třeba
vyhodnotit. K tomu slouží tzv. vyhodnocovací funkce. Jedná se o proceduru
poměrně hardwarově náročnou a na rozdíl od prohlédávání stromu i relativně
sofistikovanou. Při hodnocení pozice počítač samozřejmě vyhodnocuje počet figur
obou stran, ale i jejich postavení, bezpečnost králů a mnoho dalších položek.
Když se ukáže, že program selhává v určitém typu pozic, je do systému včleněno
nové kritérium. Hodnotící funkce se následkem toho neustále zjemňuje a
zpřesňuje.
Počítač následně pozice seřadí podle výhodnosti a zvolí cestu, která povede k
nejlepšímu výsledku i při nejlepších odpovědích soupeře. Programy hrají
"mechanicky", nekalkulují se soupeřovými chybami, nekladou žádné léčky, ale
prakticky ani do žádných léček nepadají.
Tady se ukazují obrovské rozdíly oproti lidskému šachistovi, který počítá
každou možnost do jiné hloubky, řídí se odhadem, některé varianty zcela pomíjí,
kalkuluje se slabými i silnými stránkami sebe i soupeře. V některých případech
je lidský přístup ještě výhodnější především tam, kde je možné situaci
zobecnit, respektive "myšlenkově zkomprimovat". Existují speciální úlohy typu
"mat 256. tahem", které jsou i pro dnešní šachové počítače prakticky
neřešitelné, zatímco lidský šachista je vyřešit dokáže, pokud odhalí princip.
Důležité však je zdůraznit právě fakt, že jde o pozice speciální, obvykle uměle
připravené a nevyskytující se prakticky v reálných partiích. Množství pozic
tohoto typu navíc postupně klesá, protože stále větší okruh problémů vyřeší
program hrubou silou. Dnes už otázka nestojí, zda budou nejsilnější šachové
programy silnější než lidé, ale spíše "kdy se tak stane".

Deep Fritz na scéně
K šachovým programům se pozornost médií soustředila opět letos v říjnu. Program
Deep Fritz tehdy uhrál nerozhodný výsledek s velmistrem Kramnikem (označení
Kramnika za mistra světa nepoužíváme jen kvůli rozkolu v mezinárodním šachovém
hnutí; rozhodně však jde o jednoho z nejsilnějších současných šachistů vůbec).
Na několik otázek týkajících se tohoto střetnutí nám odpoví Dušan Dobeš, autor
domácího šachového programu Phalanx. Společnost Chess Base, která se zabývá
prodejem specializovaných šachových programů a databází, tento software
zařadila na CD--ROM "Young Talents". Program Phalanx je však nadále i volně
šiřitelný a verze pro Linux i Windows lze stáhnout z adresy
http://dusan.freeshell.org/phalanx.

Myslíte si, ze výsledek zápasu Kramnik versus Deep Fritz něco vypovídá o
pokroku šachových programů?
Něco málo jistě ano. V tomto ohledu jsou ale mnohem zajímavější než jednotlivé
zápasy turnaje, kde se střetne více lidských hráčů a více programů najednou.
Například v řadě turnajů Aegon se s programy utkávali lidé různých
výkonnostních kategorií, od běžných klubových hráčů až po velmistry. Poslední
ročník se bohužel uskutečnil už před více než pěti lety, v roce 1997.

V čem tedy podle vás spočívá pokrok šachových programů v posledních letech?
Jaké slabiny dnes ještě šachovým počítačům zbývají?
Mám za to, že mnohem větší význam něž objev nějakých nových algoritmů má
skutečně pokrok na poli hardwaru. To šachovým programům stále ještě pomáhá. I
když z pohledu lidského hráče v tom již není rozdíl, u počítače stále záleží na
tom, zda je schopný analyzovat dopředu 16 nebo 18 půltahů.

Proč hrají nejlepší lidští šachisté proti počítačům tak špatně? Před pěti lety
Kasparov ostudně prohrál s programem Deep Blue, nyní Kramink uhrál proti
programu běžícímu na běžném PC pouhou remízu...
Ano, velmistři opravdu hráli v obou uvedených zápasech nezvykle slabě. Kramnik
udělal v páté partii zápasu hrubku, jakou jeho kariéra nepamatuje. Riskantní
oběť jezdce v šesté partii je zase ukázkovým příkladem toho, jak se proti
počítači hrát nesmí.

Je pak logické, že v případě Kasparova i Kramnika se ihned objeví spekulace o
podvodu, podplácení velmistrů apod. Jaký je váš názor?
Můžeme jen spekulovat nad Kramnikovým slabým výkonem. Od něho samého bohužel
žádné srozumitelné vyjádření k dispozici není. Zajímavý názor ale napsal jeden
"rejpal" do interetového diskusního fóra: "Představte si, že jste Kramnik a že
po čtvrté partii zápasu vedete o dva body. Vypadá to, že mašinka dostane
pořádně nařezáno. To přece těm sympatickým lidem z Chessbase nemůžu udělat,
napadne vás. Věnovali tolik úsilí tomu, aby se celá akce mohla uskutečnit. A
peníze, které tady dostanu za těch pár partií, jsou i na vrcholových
velmistrovských turnajích nevídané. Snad bych mohl trošku zaexperimentovat a
dát stroji možnost ukázat se v lepším světle. Při vyrovnaném výsledku budou mít
navíc všichni zúčastnění chuť do odvety..." Je tohle podvod?

Jak jste vy před zápasem odhadoval "regulérní" výsledek střetnutí?
Ale on to asi byl regulérní výsledek, viz výše. Před zápasem jsem hádal 4 : 2,
možná i 5 : 1 pro Kramnika. Velmistr měl skutečně mnoho výhod. Mohl se s
programem detailně seznámit a prohlédnout si jeho knihovny zahájení. Tvůrci
Deep Fritze navíc museli slíbit, že v průběhu zápasu nebudou program nijak
modifikovat, počítač se tedy nemohl poučit ze sehraných partií a vlastních chyb.

Co se týče poslední partie zápasu, Kramnik ji dal podle řady komentátorů za
remis v téměř vyhrané pozici...
Nechal jsem svůj program Phalanx pozici podrobně analyzovat. Žádnou výhru
nenašel, i když o něco lépe bílý stál.

Pojďme k trochu obecnějším otázkám. Jsou šachové programy schopné šachovou hru
zcela vyčerpat?
Z matematického hlediska rozhodně ne. Časová a paměťová náročnost generování
výrazně roste s počtem kamenů. Všechny tříkamenové koncovky zaberou 70 KB,
čtyřkamenové 30 MB a pětikamenové 7 GB. Z toho je vidět, že touto cestou nemáme
šanci dospět k úplné analýze šachové hry od základní pozice což by vlastně
odpovídalo analýze dvaatřicetikamenové "koncovky".
Jinou věcí ale je, že šachové programy budou v brzké době silnější než lidští
velmistři. V této souvislosti se spekuluje o vzniku zvláštní skupiny lidských
šachistů, kteří se budou soustředit na boj proti počítačům a budou důsledně
kormidlovat partie do pozic, v nichž šachové programy nebudou schopné uplatnit
své přednosti, ale naopak vyniknou jejich slabiny problémy v zavřených
pozicích, neschopnost dlouhého plánování strategií související s tím, že
šachové počítače pozici "nerozumějí", zranitelnost v určitém typu koncovek...

Jak šachové programy obohatily naše chápání královské hry?
Kupodivu ani moc ne. Uvědomte si, že ze dvou směrů vývoje šachových programů se
jako jasně perspektivnější ukázala být metoda hrubé síly. Počítače pouze
počítají, v případě současných šachových programů nejde o snahu napodobit
lidské myšlení, nemáme před sebou nic na způsob umělé inteligence. Počítače
královské hře nerozumějí, proto mohou jen těžko nějak posunout chápání lidské.
Abych ale nebyl zbytečně skeptický. Nějaké pokroky tu přece jenom jsou. Díky
počítačovým databázím šachových koncovek byly odhaleny chyby ve výsledcích
práce nejlepších lidských teoretiků. Počítač tak za několik hodin až dnů práce
s generováním databáze odhalí to, na co lidským mozkům nestačila staletí.
Známým příkladem je koncovka dvou střelců proti jezdci. V roce 1851 byl vydán
podrobný rozbor této koncovky zpracovaný teoretiky Klingem a Horowitzem.
Výsledkem tohoto rozboru je mimo jiné typ pozice, ve které se slabší strana
ubrání. Až výsledky databázového zpracování této koncovky ukázaly, že ukázková
Kling-Horowitzova pozice je vyhraná pro silnější stranu.

Šachy na internetu
http://www.sachinfo.cz, http://www.chess.cz, http://www.chessjournal.cz České
šachové servery.
http://www.chessjournal.cz/cz/one_news.asp?IDNews=586 Aktuální ELO žebříček
šachových programů.
http://www.chessbuddy.com Chess Buddy, šachový program napsaný v Javě pro
mobilní telefony podporující tuto technologii (např. Motorola i85). Na webu je
možné si zkusit i emulátor šachové partie v mobilním telefonu.
http://www.chessters.de.vu/ Chesster S, program, který nechá na mobilním
telefonu hrát proti sobě lidské soupeře a pouze kontroluje, zda partie vyhovuje
pravidlům.
http://www.chessgenius.com/palm.htm Chess Genius, program pro Palm OS.
http://www.handmark.com/products/pocketchess/, Pocket Chess, další z šachových
z programů pro PDA.
http://www.chessbase.com/ Společnost ChessBase, nejznámější výrobce šachového
softwaru. Pro stroje s Windows CE a MDA nabízí verzi Pocket Fritz s odhadovaným
ELO koeficientem až 2200.
http://www.chesslive.de/ On-line přístup k databázi ChessBase
http://www.freechess.org, http://www.chess.net U počítače připojeného k
internetu se samozřejmě nemusíte omezovat na hru proti programům. Existuje celá
řada veřejných šachových serverů, kde můžete téměř každou hodinu narazit také
na lidské soupeře odpovídající vaší síle. Partie probíhají buď přes webové
rozhraní, nebo s použitím speciálních klientů.









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.