Sciencemag.cz
Doporučujeme
Hry patří k lidstvu od nepaměti. Je to vhodný nástroj, jak se naučit novým věcem, proto je dětství plné her, které nenásilnou podobou pomáhají osvojit si různé pohybové i kognitivní dovednosti. Někdy na toto poslání her v pokročilejším věku zapomínáme a hraní bereme tak trochu jako ztrátu času, i když často příjemnou. Tady pozor – hrát hru je něco jiného než pouze sledovat, jak hraje někdo jiný. Sice se při tom [sledování] také dá spousta věcí naučit (viz dále), ale zanícený fanoušek fotbalu se málokdy stane také vynikajícím fotbalistou.
Některé hry mají z pohledu umělé inteligence tu výbornou vlastnost, že v nich lze poměrně snadno měřit míru úspěchu. Připomeňme, že umělá inteligence je hlavně o maximalizaci očekávaného užitku. Pokud máme daný přesný vzoreček, jak užitek měřit, ať už to je počet gólů, dosažený čas, získané body, nebo jiné měřítko úspěchu, je možné veškeré úsilí vrhnout na hledání vhodného optimalizačního programu. Je tedy celkem přirozené, že se hraní her záhy dostalo do hledáčku počítačových vědců, zvláště těch zabývajících se umělou inteligencí.
U her máme jasně daná pravidla a jasně dané cíle, což je pro počítače vždy jednodušší než často ne zcela přehledný reálný svět.Člověk vs. stroj, v herním kolbišti takový souboj nikomu nevadí a pro obě strany, tedy člověka stojícího za vývojem toho stroje a člověka „hrajícího“ s tímto strojem, to je zajímavá výzva.
Začínající programátoři často zkoušejí naprogramovat nějakou jednoduchou hru, třeba hraní piškvorek. Pokud znají základní techniky umělé inteligence, může to být docela snadné. My si některé z nich za chvíli představíme, a protože jsme v knize o umělé inteligenci, začneme rovnou od hry, v níž je schopnost vítězit tradičně spojována s mírou inteligence hráče, u šachů.
Člověk už není na trůnu
Není asi žádnou novinkou a nadpis této kapitoly to jen zdůrazňuje, že v šachu lidé již dávno dostali od strojů na frak. V roce 1997 porazil počítač Deep Blue firmy IBM světového šampiona Garryho Kasparova v poměru 3,5 ke 2,5 bodům. Od té doby uplynulo hodně času a dnes šachový program běžící na běžném laptopu porazí převážnou většinu šachistů. Protože je hraní šachu považováno za intelektuálně náročnou činnost, mohlo by se zdát, že stroje mají nad lidmi intelektuálně navrch již dávno. Ale není tomu tak. Úspěch Deep Blue i řady jeho následovníků, nejen na poli hraní šachu, je hlavně dílem hrubé síly a v té jsou počítače lepší než lidé již od svého „narození“.
Přístup k řešení problémů hrubou silou je založený na prostém prozkoumání možných alternativ a výběru té nejlepší. Takto se k řešení problémů v umělé inteligenci přistupovalo v jejím začátku a stejný přístup najdeme v „trochu“ chytřejší podobě i v dnešních programech. Jak se tedy hrubá síla použije při hraní her? Počítač vygeneruje všechny možné partie, tj. zkusí všechny své tahy a pro každý svůj tah všechny tahy soupeře atd., až dojde na konec hry. Tímto postupným větvením vznikne strom hry s kořenem reprezentujícím počáteční situaci a listy odpovídajícími finálním stavům. Finální situace počítač ohodnotí podle výsledku (například +1 pro vlastní vítězství, -1 pro vítězství soupeře a 0 pro remízu) a tyto hodnoty potom posílá zpět na začátek partie dle principu, že každý hráč optimalizuje svůj užitek. Tím získá informaci, jaký tah je pro něj nejlepší, když protihráč bude hrát optimálně (bez chyb).
Algoritmu se dle základního principu říká minimax (jeden hráč maximalizuje a druhý minimalizuje hodnotu hry). Všimněme si, jak minimax odpovídá již představenému základnímu vzorci umělé inteligence – počítač vybírá tah s největším očekávaným užitkem, přičemž očekává, že protihráč dělá to samé.
Pro počítačové hraní šachů je zde jeden zásadní zádrhel.
Průměrný možný počet tahů pro každého hráče je v šachu 35. Při celkové délce hry kolem 80 tahů by tedy počet různých partií byl 3580, tedy zhruba 10123 (pokud budeme ignorovat, že se různými posloupnostmi tahů můžeme dostat do stejných pozic). Deep Blue zvládl v jedné sekundě prozkoumat 200 milionů tahů, takže prozkoumat všechny tahy by mu zabralo 10107 let. Jak to tedy Deep Blue udělal, že se mu podařilo Kasparova porazit v „řádné“ hrací době?
Způsobů vylepšení základní hrací techniky minimax je několik. Předně, není potřeba prozkoumávat další tahy, pokud víme, že si v některé dřívější situaci soupeř pro sebe může vybrat jiný, lepší tah. Tomuto postupu se říká alfa-beta prořezávání a je to klasický postup, jak za daný čas prozkoumat delší partie, než zvládne minimax. Ani to však na hry, jako jsou šachy, zdaleka nestačí. Konkrétně Deep Blue zvládal prohledat zhruba 14 tahů dopředu, ale u šachu má partie v průměru již zmíněných 80 tahů. Zrychlování počítačů a zvětšování kapacity paměti tady díky kombinatorické explozi moc nepomůže. Můžeme prozkoumat jen vybrané tahy (k této technice se ještě vrátíme u programu AlphaGo) nebo průzkum partie ukončit dříve a odhadnout, jak hra dopadne. Deep Blue a další programy pro hraní her používají většinou tento druhý přístup, při němž se znalosti generací lidských hráčů převedou do podoby formule a ta ohodnotí rozehranou partii, takže program dostane odhad, jak to dopadne. Počítače k tomu přidávají rychlé prozkoumání velkého počtu možností, což ve výsledku vede k programům, které hrají lépe než nejlepší šachisté. Tohle rozhodně není důvod, proč bychom se takových programů měli bát. Lidský šachista ve spojení s šachovým počítačovým programem je stále lepší než program samotný i než samotný člověk. Podobně jako je člověk v autě rychlejší než člověk, který jde pěšky. Stroje posouvají naše schopnosti do výšin, kterých bychom bez nich nebyli schopni dosáhnout.
Dáma má přednost
Vítězství Deep Blue nad lidským šampionem bylo jistě skvělým marketingovým tahem pro zviditelnění firmy IBM, přestože Deep Blue zřejmě nebyl ani nejlepším šachovým programem své doby a ani nepřinesl žádnou novou převratnou techniku. V každém případě Deep Blue pomohl k zviditelnění výsledků umělé inteligence a i neodborná veřejnost si tento úspěch dosud pamatuje. Mohli byste si myslet, že se šachy zařadily mezi vyřešené problémy, ale tak tomu není. Vyřešení by znamenalo,
že tuto hru umíme hrát dokonale, tedy už na začátku víme, jak to dopadne, pokud hráči hrají bez chyb. Počet možných šachových partií je natolik velký, že ani různé techniky prořezání nám zatím neumožňují rozhodnout, jaký je nejlepší první tah. Pořád je tedy co zlepšovat. Existuje ovšem podobná desková hra, pro niž už tento výsledek známe. Touto hrou je dáma, jejíž vyřešení zůstalo tak trochu ve stínu Deep Blue, přestože pro odbornou komunitu to byl podobný svátek. Jaký je tedy výsledek dámy, pokud ji budeme hrát neomylně? Na to si odpovíme až po krátkém pohledu do historie počítačového hraní dámy.
V kapitole o šachu jsme si představili základní techniky hraní her, které se v různých variantách objevují v převážné většině herních programů, dámu nevyjímaje. Jádrem je tedy prohledávací algoritmus pro prozkoumávání možností (včetně různého ořezávání „nepotřebných“ větví) doplněný o ohodnocovací funkci, která říká, jak je daná pozice pro daného hráče výhodná. K tomu se často ještě používají databáze koncovek, případně otvíracích tahů. Stejné techniky používal i program Chinook pro hraní dámy vyvinutý pod vedením Jonathana Schaeffera na Univerzitě v Albertě. Chinook byl prvním programem, který se stal mistrem světa v dámě v soutěži proti lidem. Již na začátku devadesátých let minulého století porážel nejlepší lidské hráče a v letech 1994 a 1995 (tedy ještě před úspěchem Deep Blue) se stal světovým šampionem v souboji proti člověku. Chinook se potom stáhnul ze soutěžního života a tým v Albertě se soustředil na kompletní vyřešení dámy.
Po řadě let, kdy program běžel paralelně na množství počítačů, se výsledek dostavil. V roce 2007 byl oznámen výsledek. Odpověď je: 42. Tedy pardon, to jsem prozradil odpověď na základní otázku života, vesmíru a vůbec, kterou řešil trochu jiný počítač (v knize Stopařův průvodce Galaxií). Pokud jde o dámu, je odpověď o něco méně magická. Hrají-li oba hráči neomylně, bude výsledkem hry remíza. Trochu to ubírá na poetičnosti hry, ale pokud ji budete hrát proti člověku, jistě někde nějakou chybu udělá. Dáma se tak zařadila mezi hry, pro něž známe optimální strategii, tedy strategii, která pro daného hráče vždy povede k nejlepšímu možnému výsledku. Další hry na svůj první počítačový úspěch teprve čekaly.
Tento text je úryvkem z knihy
Roman Barták: Co je nového v umělé inteligenci
Nová beseda 2017
O knize na stránkách vydavatele
