FAKULTA INFORMAČNÍCH TECHNOLOGIÍ

ˇ ´I TECHNICK E´ V BRN Eˇ VYSOK E´ U CEN ˇ ´ICH TECHNOLOGI ´I FAKULTA INFORMA CN

Uk´azka vyuˇzit´ı UI v poˇc´ıtaˇcov´ych hr´ach Bakal´aˇrsk´y projekt

2005

Michal Hejtm´anek

Uk´azka vyuˇzit´ı UI v poˇc´ıtaˇcov´ych hr´ach Odevzd´ano na Fakultˇe informaˇcn´ıch technologi´ı Vysok´eho uˇcen´ı technick´eho v Brnˇe dne 2. kvˇetna 2005

c Michal Hejtm´anek, 2005

Autor pr´ace t´ımto pˇrev´ad´ı sv´a pr´ava na reprodukci a distribuci kopi´ı cel´eho d´ıla i jeho cˇ a´ st´ı na Vysok´e uˇcen´ı technick´e v Brnˇe, Fakultu informaˇcn´ıch technologi´ı.

Prohl´asˇen´ı Prohlaˇsuji, zˇ e jsem tuto bakal´aˇrskou pr´aci vypracoval samostatnˇe pod veden´ım Ing. Pavla Slav´ıcˇ ka. Uvedl jsem vˇsechny liter´arn´ı prameny a publikace, ze kter´ych jsem cˇ erpal.

....................... Michal Hejtm´anek 2. kvˇetna 2005

Abstrakt Bakal´aˇrsk´a pr´ace popisuje vliv akademick´e UI na rozv´ıjej´ıc´ı se hern´ı pr˚umysl v podobˇe zrodu a v´yvoje z´abavn´ı inteligence a jej´ı zpˇetn´y vliv na akademickou. Hlavn´ı cˇ a´ st pr´ace je zamˇeˇrena na porovn´an´ı z´astupc˚u dvou z´akladn´ıch smˇer˚u hern´ı umˇel´e inteligence, na logick´e hˇre piˇskvorky: Jedn´ım je matematick´y Goli´asˇ“, typick´y reprezentant hrub´e s´ıly, kter´y prohled´av´a stavov´y prostor ” o velk´e sˇ´ıˇrce, ale mal´e hloubce – kv˚uli geometrick´emu n´ar˚ustu zkouman´ych stav˚u. Druh´ym je David“, soustˇred´ı se jen na p´ar nadˇejn´ych tah˚u, ale z tˇech si vyb´ır´a velmi d˚ukladnˇe. Pˇri ” hled´an´ı do hloubky mu roste poˇcet zkouman´ych stav˚u pouze aritmetickou ˇradou. Vede si z´aznam o pˇredeˇsl´ych hr´ach, snaˇz´ı se vyvarovat stejn´ych chyb a pokouˇs´ı se vyuˇz´ıt i odkoukan´ych zkuˇsenost´ı ve sv˚uj prospˇech. V bakal´aˇrsk´e pr´aci je uveden podrobn´y popis u obou algoritm˚u, jejich princip, chov´an´ı v uk´azkov´ych situac´ıch a srovn´avac´ı testy.

Kl´ıcˇ ov´a slova AI middleware, umˇel´a inteligence, z´abavn´ı inteligence, znalostn´ı inteligence, Turinguv test, model neuronu, Mini-max, AlfaBeta, heuristick´a funkce, backtracking, hrub´a s´ıla, bot, koneˇcn´y automat, pathfinding, genetick´e algoritmy, evoluˇcn´ı algoritmy, neuronov´a s´ıt’, zrcadlov´e kombinace, posuvn´a modifikace, vztaˇzn´y kvadrant, kritick´y tah

Podˇekov´an´ı Za zaj´ımav´y design hry (viz screenshot pˇr´ıloha B) bych r´ad podˇekoval grafik˚um Karlu B¨ohmovi ˇ a V´ıtˇezslavu Sudomovi a za mnoho cenn´ych rad a nekoneˇcnou trpˇelivost Ing. Pavlu Slav´ıcˇ kovi.

Abstract This bachelor essay describes the influence of the academic artificial intelligence algorithms on the game industry. It tries to discover, how these algorithms affect “entertainment intelligence”. Alghoritms used in a great variety of games or automats, and vice-versa. The main part of the text focuses on the comparation of two representatives of the main trends in the entertainment intelligence. It observes these two playing together a simple logic game five-in-a-row. I call the first algorithm “Goliath”, because it is a typical representant of brute strenght, but it does not seem to be very smart. It searches fairly through the wide state space of all possibilities, which the game offers. Because of this, it cannot go very deep. The amount of states, which it examines, increases very rapidly by each step deeper. The second one, Goliath’s opponent, I call “David”. It concentrates its attention only on a few, but promising moves. It can then choose from them very carefully, because it has not so many states to explore, and the amount of the states does not increases as fast as by Goliath, when it tries to go deeper. David has also a memory, and it remembers the previous games. It can learn from its own, but also from the opponent’s successes. In this technical essay is detailed description of both algorithms, their principles, behaviours in sample situations and the comparative tests.

Keywords AI middleware, artificial intelligence, entertainment intelligence, knowledge intelligence, Turing test, neuronal model, Mini-max, AlfaBeta, heuristic function, backtracking, brute strenght, bot, finite automata, pathfinding, genetic algorithm, evolutionary algorithm, neuron network, mirror combination, movable modification, reference quadrant, critical turn

Obsah Obsah

6

´ 1 Uvod

8

2

Umˇel´a inteligence 2.1 Rozd´ıl mezi inteligenc´ı lidskou a umˇelou . . . . . . . . . . . . . . . . . . . . . . 2.2 Z´abavn´ı inteligence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Historie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9 9 10 10

3

Typy poˇc´ıtaˇcov´ych her a jejich UI 3.1 Logick´e . . . . . . . . . . . . . . . . . . . . . . 3.2 Takticko-strategick´e . . . . . . . . . . . . . . . . 3.3 Akˇcn´ı (3D) . . . . . . . . . . . . . . . . . . . . 3.4 Textov´e – konverzaˇcn´ı . . . . . . . . . . . . . . 3.5 RPG, Ark´ady, Adventury, Simul´atory, Online-hry

12 12 12 13 14 14

4

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

Dva hlavn´ı smˇery UI

15

´ 5 Uvod k implementaci algoritmu˚ 5.1 Hodnot´ıc´ı funkce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Blokov´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

7

8

Goli´asˇ 6.1 Pˇr´ıliˇs hrub´a s´ıla . 6.2 Odlehˇcen´ı . . . . 6.3 Mini-max . . . . ˇ ek 6.4 Goli´asˇ vs. Clovˇ 6.5 Goli´asˇ vs. Goli´asˇ

16 16 17

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

19 19 19 20 21 22

David 7.1 Z´aznam znalost´ı . . . . . . . 7.1.1 K´odov´an´ı . . . . . . 7.1.2 Vztaˇzn´y kvadrant . . 7.1.3 Ovˇeˇren´ı pouˇzitelnosti 7.2 Vyhodnocovac´ı j´adro . . . . ˇ ek . . . . . . 7.3 David vs. Clovˇ 7.4 David vs. David . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

23 23 24 25 27 27 27 30

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

Srovn´av´an´ı David vs. Goli´asˇ

31 6

OBSAH 9

Z´avˇer 9.1 Dalˇs´ı moˇzn´a vylepˇsen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Zhodnocen´ı pˇr´ınosu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 33 33 33

Kapitola 1

´ Uvod Bakal´aˇrsk´a pr´ace je pˇrehledem typ˚u poˇc´ıtaˇcov´ych her, jejich UI a algoritm˚u kter´e se na nˇe pouˇz´ıvaj´ı. D˚uraz je kladen na dva hlavn´ı smˇery v´yvoje hern´ı UI, jejich teoretick´e i praktick´e srovn´an´ı. Teoretick´a cˇ a´ st popisuje v druh´e kapitole principy UI obecnˇe a rozd´ıl mezi lidskou a umˇelou inteligenc´ı na hˇre sˇachy. Pˇrev´azˇ n´a cˇ a´ st je vˇenov´ana hern´ı inteligenci, jej´ımu zrodu, v´yvoji a oˇcek´avan´e bl´ızk´e budoucnosti. Tˇret´ı kapitolou n´asleduje ucelen´y pˇrehled typ˚u dneˇsn´ıch her, rozbor probˇ lematiky jejich EI a n´astin algoritm˚u, kter´e se k jejich ˇreˇsen´ı pouˇz´ıvaj´ı. Ctvrt´ a kapitola shrnuje teoretickou cˇ a´ st do dvou z´akladn´ıch smˇer˚u v´yvoje UI, na hrubou s´ılu a znalostn´ı inteligenci, aby praktick´a cˇ a´ st mohla nav´azat jejich implementac´ı, testov´an´ım a porovn´an´ım. Praktick´a cˇ a´ st nejprve p´atou kapitolou osvˇetluje spoleˇcn´y z´aklad obou typ˚u UI a jejich zasazen´ı do hry piˇskvorky, na kter´e budou testov´any. Kapitoly 6 a 7 podrobnˇe popisuj´ı algoritmy z´astupc˚u tˇechto smˇer˚u: 1. Reprezentantu hrub´e s´ıly, budu ˇr´ıkat Goli´asˇ“, protoˇze tato m´ytick´a postava pˇresnˇe vystihuje ” jeho vlastnosti, kter´e jsou t´ım patrnˇejˇs´ı. 2. Protikladem Goli´asˇe je David“, pˇredstavuj´ıc´ı smˇer znalostn´ı inteligence. Ten se svoj´ı snahou ” uˇcit se a vyv´ıjet, v´ıce bl´ızˇ´ı lidsk´emu myˇslen´ı. Obsahuje tak´e zaj´ımavou uk´azku reprezentace, modifikace a aplikace z´ıskan´ych znalost´ı v nov´ych situac´ıch. D˚ukladn´y popis obou algoritm˚u je doprov´azen z´aznamem uk´azkov´e hry s cˇ lovˇekem. V n´ı pˇredv´ad´ım na p´ar kritick´ych situac´ıch slab´a m´ısta algoritm˚u a posuzuji jejich reakce. Demonstrace je zakonˇcena rozborem hry algoritmu proti sobˇe sam´emu. Cel´a osm´a kapitola rozeb´ır´a jednotliv´e souboje obou algoritm˚u mezi sebou. Hry se vz´ajemnˇe liˇs´ı pr´avˇe reakcemi rychle se uˇc´ıc´ıho Davida, kter´y se snaˇz´ı vyvarovat zaznamenan´ym prohr´am. Z´avˇereˇcn´a dev´at´a kapitola je souhrnem a vyhodnocen´ım vˇsech v´ysledk˚u tohoto teoretick´eho i praktick´eho srovn´av´an´ı obou smˇer˚u a snaˇz´ım se v n´ı podchytit v´yhody a nev´yhody obou pˇr´ıstup˚u. Zbytek kapitoly patˇr´ı diskusi moˇzn´ych vylepˇsen´ı a pˇr´ınosu t´eto pr´ace pro mne.

8

Kapitola 2

Umˇel´a inteligence C´ılem tohoto oboru je nauˇcit stroje inteligentn´ımu chov´an´ı. Inteligence je vlastnost´ı nˇekter´ych zˇ iv´ych organism˚u. Vznikala a vyv´ıjela se v pr˚ubˇehu dlouh´eho cˇ asov´eho intervalu a dnes jim umoˇznˇ uje optim´alnˇe reagovat i na sloˇzit´e projevy prostˇred´ı. Za jej´ı projev povaˇzujeme schopnost efektivnˇe ˇreˇsit r˚uzn´e probl´emy, v rozumn´em cˇ ase. Pˇredstavuje urˇcit´y stupeˇn hodnocen´ı kvality ˇreˇsen´ı i sloˇzit´ych u´ loh. M´ame docela jasnou pˇredstavu o tom co je kvalitn´ı, ale sloˇzit´e je pro kaˇzd´eho nˇeco jin´eho, pˇr´ımo z´avisl´e na jeho inteligenci. Lze povaˇzovat za r˚uznˇe sloˇzit´e hry: cˇ lovˇecˇ e nezlob se, piˇskvorky, a sˇachy. Jsou to stoln´ı hry pro dva hr´acˇ e (napˇr´ıklad), kde je smyslem hry dosaˇzen´ı v´yhern´ıho postaven´ı dˇr´ıve, neˇz to udˇel´a protihr´acˇ . Liˇs´ı se pˇredevˇs´ım poˇctem, sloˇzitost´ı pravidel a mnoˇzstv´ım pˇr´ıpustn´ych tah˚u. U sˇach˚u se odhaduje 1043 ÷ 1050 povolen´ych postaven´ı [3], u piˇskvorek to bude o pozn´an´ı m´enˇe a o cˇ lovˇecˇ e nezlob se ani nemluvˇe. Co je pro nˇekoho sloˇzit´e, pro jin´eho b´yt nemus´ı. Pojem inteligentn´ı“, stejnˇe tak jako sloˇzit´y“, ” ” ch´apeme velmi subjektivnˇe. A z toho vypl´yv´a n´asleduj´ıc´ı definice: Umˇel´a inteligence je nauka o tom, jak konstruovat stroje, jejichˇz cˇ innost, kdyby ji vykon´avali lid´e, bychom povaˇzovali za projev jejich inteligence. [2] Jedn´ım ze zakladatel˚u t´eto poˇc´ıtaˇcov´e discipl´ıny je Alan Turing. Podle jeho pˇredpoklad˚u mˇely b´yt poˇc´ıtaˇce roku 2000 schopn´e proj´ıt takzvan´ym Turingov´ym testem. 70% pr˚umˇern´ych lid´ı nemˇelo b´yt schopno po pˇeti minut´ach konverzace rozpoznat, zˇ e nehovoˇr´ı s cˇ lovˇekem. [1] Odtud tak´e: Chytr´e je to, co se chytˇre chov´a“. ”

2.1

Rozd´ıl mezi inteligenc´ı lidskou a umˇelou

Byly to pr´avˇe sˇachy, hra natolik sloˇzit´a, zˇ e byla do ned´avna povaˇzov´ana za v´yhradnˇe lidskou dom´enu, kter´e prok´azaly z´akladn´ı rozd´ıl mezi lidskou a umˇelou inteligenc´ı. Inteligence poˇc´ıtaˇce prozat´ım spoˇc´ıv´a pˇredevˇs´ım v hrub´e s´ıle, kdy propoˇc´ıt´av´a obrovsk´e mnoˇzstv´ı kombinac´ı, zat´ımco cˇ lovˇek dok´azˇ e okamˇzitˇe zavrhnout miliony nev´yhodn´ych tah˚u, coˇz je fakt, ukazuj´ıc´ı na znaˇcn´y vliv zkuˇsenost´ı na rozhodov´an´ı o dalˇs´ım postupu. T´ım byl urˇcen dalˇs´ı smˇer v´yvoje UI. Pokusy prok´azaly, zˇ e nejvˇetˇs´ı potenci´al inteligence maj´ı pr´avˇe znalosti a jejich aplikace. Naproti tomu vliv vyhodnocovac´ıho apar´atu hrub´e s´ıly, se s rostouc´ımi zkuˇsenostmi sniˇzuje. I tak, UI zaloˇzen´a pˇredevˇs´ım na slabˇs´ı“, m´enˇe perspektivn´ı vˇetvi, v proveden´ı superpoˇc´ıtaˇce ” Deep Blue od firmy IBM, porazila v kvˇetnu 1997 sˇachov´eho mistra svˇeta Garry Kasparova. Bylo to 9

ˇ A´ INTELIGENCE KAPITOLA 2. UMEL

10

poprv´e v historii, kdy poˇc´ıtaˇc zv´ıtˇezil nad sˇpiˇckov´ym sˇachistou. [7] Jen m´alo sˇachov´ych poˇc´ıtaˇcu˚ si ale m˚uzˇ e dovolit zkoumat vˇsechny moˇzn´e pozice aˇz na 9 tah˚u dopˇredu, jako Deep Blue. Ten k tomu m´a ovˇsem paraleln´ı architekturu s 500 speci´aln´ımi procesory, kter´e mu umoˇznˇ uj´ı v´ykon 400 mili´on˚u analyzovan´ych pozic za sekundu. D´ıky nim mu staˇc´ı na onˇech devˇet tah˚u dopˇredu pouze necel´e tˇri minuty, zat´ımco PC by potˇrebovalo v´ıce neˇz 5 hodin. I tento superpoˇc´ıtaˇc byl obohacen o dalˇs´ı informace, jako napˇr´ıklad z´aznamy her velmistr˚u, kter´e mu umoˇznˇ uj´ı odhadovat s´ılu jednotliv´ych styl˚u her a zamˇeˇrit se na siln´e tahy. Deep Blue mˇel v datab´azi celkem 600.000 her, ale ty mu byly d´any omyln´ymi lidmi, efektivnˇejˇs´ı by jistˇe bylo, kdyby si je vytvoˇril s´am, spojen´ım vlastn´ıch neuron˚u. [6] V polovinˇe roku 2000, ozn´amila IBM dokonˇcen´ı superpoˇc´ıtaˇce tis´ıckr´at rychlejˇs´ıho neˇz Deep Blue. . .

2.2

Z´abavn´ı inteligence

Oznaˇcuje se ZI, nebo jako EI (entertainment inteligence). Jej´ım hlavn´ım c´ılem je pobavit hr´acˇ e a udrˇzet si jeho pozornost. Snaˇz´ı se hr´acˇ e pˇresvˇedˇcit, zˇ e postavy ve hˇre jsou inteligentn´ı, autonomnˇe jednaj´ıc´ı bytosti a ne pevnˇe pˇredskriptovan´e, bezduch´e loutky, neschopn´e vymyslet cokoliv nov´eho a jen do koleˇcka opakuj´ıc´ı jiˇz zn´am´e, pˇredpovˇediteln´e a tak nezaj´ımav´e vzorce chov´an´ı. Dnes je jedn´ım z nejbouˇrlivˇeji se rozv´ıjej´ıc´ıch odvˇetv´ı z´abavn´ıho pr˚umyslu. Vznikla pˇri programov´an´ı her, jako snaha neust´ale pˇrekvapovat hr´acˇ e nˇecˇ´ım nov´ym a v posledn´ıch letech se zaˇc´ın´a uplatˇnovat dokonce i pˇri akademick´em v´yzkumu UI. Sloˇzitost, komplexnost a hloubka ˇreˇsen´eho probl´emu jsou pˇr´ımo z´avisl´e na technick´ych prostˇredc´ıch a hern´ıch poˇzadavc´ıch. Nˇekter´e algoritmy mus´ı bˇezˇ et v re´aln´em cˇ ase i na pr˚umˇern´ych dom´ac´ıch poˇc´ıtaˇc´ıch, u jin´ych se toleruje zpoˇzdˇen´ı i nˇekolika vteˇrin.

2.2.1

Historie

Filozofick´a ot´azka: Mohou stroje myslet?“, poch´az´ı jiˇz ze 17. stolet´ı. ” Poˇca´ tky UI jsou datov´any kolem roku 1946 - model neuronu, jenˇz se doposud mnoho nezmˇenil. Aˇz do druh´e poloviny 90. let byla UI v poˇc´ıtaˇcov´ych hr´ach povaˇzov´ana za okrajovou z´aleˇzitost. Hern´ı v´yvoj´aˇri mˇeli v t´e dobˇe jin´e priority: dokonalejˇs´ı, realistiˇctˇejˇs´ı a tehdy na procesor velice n´aroˇcnou grafiku. To mˇelo za n´asledek m´alo cˇ asu procesoru na jakoukoli UI a tak se o nˇejak´e hern´ı inteligenci nedalo moc hovoˇrit. Na sklonku 90. let se situace v´yraznˇe zlepˇsila s rozmachem grafick´ych akceler´ator˚u, kter´y vedl k podstatn´emu sn´ızˇ en´ı zat´ızˇ en´ı procesoru, aby se ten mohl vˇenovat i n´aroˇcnˇejˇs´ım algoritm˚um. Jedn´a se o typick´y pˇr´ıklad vz´ajemn´e z´avislosti akademick´e a z´abavn´ı umˇel´e inteligence. V´yvoj her zapˇr´ıcˇ inil rozvoj hardwaru, coˇz umoˇznilo i rozmach hern´ı UI a to pˇrineslo pozornost a prostˇredky i k t´e akademick´e. V dneˇsn´ı dobˇe m˚uzˇ eme sledovat dalˇs´ı uk´azku t´eto z´avislosti. Grafika jiˇz dosahuje sv´ych mezn´ıch“ ” moˇznost´ı a tak se v´yvoj´aˇri snaˇz´ı hru oˇzivit autonomn´ım chov´an´ım, snaˇz´ıc´ım se reagovat pˇr´ımo na zmˇeny hr´acˇ ovy taktiky. Jiˇz se neomezuje na pouh´e stˇr´ıd´an´ı pˇredem nastaven´ych strategi´ı, pˇrechody mezi f´azemi u´ toku cˇ i obrany. Dneˇsn´ı hern´ı UI se vyv´ıj´ı akademick´ym smˇerem k zapamatov´an´ı si zkuˇsenost´ı, uˇcen´ı se a vym´ysˇlen´ı“ nov´ych ˇreˇsen´ı. To vede k v´yraz” n´emu pokroku v obou oborech, kter´y pˇrin´asˇ´ı prvn´ı ovoce v podobˇe standardizace z´akladn´ıch algoritm˚u UI a jejich implementaci do knihoven.

ˇ A´ INTELIGENCE KAPITOLA 2. UMEL

11

ˇ ık´a se jim AI middleware a jedn´a se o obdobu 3D grafick´ych knihoven pro oblast hern´ı R´ UI. V´yvoj´aˇri tak nemus´ı st´ale znova implementovat ty stejn´e algoritmy, ale mohou j´ıt d´al a soustˇredit se na zkvalitˇnov´an´ı UI, jejich efektivnˇejˇs´ım pouˇzit´ım, pˇr´ıpadnˇe pˇrid´av´an´ım nov´ych. Vznikaj´ı i nov´a slov´ıcˇ ka - jako Bot“ - coˇz je oznaˇcen´ı pro hern´ı postavu ovl´adanou poˇc´ıtaˇcem, ” snaˇz´ıc´ı se simulovat lidsk´e chov´an´ı, at’ uˇz jako protivn´ık, nebo spoluhr´acˇ cˇ lovˇeka. [5] V budoucnu pˇredpokl´ad´am rozvoj a standardizaci tˇechto AI knihoven a s rostouc´ı n´aroˇcnost´ı na cˇ as procesoru i odpov´ıdaj´ıc´ı hardwarovou podporu. Historie se tedy nejsp´ısˇe zopakuje pro hern´ı UI stejnˇe, jako tomu bylo u hern´ı grafiky a tak d´a vzniknout AI akceler´ator˚um“. ” Rovnˇezˇ lze pˇredpokl´adat, zˇ e s rostouc´ı d˚uleˇzitost´ı a n´aroky se stanou natolik specializovan´ymi zaˇr´ızen´ımi, aˇz opust´ı univerz´aln´ı sbˇernici pro obyˇcejn´a zaˇr´ızen´ı a vydobudou si i sv´e vlastn´ı m´ısto na z´akladov´e desce, jakousi obdobu AGP portu. UI tedy pˇredstavuje pˇrirozen´e pokraˇcov´an´ı poˇc´ıtaˇcov´e revoluce a pˇredpokl´ad´am i masivn´ı vyuˇzit´ı na poli operaˇcn´ıch syst´em˚u. Tendence k automatick´ym optimalizac´ım dle potˇreb konkr´etn´ıho uˇzivatele, bez z´asahu program´atora, nebo u´ drˇzb´aˇre, lze sledovat u nov´ych operaˇcn´ıch syst´em˚u uˇz nyn´ı. Dalˇs´ım krokem tedy nejsp´ısˇ bude samov´yvoj i bez zˇrejm´ych potˇreb (podnˇet˚u) uˇzivatele.

Kapitola 3

Typy poˇc´ıtaˇcov´ych her a jejich UI Jak jsem uvedl v´ysˇe, v souˇcasn´e dobˇe je sice snaha o univerz´aln´ı mysl´ıc´ı UI pouˇzitelnou do v´ıce her, na ˇreˇsen´ı r˚uzn´ych u´ loh, ale bohuˇzel nen´ı jeˇstˇe tak daleko, abychom mˇeli jednu UI pouˇzitou ve dvou r˚uzn´ych hr´ach, jako tˇreba piˇskvorky a sˇachy. A to se jedn´a o stejn´y typ hry. Tato kapitola je vˇenov´ana v´ycˇ tu typ˚u her, rozboru poˇzadavk˚u na jejich UI a jejich algoritm˚um:

3.1

Logick´e

Typicky deskov´e tahov´e hry pro dva hr´acˇ e s sˇachovnicov´ym hern´ım polem, na kter´e se dle zadan´ych pravidel rozmist’uj´ı figurky, kameny, nebo jak´ekoli jin´e znaˇcky, zn´azorˇnuj´ıc´ı souˇcasn´y stav, kter´y se postupem hry mˇen´ı aˇz do stavu v´yhry, prohry, nebo rem´ızy. UI se zde pouˇz´ıv´a v´yhradnˇe jako protihr´acˇ a hratelnost b´yv´a postavena na voliteln´e obt´ızˇ nosti. Z´akladem kaˇzd´e umˇel´e inteligence je matematika. Je to obor silnˇe deterministick´y a tohle je jedin´y typ hry, od kter´e pr´avˇe takov´eto chov´an´ı oˇcek´av´ame. K t´eto deterministick´e UI staˇc´ı p´ar jednoduch´ych algoritm˚u na posouzen´ı situace a proveden´ı takov´eho tahu, kter´y vyjde v posuzovan´e hloubce (tah˚u dopˇredu) jako nejv´yhodnˇejˇs´ı. Typicky se k tomu pouˇz´ıv´a algoritus: mini-max, pˇr´ıpadnˇe s AlphaBeta proˇrez´av´an´ım stromu a heuristick´a funkce na hodnocen´ı situace. Pr´avˇe na detailn´ı popis, srovn´an´ı a vyhodnocov´an´ı tˇechto z´akladn´ıch algoritm˚u logick´e UI na hˇre piˇskvorky, se budu v dalˇs´ıch cˇ l´anc´ıch soustˇredit. Algoritmy lze d´ale rozˇs´ıˇrit o z´aznam zkuˇsenost´ı, cˇ´ımˇz se hra m˚uzˇ e st´at z´abavnˇejˇs´ı, protoˇze bude vˇernˇeji simulovat lidsk´eho (uˇc´ıc´ıho se) protihr´acˇ e. Tento protihr´acˇ je ale v nˇekter´ych smˇerech ˇ ek je zase kreativnˇejˇs´ı a l´epe schopnˇejˇs´ı neˇz protihr´acˇ lidsk´y. Uˇc´ı se rychleji a nedˇel´a chyby“. Clovˇ ” ˇreˇs´ı nov´e situace. A to dˇel´a tento typ her velmi atraktivn´ı: souboj lidsk´e vynal´ezavosti a strojov´e preciznosti.

3.2

Takticko-strategick´e

U tohoto typu her je hr´acˇ na u´ rovni vl´adce. Jeho strategick´ym u´ kolem je udrˇzet ekonomickou, vˇedeckou, vojenskou, politickou, pˇr´ıpadnˇe jeˇstˇe nˇejakou dalˇs´ı sloˇzku ˇr´ısˇe v rovnov´aze tak, aby co nejefektivnˇeji podporovala jeho taktick´e dovednosti. Pokud bude m´ıt tato spoleˇcnost vyvinutou jednu sloˇzku na u´ kor ostatn´ıch, stane se zranitelnou. ´ Prvn´ım ukolem UI – jako protihr´acˇ e – je vystihnut´ı a vyuˇzit´ı tˇechto slab´ych m´ıst k dosaˇzen´ı v´ıtˇezstv´ı. Slouˇz´ı mu k tomu s´erie pˇredem naprogramovan´ych strategi´ı na kaˇzdou pˇr´ıleˇzitost“, jeˇz ” kombinuje podle moment´aln´ı potˇreby, z´avisl´e na cˇ innosti hr´acˇ e. Takto postaven´y hern´ı syst´em b´yv´a 12

ˇ ´ COV ´ KAPITOLA 3. TYPY POCˇ ITA YCH HER A JEJICH UI

13

velice dynamick´y. Poˇc´ıtaˇc i hr´acˇ mus´ı s pˇredstihem reagovat na vznikaj´ıc´ı situace a odhadovat soupeˇru˚ v obrann´y i u´ toˇcn´y potenci´al. Aby byla d˚uleˇzitost nejen strategie, ale i taktiky jeˇstˇe pos´ılena, hra umoˇznˇ uje kombinovat nˇekolik zp˚usob˚u u´ toku i obrany: vzduˇsnou, pozemn´ı, n´amoˇrn´ı, atp. C´ılem hry je rovnov´aha mezi kvalitou a kvantitou jednotek i jejich dobr´e taktick´e vyuˇzit´ı k poraˇzen´ı nepˇr´ıtele. Takov´ychto moˇznost´ı na poraˇzen´ı nepˇr´ıtele b´yv´a hned nˇekolik: vyhlazen´ı, vyhla-dovˇen´ı, koupen´ı, apod. Typicky je hra postavena na surovin´ach, vyn´alezech, civiln´ıch a vojensk´ych jednotk´ach. Kdyˇz nebude m´ıt hr´acˇ dost civiln´ıch jednotek na tˇezˇ bu surovin, bude r˚ust jeho spoleˇcnosti omezen. Naopak pokud investuje pˇr´ıliˇs do civiln´ıch jednotek na u´ kor vojensk´ych, stane se jeho spoleˇcnost zranitelnou a bude snadno pˇremoˇzen. Po str´ance strategick´e se nejedn´a o zˇ a´ dnou jednoduchou z´aleˇzitost. Hry obsahuj´ı obrovsk´a mnoˇzstv´ı velmi komplikovan´ych pravidel a to ned´av´a mnoho prostoru pro vyuˇzit´ı hrub´e s´ıly UI. Proto se vˇetˇsinou pouze“ pˇrep´ınaj´ı, pˇr´ıpadnˇe obmˇenˇ uj´ı strategie jiˇz pˇreprogramovan´e, nebo se ” nˇekter´e prvky nahodile mˇen´ı aby se cˇ lovˇeku zt´ızˇ il odhad dalˇs´ıho poˇc´ıtaˇcova kroku. ´ Druh´ym ukolem UI je taktika, ale po t´eto str´ance b´yvaj´ı algoritmy dost oˇsizeny. Poˇc´ıtaˇc vˇetˇsinou kv˚uli strategi´ı nem´a na d˚umyslnˇejˇs´ı taktick´e algoritmy cˇ as. Zde maj´ı tedy v´yvoj´aˇri jeˇstˇe co doh´anˇet. ´ Tˇret´ım ukolem UI je prov´adˇen´ı element´arn´ıho chov´an´ı hern´ıch jednotek: Pohyb, u´ tok, obrana, hl´ıdka, pˇreskupen´ı atd. Zde se pouˇz´ıvaj´ı koneˇcn´e automaty a algoritmy BFS, DLS, A* a mnoho dalˇs´ıch, napˇr´ıklad pro nalezen´ı nejrychlejˇs´ıch cest cˇ lenit´ym ter´enem. Tyto algoritmy mus´ı b´yt velmi rychl´e, protoˇze jsou pouˇz´ıv´any des´ıtkami, aˇz stovkami jednotek, pohybuj´ıc´ıch se v re´aln´em cˇ ase. Pr´avˇe tato inteligence b´yv´a terˇcem nejˇcastˇejˇs´ı kritiky. Poslat na bojiˇstˇe odd´ıl 50 hezky seˇsikovan´ych jednotek, aby tam doˇsla sotva polovina a to jeˇstˇe po jednom, kv˚uli pˇr´ıliˇs cˇ lenit´emu ter´enu na pouˇzit´y jednoduchouˇck´y algoritmus. . . hr´acˇ e moc nepotˇesˇ´ı.

3.3

Akˇcn´ı (3D)

U tˇechto her je UI jen v jedin´e podobˇe: bot“ - dalˇs´ı postava ve hˇre, poˇc´ıtaˇcov´y protihr´acˇ , nebo ” spoluhr´acˇ . Jeho inteligence je ˇreˇsena na tˇr´ı z´akladn´ıch u´ rovn´ıch: Hern´ı z´amˇer je snaha pˇripravit si v´yhodn´e situace sb´ır´an´ım taktick´ych informac´ı o ter´enu, pˇrek´azˇ k´ach, skladech, vlajk´ach, obl´ıben´ych m´ıstech pobytu nepˇra´ tel, dobr´ych u´ krytech, nebo m´ıst pro pˇrepaden´ı ze z´alohy, apod. Pr´avˇe zde se zaˇc´ın´a vyuˇz´ıvat akademick´e inteligence. Volba strategie poˇc´ıtaˇce z´avis´ı hlavnˇe na zkuˇsenostech, z´ısk´avan´ych pr´avˇe hrou proti cˇ lovˇeku. Bot se tedy snaˇz´ı opakovanˇe neskoˇcit na pˇripravenou l´ecˇ ku a naopak zkus´ı vyuˇz´ıt t´eto znalosti ve sv˚uj prospˇech, pro vlastn´ı proti-l´ecˇ ku, napˇr´ıklad neˇcekan´ym pˇr´ıchodem cˇ´ıhaj´ıc´ımu protivn´ıkovi do zad. Tak´e brzy zjist´ı zˇ e je dobr´e se, vybavit obrann´ymi prostˇredky jako jsou vesta, cˇ i helma, pokud jsou k dispozici a nebo zˇ e pokud je zranˇen, je l´epe se ukr´yt a vyl´ecˇ it pˇred dalˇs´ım u´ tokem. Na vˇsechny tyto strategick´e prvky ve hˇre pˇrich´az´ı s´am, vlastn´ımi zkuˇsenostmi a nezˇr´ıdka pˇrijde i na nˇeco u´ plnˇe nov´eho. Bez nads´azky lze ˇr´ıci, zˇ e aˇz se on pˇrestane uˇcit od n´as, zaˇcneme se my uˇcit od nˇej. Obˇcas si ale – bohuˇzel – vyvine jak´esi super ˇreˇsen´ı“, zneuˇz´ıvaj´ıc´ı chyby v pravidlech hry, kter´a ” se tak stane nezaj´ımavou. ˇ sen´ı konkr´etn´ıch situac´ı je snaha o co nejlepˇs´ı zvl´adnut´ı vznikl´e situace vhodnou volbou Reˇ zbranˇe pro dan´e prostˇred´ı, nebo spr´avn´ym u´ hybn´ym man´evrem. Za t´ımto u´ cˇ elem si vede statistiku

ˇ ´ COV ´ KAPITOLA 3. TYPY POCˇ ITA YCH HER A JEJICH UI

14

k jednotliv´ym zbran´ım, man´evr˚um a pomˇernˇe rychle pˇrijde na to, zˇ e v uzavˇren´ych m´ıstnostech nen´ı radno pouˇz´ıvat zbranˇe hromadn´eho“ niˇcen´ı, ale zˇ e jsou naopak vhodnˇejˇs´ı, na hlouˇcek protivn´ık˚u. ” Protoˇze tyto hry jsou zaloˇzeny na procviˇcov´an´ı pr´avˇe taktick´ych dovednost´ı, b´yv´a ve hˇre k dispozici velk´y v´ybˇer r˚uzn´ych typ˚u zbran´ı: miny, gran´aty, bazuka, sniper-puˇska a tak´e r˚uzn´e druhy ter´enu, ve kter´ych se daj´ı vhodnˇe kombinovat. Vznik´a tak pomˇernˇe sluˇsn´y prostor pro uplatnˇen´ı znalostn´ı inteligence, kdyˇz se nech´av´a na botovi“, aby si metodou pokusu omylu vypracoval vlastn´ı ” optim´aln´ı taktiku i strategii, uˇsitou pˇresnˇe na m´ıru protihr´acˇ e. Element´arn´ı chov´an´ı aneb jak prov´est poˇzadovan´y man´evr: vystˇrelit, pˇreb´ıt zbraˇn, uhnout, nebo se co nejrychleji a nejbezpeˇcnˇeji pˇrem´ıstit na dalˇs´ı pozici. K tomu se pouˇz´ıv´a pathfinding, cˇ asto zaloˇzen´y na heuristick´em prohled´av´an´ı grafu. Pro jeho efektivn´ı vyuˇzit´ı je ale potˇreba m´ıt jiˇz pˇripravenou navigaˇcn´ı s´ıt’ - ony taktick´e informace o ter´enu. Tato s´ıt’ b´yv´a obˇcas pˇripravena pro konkr´etn´ı mapu od jej´ıho tv˚urce, ale to omezuje pouˇzit´ı takov´eho bota jinde. Proto se dalˇs´ı v´yvoj zamˇeˇruje i na tuto cˇ a´ st UI a snaˇz´ı se nauˇcit poˇc´ıtaˇc: uˇcit se ter´en“. Pokusem a omylem m˚uzˇ e pˇrece ” pˇrij´ıt nejen na to, zˇ e zd´ı neprojde a dveˇrmi ano, ale tˇreba i jak si je otevˇr´ıt.[5]

3.4

Textov´e – konverzaˇcn´ı

Zde se velmi vyuˇz´ıv´a uˇcen´ı a sb´ır´an´ı zkuˇsenost´ı. Nejd˚uleˇzitˇejˇs´ı a nejtˇezˇ sˇ´ı je zaveden´ı zpˇetn´e vazby, protoˇze poˇc´ıtaˇc potˇrebuje neust´ale vyhodnocovat kvalitu sv´eho v´ykonu, aby se mohl vyv´ıjet. Dosud nej´uspˇesˇnˇejˇs´ım konverzaˇcn´ım programem je A.L.I.C.E. (Artificial Inteligence Internet Computer Entity) Syst´em vyvinul v roce 1995 Dr. Richard S. Wallace a od t´e doby se na jeho zdokonalov´an´ı pod´ılely stovky v´yvoj´aˇru˚ . V lednu 2000 z´ıskal poprv´e Loebnerovu cenu za nej´uspˇesˇnˇejˇs´ı v´ysledek v Turingovˇe testu, protoˇze se nejvˇetˇs´ı poˇcet sud´ıch domn´ıval, zˇ e hovoˇr´ı s cˇ lovˇekem. [4]

3.5

RPG, Ark´ady, Adventury, Simul´atory, Online-hry

Inteligence v tˇechto hr´ach nen´ı tak v´yznamn´a, nebo se neliˇs´ı od nˇekter´ych v´ysˇe jmenovan´ych.

Kapitola 4

Dva hlavn´ı smˇery UI Jak bylo naznaˇceno v´ysˇe, pojem inteligentn´ı lze t´ezˇ ch´apat jako efektivn´ı a to jak ve smyslu v´ykonu (pˇri hled´an´ı ˇreˇsen´ı), tak i kvality (pˇri hodnocen´ı nalezen´eho ˇreˇsen´ı). Podle toho rozezn´av´ame dva z´akladn´ı smˇery ve v´yvoji inteligence: Hrub´a s´ıla je v´ykon, tedy poˇcet prozkouman´ych kombinac´ı za cˇ as. Snaˇz´ı se co nejrychleji vyhodnotit co nejvˇetˇs´ı mnoˇzstv´ı kombinac´ı a vybrat si z nich co nejlepˇs´ı ˇreˇsen´ı. Jedn´a se o mˇelk´e prohled´av´an´ı sˇirok´eho stavov´eho prostoru. Znalostn´ı inteligence se snaˇz´ı na z´akladˇe zkuˇsenost´ı, statistiky, nebo jin´eho principu, odhadnout moˇzn´a ˇreˇsen´ı a vybrat si z nich to nejkvalitnˇejˇs´ı. D˚uraz je v tomto smˇeru kladen na v´ybˇer perspektivn´ıch kandid´at˚u, kter´e lze n´aslednˇe posoudit velmi d˚ukladnˇe. Zaj´ımavou kombinac´ı obou jsou genetick´e a evoluˇcn´ı algoritmy. Ty se tak´e uˇc´ı“, ale pouze v r´amci ” jednoho projektu. Nejprve projdou cel´y stavov´y prostor a hledaj´ı, zkoumaj´ı a kombinuj´ı cˇ a´ steˇcn´a ˇreˇsen´ı, aˇz dojdou k tomu nejlepˇs´ımu. Podobnˇe pracuj´ı i neuronov´e s´ıtˇe, simuluj´ıc´ı vybran´e procesy jejich biologick´ych protˇejˇsk˚u. Velmi zjednoduˇsenˇe ˇreˇceno: Vytv´aˇr´ı soustavu n´ahodn´ych“ vazeb, jeˇz jsou n´aslednˇe spojov´any ˇ” a rozpojov´any, podle vlivu na kvalitu ˇreˇsen´ı. Casem tak syst´em vazeb konverguje k optim´aln´ımu ˇreˇsen´ı. Je d˚uleˇzit´e neskonˇcit v nˇekter´em z lok´aln´ıch extr´em˚u. Proto se vˇetˇsinou proces opakuje nˇekolikr´at a vyb´ır´a se z nalezen´ych ˇreˇsen´ı to nejlepˇs´ı. Jedn´a se doslova o implementaci pˇr´ırodn´ıch z´akon˚u pˇrirozen´eho v´ybˇeru a tak pˇr´ıslov´ı: pˇr´ıroda ” si najde vˇzdycky cestu“, m˚uzˇ eme vzt´ahnout i na takov´eto umˇel´e inteligence.

15

Kapitola 5

´ Uvod k implementaci algoritmu˚ Pro lepˇs´ı pˇredstavu d´ale popisovan´ych algoritm˚u uvedu nejprve struˇcn´y popis prostˇred´ı, ve kter´em jsou implementov´any. UI je samostatn´a jednotka, kter´a si ukl´ad´a informace o jednotliv´ych taz´ıch hr´acˇ u˚ (viz obr´azek 5.1) do hern´ıho pole na obr´azku (5.2) a na poˇza´ d´an´ı vr´at´ı souˇradnice tahu, kter´y povaˇzuje pro zadan´eho hr´acˇ e za nejlepˇs´ı. Nejkrajnˇejˇs´ı sloupce a ˇra´ dky hern´ıho pole tvoˇr´ı ob´alku, vymezuj´ıc´ı jeho hranice. To usnadˇnuje pole proch´azej´ıc´ı algoritmy, kter´e tak nemus´ı tyto hranice neust´ale sledovat. K nˇemu koresponduje i vhodn´e pole na obr´azku (5.3), kter´e vymezuje tahy vhodn´e pro simulaci. Jsou to neobsazen´a pole v hern´ı oblasti, s nepr´azdn´ym okol´ım. Nenulov´e cˇ´ıslo tohoto pole urˇcuje vzd´alenost k nejbliˇzsˇ´ımu tahu.

Obr´azek 5.1: tahy hr´acˇ u˚

5.1

Obr´azek 5.2: hern´ı pole

Obr´azek 5.3: vhodn´e pole

Hodnot´ıc´ı funkce

Slouˇz´ı pro ohodnocen´ı pˇr´ınosu jednotliv´ych tah˚u na stejn´e u´ rovni stromu. Spoˇc´ıt´a kolik nepˇreruˇsen´ych n-tic dan´ym tahem vzniklo a jestli pˇri tom nastal v´yhern´ı stav (pˇetice). Protoˇze m´ame jen cˇ tyˇri smˇery (spoleˇcnˇe s jejich protismˇery), mohou jedn´ım tahem vzniknout maxim´alnˇe cˇ tyˇri n-tice. Z naznaˇcen´eho tahu na obr´azku (5.4) je patrn´e, zˇ e t´ımto tahem vznikne ve tˇr´ı smˇerech jednice“ a v jednom smˇeru trojice. Funkce tomuto tahu za zelen´eho hr´acˇ e pˇriˇrad´ı ” cˇ´ıslo 10 + 10 + 10 + 1000 = 1030.

16

´ KAPITOLA 5. UVOD K IMPLEMENTACI ALGORITMU˚

17

Obr´azek 5.4: smˇery Takovouto hodnot´ıc´ı funkc´ı bychom mohli rozumnˇe rˇeˇsit z´akladn´ı situace aˇz od cˇ tyˇr p˚ultah˚u napˇred, protoˇze aˇz pak by se projevilo sn´ızˇ en´ı priority tahu u´ toˇcn´ıka kvalitn´ı obranou. Pˇritom se jedn´a o kritick´e situace, konˇc´ıc´ı v pˇr´ıpadˇe chybn´eho rozhodnut´ı prohrou.

5.2

Blokov´an´ı

Pˇrid´ame tedy pravidlo kter´e sniˇzuje taktickou hodnotu o jednu u´ roveˇn za kaˇzdou blokovanou stranu dan´eho smˇeru. Pokud budou takto zablokov´any obˇe strany a nezbude dost m´ısta pro rozestaven´ı v´yhern´ı pˇetice, bude taktick´a hodnota takov´eho smˇeru nulov´a, protoˇze v´yhra v tomto smˇeru nen´ı moˇzn´a. Obrana

Obr´azek 5.5 1020 : 120 1020 : 120

Obr´azek 5.6 10020 : 30 1020 : 20

Obr´azek 5.7 200 : 30 200 : 30

´ Utok

Obr´azek 5.8 1020 : 120 1020 : 120

Obr´azek 5.9 10020 : 1020 10020 : 1020

Obr´azek 5.10 VYHRA : MINIMUM VYHRA : MINIMUM

´ KAPITOLA 5. UVOD K IMPLEMENTACI ALGORITMU˚

18

NA obr´azku (5.5) je uk´azkov´a situace a pod n´ı patˇriˇcn´e ohodnocen´ı posledn´ıho tahu zelen´eho vs. cˇ erven´eho hr´acˇ e bez blokov´an´ı. Pod n´ım je pro srovn´an´ı ohodnocen´ı situace s blokov´an´ım. Obr´azky (5.6) a (5.7) ukazuj´ı obrann´y rozvoj a jeho ohodnocen´ı. Obr´azek (5.8) zobrazuje stejnou situaci, ale obr´azky (5.9) a (5.10) ukazuj´ı jej´ı u´ toˇcn´y rozvoj. U (5.6) je jiˇz patrn´y u´ cˇ inek obrany s blokov´an´ım (na sn´ızˇ en´ım priority protihr´acˇ e v obrann´em rozvoji proti u´ toˇcn´eu), zat´ım co bez blokov´an´ı je u´ cˇ inek patrn´y aˇz o tah pozdˇeji na (5.7). D´ıky tomu lze pˇredv´ıdat hrozbu dˇr´ıve, neˇz ji odhal´ı mini-max strom popisovan´y d´ale a s pˇredstihem na ni reagovat.

Kapitola 6

Goli´asˇ Je pˇredstavitelem hrub´e v´ypoˇcetn´ı s´ıly a bude proch´azet obrovsk´e mnoˇzstv´ı vˇetv´ı metody mini-max. D´ıky minim´aln´ım rozd´ıl˚um mezi jednotliv´ymi vˇetvemi stromu m˚uzˇ eme v´yhodnˇe pouˇz´ıt algoritmus backtracking, kter´emu staˇc´ı drˇzet v pamˇeti pouze zkoumanou situaci.

6.1 Pˇr´ıliˇs hrub´a s´ıla Pˇri implementaci Goli´asˇe je nejd˚uleˇzitˇejˇs´ı v´ysˇka stromu a poˇcet kombinac´ı kter´e ho nech´ame proj´ıt. V ide´aln´ım pˇr´ıpadˇe by mˇel proj´ıt vˇsechny moˇzn´e korektn´ı kombinace, aˇz do poˇzadovan´e hloubky: (xy − o)! (xy − o − t)! x, y - sˇ´ıˇrka, v´ysˇka hern´ıho pole

o - jiˇz obsazen´ych tah˚u

t - tah˚u mysl´ıc´ıch napˇred

Napˇr´ıklad: U hern´ıho pole 23 na 23 by prvn´ım tahem, pˇri simulaci dvou-p˚ultah˚u napˇred, proˇsel 279.312 kombinac´ı a pˇri pouh´ych cˇ tyˇr p˚ultaz´ıch uˇz pˇres 77 miliard, coˇz by pˇri rychlosti poˇc´ıtaˇce 10.000 kombinac´ı za vteˇrinu, trvalo cel´e 3 mˇes´ıce.

6.2

Odlehˇcen´ı

Je tˇreba v´yraznˇe sn´ızˇ it poˇcet zkouman´ych kombinac´ı vynech´an´ım nesmysln´ych tah˚u: • Zaˇc´ın´a-li UI, nebude uvaˇzovat nad prvn´ım tahem a um´ıst´ı ho rovnou do stˇredu HP. • Zvaˇzovat se budou pouze tahy do bezprostˇredn´ıho okol´ı jiˇz proveden´ych tah˚u. Kaˇzd´y tah, hned po tom prvn´ım, je pouhou“ reakc´ı na soupeˇre˚uv pˇredeˇsl´y, at’ uˇz se jedn´a o u´ tok, ” rozv´ıjej´ıc´ı vlastn´ı postaven´ı, nebo obranu. Osamocen´y tah mimo ostatn´ı tahy hr´acˇ u˚ je ztr´atov´y z hlediska u´ toku (´utok selhal, zaˇc´ın´a nov´y) a nesmysln´y z hlediska obrany. Nˇekter´e tahy se mohou uk´azat v´yhodn´e aˇz ve vˇetˇs´ı v´ysˇce stromu, neˇz jakou budeme pˇri rozhodov´an´ı pouˇz´ıvat. Nebudou tedy vybr´any a tak nem´a smysl se jimi zab´yvat. Proto zavedeme n´asleduj´ıc´ı pravidla pro v´ybˇer zvaˇzovan´ych tah˚u: 1. Zvaˇzujeme jen tahy v bezprostˇredn´ım okol´ı jiˇz proveden´ych tah˚u a tahy kde se ob-jedno prot´ınaj´ı dvˇe alespoˇn dvojice, jak je zn´azornˇeno na obr´azku (6.1). 19

KAPITOLA 6. GOLIA´ Sˇ

20

2. Kaˇzd´y dalˇs´ı tah bude veden v pomysln´em kˇr´ızˇ i, zn´azornˇen´em zˇ lut´ymi body na obr´azc´ıch (6.2) a (6.3), kter´y vznik´a pˇri z´apisu nesimulovan´eho tahu, ve vˇsech smˇerech od nˇej. To sniˇzuje poˇcet vznikaj´ıc´ıch kombinac´ı pˇrid´av´an´ım simulovan´ych tah˚u, na nezbytn´e minimum. Optim´aln´ı d´elka tohoto kˇr´ızˇ e pro cˇ tyˇri p˚ultahov´a zanoˇren´ı jsou tˇri pole.

Obr´azek 6.1: okol´ı 1

Obr´azek 6.2: okol´ı 2

Obr´azek 6.3: okol´ı 3

T´ım jsme sn´ızˇ ili poˇcet zvaˇzovan´ych kombinac´ı (v pˇr´ıpadˇe reakce na prvn´ı tah), bez v´azˇ nˇejˇs´ı ztr´aty kvality ˇreˇsen´ı, aˇz na pˇrijateln´ych: 8 · 10 · 10 · 9 − 4 · 4 · 3 · 9 = 6.768 Vynechan´e moˇznosti by se stejnˇe neuk´azaly efektivn´ımi do hloubky cˇ tyˇr-p˚ultah˚u, kterou se budeme zab´yvat.

6.3

Mini-max

J´adrem Goli´asˇe je metoda mini-max, kter´a simuluje v´ysˇe popsan´ym zp˚usobem vybran´e tahy. Na kaˇzd´y z nich zvaˇzuje vˇsechny“ (vybran´e) odpovˇedi soupeˇre a na kaˇzdou z nich zase vˇsechny“ ” ” moˇznosti vlastn´ıch tah˚u s odpov´ıdaj´ıc´ımi reakcemi soupeˇre. Teprve po simulaci tˇechto dvou u´ pln´ych tah˚u pouˇzije hodnot´ıc´ı funkci pro taktick´e posouzen´ı posledn´ıho vlastn´ıho tahu, zmenˇsen´e o hodnocen´ı posledn´ıho tahu protihr´acˇ e. Tento princip je naznaˇcen na obr´azku (6.4). Jedin´y rozd´ıl spoˇc´ıv´a v tom, zˇ e m´ısto zobrazen´ych dvou potomk˚u kaˇzd´eho uzlu, jich m´a mini-max kolem deseti. Strom tak rychle roste do astronomick´e sˇ´ıˇrky. Metoda mini-max vyb´ır´a na nejniˇzsˇ´ı u´ rovni nejmenˇs´ı hodnoty tˇechto taktick´ych koeficient˚u, protoˇze pˇredstavuj´ı nejlepˇs´ı protihr´acˇ ovy reakce na dan´y tah a pˇred´a je otcovsk´emu uzlu, aby si z nich vybral tu, kter´a vyjde pro hr´acˇ e nejl´ıp. Z tˇechto maxim se opˇet vyb´ıraj´ı minima a z nich zase maximum, posledn´ı na vrcholu stromu. To pˇredstavuje n´asˇ hledan´y, na cˇ tyˇri p˚ultahy dopˇredu nejlepˇs´ı, tah. Pokud bˇehem konstrukce stromu dojde k v´yhˇre nˇekter´eho z hr´acˇ u˚ , tato vˇetev konˇc´ı s hodnotou minim´aln´ı + v´ysˇka, nebo maxim´aln´ı − v´ysˇka, podle v´yhry hr´acˇ e, cˇ i protihr´acˇ e. Z takov´ychto stav˚u by si vybral nejrychlejˇs´ı v´yhru, nebo nejpomalejˇs´ı prohru (nemˇel by-li lepˇs´ı moˇznost).

KAPITOLA 6. GOLIA´ Sˇ

21

´ y cˇ tyˇrp˚ultahov´y strom se dvˇema potomky kaˇzd´eho uzlu Obr´azek 6.4: Upln´

6.4

ˇ ek Goli´asˇ vs. Clovˇ

Vˇetˇsinu lid´ı na poprv´e poraz´ı, ale brzy prohl´ednou jeho slabiny a metodou pokusu a omylu pˇr´ıjdou na posloupnost silnˇejˇs´ıch tah˚u, neˇz je dvoutahov´y mini-max schopen rozliˇsit. Pˇr´ıklad takov´e posloupnosti je na obr´azku (6.5), aby ji se zelen´ym kˇr´ızˇ kem hraj´ıc´ı Goli´asˇ spr´avnˇe vyhodnotil, musel by m´ıt minim´alnˇe cˇ tyˇr-p˚ultahov´y mini-max strom.

Obr´azek 6.5: V´yhern´ı posloupnost tah˚u nad Goli´asˇem

KAPITOLA 6. GOLIA´ Sˇ

22

Kritick´y, sˇpatnˇe vyhodnocen´y tah je na obr´azku na obr´azku (6.5) zn´azornˇen zˇ lutˇe. Posloupnost tah˚u vedouc´ı k neodvratn´e v´yhˇre cˇ erven´eho hr´acˇ e, je zn´azornˇena cˇ erven´ymi body a odpov´ıdaj´ıc´ı Goli´asˇova reakce zelen´ymi. Je vidˇet, zˇ e po kritick´em tahu hra spˇeje k neodvratn´emu konci, protoˇze vede ke vzniku typick´e neodvratn´e situace, se dvˇema neblokovan´ymi posloupnostmi trojic, naznaˇcen´ych kˇr´ızˇ em. Zelen´y m˚uzˇ e n´aslednˇe blokovat jen jednu z nich a cˇ erven´y tak dokonˇc´ı nepˇreruˇsenou posloupnost na v´yhern´ıch pˇet u t´e druh´e. Je-li tento typ UI jednou poraˇzen, pro cˇ lovˇeka ztrat´ı v´yznam s n´ım hr´at, protoˇze takto ho poraz´ı vˇzdy.

6.5

Goli´asˇ vs. Goli´asˇ

Jak patrno na obr´azku (6.6), vyhr´al zaˇc´ınaj´ıc´ı zelen´y po 30 taz´ıch. I zde je zˇretelnˇe vidˇet n´asledek sˇpatnˇe vyhodnocen´eho kritick´eho bodu, jeˇz vedl k nebr´aniteln´e situaci. Zvˇetˇsen´ı mini-max stromu o p´ar dalˇs´ıch pater by podstatnˇe zv´ysˇilo inteligenci, kvalitu vybran´ych tah˚u, ale princip by z˚ustal stejn´y. Opˇet by nˇekter´y z hr´acˇ u˚ pˇrehl´edl kritick´y tah, protoˇze by se uk´azal pozdˇeji, neˇz kam aˇz simuloval jeho strom. Zato doba na vybr´an´ı tahu by se nˇekolik set kr´at prodlouˇzila a hra by pˇrestala b´yt pro cˇ lovˇeka hratelnou.

Obr´azek 6.6: V´yhern´ı posloupnost tah˚u nad Goli´asˇem Na obr´azku (6.6) vlevo dole, vedle posledn´ıho v´yhern´ıho pol´ıcˇ ka, je vidˇet dalˇs´ı otevˇren´a posloupnost. Bohuˇzel, chybou pouˇzit´eho algoritmu je, zˇ e jakmile Goli´asˇ zjist´ı, zˇ e nem´a sˇanci, protoˇze je schopen br´anit jen jednu posloupnost a protihr´acˇ m´a pˇripraveny dvˇe, vzd´a to. Tomu odpov´ıdaj´ı dva ˇ ek by se pokusil br´anit alespoˇn jednu, ale poˇc´ıtaˇc v tom nesmysln´e cˇ erven´e tahy vlevo nahoˇre. Clovˇ nevid´ı smysl, protoˇze pro nˇej uˇz to, zˇ e hra skonˇcila, je hotov´a z´aleˇzitost ve chv´ıli kdy si to uvˇedom´ı, coˇz je pˇresnˇe dva tahy pˇred opravdov´ym koncem. Pro poˇc´ıtaˇc je to sˇach-mat druh´ym tahem“. ”

Kapitola 7

David Pouˇz´ıv´a sice stejn´e hern´ı pole i stejnou hodnot´ıc´ı funkci, ale jeho z´akladn´ı algoritmus je jin´y. Zat´ımco Goli´asˇu˚ v mini-max prom´ysˇlel vˇsechny vhodn´e kombinace aˇz do zadan´e hloubky, David simuluje jen n´asleduj´ıc´ı cˇ tyˇri vˇetve pro kaˇzd´y vhodn´y tah: ´ cn´a vˇetev logick´a si vyb´ır´a nejlepˇs´ı tah pro hr´acˇ u˚ v u´ tok, protihr´acˇ reaguje nejlepˇs´ı obra1. Utoˇ nou. To se opakuje aˇz do zadan´e hloubky, kde se vyhodnot´ı dosaˇzen´ı taktick´ych v´ysledk˚u hr´acˇ e. 2. Obrann´a vˇetev logick´a pracuje obr´acenˇe. Protihr´acˇ u´ toˇc´ı a hr´acˇ se br´an´ı. ´ cn´a vˇetev znalostn´ı je stejn´a jako u´ toˇcn´a vˇetev logick´a, s t´ım rozd´ılem, zˇ e u´ tok je simulov´an 3. Utoˇ dle z´aznamu zkuˇsenosti, se zjiˇstˇenou podobnost´ı s posledn´ım tahem hr´acˇ e. Vyhodnocuje se, zda vˇetev konˇc´ı koncem z´aznamu v´yhrou, nebo jeˇstˇe dˇr´ıve pokusem o nekorektn´ı tah. 4. Obrann´a vˇetev znalostn´ı simuluje u´ tok protihr´acˇ e dle z´aznamu zkuˇsenosti s pˇredpokl´adanou obranou hr´acˇ e. David tedy proch´az´ı m´enˇe kombinac´ı, ale plat´ı za to horˇs´ı kvalitou nalezen´ych ˇreˇsen´ı, kterou se snaˇz´ı dorovnat zkuˇsenostmi.

7.1

Z´aznam znalost´ı

Kaˇzd´a hra m´a 8 zrcadlov´ych kombinac´ı s aˇz 528 modifikacemi dle souˇradnic poˇca´ teˇcn´ıho tahu. S obyˇcejnou pamˇet´ı jednotliv´ych her bychom se tak daleko nedostali. Ani prov´adˇet 4224 modifikac´ı kaˇzd´eho z´aznamu nen´ı rozumn´e. Z´aznam znalost´ı mus´ı b´yt kromˇe snadn´e a rychl´e dostupnosti i efektivn´ı na zrcadlov´e a posuvn´e modifikace. Jinak by uˇcen´ı bylo chaotick´e, trvalo nepˇrimˇeˇrenou dobu, nebo by z´aznamy zab´ıraly mnoho m´ısta a vyhled´av´an´ı v nich zase cˇ asu. Z´aznam bude tedy ve speci´aln´ım vysuˇsen´em“ form´atu, oproˇstˇen´em od poˇca´ teˇcn´ıch souˇradnic ” a zrcadlov´ych kombinac´ı. Protoˇze nejˇcastˇejˇs´ı z´aznamovou operac´ı bude cˇ ten´ı (pˇr´ımo u´ mˇern´e poˇctu z´aznam˚u), bude nejlepˇs´ı vysuˇsit“ tah z hern´ıch souˇradnic na z´aznamov´y form´at a pak pohodlnˇe ” porovnat se vˇsemi tahy vˇsech dostupn´ych z´aznam˚u her. Takto jedin´ym pr˚uchodem s jedin´ym porovn´an´ım efektivnˇe vyhodnot´ıme vˇsechny zrcadlov´e a posuvn´e kombinace.

23

KAPITOLA 7. DAVID

7.1.1

24

K´odov´an´ı

Pro nejefektivnˇejˇs´ı porovn´av´an´ı z´aznamov´ych tah˚u bude tah zaps´an jako jedin´e cel´e cˇ´ıslo. Toto cˇ´ıslo je obyˇcejn´y vektor posunu proti pˇredeˇsl´emu tahu, jehoˇz sloˇzky x a y dostaneme rozkladem na souˇcin prvoˇc´ısel. Pˇr´ıtomnost prvoˇc´ısel 2 a 3 v tomto rozkladu urˇcuje kvadrant, ve kter´em se posun odehr´av´a. Ten je ovˇsem z´avisl´y na pˇredeˇsl´ych taz´ıch, takˇze pˇr´ıtomnost tˇechto prvoˇc´ısel n´am pouze ˇrekne, zda je posun ve smˇeru nastaven´eho vztaˇzn´eho kvadrantu, nebo v opaˇcn´em.

Obr´azek 7.1: K´odov´an´ı tahu do prvoˇc´ıseln´ych souˇradnic

Obr´azek (7.1) zn´azorˇnuje posuny s nastavenou osou x vodorovnˇe a vztaˇzn´ym kvadrantem odpov´ıdaj´ıc´ım kvadrantu druh´emu. Tyto parametry jsou promˇenn´e, tvoˇr´ı pr´avˇe 8 zrcadlov´ych kombinac´ı a jsou z´avisl´e na smˇeru poˇca´ teˇcn´ıho v´yvoje hry.

Mˇejme posloupnost prvoˇc´ısel: 2,3,5,7,11,13,17,19,. . . 2 urˇcuje posun od/do vztaˇzn´eho kvadrantu po ose x 3 urˇcuje posun od/do vztaˇzn´eho kvadrantu po ose y 5,11,17,. . . znamenaj´ı posun o 1,2,3,. . . po ose x 7,13,19,. . . znamenaj´ı posun o 1,2,3,. . . po ose y

V poˇrad´ı lich´a prvoˇc´ısla (pˇetkou poˇc´ınaje) ud´avaj´ı posun po ose x a sud´a zase (sedmiˇckou poˇc´ınaje) po ose y. V´ysledn´y k´od tahu je sloˇzen ze souˇcinu tˇechto dvou prvoˇc´ısel a pokud byl posun v opaˇcn´em kvadrantu osy x, vyn´asob´ı se dvˇema, pˇr´ıpadnˇe tˇremi pro osu y.

Pˇr´ıklad: Posun 1,1 ve vztaˇzn´em kvadrantu 5 · 7 = 35. Stejn´y posun v opaˇcn´em smˇeru 2 · 3 · 5 · 7 = 210.

25

KAPITOLA 7. DAVID T´ımto zp˚usobem m˚uzˇ eme jednoznaˇcnˇe de / k´odovat jak´ekoli souˇradnice x, y aˇz do velikosti: q 2n )−2 PrvociselDo( 2·3 2 n - poˇcet bit˚u promˇenn´e

32 bit˚u pokr´yv´a interval < (0, 0), (1467, 1467) >, coˇz bohatˇe postaˇcuje na pokryt´ı hern´ı plochy.

7.1.2 Vztaˇzn´y kvadrant Prvn´ı tah se nek´oduje. Oznaˇcuje pouze startovn´ı pozici obrazce“ n´asleduj´ıc´ıch tah˚u, kter´a pro ” z´aznam nem´a zˇ a´ dn´y v´yznam. Kaˇzd´y n´asleduj´ıc´ı tah se zak´oduje jako posun v˚ucˇ i pˇredeˇsl´emu. Pˇr´ıklad: Tah − Pˇredeˇsl´y tah = (11, 12) − (12, 12) = (−1, 0) = 5 · 1 = 5 Tah − Pˇredeˇsl´y tah = (13, 12) − (12, 12) = ( 1, 0) = 5 · 2 = 10 Jak vid´ıme v pˇr´ıkladu, v´ysledek obou z´aznam˚u by byl bez zohlednˇen´ı vztaˇzn´eho kvadrantu stejn´y. V tomto pˇr´ıpadˇe je vztaˇzn´y kvadrant pro osu x, kter´a je vodorovn´a, nastaven z´aporn´y. Vˇsechny posuny s kladn´ym v´ysledkem x jsou v opaˇcn´em kvadrantu a jejich prvoˇc´ıseln´y rozklad obsahuje prvoˇc´ıslo 2.

Tabulka 7.1 zobrazuje vˇsech osm zrcadlov´ych kombinac´ı, kter´ymi si m˚uzˇ eme vysuˇsen´y“ z´aznam ” 5 5 7“ vyloˇzit nastaven´ım promnˇenn´ych: kvadrant x, kvadrant y, osa x (+−, +−, vodorovn´a / kolm´a). ” Osa x Kvadrant y Kvadrant x

vodorovn´a − −

kolm´a −

+ +

−

+

−

+ +

−

Tahy

Tabulka 7.1: osm zrcadlov´ych moˇznost´ı jak vyloˇzit z´aznam 5 5 7“ ”

Vztaˇzn´y kvadrant x, y a smˇer osy x se urˇcuje hned na zaˇca´ tku hry dle prvn´ıch tah˚u.

+

KAPITOLA 7. DAVID

26

´ y pˇrehled nastaven´ı vztaˇzn´eho kvadrantu a osy x dle poˇca´ teˇcn´ıch tah˚u (v poli 5 na 5) rozdˇelen´y Upln´ do tˇr´ı hlavn´ıch kategori´ı: 1 1. Jednoznaˇcn´y vztaˇzn´y kvadrant x, y i osa x • Obˇe sloˇzky posunu x i y jsou nenulov´e, jedna je vˇetˇs´ı neˇz druh´a.

• Osa x je stanovena ve smˇeru vˇetˇs´ı z obou sloˇzek. • Kvadrant x pˇreb´ır´a znam´enko sloˇzky x. • Kvadrant y pˇreb´ır´a znam´enko sloˇzky y.

2. Jednoznaˇcn´y vztaˇzn´y kvadrant x, y, nezn´am´a osa x • Obˇe sloˇzky posunu x i y jsou stejn´e, nenulov´e.

• Kvadrant x pˇreb´ır´a znam´enko sloˇzky x. • Kvadrant y pˇreb´ır´a znam´enko sloˇzky y. • Dokud budou obˇe sloˇzky posunu v˚ucˇ i prvn´ımu tahu stejn´e, nelze urˇcit smˇer osy x. Tyto nerozhodn´e tahy mohou b´yt pouze ve smˇeru vztaˇzn´eho kvadrantu (x i y), nebo v protismˇeru obou tˇechto sloˇzek. Smˇer osy x se pro tento tah nijak neuplatn´ı, protoˇze obˇe sloˇzky jsou stejn´e a posun je obˇema sloˇzkami bud’ ve vztaˇzn´em kvadrantu, nebo v opaˇcn´em.

3. Jednoznaˇcn´y vztaˇzn´y kvadrant x, nezn´am´y y, zn´am´a osa x • Jedna ze sloˇzek je nulov´a.

• Protoˇze je sloˇzka nulov´a, nem´a v k´odu souˇcasn´eho tahu zˇ a´ dn´y v´yznam a tak nemus´ı b´yt zat´ım urˇcena. Tak jako v kategorii (2), rozhodne o znam´enku dalˇs´ı tah.

Dvˇe ze tˇr´ı sloˇzek lze zjistit hned pˇri z´apisu druh´eho tahu (prvn´ıho posunu), ta zb´yvaj´ıc´ı (pokud nebyla zjiˇstˇena) nem´a na k´odovan´y tah vliv a lze ji proto zjistit pozdˇeji. Jednopr˚uchodov´e k´odov´an´ı je tedy vˇzdy jednoznaˇcn´e a u´ pln´e.

1 Na obr´azc´ıch konkr´etn´ıch pˇr´ıpad˚ u u jednotliv´ych kategori´ı je zn´azornˇena osa x modˇre, tah posunu v˚ucˇ i tahu do stˇredu

cˇ ervenˇe a vstaˇzn´y kvadrant sˇedˇe.

KAPITOLA 7. DAVID

7.1.3

27

Ovˇerˇ en´ı pouˇzitelnosti

Z´aznam pˇredeˇsl´ych her poˇrizujeme za u´ cˇ elem odhadnut´ı“ n´asleduj´ıc´ıho tahu. Rekonstrukce prob´ıh´a ” tak, zˇ e na zaˇca´ tku hry urˇc´ıme vztaˇzn´y kvadrant x, y a osu x z tah˚u hr´acˇ e, v´ysˇe uveden´ym zp˚usobem. Posledn´ı zak´odovan´y tah hr´acˇ e hled´ame v pamˇeti pˇredeˇsl´ych her. Pokud je nalezen, je zkoum´ano, zda zb´yvaj´ıc´ı posloupnost tah˚u z´aznamu vede k v´ıtˇezstv´ı i v t´eto situaci. Ve vˇetˇsinˇe pˇr´ıpad˚u se bude jednat o faleˇsn´y poplach a simulace zb´yvaj´ıc´ı cˇ a´ sti z´aznamu od nalezen´e shody, znalost vs. reakce, skonˇc´ı pˇred koncem z´aznamu nekorektn´ım tahem. Pokud ale bude znalostn´ı u´ tok dotaˇzen aˇz do v´yhern´ıho konce i pˇres simulovanou obranu, je znalost pouˇziteln´a pro tuto hru a takto veden´y u´ tok bude pravdˇepodobnˇe v´yhern´ı. Hodnˇe z´aleˇz´ı na kvalitˇe simulovan´e obrany. Obdobnˇe se postupuje i pˇri posuzov´an´ı obrany. Je zkoum´ano, zda n´asleduj´ıc´ım tahem m˚uzˇ e protihr´acˇ navodit situaci, kter´a jiˇz jednou vedla k jeho v´yhˇre.

7.2

Vyhodnocovac´ı j´adro

Jak jsem jiˇz naznaˇcil v u´ vodu t´eto kapitoly, David provede simulaci n´asledk˚u vˇsech vhodn´ych tah˚u v podobˇe logick´e a zkuˇsenostn´ı vˇetve, pro sv˚uj i protihr´acˇ u˚ v u´ tok. K tomu si jeˇstˇe zapamatuje nejnadˇejnˇejˇs´ı tah (s nejvˇetˇs´ı prioritou), u kter´eho zˇ a´ dn´a z obou vˇetv´ı neskonˇcila prohrou. Upˇrednostˇnuje tah, vedouc´ı k nejrychlejˇs´ımu v´ıtˇezstv´ı. Pokud takov´y nenalezne, vyb´ır´a nejnadˇejnˇejˇs´ı z neprohr´avaj´ıc´ıch a nen´ı-li ani zˇ a´ dn´y takov´y, spokoj´ı se s tahem nejdelˇs´ı obrany. I David trp´ı syndromem druh´ym tahem mat“ a jak mile zjist´ı zˇ e prohru jiˇz nelze zastavit ani zpo” malit, vzd´a to. ˇ Podrobn´e sch´ema popisuj´ıc´ı funkci j´adra je v pˇr´ıloze A. Sipkami jsou v nˇem zn´azornˇeny vˇetve perspektivn´ı, pokraˇcuj´ıc´ı a obyˇcejn´ymi cˇ arami vˇetve neperspektivn´ı, koncov´e. Z´asadn´ı rozd´ıl oproti Goli´asˇovi spoˇc´ıv´a v tom, zˇ e z kaˇzd´eho uzlu v´ysˇe popsan´e vˇetve se pokraˇcuje pouze do jedin´eho dalˇs´ıho a zbytek je zavrˇzen. M´ısto geometrick´eho n´ar˚ustu kombinac´ı tak m´ame aritmetick´y.

7.3

ˇ ek David vs. Clovˇ

Davidovu obt´ızˇ nost lze nastavit limitem zkouman´ych tah˚u do hloubky u logik´ych vˇetv´ı. Slouˇz´ı k tomu tlaˇc´ıtko u´ roveˇn. (viz screen-shot ze hry v pˇr´ıloze B, pˇr´ıpadnˇe uˇzivatelsk´a pˇr´ıruˇcka pˇr´ıloha C) Doporuˇcen´a hodnota je kolem deseti tah˚u dopˇredu. M´enˇe znamen´a pozdn´ı odhalen´ı kritick´ych tah˚u a v´ıce zbyteˇcnou nepˇresnost simulace, vzhledem k jednoduchosti pouˇzit´eho postupu. Pokud vˇsak nastav´ıme u´ roveˇn pod dva tahy dopˇredu, David pˇrestane rozezn´avat i z´akladn´ı kritick´e situace a stane se nepouˇziteln´ym. Znalostn´ı vˇetve lze vyˇradit odstranˇen´ım souboru zkusenosti.dat“. Kaˇzdou v´yhrou cˇ lovˇeka, cˇ i ” stroje, pˇribude do tohoto souboru z´aznam v´yhern´ıch tah˚u a tomu se pak v dalˇs´ıch hr´ach snaˇz´ı u´ tokem pˇribl´ızˇ it a v obranˇe vyhnout. Pokud stroj poraz´ım nˇejakou d˚umyslnou past´ı, na v´ıce tah˚u dopˇredu neˇz rozpoznala jeho logick´a vˇetev, nejen zˇ e se j´ı v pˇr´ısˇt´ı hˇre vyhne d´ıky varov´an´ı znalostn´ı vˇetve, ale pˇri vhodn´e situaci ji pouˇzije zase proti mnˇe. Protoˇze poˇc´ıtaˇc se uˇc´ı rychleji neˇz cˇ lovˇek, je schopen proch´azet - pˇredv´ıdat mnohem v´ıce stav˚u, hra pˇredstavuje zaj´ımav´y souboj intelektu cˇ lovˇeka a stroje. Pro n´azorn´y pˇr´ıklad Davidovi schopnosti uˇcen´ı na obr´azc´ıch (7.2) aˇz (7.6) mu byla nejprve vymaz´ana pamˇet’ z´aznam˚u her a hloubka logick´ych vˇetv´ı nastavena na 10. David hraje se znaˇckou zelen´eho kˇr´ızˇ ku a cˇ lovˇek cˇ erven´eho koleˇcka. Kritick´e tahy jsou zn´azornˇeny zˇ lutou v´ypln´ı pole,

28

KAPITOLA 7. DAVID

v z´aznamech v´ıtˇezn´e posloupnosti pak tuˇcn´ym p´ısmem. Neodvratn´e tahy vedouc´ı do bezv´ychodn´e situace jsou naznaˇceny teˇckami barev odpov´ıdaj´ıc´ıch hr´acˇ u˚ m a cˇ erven´e cˇ a´ ry ukazuj´ı dvˇe otevˇren´e posloupnosti, kdy poˇc´ıtaˇc je schopen oboustrannˇe zablokovat jen jednu z nich. Davidova diskutovan´a reakce na kritick´y tah je zv´yraznˇena zˇ lut´ym r´amem.

Obr´azek 7.2: Zaznamen´an´ı por´azˇky

Obr´azek 7.3: Vliv z´aznamu na dalˇs´ı hru

Obr´azek (7.2) ukazuje v´yhern´ı posloupnost tah˚u cˇ lovˇeka nad Davidem. Pro vˇcasn´e rozpozn´an´ı kritick´eho tahu by musel myslet pln´ych pˇet tah˚u napˇred. Logick´a vˇetev m´a sice nastaven´ych 10, ale nebere v u´ vahu vˇsechny moˇznosti. Z´aznam v´ıtˇezn´e posloupnosti tah˚u: 35 858 210 119 10 21 5 22 17“ ” Na Obr´azku (7.3) je vidˇet odliˇsn´a reakce na stejnou situaci jako byla na (7.2). D´ıky z´aznamu pˇredeˇsl´e hry si David uvˇedomil (´uspˇesˇnˇe odsimuloval) hroz´ıc´ı nebezpeˇc´ı a vyhnul se mu. M´ısto u´ toku kter´y jiˇz jednou nestihl, byl opatrnˇejˇs´ı a zvolil obranu.

Obr´azek 7.4: Dalˇs´ı z´aznam por´azˇky

Obr´azek 7.5: Vliv obou z´aznam˚u na dalˇs´ı hru

29

KAPITOLA 7. DAVID

ˇ ek se ned´a tak snadno zahanbit a vymyslel nov´y zp˚usob na obr´azku (7.4) jak Davida porazit. Clovˇ Z´aznam druh´e v´ıtˇezn´e posloupnosti tah˚u: 35 858 210 119 7 22 7 70 2001“. ” David se opˇet adaptoval a znemoˇznil pouˇzit´ı obou pˇredeˇsl´ych postup˚u tahem na obr´azku (7.5). Aby ho cˇ lovˇek mohl znovu porazit, musel se v´ıce snaˇzit a myslet aˇz na sˇest tah˚u dopˇredu. (viz obr. 7.6) Z´aznam hry: 35 858 210 119 10 130 285 10 11 5“ ” Takto lze pokraˇcovat poˇra´ d“, cˇ lovˇek bude hledat st´ale sloˇzitˇejˇs´ı a rafinovanˇejˇs´ı zp˚usoby na ” poraˇzen´ı poˇc´ıtaˇce a ten se zase bude uˇcit jim br´anit, cˇ´ımˇz se budou vyv´ıjet oba. Kdopak to asi vydrˇz´ı d´ele.

Obr´azek 7.6: Dalˇs´ı z´aznam por´azˇky Nyn´ı vymaˇzeme posledn´ı z´aznam hry (7.6). Obr´azek (7.7) ukazuje zrcadlovou kombinaci hry (7.5), kde m´ısto v pravo dole pokraˇcovala hra obdobnˇe vpravo nahoˇre. Jin´ym smˇerem poˇca´ teˇcn´ıho v´yvoje hry doˇslo k odliˇsn´emu nastaven´ı vztaˇzn´eho kvadrantu a osy x, coˇz umoˇznilo pˇri simulaci stejn´eho z´aznamu doj´ıt k jin´ym (spr´avn´ym) souˇradnic´ım tah˚u. Posledn´ı obr´azek (7.8) ukazuje stejnou reakci i u posuvn´e modifikace hry. Na obou obr´azc´ıch (7.7) i (7.8) je prvn´ı David˚uv tah vlevo dole na souˇradnici (12,12).

Obr´azek 7.7: zrcadlov´a kombinace

Obr´azek 7.8: posuvn´a modifikace

30

KAPITOLA 7. DAVID

7.4

David vs. David

N´asleduj´ıc´ı hry zaˇc´ınaj´ı s pr´azdnou pamˇet´ı z´aznam˚u a hloubka logick´ych vˇetv´ı je nastavena na simulace dvou tah˚u dopˇredu.

Obr´azek 7.9

Obr´azek 7.10

Obr´azek 7.11

Obr´azek 7.12

Obr´azek 7.13

Obr´azek 7.14

Z nevelk´ych her je patrn´y nedostateˇcn´y obrann´y charakter logick´ych vˇetv´ı. Ty jsou velmi platn´e pˇri pl´anov´an´ı brilantn´ıho u´ toku, ale neposkytuj´ı mnoho moˇznost´ı pro u´ cˇ innˇejˇs´ı obranu. Znalostn´ı vˇetve sice na podruh´e zjist´ı hroz´ıc´ı nebezpeˇc´ı a algoritmus se mu u´ cˇ inˇe vyhne, ale protihr´acˇ rychle vymysl´ı nˇejak´e dalˇs´ı. S rostouc´ımi znalostmi roste d´elka i u´ roveˇn her, coˇz ukazuje na postupnou auto-kompenzaci hendikepu zp˚usoben´eho stvoˇritelem a (v teoretick´e cˇ a´ sti pˇredpovˇezen´e) minimalizaci vlivu logick´ych vˇetv´ı, posilov´an´ım znalostn´ıch.

Kapitola 8

Srovn´av´an´ı David vs. Goli´asˇ Davidova hlavn´ı v´yhoda, schopnost uˇcit se a pˇrizp˚usobovat byla demonstrov´ana v´ysˇe. N´asleduj´ıc´ı hry jsou zkouˇskou jeho logick´ych vˇetv´ı a z´aznamy her jsou vˇzdy vymaz´any. Na obr´azku (8.1) zaˇc´ınal Goli´asˇ a porazil davida na des´at´e u´ rovni. Pokud ale dostal v´yhodu prvn´ıho tahu David, obr´azek (8.2), staˇcilo mu to k v´ıtˇezstv´ı. Posledn´ı obr´azek (8.3) ukazuje souboj zaˇc´ınaj´ıc´ıho Goli´asˇe a Davida na 20 u´ rovni. Z rozsahu hry je vidˇet, zˇ e Davidovy chv´ıli trvalo vypoˇra´ dat se s Goli´asˇovou v´yhodou prvn´ıho tahu, ale na konec zv´ıtˇezil. Prohled´av´an´ı do sˇ´ıˇrky vs. do hloubky tedy 1 : 2.

Obr´azek 8.1: Goli´asˇ vs. David(10)

Obr´azek 8.2: David(10) vs. Goli´asˇ

31

´ AN ´ I´ DAVID VS. GOLIA´ Sˇ KAPITOLA 8. SROVNAV

Obr´azek 8.3: Goli´asˇ vs. David(20)

32

Kapitola 9

Z´avˇer Bez hrub´e s´ıly to nep˚ujde. Jestliˇze se z teoretick´eho u´ vodu mohlo zd´at, zˇ e hrub´a s´ıla je zastaral´y model a bude kompletnˇe nahrazena znalostmi, v praktick´e cˇ a´ sti se uk´azalo, zˇ e oba maj´ı sv´e chyby i pˇrednosti a nejefektivnˇejˇs´ı je zat´ım kombinace obou. Porazit Goli´asˇe cˇ lovˇeku sice zabere delˇs´ı dobu, ale pak s n´ım ztrat´ı smysl hr´at. U Davida je to snaˇzsˇ´ı, ale jeho u´ roveˇn znalostmi roste. Samov´yvoj David vs. David je pomal´y a zaˇc´ın´a na pˇr´ıliˇs n´ızk´e u´ rovni. Je l´epe ho nejprve natr´enovat na vˇs´ımavˇejˇs´ı UI, nebo lidech. Pak je schopen samov´yvoje bez patrn´ych omezen´ı j´ın´ych neˇz cˇ asov´ych.

9.1

Dalˇs´ı moˇzn´a vylepˇsen´ı

´ cinnost proˇrez´av´an´ı AlfaBety se d´a Goli´asˇe lze vylepˇsit pouˇzit´ım AlfaBeta proˇrez´av´an´ı stromu. Uˇ zv´ysˇit zaˇrazen´ım silnˇejˇs´ıho tahu na prvn´ı pr˚uchod algoritmu. Takov´y lze rychle vybrat logickou vˇetv´ı jako m´a David. Pokud by dostateˇcnˇe klesl poˇcet zvaˇzovan´ych stav˚u, mohl by se pouˇz´ıt hlubˇs´ı strom, mysl´ıc´ı v´ıce tah˚u dopˇredu, coˇz by zvedlo jeho inteligenci. Davidovou slabinou je logick´a obrana, kter´a je zase Goli´asˇovou pˇrednost´ı. Nejlepˇs´ı cesta dalˇs´ıho v´yvoje se tedy zd´a ve vhodn´e kombinaci obou tˇechto pˇr´ıstup˚u. Za u´ vahu by snad st´alo i pouˇzit´ı genetick´ych cˇ i evoluˇcn´ıch algoritm˚u.

9.2

Zhodnocen´ı pˇr´ınosu

Bakal´aˇrsk´a pr´ace pro mne byla rozhodnˇe pˇr´ınosem. Kromˇe programov´an´ı hry a UI jsem se nauˇcil z´aklad˚um pr´ace s LATEXem a mimo jin´e si i uvˇedomil dvˇe podstatn´e vˇeci: 1. HW podpora standardizovan´ych algoritm˚u UI znaˇcnˇe zv´ysˇ´ı jejich v´ykon. Poˇc´ıtaˇc bude moci proch´azet na sobˇe nez´avisl´e vˇetve stromu paralelnˇe a pˇritom se nezdrˇzovat ani u´ klidem pˇri n´avratu. Takto podporovan´a hrub´a s´ıla se stane ˇra´ dovˇe rychlejˇs´ı, jako tomu je u Deep Blue. Procesor bude m´ıt rovnˇezˇ v´ıce cˇ asu starat se o bˇeh prograu, GUI a jin´e potˇrebn´e, m´enˇ e specifick´e vˇeci. 2. I omyln´y cˇ lovˇek m˚uzˇ e stvoˇrit inteligenci schopnou samov´yvoje a potenci´alem pˇrevyˇsuj´ıc´ım ten jeho. Bude to nejsp´ısˇ jen dalˇs´ı a zˇrejmˇe nevyhnuteln´y krok ve v´yvoji. Ot´azkou je, jestli jsme pˇripraveni takovouto filozofii pˇr´ıjmout. Zat´ım byl inteligentnˇejˇs´ı a kreativnˇejˇs´ı cˇ lovˇek, pouˇz´ıval sˇikovnˇejˇs´ı, silnˇejˇs´ı a pˇresnˇejˇs´ı stroje, ale nebylo tomu tak – a asi ani nebude – vˇzdy.

33

Literatura [1] Refer´at z pˇredmˇetu umˇel´a inteligence na t´ema historie ai a vymezen´ı problematiky. http://zdenek.euweb.cz/other/ai.html, Kvˇeten 2005. ˇ F. Z´aklady umˇel´e inteligence. [2] ZBORIL https://www.fit.vutbr.cz/study/courses/IZU/private/, Kvˇeten 2005. [3] KALKUS J. Chess. http://wikipedia.infostar.cz/c/ch/chess_1.html, Kvˇeten 2005. ˇ [4] SVRSEK J. Umˇel´a inteligence. http://www.gymtc.cz/natura/2004/3/20040301.html, Kvˇeten 2005. [5] JAKOB M. Umˇel´a inteligence v poˇc´ıtaˇcov´ych hr´ach. http://www.scienceworld.cz/sw.nsf/ID/77BBB33A0476FAA9C1256EB5004DF919, Kvˇeten 2005. [6] RYBKA M. Umˇel´a inteligence v poˇc´ıtaˇcov´ych hr´ach. http://www.krokodyyl.wz.cz/inteligence.htm, Kvˇeten 2005. ˇ ek versus stroj. http://www.sever.cz/text.asp?clanek=605, [7] BURGER T. Clovˇ Kvˇeten 2005.

34

Pˇr´ıloha A: j´adro Davida

35

Pˇr´ıloha B: screen-shot hry

36

Pˇr´ıloha C: uˇzivatelsk´a pˇr´ıruˇcka Na pˇr´ıloze B screen-shotu ze hry je vidˇet pˇet hlavn´ıch ovl´adac´ıch prvk˚u: R´am s hern´ım polem - Po spuˇstˇen´ı programu je vidˇet pouze r´am a chyb´ı modr´y hern´ı rastr. Ten se objev´ı aˇz pˇri startu hry, po stisknut´ı tlaˇc´ıtka Nov´a hra“. V pˇr´ıpadˇe zˇ e je ve hˇre na tahu ” cˇ lovˇek, kurzor myˇsi je zobrazen v podobˇe jeho znaˇcky a hr´acˇ m˚uzˇ e lev´ym kliknut´ım myˇsi zapsat tah do libovoln´eho pr´azdn´eho pole v hern´ı oblasti, cˇ´ımˇz pˇred´a slovo“ druh´emu hr´acˇ i. ” Stavov´a tabulka UI ukazuje hodnoty: • • • • •

Stav – pokud je na tahu UI, zobrazuje kolik procent stavov´eho prostoru jiˇz prozkoumala Tah˚u do v´yhry – poˇcet tah˚u zb´yvaj´ıc´ıch do zjiˇstˇen´e v´yhry. U Davida je jen orientaˇcn´ı Tah˚u do prohry – poˇcet tah˚u zb´yvaj´ıc´ıch do zjiˇstˇen´e prohry. U Davida je jen orientaˇcn´ı Davidova u´ roveˇn znalostn´ı – poˇcet znalost´ı kter´ymi disponuje (soubor zkuˇsenosti.dat) Davidova u´ roveˇn logick´a – maxim´aln´ı hloubka logick´e vˇetve. Lze pˇrid´avat lev´ym a ub´ırat prav´ym tlaˇc´ıtkem myˇsi

Panel pro voliteln´a nastaven´ı parametr˚u hr´acˇ u˚ : • hr´acˇ 1,2 – slouˇz´ı k nastaven´ı prvn´ıho a druh´eho hr´acˇ e. (Goli´asˇ, David, cˇ lovˇek) • znak – kaˇzd´y hr´acˇ si m˚uzˇ e vybrat sv˚uj z´astupn´y symbol na hern´ı poli (kˇr´ızˇ ek, koleˇcko,. . . ) • v´yhra – touto volitelnou znaˇckou bude zobrazena v´yhra pˇr´ısluˇsn´eho hr´acˇ e Tlaˇc´ıtko nov´a hra“ - citliv´e na pohyb myˇsi, zm´acˇ knut´ım je zah´ajena hra ” Tlaˇc´ıtko konec“ - citliv´e na pohyb myˇsi, zm´acˇ knut´ım je program ukonˇcen. ”

INFORMACE: Kompilov´ano na OS: Podpora dalˇs´ıch OS: Akcelerace grafiky: Form´at zdroje grafiky: Multithreading:

Linux, FreeBSD, WindowsXP BeOs, MacOS, MacOS X, IRIX, Solaris DirectX nebo OpenGL (dle OS) jpg, png, gif GUI, UI

Ke kompilaci mimo DevC++, MVS.NET je tˇreba m´ıt nainstalov´ano SDL s SDL_Image, SDL_Mixer. D´ıky tomu zˇ e GUI bˇezˇ´ı ve vlastn´ım vl´aknu, nez´avisl´em na UI, lze program kdykoli ukonˇcit, bez nutnosti cˇ ekat na dokonˇcen´ı tahu UI. Tato v´yhoda pˇrin´asˇ´ı probl´em s nedoˇreˇsenou kritickou sekc´ı. Pokud bˇezˇ´ı UI a uˇzivatel zad´a novou hru se stejnou UI pr´avˇe na tahu, bˇezˇ´ıc´ı UI ze star´e hry se nemus´ı vˇcas ukonˇcit a m˚uzˇ e tak doj´ıt k neˇza´ douc´ı schizofrenick´e“ situaci, kdy obˇe UI sd´ılej´ı“ ” ” stejnou pamˇet’. 37