Výpočetní dynamika, která ohrožuje superpočítače

Výzkumníci hledají způsob, jak omezit složitost vyskytující se v úlohách analyzujících reálný svět. Jde zcela...


Výzkumníci hledají způsob, jak omezit složitost vyskytující se v úlohách
analyzujících reálný svět.

Jde zcela určitě o jednu z nejvíce fascinujících prezentací, jaká kdy byla
vytvořena. Znázorňuje graf, kde hodnota jednoho z nejmenších čísel svislé osy
činí 1017 a udává počet sekund od současnosti do okamžiku, kdy vyhasne Slunce.
Následuje jej 1047, počet atomů na celé Zemi. Po něm rostou čísla opravdu hodně
a ukončují stupnici na hodnotě 10301 020.
Tento graf pochází od Agentury pro projekty pokročilého obranného výzkumu
(Defense Advanced Research Projects Agency, DARPA) a prezentuje exponenciální
růst možných stavů v celé škále aktivit, od jednoduché diagnostiky
automobilového motoru se 100 proměnnými až k válečným simulacím s milionem
proměnných (to je pak představováno oním číslem 10301 020).
Idea myšlenky, kterou se DARPA snaží při vysvětlování svého projektu pro
vyhodnocování (situací) reálného světa vyjádřit, tkví v tom, že počítače
nebudou nikdy schopny vyčerpávajícím způsobem prozkoumat všechny možné výsledky
složitých aktivit, stejně jako místnost zaplněná opicemi s psacími stroji nikdy
znovu nevytvoří Shakespearova díla.
Ale v právě ukončené první fázi projektu Real (Realita) odhalila agentura
zkratky, jež mohou omezit drastickou kombinační složitost, která po desetiletí
mařila úsilí modelovat skutečný svět.

Za brutální silou
Bart Selman, profesor informatiky na Cornellově univerzitě a jeden ze tří
pracovníků najatých agenturou DARPA na tento projekt, poukazuje na skutečnost,
že už celých deset let máme k dispozici nástroje pro automatické vyhodnocování,
které umějí odhalit vady v čipu nebo v návrhu softwaru. Tyto nástroje prověří
správnost návrhu oproti jeho specifikacím, aniž by musely otestovat úplně
všechny situace, na něž může čip nebo software narazit.
Ale současně tyto nástroje zvládnou vykonat jen to, čemu se říká
jednočinitelové vyhodnocování. Profesor Selman rozšiřuje nastíněnou koncepci
pro mnohem náročnější třídu problémů. Jde o tzv. vícečinitelové scénáře, ve
kterých vystupuje jedna nebo více protichůdných sil. Pro ověření svých myšlenek
vyvinul speciální šachový program. Nejlepší šachové programy dneška, jako je
například Deep Blue firmy IBM, vynikají hrubou silou při zkoušení tahů, při
němž za sekundu zanalyzují miliony pozic na šachovnici. "Deep Blue prozkoumává
miliony strategií, ale většina z nich je velmi hloupých," říká Selman."
Velmistři berou v potaz pouze tři nebo čtyři možné hrací linie."
"Cornellský šachový program pracuje více stylem šachového velmistra," dodává.
"Umí využít určité strategie a pak zjistit, že nejsou úspěšné. Poučí se z toho
a přidá si tuto informaci do své znalostní báze. Čím častěji hraje, tím více
zdokonaluje své schopnosti, dokonce i během jediné partie," vysvětluje profesor
Selman a dodává: "Systém vyvíjí pojmový popis šachovnice a vyhledává pozice,
které mu přinášejí výhodu."
Aplikací těchto učících se technik a jinými vylepšeními tradičních
vyhodnocovacích nástrojů dosáhl zatím Selmanův tým rychlostního zlepšení 109
oproti standardním přístupům.

Hrou k výsledkům
Patrick Lincoln, ředitel neziskové Computer Science Laboratory, aplikoval
mechanismus kontroly modelu, jenž se normálně používá k ověření návrhu
polovodičových součástek, k herní variantě šachů se čtyřmi hráči nebo pro
Diplomacii, deskovou hru až sedmi hráčů, která vznikla v Evropě těsně před 1.
světovou válkou.
Lincoln vyvinul algoritmus, který ve hře umí najít takzvaný Nashův rovnovážný
bod. Jde o situaci, kdy se žádný hráč nemůže odchýlit od své strategie, aniž by
tím nesnížil svůj výsledek. Jakmile je takový bod určen a jsou známy strategie
jednotlivých hráčů, kontrola modelu umí najít nejlepší taktické tahy a v potaz
bere i různá spojenectví hráčů. "To představuje nejspíše hlavní výpočetní
výzvu," připouští Lincoln.
Stejně jako profesor Selman i Lincoln použil techniky ověřování modelu k
matematickému prořezávání kombinačního stromu. "Děláme to symbolicky, způsobem,
při němž nemusíme prohlédnout úplně všechny možnosti," říká.
Mezitím výzkumníci z Kalifornské univerzity v Berkeley zavádějí do
automatického vyhodnocování pojmy neurčitosti. Modelují Kriegspielovy šachy
čili herní variantu, kterou v 19. století využívala pruská armáda pro výcvik
svých důstojníků. Při Kriegspielových šachách žádný ze soupeřů nevidí na
figurky ani na tahy toho druhého, takže každý z nich pracuje pouze s
informacemi, které vydedukoval z důsledků svých vlastních tahů.

Rychlost řešení
Stuart Russel, profesor informatiky v Berkeley, říká, že jeho tým přišel na
vyhledávací algoritmy, jež jsou 100krát až 1 000krát rychlejší než dřívější
metody pro řešení tohoto druhu problémů. Některé umějí najít řešení přímo, bez
zkoušení všech možností. Tvrdí, že jeho techniky by mohly být jednoho dne
využity v aplikacích zabývajících se situacemi z reálného života. Šlo by
zejména o stavy, jejichž dynamika je rozpoznatelná jen částečně, jako
vyjednávání, řízení dopravních toků nebo provoz dodavatelských distribučních
systémů.
"S těmito technologiemi bychom mohli vytvořit systémy na podporu logistických
rozhodnutí, jež by mohly zvažovat pravděpodobnost vývoje budoucích událostí,
jako jsou například přírodní katastrofy. Jejich důsledky potom transformuje do
logistického procesu," říká Tom Wagner, programový šéf projektu Real v agentuře
DARPA. "Stejný logistický systém by také mohl vyhodnocovat hodnotu utvářejících
se vztahů k jiné firmě, eventuálně i ke konkurenci. V obou přístupech by šlo o
způsob, jak zlepšit reakci na vzniklou situaci." "Exponenciální závislosti jsou
děsivé. Jediný způsob, jak můžeme v tomto oboru postoupit, spočívá v jejich
algoritmickém zkrocení," říká Lincoln.









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