Brutus - Brutus - 23. 4. 2002
Snad každý šachista si už zahrál s elektronickým soupeřem, ať už ve formě softwaru nebo specializovaného přístroje. Software se dodává pro nejrůznější platformy – vedle PC jsou dnes velkou módou verze pro Palmy a PocketPC. Specializované přístroje existují jak ve stolním provedení s elektronikou zabudovanou v šachovnici, tak ve verzích cestovních ve tvaru kapesních šachů kombinovaných s „kalkulačkou“. V každém případě jde ale o „softwarového“ soupeře. S „hardwarovým“ šachistou se zatím setkalo jen pár vyvolených, což se možná brzy změní.
1. Princip elektronického šachisty
Jádrem každého elektronického
šachisty je generátor tahů a oceňovací funkce. Nad těmito základními
kameny je vybudován hledací algoritmus.
Generátor tahů postupně vytváří větve stromu variant, na
jejichž konci se aplikuje oceňovací funkce. Zpětným
minimaxovým postupem potom najde počítač větev s nejlepším
hodnocením.
Skutečný hledací algoritmus je složitější. Chytrými
matematickými postupy i šachovými heuristikami se strom co
nejvíc redukuje (alfa-beta algoritmus, selektivní algoritmus,
forward pruning, nultahový algoritmus). Jinými chytrými
postupy se ale také zjišťuje, zda daná větev skutečně končí
ustáleným stavem, jinak je její propočet prohlouben (singular
extension).
2. Rychlost propočtu
Generátor tahů a oceňovací
funkce běží většinu času šachového programu a rozhodují
proto do značné míry o jeho rychlosti.
V kursech programování je generátor tahů oblíbenou ukázkou
práce s dvourozměrným polem a výpočetními cykly. Skutečný
profesionální generátor vyladěný k dokonalosti však obvykle
vypadá úplně jinak. Šachovnice je sada bitových polí pro každý
kámen zvlášť (BitBoard), se kterými lze bleskurychle provádět
bitové operace, zejména na 64 bitových CPU. Také tahy kamenů
se nepočítají matematicky, ale přímo čtou z předem připravených
bitových tabulek pro každý kámen a pole.
Klíčovou součástí je oceňovací funkce, která zhodnotí
číslem statické vlastnosti pozice. Při výpočtu se obvykle
vyjde ze stavu materiálu, který je korigován kladnými i zápornými
opravami za volné dráhy a sloupce, centrum, volné pěšce,
dvojpěšce, bezpečnost krále a mnohé další.
Každá taková oprava znamená přirozeně prodloužení výpočtu
a z této pasti nemá „softwarový“ šachista úniku. Nové a
nové verze dnešních špičkových programů jsou víceméně
hledáním a dolaďováním kompromisu mezi rychlostí propočtu
na jedné straně a zabudovanými šachovými znalostmi na straně
druhé.
Fritz dlouho vynikal především propočtem a jeho rychlostní
optimalizace vyvrcholila verzí 5.32, označovanou jako taktické
monstrum. Šestka a sedmička však mírně zpomaluje a na oplátku
se stává šachově inteligentnější.
3. Princip a výhody hardwarového šachisty
U „hardwarového“ šachisty
nejsou tahy a oceňovací funkce generovány sekvenčním
softwarovým propočtem, ale složitým jednoúčelově navrženým
kombinačním obvodem.
šachová pozice > kombinační obvod > generované tahy
šachová pozice > kombinační obvod 1 > část oceňovací
funkce 1 > oceňovací funkce
> kombinační
obvod 2 > část oceňovací funkce 2 >
> kombinační
obvod n > část oceňovací funkce n >
Průchod elektrického signálu kombinačním obvodem je velmi
rychlý (v řádu nanosekund), což samo o sobě znamená značnou
výhodu proti softwarovému řešení. Naprosto klíčovou předností
je ovšem možnost libovolně rozšiřovat oceňovací funkci. Tím
sice roste složitost, velikost a cena kombinačního čipu,
samotné oceňování však probíhá paralelními větvemi a
jeho rychlost se proto prakticky nemění.
4. Hardwarové šachové stroje
Průkopníkem „hardwarového“
šachového stroje je legendární Ken Thompson. V roce 1960 se
Ken podílel na vývoji Unixu a jazyka C. O deset let později
postavil speciální stroj Belle, který k velkému překvapení
vyhrál mistrovství světa 1980 před sálovými superpočítači.
Ken toto zařízení dále nevyvíjel, ale pro šachy udělal
mnoho dalších užitečných věcí. Jako první dal počátkem
devadesátých let řadovému uživateli databázi důležitých
pětikamenových konstelací na čtyřech CD s dokonalým řešením
každé pozice. Na přelomu století zopakoval tento výkon i se
šesti kameny, dotazovací server je umístěn na webu.
Druhou hardwarovou legendou je DeepBlue, který vyvinul u IBM
Feng-hsiung Hsu. V roce 1989 získal titul mistra světa, ale
vyvrcholením kariéry je nepochybně vítězství v regulérním
zápase s Kasparovem v roce 1997.
5. Peníze, peníze
V té době jsme tajně doufali,
že IBM využije svých možností a nabídne malou verzi
DeepBlue jako zásuvnou desku do našich PC. Bohužel manažment
modrého giganta považoval celou věc za ukončenou a projekt
prostě zastavil. Snad měl dokonce pravdu – vynaložené prostředky
se IBM vrátily úžasnou mediální odezvou zápasu a technické
využití nebylo ekonomicky až tak zajímavé.
Hsu se pokusil o další soukromý vývoj, ale narazil na nezájem
sponzorů a šachové aktivity ukončil. Samotní budoucí uživatelé
by projekt prostě nezaplatili.
Ekonomicko-technická rozvaha nepostrádá zajímavosti. Kombinační
šachové logické obvody byly realizovány koncepcí jednoúčelových
speciálně vyrobených čipů ASIC (Application Specific
Integrated Circuit). Statisíce tranzistorů a jejich propojení
není možné navrhnout ručně. Pro popis logických funkcí se
použije speciální popisný jazyk HDL (Hardware Description
Language), například Verilog nebo VHDL. Ten vygeneruje příslušné
masky, které se pošlou to továrny. Čipy se musí vyrobit,
zapouzdřit, osadit a testovat. Každá vážnější chyba nebo
změna vede k novému cyklu vývoj – masky – továrna –
testování. Jde o špičkovou technologii, kterou si každý
nechá dobře zaplatit. Jeden cyklus proto trvá 2-3 týdny a
stojí kolem 100.000 US dolarů, celý vývoj odhadl Hsu na 2
milióny.
6. Do hry vstupuje ChessBase
Vedle šachového programování
sponzorovaného jako věda nebo reklama existuje také šachové
programování komerční. Vedoucí postavení má hamburská
firma ChessBase, jejímž duchovním otcem je velký nadšenec počítačového
šachu Frederic Friedel. ChessBase si vypracovala takovou pozici,
že je ve svém oboru srovnávána s Microsoftem.
Byl to zase Ken Thompson, kdo upozornil Friedla na možnost použít
pro vývoj hardwarového šachisty novou generaci čipů typu
FPGA (Field Programmable Gate Array). FPGA jsou také uživatelsky
navržené kombinační obvody, ale ve srovnání s ASIC mají
asi takovou výhodu, jako přepisovatelné CD proti lisovanému.
Nemusí se posílat do výroby, nýbrž se programují přímo ve
vývojovém nástroji a hlavně lze obsah mnohokrát měnit. Tím
se celý vývoj urychlí a zlevní o několik řádů. Začátkem
roku 2000 dosáhly čipy FPGA dostačující kapacity při rozumné
ceně.
7. ..a Dr. Donninger
Samotný Thompson však právě
odchází ze slavných Bellových laboratoří na odpočinek, kde
se hodlá věnovat letecké pilotáži a instruktáži. Proto
byla realizace projektu nabídnuta Dr. „Chrilly“ Donningerovi.
Ten je znám svým špičkovým šachovým programem Nimzo, ale
také vynikajícími populárně-naučnými články z oboru. Veškerou
činnost koření bodrým rakouským humorem, například jeho
poslední multimediální šachový program se jmenuje
Schweinehund.
ChessBase zaplatila výlet do USA, kde si Chrilly zalétal
Kenovou cessnou, pak ale začala velmi tvrdá práce.
8. Brutus
Celý projekt byl pojmenován
Brutus a vedle Donningera v něm účinkuje několik dalších
odborníků. Chrilly například nechtěl vyrobit jen další
verzi Nimza, proto si nechal oceňovací funkci na logické úrovni
navrhnout od Ernsta Heinze (program Dark Thought) a velmistra
Timoščenka. Při testování a ladění zase spolupracuje starý
člen Nimzo týmu Alex Kure.
Donninger sám se soustředil na hardwarový čip a jeho
programování. Při testování se ukázala zajímavá věc, že
totiž s počtem komponent oceňovací funkce roste význam
jejich vah. Pro zajímavost – DeepBlue měl více než 8000
komponent.
Vhodným časováním kombinačních obvodů lze dosáhnout i
sekvenčních funkcí. Donninger proto zabudoval do hardwarové
části jednoduchý hledací algoritmus do hloubky tří polotahů.
Podle jeho vyjádření však šlo doslova o kulturní šok, při
kterém musel zapomenout vše, co se posledních dvacet let o
programování naučil. Tato hloubka by samozřejmě nestačila,
proto je předřazeno softwarové prohledávání se všemi známými
jemnostmi jako jsou hash tabulky nebo přístup k tablebasím
koncovek. Podobně fungoval i DeepBlue.
9. Paderborn
Celý projekt měl několik krizí, ta poslední se například týkala náhodných vnitřních restartů šachové karty Alpha Data, způsobených elektrickým rušením v PC. U Donningera na poskládaném Nonamu se závada neprojevila, zato u Kura na Dellu velmi často. Nakonec přece jen stihli s odřenýma ušima koncem února 2002 start na Paderbornu – neoficiálním otevřeném přeboru Německa v počítačovém šachu. Brutus sehrál už velmi slušné partie, i když optimisté čekali lepší výsledek než 50 procent bodů.
10. Je rychlost dostatečná?
Mě spíš zarazil v materiálech
z Paderbornu údaj o rychlosti. Na PC s Pentiem4 1.7 GHz
dosahoval Brutus 2-3 milióny pozic za sekundu, což není až
tak velký náskok před softwarovým DeepFritzem na dual AMD
1900+, který propočítal 1,6 miliónu pozic.
Autor k tomu na specializovaném diskusním fóru uvádí zhruba
toto.
Frekvence není u FPGA pevná, ale stanoví se délkou nejdelšího
průchodu signálu kombinačním obvodem. Na jedno logické
hradlo se počítá 1 ns. Náš čip byl taktován bez
optimalizace na 33 MHz. FPGA čipy se ovšem – stejně jako
procesory – vyvíjejí. Každým rokem se jejich kapacita
zhruba zdvojnásobí při růstu rychlosti. Dnešní FPGA by mohl
běžet nejméně na 45 MHz.
Brutus je navíc navržen tak, aby čipy mohly pracovat paralelně.
Zdvojení čipu je jedním z nejbližších úkolů.
Po dosažení určitého stavu vývoje, vhodného například pro
prodej, nebude problém využít hotový stav a nechat podle něj
„vypálit“ čipy ACIS. Ty mohou podle Intelu běžet až 30x
rychleji.
11. Perspektivy
DeepBlue byl vyvíjen 10 let a v některých
fázích na něm pracovalo až 40 lidí. Tolik času ani peněz
ChessBase nemá, směje se Donninger. Už na mistrovství světa
v červnu 2002 v Maastrichtu bychom chtěli ukázat jasný pokrok
a krajní mezí pro úspěšnost celého projektu „malého
lidového DeepBlue do vašeho PC“ bude další mistrovství v
listopadu 2003 v Grazu.
Donninger navíc prozradil, že podle smlouvy s ChessBasí
dostane slušnou prémii, pokud dosáhne ELA o 50 bodů vyššího
než nejlepší programy na duálním systému. Nechme se tedy překvapit
a držme palce.
12. Odkazy
Prohlédněte si fotky zařízení
na http://www.chessbase.com/newsdetail.asp?newsid=221 .
Přečtěte si Sperchstunde s Donningerem na http://www.computerschach.de/sprechstunde/index.htm
Alpha Data -
výrobce hardwaru