A mechanikus játékok korai történetére számos csalás rányomta a bélyegét. Ezek közül a legnevezetesebb Kempelen Farkas báró 1769-ben kiállított „Törökje”, egy feltételezett sakkautomata, amely Napóleont is megverte, mielőtt kiderült, hogy a szekrénye valójában egy törpe növésű emberi sakkmestert rejtett (Levitt, 2000). A Török 1769-től 1854-ig játszott. Úgy tűnik, Charles Babbage (aki a Török hatása alatt állt) volt az első, aki 1846-ban számítógépes sakk és dámajáték megvalósíthatóságának első komoly elemzését adta (Morrison és Morrison, 1961). Tervezett egy 3 × 3-as amőbát játszó célgépet is, amit soha sem épített meg. Az első igazi játékgépet 1890 táján egy spanyol mérnök, Leonardo Torres y Quevedo tervezte és építette meg. A „KRK” a sakkvégjátékra specializált gép volt (király és bástya a király ellen) és képes volt bármilyen kiinduló állásból mattot adni.

A minimax algoritmust sokszor Ernst Zermelo, a modern halmazelmélet atyja 1912-es cikkéhez vezetik vissza. A cikk sajnálatos módon tartalmaz hibákat, és a minimaxot nem írja le helyesen. A játékelmélet komoly alapjait a nagy hatású Theory of Games and Economic Behavior c. munkában Neumann és Morgenstern (Neumann és Morgenstern, 1944) fektették le, kimutatva azt is, hogy egyes játékokban szükség van randomizált (avagy nem megjósolható) stratégiákra. (További információért lásd 17. fejezet.)

A korai számítógépes korszak számos prominens személyét kíváncsivá tette a számítógépes sakk lehetősége. Konrad Zuse – aki elsőként tervezett programozható számítógépet – igen részletes ötleteket dolgozott ki arra, hogy ezt hogyan lehetne megvalósítani (Zuse, 1945). Norbert Wiener nagy befolyású Cybernetics c. könyve (Wiener, 1948) tartalmazta egy számítógépes sakkprogram működésének egy lehetséges vázlatát, a minimax keresést, a mélységi levágást és a kiértékelő függvényt is beleértve. Claude Shannon a modern számítógépes játékok elvi alapjait sokkal részletesebben fejtette ki, mint Wiener (Shannon, 1950). Shannon bevezette az egyensúlyi állás fogalmát, és néhány ötletet vázolt fel a szelektív (nem kimerítő) játékfakeresésre vonatkozólag. Slater és az ugyanabban a kötetben a cikkére reflektáló szerzők szintén megvizsgálták a számítógépes sakkozás lehetőségeit (Slater, 1950). I. J. Good Shannontól függetlenül kidolgozta az egyensúlyi állás fogalmát (Good, 1950).

1951-ben Alan Turing írta meg az első valódi számítógépes programot, ami képes volt egy teljes sakkjátszmát lejátszani (Turing és társai, 1953). Valójában azonban Turing programja sohasem futott számítógépen, kézi szimulációval tesztelték egy nagyon gyenge emberi sakkjátékos ellen, aki legyőzte a programot. Időközben D. G. Prinz megírt és valóban futtatott is egy programot (Prinz, 1952), ami sakkfeladványokat oldott meg, bár nem játszott teljes játszmát. Alex Bernstein írta az első olyan sakkprogramot, amely egy teljes standard sakkjátszmát játszott (Bernstein és Roberts, 1958; Bernstein és társai, 1958).^[58]

Az alfa-béta keresés alapötletét John McCarthy dolgozta ki 1956-ban, habár nem publikálta. Az NSS-sakkprogram az alfa-béta algoritmus egy leegyszerűsített változatát használta, ez volt az első sakkprogram, ami ezt alkalmazta (Newell és társai, 1958). Nilsson szerint Arthur Samuel dámaprogramja (Samuel, 1959; 1967) szintén alfa-béta algoritmust használt, habár maga Samuel ezt nem említi a rendszerről publikált beszámolóiban (Nilsson, 1971). Az 1960-as évek elején jelentek meg az alfa-béta algoritmust ismertető cikkek (Hart és Edwards, 1961; Brudno, 1963; Slagle, 1963b). Az alfa-béta algoritmus egy teljes implementációját Slagle írta le egy cikkben (Slagle és Dixon, 1969), ami a kalah^[59] játékot játszó játékprogram működését ismertette. A John McCarthy egyik diákja által írt „Kotok–McCarthy” sakkprogram (Kotok, 1962) is az alfa-béta algoritmust használta. Knuth ismerteti az alfa-béta algoritmus történetét (Knuth és Moore, 1975), megadja az algoritmus teljességének a bizonyítását és elvégzi az időigény elemzését. Knuth és Moore elemzése az alfa-béta keresésnek a követők véletlen sorba rendezésével O((b/logb)^d) aszimptotikus komplexitást mutatott ki, ami lehangoló eredmény, mert a b/logb effektív elágazási tényező magánál a b-nél nem sokkal jobb. Később jöttek rá, hogy az aszimptotikus képlet csak a b > 1000 igaz, és az aktuális játékokra található elágazási tényezőkre a gyakran idézett O(b^3d/4) érvényes. Pearl megmutatta (Pearl, 1982b), hogy az alfa-béta algoritmus aszimptotikusan optimális az összes rögzített mélységű játékfa-keresési algoritmus között.

Az első két sakkprogram, ami egymás ellen játszott, a Kotok–McCarthy-program és a Moszkvai Elméleti és Kísérleti Fizika Intézet által megírt „ITEP” program (Adelson-Velsky és társai, 1970) volt az 1960-as évek közepén. Ezt az interkontinentális mérkőzést távírón játszották le. A küzdelem 1967-ben az ITEP-program 3:1 arányú győzelmével ért véget. A MacHack 6 volt az első olyan sakkprogram, ami sikeresen játszott emberek ellen (Greenblatt és társai, 1967). 1400-as Élő-pontszáma jóval több volt, mint a kezdők 1000-es Élő-pontja, azonban így is igen messze volt a 2800 vagy több Élő-ponttól, ami szükséges lett volna, hogy Herb Simon 1957-es jóslata teljesüljön, miszerint 10 éven belül a számítógépes sakkprogramok lesznek a sakkvilágbajnokok (Simon és Newell, 1958).

Az 1970-es első ACM Észak-Amerikai Számítógépes Sakkbajnoksággal a sakkprogramok versengése komollyá vált. A korai 1970-es évek programjai igen bonyolultak voltak, számos trükköt vetettek be, hogy a keresés bizonyos ágait levágják, elfogadható lépéseket generáljanak stb. Az első Számítógépes Sakkvilágbajnokságot 1974-ben Stockholmban rendezték. Ezt az első világbajnokságot a Kaissa (Adelson-Velsky és társai, 1975), egy másik ITEP-program nyerte meg. Kaissa egy egyszerűbb megközelítésen alapult és kimerítő alfa-béta keresést használt egyensúlyi kereséssel vegyítve. A megközelítés felsőbbrendűségét igazolta a CHESS 4.6 győzelme az 1977-es Számítógépes Sakkvilágbajnokságon. A CHESS 4.6 lépésenként 400 000 állást elemzett és 1900 Élő-pontot ért el.

Greenblatt MacHack 6-osának egy későbbi változata volt az első olyan sakkprogram, amely már kifejezetten a sakkra tervezett célhardveren futott (Moussouris és társai, 1979), de a Belle (Condon és Thompson, 1982) volt az első olyan program, ami a célhardvernek köszönhetően jelentős sikereket ért el. A Belle lépésgeneráló és állásértékelő hardvere lehetővé tette, hogy lépésenként néhány millió állást is elemezzen. A Belle 2250 Élő-pontot ért el, és az első mesteri fokozat szintű program lett. A HITECH rendszer egy speciális rendeltetésű számítógép volt, amit Hans Berliner, a korábbi levelező sakkvilágbajnok és egy CMU-beli diákja, Carl Ebeling tervezett, hogy a kiértékelő függvények gyors számítását tegyék lehetővé (Ebeling, 1987; Berliner és Ebeling, 1989). A HITECH észak-amerikai sakkbajnok lett 1985-ben, és 1987-ben az első olyan program volt, amely egy emberi nagymestert is legyőzött. A CMU-n szintén kifejlesztett Deep Thought (Hsu és társai, 1990) a tiszta keresés sebességét tovább fokozta. 2551 Élő-pontot ért el és a Deep Blue előfutára lett. Az 1980-ban alapított Fredkin-díj 5000 dollárt ajánlott fel annak a sakkprogramnak, amelyik elsőként éri el a mesterfokozatot, és 10 000 dollárt ajánlott fel annak a sakkprogramnak, amely elsőként éri el a USCF (Amerikai Egyesült Államok Sakkszövetsége) 2500-as Élő-pontot (ez a nagymesteri szinthez közeli érték), és 100 000 dollárt ajánlott fel azon sakkprogramnak, amelyik elsőként legyőz egy emberi sakkvilágbajnokot. Az 5000 dolláros díjat 1993-ban a Belle, a 10 000 dolláros díjat 1989-ban a Deep Thought, majd a 100 000 dolláros díjat 1997-ben a Deep Blue nyerte el a Kaszparov felett aratott győzelemért. Fontos emlékezni, hogy a Deep Blue sikerét mind az algoritmikus javítások, mind a hardver biztosította (Hsu, 1999; Campbell és társai, 2002). Az olyan technikák, mint a nulla lépés heurisztika (Beal, 1990) a keresésben igen szelektív programokhoz vezettek. Az utolsó három Számítógépes Sakkvilágbajnokságot 1992-ben, 1995-ben és 1999-ben a standard PC-n futó programok nyerték meg. Egy korszerű sakkprogramnak talán a legrészletesebb leírását Ernst Heinz adja meg (Heinz, 2000), amelynek DARKTHOUGHT programja volt a legmagasabb pontszámú nem kereskedelmi program az 1999-es világbajnokságon.

Kísérletek történtek arra, hogy a „standard megközelítés” 6.7. alfejezetben leírt problémáit leküzdjék. Az első szelektív kereső algoritmus, elméleti igénnyel, valószínűleg a B^* algoritmus (Berliner, 1979) volt, ami megkísérli, hogy a játékfa csomópontjainak az értékeire egyetlen becsült érték helyett intervallumkorlátokat adjon. A levélcsomópontok kifejtése annak érdekében történik, hogy a legfelső szintű korlátokat finomítsuk, amíg egy „nyilván legjobb” lépést nem találunk. Palay az alfa-béta algoritmus becsült értékei, illetve a B^* algoritmus intervallumai helyett valószínűség-eloszlásokat használ (Palay, 1985). David McAllester konspirációs szám keresési algoritmusa azokat a levélcsomópontokat fejti ki, amelyek, ha megváltoznának az értékeik, előidéznék, hogy az algoritmus a gyökérnél új lépést válasszon (David McAllester, 1988). Az MGSS^* (Russell és Wefald, 1989) a 16. fejezet fejlett döntéselméleti technikáit használja minden levélcsomópont kifejtésének értékbecslésére a gyökérszintű döntés minőségében tapasztalt várható javulás függvényében. Ez a program az Othellóban képes volt jobb eredményeket elérni, mint az alfa-béta algoritmus, annak ellenére, hogy egy nagyságrenddel kevesebb csomópontot vizsgált meg. Az MGSS^* megközelítés elvben alkalmas a következtetés bármilyen formájának vezérlésére.

Az alfa-béta keresés több szempontból a mélységi áglenyeső megfelelője két játékos esetén, amit az egyedi ágens esetében az A^* dominál. Az SSS^* algoritmus (Stockman, 1979) egy kétszemélyes A^*-nak tekinthető, és azonos döntés eléréséhez soha nem fejt ki több csomópontot, mint az alfa-béta algoritmus. Eredeti formájában az SSS^* memóriaigénye és a sorba állítás számítási overheadje miatt nem praktikus, azonban az RLEK algoritmusból kifejlesztettek egy lineáris tárkomplexitású változatot (Korf és Chickering, 1996). Plat az SSS^*-ja egy új megközelítést dolgozott ki (Plat és társai, 1996) az alfa-béta keresés és a transzpozíciós táblák együtteseként, és megmutatta, hogy az eredeti algoritmus problémáit hogyan kell elkerülni, végül MTD(f) néven egy új változatot fejlesztett ki, amit sok kiemelkedő teljesítményű programba építettek be.

D. F. Beal és Dana Nau a minimax közelítő kiértékelésekre történő alkalmazásoknál jelentkező gyengeségeit tanulmányozták (Beal, 1980; Dana Nau, 1980; 1983). Kimutatták, hogy a levélértékeknek a fában való eloszlására bizonyos függetlenségi feltételezésekkel élve, a minimax algoritmus kevésbé megbízható becsléseket ad a gyökérre, mintha a kiértékelő függvényeket közvetlenül, mindenféle keresés nélkül alkalmaznánk. Pearl Heuristics c. könyve (Pearl, 1984) ezt a látszólagos paradoxont részben megmagyarázza és számos játékalgoritmust elemez. Baum és Smith (Baum és Smith, 1997) a minimax egy valószínűség-alapú helyettesítését javasolja, és azt mutatja ki, hogy ez bizonyos játékokban jobb döntésekhez vezet. A keresés különféle szinteken való levágásából és a kiértékelő függvény alkalmazásából adódó hatások elmélete még mindig szegényes.

A várhatóminimax algoritmust Donald Michie vetette fel (Michie, 1966), habár az közvetlenül következik Neumann és Morgenstern játékfa-kiértékelési elméletéből. Bruce Ballard az alfa-béta nyesést kiterjesztette a véletlen csomópontokat is tartalmazó fákra (Bruce Ballard, 1983). Az első sikeres ostáblaprogram a BKG volt (Berliner, 1977; 1980b). Csak 1 mélységig keresett és bonyolult, manuálisan összeállított kiértékelő függvényt használt. Ez volt az első számítógépes program, ami képes volt legyőzni egy emberi világbajnokot az ismert klasszikus táblajátékok egyikében (Berliner, 1980a), habár Berliner elsőként ismerte el, hogy ez csak egy rövid, bemutató mérkőzés volt (nem egy világbajnoki mérkőzés), és hogy a BKG nagyon szerencsés „kézzel” dobott a kockával. Gerry Tesauro kutatásai, először a NEUROGAMMON (Tesauro, 1989), majd a TD-GAMMON (Tesauro, 1995) programokkal, azt mutatták, hogy sokkal jobb eredmény érhető el a megerősítéses tanulással (amely területtel a 21. fejezetben foglalkozunk).

A dáma, és nem a sakk volt az első olyan klasszikus játék, amire egy valóban számítógépen futó program képes volt végigjátszani egy teljes játszmát. Christopher Strachey írta az első működőképes dámajátékprogramot (Strachey, 1952). Schaeffer (Schaeffer, 1997) nagyon olvasmányosan leírja a Chinook – a világbajnok dámajátékprogram – fejlesztéstörténetét az összes műhelytitkával együtt.

Az első góprogramokat valamivel a dáma- és a sakkprogramok után fejlesztették ki (Lefkovitz, 1960, Remus, 1962), és lassabban fejlődtek a dáma- és a sakkprogramoknál. Ryder tiszta keresésalapú megközelítést használt (Ryder, 1971) a szelektív nyesési módszerek egész palettájával, hogy le tudja győzni a hatalmas elágazási tényezőből adódó problémát. Zobrist feltétel-cselekvés szabályokat használt elfogadható lépések generálására, ha a játékban ismert alakzatok jelentek meg (Zobrist, 1970). Reitman és Wilcox jó eredménnyel kombinálta a szabályokat és a keresést (Reitman és Wilcox, 1979), a legtöbb modern program követte ezt a hibrid megközelítést. A számítógépes gó jelenlegi állását Müller (Müller, 2002) foglalja össze, és tömérdek hivatkozást is közöl. Anshelevich (Anshelevich, 2000) hasonló módszereket a HEX játékra alkalmaz. A friss fejleményekről a Számítógépes Go Szövetség által kiadott Computer Go Newsletter számol be.

A számítógépes játékokról több fórumon jelennek meg cikkek. A felettébb félrevezető nevű konferenciakiadvány, a Heuristic Programming in Artificial Intelligence számol be a Számítógépes Sakkolimpiákról, amely rendezvények a játékok egész sorára terjednek ki. A játékprogramok kutatásáról fontos cikkeket publikáltak számos szerkesztett cikkgyűjteményben (Levy, 1988a; Levy, 1988a; Marsland és Schaeffer, 1990). Az 1977-ben alapított Nemzetközi Számítógépes Sakkszövetség (International Computer Chess Association, ICCA) negyedévenként adja ki az ICGA Journalt (korábban ICCA Journal). (Clarke, 1977) óta fontos cikkek jelentek meg az Advances in Computer Chess antológiasorozatban. Az Artificial Intelligence folyóirat 134. kötete (Artificial Intelligence, 2002) leírásokat tartalmaz a legfejlettebb sakk, Othello, Hex, shogi, gó, ostábla, póker, Scrabble™ és más játékprogramokról.

6.1.

Ez a feladat a játékok alapvető elveit a 3 × 3-as amőbán (körök és ikszek) keresztül gyakoroltatja be. X_n azon sorok, oszlopok vagy átlók számát jelöli, ahol pontosan n db X, míg egyetlen O sem található. Hasonlóan, O_n azon sorok, oszlopok vagy átlók számát jelöli, ahol pontosan n db O, míg egyetlen X sem található. A hasznosságfüggvény +1-et rendel minden olyan álláshoz, ahol X₃ = 1, és –1-et rendel minden olyan álláshoz, ahol O₃ = 1. Az összes többi végállás hasznossága 0. A nem végállapotok esetén az alábbi módon definiált lineáris kiértékelő függvényt fogjuk használni:

Kiértékel(s) = 3X2(s) + X1(s) – (3O2(s) + O1(s))

6.2.

Bizonyítsa be az alábbi állítást: minden játékfa esetén a MAX által kapott hasznosság, amikor MAX a minimax döntést használva játszik egy szuboptimális MIN-nel szemben, sohasem lesz alacsonyabb, mint az a hasznosság, ami akkor ér el, ha egy optimális MIN-nel szemben játszana. Ki tud találni egy olyan játékfát, ahol MAX egy szuboptimális stratégiával egy szuboptimális MIN-nel szemben még jobban teljesítene?

6.3.

Tekintse a 6.14. ábrán látott kétszemélyes játékot.

6.14. ábra - Egy egyszerű játék kiinduló állása. Az A játékos indul elsőnek. Mindkét játékos felváltva lép és a zsetonját a szomszédos szabad helyre helyezheti, mindkét irányban. Ha a szomszédos mező foglalt, akkor a játékos az ellenfél felett átugorhat a következő szabad helyre, ha van ilyen. (Például ha A a 3-n és B a 2-n van, akkor A visszaléphet 1-re.) A játéknak vége, ha az egyik játékos eléri a tábla ellentétes végét. Ha az A játékos elsőnek éri el a 4-et, a játék értéke +1, ha B játékos éri el elsőnek az 1-et, a játék értéke az A számára –1.

6.4.

6.5.

Állítsa elő az alfa-béta nyesés helyességének formális bizonyítását. Ehhez tekintse a 6.15. ábrán bemutatott helyzetet. A kérdés az, hogy az algoritmus lenyesse-e az n_j csomópontot, ami egy max-csomópont és az n₁ leszármazottja. Az alapötlet, hogy akkor és csak akkor nyessük le, ha n₁ minimax értéke igazolhatóan független n_j értékétől.

n1 = min(n2, n21, …, n2b2)

Adjon egy hasonló kifejezést n₂-re, és n₁-re, n_j-t felhasználva.

6.15. ábra - Az a helyzet, amikor az algoritmus eldönti, hogy lenyesheti-e az n_j csomópontot

6.6.

6.7.

Bizonyítsa be, hogy a levélcsomóponti értékek pozitív lineáris transzformációja (azaz egy transzformáció x-től ax + b-ig, ahol a > 0), nincs befolyással a lépések választékára a játékfában, akkor sem, ha léteznek benne véletlen csomópontok.

6.8.

Tekintse az alábbi eljárást a lépések megválasztására a véletlen csomópontot is tartalmazó játékokban:

Helyesen fog működni ez az eljárás? Miért (nem)?

6.9.

Írjon és implementáljon egy valós idejű, többszemélyes játszókörnyezetet, ahol az idő a környezeti állapot része, és a játékosok rögzített időszeleteket kapnak.

6.10.

Adja meg és/vagy implementálja az alábbi játékok egyikére vagy akár többre is az állapotleírást, lépésgenerálást és a kiértékelő függvényt: Monopoly, Játék a betűkkel, bridzs (egy konkrét licitet feltételezve) és póker (válassza meg a kedvenc változatát).

6.11.

Gondosan tekintse át a 6.10. feladat minden egyes játékában a véletlen események és a részleges információk összefüggéseit.

6.12.

A minimax algoritmus feltételezi, hogy a játékosak felváltva lépnek, az olyan kártyajátékokban azonban, mint a whist vagy a bridzs, mindig a leütés győztese indul a következőnek.

6.13.

A Chinook dámaprogram kiterjedten használja a végjáték adatbázisokat, amelyek pontos értéket adnak a játék utolsó hat lépésében előálló összes álláshoz. Hogyan lehet egy ilyen adatbázist hatékonyan legenerálni?

6.14.

Vitassa meg, hogyan alkalmazható a játékok standard megközelítése az olyan játékokra, mint például a tenisz, a póló és a krikett, amelyeket folytonos, fizikai állapottérben játszanak.

6.15.

Írja le, hogy a minimax és az alfa-béta hogyan változik kétszemélyes, nem zérusösszegű játékok esetén, ahol minden játékosnak külön kiértékelő függvénye van. Feltételezheti, hogy mindegyik játékos mások kiértékelő függvényeit ismeri. Ha a két véghasznosság értékére nincs korlát, lehetséges-e valamelyik csomópont számára, hogy az alfa-béta lenyesi?

6.16.

Tegyük fel, hogy egy olyan sakkprogrammal rendelkezik, amely képes egymillió csomópontot kiértékelni másodpercenként. Válassza a játékállás egy tömör reprezentációját a transzpozíciós tábla számára. Kb. mennyi állást képes eltárolni memóriában, az 500 Mbájt nagyságú táblában? Elég lesz-e ez a lépésenként allokált 3 perces kereséshez? Hány táblakiolvasást képes megvalósítani egy álláskiértékelés ideje alatt? Most tételezze fel, hogy a transzpozíciós tábla nagyobb, és nem fér el a memóriában. Hány kiértékelést lehetne megvalósítani egy diszkhozzáférés ideje alatt, standard diszkhardver mellett?