6.6. A jelenleg legfejlettebb játékprogramok
Azt lehetne mondani, hogy a játékok valami olyat jelentenek az MI számára, mint amit a Forma–1 versenyek a gépkocsiipar számára. A legfejlettebb játékprogramok villámgyors, hihetetlenül finoman hangolt rendszerek, amelyek nagyon fejlett módszereket alkalmaznak, de amelyeknek nem sok hasznát vesszük a vásárláskor. Bár vannak kutatók, akik azt gondolják, hogy a játékok az MI fővonalát tekintve többé-kevésbé irrelevánsak, mégis élénk érdeklődést váltanak ki, és folyamatosan fenntartják az innovációt, amit a szélesebb közösség fel is karol.
Herbert Simon 1957-ben megjósolta, hogy 10 éven belül a számítógépek legyőzik az emberi világbajnokot. Negyven év múltával hatjátszmás kirakatmérkőzésen a Deep Blue legyőzte Garri Kaszparovot. Simon tévedett, de csak egy 4-es szorzóval. Kaszparov azt írta:
|
A mérkőzés döntő játszmája a 2. játszma volt, amely emlékeimben sebként maradt meg … láttunk valamit, ami a legvadabb elképzeléseinket is felülmúlta, hogy egy számítógép hogyan lesz képes döntéseinek hosszú távú pozíciós konzekvenciáit előre látni. A gép – emberi veszélyérzetet produkálva – megtagadta, hogy egy döntően rövid távú előnyt jelentő állásba kerüljön. |
||
| --(Kaszparov, 1997) | ||
A Deep Blue-t Murray Campbell, Feng-Hsiung Hsu és Joseph Hoane fejlesztették ki az IBM-nél (Campbell és társai, 2002), a Campbell és Hsu által korábban a Carnegie Mellon Egyetemen kifejlesztett Deep Thought tervére alapozva. A győzedelmes gép egy párhuzamos számítógép volt 30 IBM RS/6000 processzorral, amelyek a „szoftverkeresést” futtatták, és 480 VLSI sakk-célprocesszorral, amelyek a lépésgenerálást (beleértve a lépések sorba rendezését), a fa utolsó néhány szintjén a „hardverkeresést” és a levélcsomópontok kiértékelését valósították meg. A Deep Blue átlagosan másodpercenként 126 millió, csúcssebességnél 330 millió csomópontot vizsgált meg. Lépésenként 30 milliárd állást generált, rutinszerűen 14-es mélységet elérve. A gép szíve a standard alfa-béta keresés volt, transzpozíciós táblával, a siker kulcsa azonban úgy tűnik, az a képessége, hogy kiterjesztéseket tudott generálni az érdekes kényszerlépés-sorozatok mélységi korlátjain túl. Egyes esetekben a keresés a 40-es mélységet is elérte. A kiértékelő függvény 8000 tulajdonsággal dolgozott, ezekből egyesek a bábuk igen specifikus konfigurációit is leírták. A rendszer felhasználta a 4000 állást tartalmazó „megnyitások könyvét” és a 700 000 nagymesteri játszmaleírást tartalmazó adatbázist, ahonnan konszenzusos javaslatokat lehetett generálni. A rendszer a megoldott végjáték-pozíciók nagy adatbázisával is rendelkezett, amely minden ötbábus és számos hatfigurás állást tartalmazott. Ez az adatbázis a keresési mélység lényeges kiterjesztését jelentette, lehetővé téve Deep Blue számára egyes esetekben a tökéletes játékot annak ellenére, hogy sok lépésre volt még a matthelyzettől.
A Deep Blue sikere megerősítette azt a széles körű hiedelmet, hogy számítógépes játékokban az előrehaladás főleg az egyre hatékonyabb hardver eredménye – ezt a véleményt az IBM is bátorította. Másfelől a Deep Blue megalkotói azt nyilatkozták, hogy a keresés kiterjesztése és a kiértékelő függvény szintén kritikusak voltak (Campbell és társai, 2002). Azonban tudjuk azt is, hogy néhány közelmúltbeli algoritmikus javítás lehetővé tette, hogy standard PC-n futó programok 1992 óta minden Számítógépes Sakkvilágbajnokságot megnyerjenek, sokszor 1000-szer több csomópont keresésére is képes masszívan parallel ellenségeket is legyőzve. A nyesési heurisztikák egész választékának használatával az effektív elágazási tényezőt kevesebb mint 3-ra lehet csökkenteni (a tényleges 35-ös elágazási tényezőhöz viszonyítva). Ezek közül legfontosabb a nulla lépés (null move) heurisztika, amely sekély keresést alkalmazva – ahol az ellenség az indulásnál kétszer is léphet – az állás értékének jó alsó becslését adja. Ez az alsó korlát sokszor lehetővé teszi az alfa-béta nyesést a teljes mélységű keresés költsége nélkül. Fontos még a hatástalanság nyesése (futility prunnig), amely segíti eldönteni, hogy mely lépések vezetnek béta nyeséshez a követő csomópontok szintjén.
A Deep Blue csapata a Kaszparovval való visszavágó alól kibújt. Helyette 2002-ben a fő mérkőzés a FRITZ program és Vlagyimir Kramnyik világbajnok összecsapása volt, amely nyolc játszmában döntetlennel végződött. A mérkőzés feltételei az emberi játékosnak sokkal jobban kedveztek, és a hardver egy közönséges PC volt, nem egy szuperszámítógép. Kramnyik véleménye szerint mégis „most már világos, hogy a csúcsprogramok és a világbajnok közel azonos szinten vannak”.
Az IBM-nél dolgozó Arthur Samuel szabad idejében 1952-től kezdve kifejlesztett egy dámaprogramot, mely a kiértékelő függvényét több ezerszer saját maga ellen játszva maga tanulta meg. Ezt az ötletet a 21. fejezetben tárgyaljuk részletesebben. Samuel programja egy kezdő játékos szintjén kezdett játszani, de miután néhány napig önmagával játszott, már Samuel játékszintjét is felülmúlta (bár Samuel nem számított erős játékosnak). 1962-ben a program Robert Nealyt – a „vak dámajáték” bajnokát is megverte, egy hibás lépése miatt. Sokan azt hitték, hogy ezzel bizonyítást nyert, hogy dámajátékban a gép erősebb, mint az ember, azonban ez így nem igaz. Ha viszont figyelembe vesszük, hogy Samuel számítógépe (egy IBM 704-es) 10 000 szavas memóriával, háttértárként mágnesszalagos egységgel és majdnem egy milliszekundumos ciklusidővel rendelkezett, ez a győzelem az MI nagy eredményeinek egyike marad.
Kevesen próbálták meg túlszárnyalni ezt a teljesítményt, amíg Jonathan Schaeffer és kollégái ki nem fejlesztették a Chinookot, amely közönséges PC-n futott és alfa béta keresést alkalmazott. A Chinook egy olyan előre létrehozott adatbázissal dolgozott, amely az összes nyolc vagy kevesebb bábut tartalmazó 444 milliárd állásból épült fel, hogy a végjátéka hibátlan legyen. 1990-ben az U.S. Openen a Chinook másodikként futott be és megnyerte a jogot, hogy a világbajnoki címért mérkőzzön. Ekkor a program Marion Tinsley képében egy problémába ütközött. Dr. Tinsley már 40 éve világbajnok volt és ez alatt a 40 év alatt összesen csak három játszmát vesztett. A Chinookkal vívott első mérkőzésén elszenvedte a negyedik, majd az ötödik vereségét is, de a bajnokságot 20,5:18,5 pontra megnyerte. 1994 augusztusában a Tinsley és a Chinook közötti világbajnoki mérkőzés idő előtt félbeszakadt, amikor Tinsleynek egészségügyi problémák miatt vissza kellett vonulnia. A Chinook lett a hivatalos világbajnok.
Schaeffer úgy gondolja, hogy megfelelő számítási teljesítménnyel a végjátékok adatbázisát annyira ki lehetne bővíteni, hogy a kezdeti pozíciótól induló előre keresés valamelyik már megoldott pozíciót mindig el tudná érni, vagyis a dámajáték teljesen megoldható lenne (volt, hogy a Chinook már az 5-ik lépésnél győzött). Az ilyen kimerítő elemzést kézi módszerekkel a 3 × 3-as amőbára meg lehet tenni és számítógépen a 4 × 4 × 4-es amőbára (Qubic), a Go-Mokura (öt egy sorban) és a Nine-Men’s Morrisra is elvégezték (Gasser, 1998). Ken Thompson és Lewis Stiller figyelemre méltó munkája (Thompson és Stiller, 1992) az összes öt- és hatfigurás sakkvégjátszmát is megoldotta, az eredményeket az interneten hozzáférhetővé téve. Stiller egy olyan kényszermatt esetét is felfedezte, amely 262 lépést igényelt. Ez egy kis felfordulást okozott, mert a sakk szabályai megkövetelik, hogy 50 lépés alatt valamilyen „előrehaladásnak” kell történnie.
Az Othello vagy más néven Reversi számítógépes játékként talán népszerűbb, mint táblajátékként. Keresési tere kisebb, mint a sakké, általában 5-15 megengedett lépés van, de a kiértékelő szaktudást a semmiből indulva kellett kifejleszteni. 1997-ben a Logistello program (Buro, 2002) az emberi világbajnokot, Takeshi Murakamit, képes volt hat nullára megverni. Általánosságban elfogadott, hogy az Othellóban az emberek nem ellenfelei a számítógépeknek.
A 6.5. alfejezetben elmagyaráztuk, hogy a kockadobásból eredő bizonytalanság a mély keresést drága luxussá teszi. Az ostáblára vonatkozó kutatások zöme a kiértékelő függvény javítására összpontosult. Gerry Tesauro (Tesauro, 1992) neurális hálós technikákkal (lásd 20. fejezet) ötvözte Samuel megerősítéses tanulási módszerét, hogy egy figyelemre méltó kiértékelő függvényt hozzon létre, amit 2-es, illetve 3-as mélységű kereséssel együtt használt. A saját magával játszott több mint egy millió tanító játszma után Tesauro programja, a TD-GAMMON a világranglistán stabilan az első három játékos között foglal helyet. A program eredményei alapján a játék nyitó lépéseit tekintve egyes esetekben az eddigi gyakorlat radikálisan megváltozott.
Ázsiában a gó a legnépszerűbb táblajáték, ami a mesterektől legalább olyan felkészültséget igényel, mint a sakk. A 19 × 19-es tábla miatt az elágazási tényező 361-gyel indul, így a hagyományos keresési algoritmusok teljesen használhatatlanok. Egészen 1997-ig kompetens programoknak híre-hamva sem volt, most azonban már programok is képesek elfogadható lépéseket tenni. A legjobb programok többsége alakzatfelismerési technikákat (amikor adott alakzat előfordul, akkor bizonyos lépés megtételét kell megfontolni) korlátos kereséssel (annak eldöntésére, hogy bizonyos köveket el lehet-e fogni, egy lokális területen maradva) kombinál. A könyv írásának idején a legerősebb programok valószínűleg Chen Zhixing Goemate és Michael Reiss Go4++ programja voltak, mindegyiket kb. 10 kyu-ra (gyenge amatőrszint) értékelték. A gó olyan területnek tűnik, ami a kifinomult következtetési módszereket alkalmazó intenzív kutatásokból valószínűleg nyerhet. Sikert hozhat például az, hogy megtaláljuk annak a módját, hogy sok, lazán csatolt „részjátszmára” (amire a gó dekomponálható) vonatkozó lokális következtetés néhány szálát hogyan kellene integrálni. Az ilyen technikák az intelligens rendszerek szempontjából hihetetlen értéket képviselnek.
A bridzs egy nem tökéletes információjú játék – az egyik játékos kártyái a többi játékos elől el vannak rejtve. A bridzs többszemélyes játék is egyben, négy játékossal kettő helyett, bár a játékosok két csapatot alkotnak, párban. Ahogyan ezt a 6.5. alfejezetben láttuk, egy bridzsparti optimális lejátszása az információgyűjtés, a kommunikáció, a blöffölés és a valószínűségek gondos mérlegelésének az elemeit is tartalmazhatja. E technikákból számos elemet használ a Bridge BaronΤΜ program (Smith és társai, 1998), amely megnyerte az 1997-es Számítógépes Bridzsbajnokságot. Bár nem játszik optimálisan, a Bridge Baron azon ritka sikeres, játékot játszó programok egyike, amelyek hierarchikus tervkészítési technikákat alkalmaznak (lásd 12. fejezet), olyan magas szintű, bridzsjátékosok számára ismerős ötleteket felhasználva, mint az impasszolás (finessing) és a dobáskényszer (squeezing).
A GIB program (Ginsberg, 1999) meggyőző fölénnyel nyerte meg a 2000. évi bajnokságot. A GIB a „jövőbe látás szerinti átlagolás” módszerét használja, két lényegi módosítással. Először, ahelyett hogy megvizsgálná, hogy egy adott választás mennyire bizonyul jónak a rejtett kártyák minden lehetséges kombinációja mellett (amiből 10 millió is lehet), a program egy véletlenszerűen választott 100 kombinációból álló mintát vizsgál. Másodszor, a GIB magyarázatalapú általánosítást (explanation-based generalization) használ arra, hogy különféle standard helyzetekre az optimális játékvezetés általános szabályait kiszámítsa és eltárolja. Ez lehetővé teszi minden leosztás egzakt megoldását. A GIB taktikai pontossága ellensúlyozza azt, hogy az információra következtetni nem tud. Az 1998-as emberi világbajnokságon az egyenlő rangú mérkőzésen (egy leosztás lejátszásában) 35-ből 12-ikként végzett, az emberi szakértők elvárásait messze túlszárnyalva.
