Logikai játékok nyerő stratégiáinak keresése Szakdolgozat

Miskolci Egyetem Gépészmérnöki és Informatikai Kar Alkalmazott Matematika Tanszék

Logikai játékok nyerő stratégiáinak keresése Szakdolgozat

Témavezető:

Készítette:

Dr. Körei Attila

Urszin Dávid

egyetemi docens

TDWT4W

Alkalmazott Matematika Tanszék

Programtervező informatikus BSc 3800 Szikszó, Jókai út 14.

MISKOLCI EGYETEM Gépészmérnöki és Informatikai Kar Alkalmazott Matematikai Tanszék

Szám:

SZAKDOLGOZAT FELADAT

Urszin Dávid (TDWT4W) BSc programtervező informatikus jelölt részére. A szakdolgozat tárgyköre: Mesterséges Intelligencia A szakdolgozat címe: Logikai játékok nyerő stratégiáinak keresése

A feladat részletezése: Az intelligencia és mesterséges intelligencia alapjainak a feltárása. A mai korban betöltött fontos szerepe és a jövőben tapasztalható következmények az iparág fejlődésével. A logikai játékok terültén betöltött és alkalmazott szerepe és története. A mesterséges intelligencia tanulási módszereinek a megismertetése. Az általános sémák szerinti tanulás, a statisztikai adatok szerinti tanulás és a megfigyeléseken alapuló tanulás. Részletesebben a megfigyelésen alapuló tanulás egyik fajtája a megerősítéses tanulás. Alapjai és az emberi gondolkodással összevetett működése. A Q-tanulás bemutatása. Egy tanuló amőba implementációja Microsoft Visual Studio 2013 segítségével a Q-tanulás alapján. A kész program kiértékelő függvényének az ismertetése és a tanulás módjának a bemutatása. Témavezető(k): Dr. Körei Attila, egyetemi docens

A feladat kiadásának ideje: 2012. szeptember 20.

.................................................... szakfelelős

2

Tartalomjegyzék 1. Bevezetés ........................................................................................................................... 5 2. Gépi tanulás ..................................................................................................................... 7 2.1. Intelligencia és Mesterséges Intelligencia .................................................................. 7 2.1.1. Intelligencia definíciója ........................................................................................ 7 2.1.2. Mesterséges Intelligencia (AI - Artifical Intelligence) definíciója ...................... 8 2.1.3. A mesterséges intelligencia osztályozása ............................................................. 8 2.2. Története ..................................................................................................................... 9 2.3. Tanulási módszerek .................................................................................................. 10 2.3.1. Általános sémák szerinti tanulási módszerek ..................................................... 10 2.3.2. Statisztikai adatokon alapuló tanulási módszerek .............................................. 11 2.3.3. Megfigyelés alapján történő tanulási módszerek ............................................... 11 3. Megerősítéses tanulás .................................................................................................... 12 3.1. Megerősítéses tanulás alapjai .................................................................................... 12 3.2. Ágens - játéktér modell ............................................................................................. 14 3.3. Passzív megerősítéses tanulás ................................................................................... 15 3.5. Aktív megerősítéses tanulás...................................................................................... 15 4. Amőba játék implementációja ...................................................................................... 16 4.1. Állapotok .................................................................................................................. 16 4.2. Kiértékelő függvény ................................................................................................. 19 3

5. Fejlesztői dokumentáció ................................................................................................ 21 5.1. Hardware és software követelmények ...................................................................... 21 5.2. Software-architektúra ................................................................................................ 22 5.3. Felhasználói felület bemutatása ................................................................................ 23 6. Összefoglalás .................................................................................................................. 33 Irodalomjegyzék ................................................................................................................ 34 Adathordozó használati útmutató .................................................................................... 35

4

1. Bevezetés A mai modern világunk hihetetlen gyors technológiai fejlődésével és az internet térnyerésének következtében megkövetelik számítógépes alapismereteink egyre magasabb szintűvé válását. Az informatikai ismeretek beható hiánya későbbi életünket nehezítheti meg, hiszen az ipari szinten gyártott felhasználók által is elérhető technológiák életünk részévé váltak. Ha csak az okos televíziókra, az egyre fejlettebb számítógépekre vagy mobiltelefonokra gondolunk. Első találkozásomkor a számítástechnikával még ezt a tényt nem tudtam, és Magyarországon eddig gyermekcipőben járt az otthoni felhasználói élmény, de ami először hatalmába kerített azok a játékok voltak. Gimnáziumi évek alatt kezdett a gondolat foglalkoztatni, hogy rajtam kívül mennyi diáktársamat rabul ejtette a virtuális világ. A közösségi oldalak és videó megosztók csak megerősítettek abban, hogy ez az iparág hatalmas szerepet fog az életünkben és az én életemben játszani. Adódott a probléma, hogy hol tudom azt tudást megszerezni. Ezért választottam a Miskolci Egyetem Programtervező Informatikus szakját. Az egyik nagyon fontos tárgy a Mesterséges Intelligencia alapjai volt. Ekkor ismerkedtem meg a szakdolgozatom témájának egyik sarokkövével, a mesterséges intelligencia fogalmával. Ennek a definíciónak a részletezésére szakdolgozatom későbbi részében térek ki. Minél több időt töltöttem el a téma feltérképezésével, annál több módszerrel és még több kérdéssel találtam szemben magam. Legjobban a játékok mesterséges intelligenciája érdekelt, hiszen korunk egyik legtöbb bevételt termelő és a legtöbb embert megmozgatni tudó iparága. Ezért szakdolgozatom is kapcsolódik a virtuális időtöltéshez. Főbb célja az egyszerű logikai játékok megoldásaihoz algoritmust és egy implementációt megalkotni. Első témaként a mesterséges intelligencia és gépi tanulás fogalmait és alapjait részletezem. Kitérve az intelligencia és a mesterséges intelligencia különbségére. Később röviden bemutatom a téma történetét. Végül pedig a gépi tanulás elméletét és módszereit tárgyalom. Szakdolgozatom második főbb témája a megerősítéses tanulás körbejárása, kitérve a jutalom és hozam fogalmára, végül pedig az optimális állapotot kiértékelő függvényre.

5

Végezetül pedig az előző témák alapján implementálok egy egyszerű tanuló amőba programot Microsoft Visual Studio 2013 fejlesztő környezetben és C# nyelven. A program, amit létrehoztam, remélhetőleg sok szórakozást nyújt majd a későbbiekben a felhasználóknak.

6

2. Gépi tanulás 2.1. Intelligencia és Mesterséges Intelligencia 2.1.1. Intelligencia definíciója Mióta a tudomány fejlődik, azóta próbálják a szakemberek az addig nem definiált fogalmakat meghatározni. Ezeknek a meghatározásoknak a maradandósága eléggé korfüggő. Jelen esetben az intelligencia fogalma eléggé megfoghatatlan, mivel mindenki számára mást és mást jelent. Történelmünk nagyjait segítségül hívva próbálom közelebb hozni az olvasót az általam is elfogadott definícióhoz. Arisztotelész így fogalmazott az intelligenciáról: „Az intelligencia az igazságot megragadó megállapítás, beleértve a következtetést, amely ahhoz a tevékenységhez kapcsolódik, amely jó, vagy rossz egy ember számára. ...és ez megfelelőnek tűnik azután egy intelligens személy számára arra, hogy képes legyen finoman megítélni, mi a jó és előnyös számára; nem néhány korlátozott területre vonatkozóan (pl. ami jó az egészség, vagy az erő számára), hanem amely általában támogatja a jólétet.” Arisztotelész nagyon jól megfogta az emberi döntést jó és rossz szempontjából. A mai időkben nagyon sok modern játék használja ezt. Ahogy döntünk úgy fog alakulni az adott történet kifejlete. A játékos kezében van a döntés joga. 1951-ben Marvin Minsky és Dean Edmonds a Princeton Egyetem matematika tanszékén megépítette az első neurális számítógépet. Marvin Minsky így vélekedik az intelligenciáról: „Az intelligencia egy gyakran használt fogalom annak a rejtélynek a kifejezésére, hogy néhány önálló elem, vagy elemek felelősek a személy következtetési képességéért. Én jobban szeretem úgy elképzelni ezt, mint amely nemcsak valami különös erőt, vagy tüneményt reprezentál, hanem egyszerűen az összes mentális képességet, amelyet mi minden pillanatban megcsodálhatunk, de még nem értettünk meg.”

7

2.1.2. Mesterséges Intelligencia (AI - Artifical Intelligence) definíciója A mesterséges intelligencia definícióját közelebb hozva, Sántáné Tóth Edit, az NJSZT Mesterséges Intelligencia Szakosztály vezetőségi tagja, így vélekedik a témáról: „A mesterséges intelligencia a számítástudomány azon részterülete, amely intelligens számítógépes rendszerek kifejlesztésével foglalkozik. Ezek pedig olyan hardver/szoftver rendszerek, amelyek képesek 'emberi módon' bonyolult problémákat megoldani: az emberi gondolkodásmódra jellemző következtetések révén bonyolult problémákra adnak megoldást, a problémamegoldást teljesen önállóan végzik, vagy közben kommunikálnak környezetükkel, tapasztalataikból tanulnak, stb.” Az én gondolkodásmódommal legjobban megegyező gondolat Chiva H. Dagli professzortól származik: „A gépi intelligencia emulálja, vagy lemásolja az emberi ingerfeldolgozást (érzéklet feldolgozást) és a döntéshozó képességet számítógépekkel. Az intelligens rendszereknek autonóm tanulási képességekkel kell bírniuk és alkalmazkodniuk kell tudni bizonytalan, vagy részlegesen ismert környezetekhez.” A két intelligencia típus, azaz az emberi intelligencia és a mesterséges intelligencia, alapvető különbsége az alkotó és alkotás közti viszonyt juttatja az eszembe. A tökéletes mesterséges tudat egy briliáns másolat az emberi elméről, az ebben megélt érzésekről és az ezek által megindított cselekvésekről. Főként a döntésekre helyezném a hangsúlyt . Az én definícióm szerint az AI egy olyan elsődlegesen ember által megalkotott gép (persze később az AI maga képes lesz hatékonyabb intelligencia fejlesztésére) amelyik képes emberi módon dönteni, úgy hogy a többi ember számára nem tűnik fel, hogy ezt egy mesterségesen létrehozott intelligencia teszi.

2.1.3. A mesterséges intelligencia osztályozása Alkalmazási területek szerint: • logikai játékok • tételbizonyítás • automatikus programozás 8

• szimbolikus számítás • látás, képfeldolgozás • robotika • beszédfelismerés • természetes nyelvek feldolgozása • korlátozás kielégítés • cselekvési tervek generálás • szakértőrendszerek • mesterséges neurális hálózatok • adatbányászat • ágensek, multi-ágensek Szakdolgozatomban a logikai játékoknak a történetét illetve az azokban alkalmazott tanulási módszereket részletezem.

2.2. Története A történelem során az elsők közt Arthur L. Samuel implementált egy játék mesterséges intelligenciáját 1947-ben. Ez a Dáma (Checkers) nevű játék volt. Egy sakkmeccsnél egyszerűbb gondolkodást igényelt és egyszerűbb játékként tartották számon, de arra megfelelő volt, hogy a gépi tanulási módszereket tanulmányozhatták rajta. Arthur az emberek érdeklődését is szerette volna felkelteni. Ennek a megalkotása két évtizedbe telt majd ez idő alatt kiadott két publikációt 1959-ben és 1967-ben, amiben a mai gépi tanulás alapjait fektette le. Azért volt egyedi ez a program az eddig létrehozott keresés alapú játékokhoz képest, mert a program egyedül alkalmas volt saját teljesítményének a növelésére. Ez a program emelte tudományos szintre a mesterséges intelligenciát. A működése az ismétléses tanulás elvét követte, azaz megjegyezte saját lépéseit és amikor későbbi játékok során találkozott újra azokkal, akkor volt ideje behatóbban megvizsgálni. Nagyszerűsége abban mutatkozott meg, hogy a kiértékelő függvény súlyozását tudta 9

változtatni a saját javára, így fejlődött. A megerősítéses tanulás alapja volt, később a paramétereinek modellje már neurális hálózatra hasonlított. Mindezek után már a fejlődés megindult a tudományos világban a mesterséges intelligencia területén. Példának okáért megalkották azt a sakk programot, ami 1997-ben megverte az akkori világbajnokot hivatalos meccsen. Ez az ember Garri Kimocsiv Kasparov volt.

2.3. Tanulási módszerek Mesterséges intelligencia tanítására nagyon sok módszer létezik. A teljesség igénye nélkül a célom a módszerek egyszerű bemutatása és osztályozása.

2.3.1. Általános sémák szerinti tanulási módszerek Magyarázat alapú tanulás Legegyszerűbb tanulási módszer. A programnak konkrétan elmondjuk, hogy ha egy adott eseménnyel találkozik, hogyan cselekedjen. Előre megadott háttéranyagra van szüksége. Nem képes önálló tanulásra, csakis fejlesztő vagy felhasználó által tud új cselekvési mintákat elsajátítani. Multinacionális cégeknél a tömeggyártást végző embereket is ilyen módon tanítják.

Relevancia alapú tanulás Relevancia jelentései: fontosság, jelentőség és jelentékenység. A program egy megadott háttéranyag és megfigyelésének használatával új módon képes a megfigyeléseit elemezni. Általánosítja a megfigyelések eredményeit és mindig ezt csiszolja és új szabályokat hoz létre. Detektív tanulási módszernek is lehet nevezni, bár önállóan nem képes háttéranyagot felépíteni a kezdetektől.

Tudásalapú tanulás Ebben az esetben az intelligencia tud néhány előre eltárolt információt a problémáról és mellette megtanítunk neki pár megoldási mintát is. Ezáltal egy általános hipotézist állít fel,

10

tehát ha később is találkozik hasonló problémával, amihez nem ismer megoldást, ezt az egyszerű „receptet” fogja használni.

2.3.2. Statisztikai adatokon alapuló tanulási módszerek Bayes-tanulási módszerek Az eddigiek ismeretében itt is megtalálhatóak az adatok - itt tényként szerepelnek - és a hipotézisek, amik alapján cselekszik a program. Ennél a módszernél kiszámolja a program a hipotézisek valószínűségét, majd amelyiknek a megoldása a legvalószínűbb, azt hajtja végre. Abban különbözik az eddigi módszerektől, hogy nem a legjobb hipotézist használja, hanem az összes hipotézis valószínűségét, mindezt súlyozva. Bonyolult hipotéziseknél kezelhetetlenné válik.

2.3.3. Megfigyelés alapján történő tanulási módszerek Ellenőrzött tanulás A megfigyelés alapján történő tanulási módszereknél a program számára két dolog a legfontosabb: a bemenő és kimenő információk és adatok. Az ellenőrzött tanulás esetén a gép ismeri a bemenő, lehetőleg a „tanár” által osztályozott adatokat vagy információkat, és tudja, hogy milyen kimeneti adatra számítunk. Ezt is általában külső felhasználó adja meg.

Nem ellenőrzött tanulás A nem ellenőrzött tanulásnál a bemeneti adatok nem osztályozva érkeznek és a program csak az információk közti kapcsolatot képes felderíteni, mivel kimeneti információ nem áll a rendelkezésére. Adatbányászat területén használják ezt a módszert.

11

3. Megerősítéses tanulás 3.1. Megerősítéses tanulás alapjai A megerősítéses tanulás legjobban a valós életben figyelhető meg. Reális példákkal könnyebben érthetővé válik ennek a módszernek a működése. Az emberi tanulási folyamatok alapján nyugtázható, hogy megszületésünktől egészen a halálunkig megerősítéses módszerrel tanulunk. Gyermekkorunkban sokkal világosabban látható ez a folyamat. Adott egy gyerek, akinek még nem áll rendelkezésére a tudás, hogy hogyan kellene például járni, beszélni vagy egyáltalán túlélni. A körülötte lévő környezet minden egyes cselekvésünkre reagál, de a gyerek esetében ezek a reakciók jó vagy rossz mibenlétük és maguk a reakciók nem ismertek. Kell egy tanító, ebben az esetben először is a szülő, aki megtanítja, hogy hogyan cselekedjen helyesen egyes helyzetekben. Iskolás korban válik nyilvánvalóvá, hogy a körülöttünk lévőknek milyen a tanítási természete. Lehet ez pozitív (jutalmazó) vagy negatív

(büntető)

módszer.

A

gyerekek

későbbi

viselkedésében

nagyon

sok

kellemetlenséget és hibát követ maga után, ha csak a büntetést használják az esetében, és nem mutatják meg, hogy mi a jó út, amit el kell érnie. Későbbi élete során sok olyan időszak fog elkövetkezni, mikor nem lesz mellette sem egy tanár, sem a szülei és egy embertársa sem. Ekkor lesz képes önállóan tanulni. Példának okáért, mikor az anya nem figyel, a gyerek pedig belenyúl a konnektorba és megrázza az áram. Emberi mivoltunk azért csodálatos, mert egyedül is képesek vagyunk megítélni egy interakciót csupán azzal, hogy milyen érzelmet vált ki belőlünk. Az önállóság, illetve, hogy nagyon sok tanítónk van az életünk során ,és egyik ember sem éli le úgy az életét, hogy csak egy tanár véleményéből tanul, képessé teszi az intelligenciánkat, hogy ok-okozati viszonyokat tudjon alkotni. A mesterséges intelligenciánál a megerősítéses tanulási módszer, ennek a modellnek egy egyszerűsített formája. Az MI-t képessé kell tenni arra, hogy tanár nélkül is képes legyen tanulni. Tudja, hogy háttértudás híján és a játéktér ismerete nélkül, csupán véletlen lépésekkel felépítse a cselekvéseit. Persze ehhez meg kell határozni, hogy mikor nyer és felfedezhetővé kell tenni az egész játékteret. Ez mindig a játék végén fog megtörténni, addig sem a szabályokat, ezáltal a játékteret, sem pedig a győzelemhez vezető utat nem 12

ismeri. Az egyetlen pozitív visszacsatolása, amiből tanulhat, hogy mikor nyer, de ezt úgy kell meghatározni a számára, hogy ne csak egy a környezet egyszerű reakciójaként értelmezze, hanem meg tudja különböztetni a visszacsatolást egy általános észleléssel. Kivételt képez a cselekvésének az osztályozása, mivel nem kap visszacsatolást, hogy az elkövetett cselekvés az jó vagy rossz cselekvés volt-e, tehát hogy a győzelem vagy a vereség felé lendítette a játékot. Vannak olyan játékok, mint például a sakk, ahol legelőször kell egy tanár, hogy csak a szabályokat megtanítsa a programnak. Úgy lehetne jellemezni a megerősítéses tanulást, hogy a mesterséges intelligencia nem ismeri a szabályokat, egy teljesen ismeretlen játékkal játszik, majd pár tíz vagy pár száz lépés után szól az ellenfél, hogy veszített ellene az MI. Célunk, hogy olyan optimális stratégiát alakítsunk ki, hogy a várható jutalom maximális legyen, úgy hogy sem a játéktérről, sem pedig a jutalomfüggvényről nincs előzetes tudásunk. Nagyon sok területen a mai számítástechnikában használatos a megerősítéses tanulás, mivel ez áll az emberi tanulási folyamatokhoz a legközelebb. Például bonyolultabb számítógépes játéknál a mesterséges intelligenciát nem lehet minden egyes helyzetre felkészíteni, még úgy sem, hogy az adott játéknak van játéktere és fizikája, tehát vannak korlátai. Ebben az esetben is szinte végtelen a megvalósítható cselekvés főleg, hogyha emberi ellenfél ellen játszik, mert nyilvánvaló, hogy az élő ellenfelek képesek felkészületlennek láttatni a játékot és a hozzá tartozó mesterséges intelligenciát. Tehát ennek a problémának az enyhítésére, mivel nem készült el egy olyan MI, ami megfelel egy embernek, vagyis a gondolkodásának, önállóvá kell tenni egy játékot, hogy tanulhasson és fejleszthesse magát. A megerősítéses tanulásban háromféle mesterséges intelligenciát használhatunk: 

hasznosság alapú



reflexszerű



Q-tanuló

Ahogy a nevében is szerepel, egy hasznosságfüggvény segítségével maximalizálja a várható jutalmat. Ez a függvény előre meghatározott állapotokhoz rendel egy értéket,. A reflexszerű az állapotokat cselekvésekre fordítja le.

13

A Q-tanuló megoldás pedig egy jóság értéket rendel egy adott cselekvéshez, ami alapján meg fogja hozni a megfelelő lépést, nem ismerve a játékteret és a szabályokat. Mivel nem tudásalapú ez a tanulási módszer, sokan megkérdőjelezik a hasznosságát a lassúsága és a behatárolt képességek miatt. Nem képes nagyon bonyolult környezetek feltérképezésére és nagyon lassú, de egyszerűbb feladatok mellett képes felépíteni egy egész játékrendszert, csak a felfedezése révén.

3.2. Ágens - játéktér modell Ezek alapján egy egyszerű modellt állíthatunk fel. Létezik egy játéktér, ami reagál és felfedezhető. Adott még egy mesterséges intelligencia, ami nem ismeri a játékteret, de folyamatosan kapcsolatban van vele. A mesterséges intelligencia a döntéshozó, a játéktér pedig reagál általában valami új helyzettel a döntésekre. A jutalom is egy ilyen reakció a játéktér által. A mesterséges intelligencia ezt a jutalmat szeretné maximalizálni.

1. ábra

14

A játéktér és MI kapcsolata egy bizonyos ideig tart, ez játékfüggő. Ez idő előtt a játéktér rendelkezik egy állapottal, amit az MI is ismer. Amikor bekövetkezik a kapcsolat akkor a játéktér közli az újabb állapotát a mesterséges intelligencia számára. Ebből kikövetkeztethető, hogy maga a kapcsolódási idő egy állapotváltozást von maga után. Tehát megkap egy állapotleírást, és az alapján cselekszik az MI. Az 1. ábra ezt ábrázolja.

3.3. Passzív megerősítéses tanulás A passzív megerősítés tanulásnál az ágens előre meghatározott szabályrendszerek szerint előre meghatározott állapotokra reagál. Nem képes felismerni az állapotváltozást, ami a játéktér és a mesterséges intelligencia kapcsolata alatt jön létre, hanem előre meghatározott módon cselekszik. Nem ismeri se a pozitív visszacsatolást (a jutalmat), se azt, hogy éppen amit cselekszik, az pozitív vagy negatív. Egy előre programozott robotnak fogható fel aki nem képes a tanára nélkül tanulni. Ellenben mindig ugyanazt cselekszi az adott szituációra, így nagyon megbízható. Alkalmazását a mai játékiparban szinte minden egydimenziós mesterséges intelligenciájú gépi ellenfélnél használják. Az aktív megerősítéses tanulással kombinálva, nagyon hatékony intelligenciává válhat.

3.5. Aktív megerősítéses tanulás A passzív megerősítéses tanulással ellentétben itt nem rögzített a stratégia, ami alapján cselekszik a játék intelligencia, hanem képes önállóan a tanulásra. Az adott cselekvésekhez adott jóságértéket adva dönti el, hogy milyen lépést tegyen, majd kiértékeli a megtett lépést. A kiértékelés történhet a lépés előtt is. Az aktív megerősítéses tanulás előnye, hogy a mesterséges intelligencia képes a felfedezésre. Képes a játéktér feltérképezésére. Ehhez az előre meghatározó jóság függvény segítségével képes dönteni a tér által közölt állapot cselekvési tervére. Ennek egy ismert fajtája a Q-tanulási módszer.

15

4. Amőba játék implementációja Az implementáció egy heurisztikával segített Q-tanuló eljárást használ. A megvalósítás során külön megfontolásokat igényelt, hogy az algoritmus által hogyan történjen az állapotok megfigyelése, illetve, hogy a megtett lépések utólagos kiértékeléséhez, milyen függvényt alkalmazunk.

4.1. Állapotok A játék során a tanuló algoritmus a játékos lépése után megvizsgálja az aktuális játékteret. A játéktéren eddig elhelyezett jelek alapján keresünk egy olyan cellahalmazt, ami szóba jöhet a gép következő lépéseként. Ha bármely cellát megengednénk, akkor az algoritmus futási ideje jelentős mértékben nőne, ezért egy való életbeli stratégia alapján heurisztikát alkalmazunk. Ez a heurisztika pedig azzal segít lecsökkenti a lehetséges cellák halmazának a méretét, hogy figyelmen kívül hagy olyan helyeket, ami nem szomszédos (sorban, oszlopban vagy átlóban) már meglévő jelekkel. Az implementáció során állapotnak egy 9x9-es méretű táblázatot tekintünk, amely a játéktérhez hasonlóan a celláiban üres maradhat vagy tartalmazhat X-t illetve O-t. Az előbb meghatározott cellahalmaz minden egyes cellájához úgy rendelünk hozzá állapotot, hogy kivágjuk a játéktérnek egy 9x9-es méretű részét a kérdéses cellával középen. Mivel előfordulhat ezáltal, hogy valamely cellához, olyan állapot tartozna, hogy kilóg a játéktérből, ezért az állapotoknál az érvénytelen, azaz Invalid, értéket is meg kell engednünk a cellákban. A kapott állapotok közül kiválasztjuk azt, amihez a tudásbázisban a legnagyobb Q érték tartozik. A tudásbázisban tehát állapotok és Q értékek párosait fogjuk tárolni. Amennyiben egy adott állapot még nem szerepel a tudásbázisban, 0 jóságértéket rendelünk hozzá. A kiválasztott legnagyobb értékkel rendelkező állapot középső cellájába a számítógép elhelyezi a jelét a játéktéren. Miután ez megtörtént, kiértékelhető a lépés jósága annak megfelelően, hogy hány helyzetet teremtett a gépnek, illetve hányat rontott el a játékosnak. A meghatározott Q értékkel a szóban forgó állapot bekerül a tudásbázisba. Ezen az értéken további módosítást végezhet a játékos következő lépése is, hiszen előfordulhat olyan, hogy egy másik lépéssel egy később kialakított helyzetet akadályoztunk volna meg. 16

2. ábra A 2. ábrán látható egy olyan lehetséges helyzet, ami a betanulás elején történhet, méghozzá akkor, ha a játékos következő lépését nem vesszük figyelembe a Q érték beállításakor. Ekkor az algoritmus eleinte véletlenszerűen választ, majd a kiértékelő függvény alapján a saját lépésére pozitív jóság értéket kap. Azonban a nem megakadályozott helyzetek okozzák a vesztét.

17

3. ábra

A 3. ábrán látható zöld színnel megjelölve, hogy a heurisztika mely cellák vizsgálatát engedi meg (tehát egy korábban lehelyezett jellel szomszédos cellák).

18

4.2. Kiértékelő függvény

4. ábra

Miután a gép megtett egy lépést az algoritmus kiértékeli annak a Q értékét. Ezt úgy teszi, hogy megvizsgálja a lépéshez tartozó állapotot. Az 4. ábrán ezt az állapotot a lila körvonalú 9x9-es négyzet mutatja, melynek középpontjába került elhelyezésre a gépi játékoshoz tartozó jel (az ábrán látható példában ez a O-t jelenti, az ábrán besatírozott lila 19

négyzet). A jósági érték meghatározásához meg kell állapítanunk, hogy hány helyzetet teremtett neki illetve hányat rontott el az ellenfélnek ez a lépés. Ezt úgy teszi, hogy a környezetében legfeljebb négy cella távolságra lévő cellák tartalmát vizsgálja négy irányban: vízszintesen, függőlegesen és a két átló mentén. Először megvizsgáljuk, hogy a gép számára milyen jósági értékű helyzeteket teremtett a lépés. Ez azt jelenti, hogy a besatírozott lila négyzet helyére O-t, azaz a tényleges lépést képzelve végezzük el az ellenőrzést. Minden irányban egy öt cella méretű ablakot mozgatunk az egyik végétől a másikba. Amennyiben az ablakban megtalálható a másik szimbólum is, akkor a jósági értéket nullával fogja növelni, különben pedig annyival ahányszor a vizsgált szimbólum megtalálható az ablakban. Ez fogja adni az egyik részét a jósági értéknek a másik részéhez megcseréljük a szerepeket: a vizsgált szimbólum az ellenfél szimbóluma lesz, illetve a lila négyzet helyére is azt a jelet helyezzük el. Megcserélt szerepekkel az előbb leírt eljárást elvégezve megtudhatjuk, hogy milyen mértékben rontottuk el az ellenfél helyzetét. Az így meghatározott érték lesz a Q érték, melyet hozzárendelünk a tudásbázisban a szóban forgó állapothoz. Mivel a lépéseknek nem csak rövidtávú hatása van, ezért a lépések sorozatát szükséges tárolni visszamenőleg valahány lépésig. Amennyiben a játék végett ér győzelemmel vagy vereséggel a tárolt lépéssorozatban levő állapotokhoz tartozó Q értékeket tovább módosítjuk, ha a gép nyert akkor növeljük őket, ha veszített akkor csökkentjük őket. Ennek a nevelésnek/csökkentésnek mértéke annál kisebb, minél régebbi lépésről van szó.

20

5. Fejlesztői dokumentáció A program implementálását Microsoft Visual Studio 2013 C# Express ingyenes fejlesztőkörnyezettel végeztem el C# nyelven.

5.1. Hardware és software követelmények Software követelmények: 

Windows XP SP3 vagy frissebb verziójú operációs rendszer

Hardware követelmények: 

Intel Pentium 4 processzor vagy annál fejlettebb



Minimum 128 MB memória

21

5.2. Software-architektúra Az osztályok létrehozásánál a célom az egyszerűség és átláthatóság volt. Minél könnyebben fejleszthető a jövőben a játék. Program.cs Ez a főprogram. Az alkalmazás felhasználói felületéül szolgáló ablak megjelenítését végzi. Grid.cs Ez az osztály reprezentálja a játékteret, melynek minden egyes cellájához háromféle érték tartozhat: 

Empty



Circle



Cross

Továbbá tartalmaz még metódusokat annak ellenőrzésére, hogy ki a nyertes (ha van), megtelt-e a játéktér, illetve egy metódust a játékmező újra inicializálására. TicTacToeForm.cs Ez az osztály képviseli a felhasználói felületet. Kezeli a felhasználó általi inputokat, többek között a menüpontok kiválasztását, illetve az „X” jel elhelyezését a játéktéren. Továbbá összefogja a többi osztályt. State.cs A tanuló algoritmus állapotait egy 9x9-es táblázatban megvalósító osztály. A cellák négyféle értéket vehetnek fel, köztük a korábban említett: 

Empty



Circle



Cross

Negyedik értékként bejön az érvénytelen, vagyis Invalid érték, amire azért van szükség, mert az állapot „kilóghat” a játéktérből. Computer.cs 22

Ebben az osztályban található a tanuló algoritmus, valamint egyéb segéd metódusok is. Ennek következtében tartalmazza a kiértékelő függvényt, valamint a kiépített tudásbázist. Az osztálynak a TakeTurn() metódusa bejárja a cellákat az amőba implementációról szóló fejezetben említettek szerint, elkészíti hozzá az állapotokat, valamint kiválasztja azt a lépést, amely jelenleg a legnagyobb Q értékkel rendelkezik. A lépés elvégzése után pedig kiértékeli az eredményt és ennek megfelelően módosítja a tudásbázist.

5.3. Felhasználói felület bemutatása A program a TicTacToe.exe fájllal indítható el. A játék telepítést nem igényel. A TicTacToe.exe mellett található TicTacToe.kb fájl tartalmazza a játék által tanult lépéseket.

23

5. ábra Kezdő képernyő

A program megnyitásakor a 5. ábrán látható kezdő képernyő fogadja a felhasználót. A címsoron megtalálható a program neve bal oldalt. Jobb oldalt pedig egy általános ablak kezelő felület ami tartalmazza balról jobbra a tálcára helyezést, átméretezést és az ablak bezárását.

24

6. ábra Első lépés

A 6. ábrán látható első lépést az egér bal gombjának megnyomásával érhetjük el, miután a négyzet felé navigáltunk, ahová a jelet szeretnénk letenni. Ezt a program indítása után rögtön megtehetjük. Ekkor már a mesterséges intelligencia ellen tud a felhasználó játszani. A játék piros X és kék O jelölést használ a játékosok lépésének a meghatározására. Ebben a játékban mindig az emberi játékos kezd piros X jelöléssel. Ezután a gépi intelligencia következik kék O jelöléssel, tehát a játékos és a gép felváltva rakják le a jelüket. A játék célja, hogy 5 azonos jel összegyűljön egy sorban, oszlopban vagy átlósan.

25

7. ábra 3-as állás

A 7.ábrán látható egy példa a 3-as állásból. Ez a pont, ahol még a két nyitott oldal ellenére meg lehet fékezni, hogy kialakuljon a piros X győzelme.

26

8. ábra 4-es állás

Az 8. ábrán látható a 4-es állás, ahol már egy lépéssel le lehet zárni a mérkőzést. Ellenkező esetben még ilyenkor megállítható az X támadása.

27

9. ábra piros X győzelem

A 9. ábrán látható egy példa a piros X győzelmére. Az öt jel átlósan található meg. A piros X győzelmekor felugró ablakban egy üzenet fogadja a játékost: „A nyertes: X”.

28

10. ábra a kék O győzelme

A 10. ábrán látható egy példa a kék O győzelmére. Az öt jel átlósan található meg. A kék O győzelmekor felugró ablakban egy üzenet fogadja a játékost: „A nyertes: O”.

29

11. ábra döntetlen

A 11. ábrán látható a döntetlen mérkőzés. Ebben a helyzetben a játék újraindításra kerül, hiszem egyik fél sem teljesítette a győzelmi feltételt, hogy 5 azonos jel egy sorban, oszlopba vagy a két átlóban legyen. Ilyenkor üzenet jelenik meg a játékos számára: „A tábla betelt” szöveggel.

30

12. ábra Menü

A 12. ábrán látható a menü sor elérhető funkciói. Három választás lehetséges: 

Új



Tudásbázis törlése



Kilép

Az „Új” funkcióra kattintva új játék indítható akár már egy elkezdett mérkőzés alatt is. Elrontott játék esetén lehet alkalmazni.

31

A „Tudásbázis törlése” funkcióval az addigi felhalmozott tanult tudásbázist tudjuk törölni. Erre azért lehet szükség, ha szeretnénk megfigyelni a program tanulásának az idejét vagy csak elemezni a tanulás folyamatát. A „Kilép” funkcióval bezárható az alkalmazás. Bezárás előtt a mesterséges intelligencia menti a tudását minden egyes lépés után, így nem kell aggódni, hogy a már elkezdett játék tudását „elfelejtené”.

32

6. Összefoglalás Mai világunkban a mesterséges intelligencia alkalmazása és megvalósítása fontos szerepet kapott. Legtöbb esetben csak egy megoldó gépként használják, de a jövőben az önálló mesterséges intelligenciák veszik át a vezető szerepet. Tanulási módokban különbözhet, de a céljuk közös: létrehozni egy olyan gépet, ami képes emberi mértékkel dönteni, ha rosszul tenné, akkor is tanul belőle. A különböző módszereknek megvan a maga előnye és hátránya. A fejlesztők számára a legfontosabb, hogy az emberek érzelmi világát is valahogy a virtuális térben megalkossák, és olyan tanulási módszert használjanak, ami a legközelebb áll a bonyolult emberi tanuláshoz. Szakdolgozatom az intelligencia és mesterséges intelligencia alapjainak a feltárásával és a mai korban betöltött fontos szerepével foglalkozik. Ezen kívül a mesterséges intelligencia tanulási módszereinek a megismertetése a cél. Ezek az általános sémák szerinti tanulás, a statisztikai adatok szerinti tanulás és a megfigyeléseken alapuló tanulás. Részletesebben a megfigyelésen alapuló tanulás egyik fajtáját, a megerősítéses tanulást, és ezen belül a Qtanulást mutatom be. A megfelelő szakirodalmat és tudományos cikkeket felhasználva jutottam hozzá a megfelelő információhoz. Majd az adatok alapján C# nyelven implementáltam egy példa programot. Ez egy tanuló amőba program, ami a megerősítéses tanulási módszereken belül a Q-tanulás módszerét használja. Ezen kívül kitértem szakdolgozatomban az implementált program felhasználói felületére és annak használatára. A jövőben hatékony fejlesztéseket kívánok a tanulási módszeren alkalmazni, ami gyorsítja a játék tanulását és kiértékelését egy nagyobb játéktérben.

33

Irodalomjegyzék 1. Dr. Dudás László: Mesterséges intelligencia módszerek, ME, Gépészmérnöki kar, Informatikai Intézet oktatási segédlet, 1999 2. Stuart Russell - Peter Norvig: Mesterséges Intelligencia - Modern megközelítésben (második, átdolgozott, bővített kiadás), 2005, forrás: http://project.mit.bme.hu/mi_almanach/books/aima/index (ellenőrizve: 2015.06.12) 3. Kollár Zoltán: Intelligens számítási módszerek alkalmazása logikai játékokban (Machine learning possibilities for games), 2011, forrás: http://miau.gau.hu/miau/160/machine_learning.pdf 4. Jiun-Hung Chen and Adrienne X. Wang: Five-In-Row with Local Evaluation and Beam Search, forrás: http://courses.cs.washington.edu/courses/cse573/04au/Project/mini1/JA/report.pdf (ellenőrizve: 2015.06.11)

34

Adathordozó használati útmutató A szakdolgozat CD mellékletén az alábbi könyvtárak találhatóak meg: • Felhasználói dokumentáció: itt található a felhasználói dokumentáció pdf formátumban. • Szakdolgozat: a szakdolgozatot tartalmazza pdf formátumban. • Program: az UrszinDavid nevezetű mappát tartalmazza, mely a szakdolgozat programcsomagot. A program indítása: TicTacToe.exe Ahhoz, hogy a program megfelelően működjön, a forrásfájlokat másoljuk át a merevlemezre vagy pendrive-ra. A program futtatásához szükséges Windows Xp vagy frissebb verziójú operációs rendszer. A program könnyebb használatához vagy a használata közben felmerülő nehézségek kiküszöböléséhez

érdemes

elolvasni

a

mellékleten

dokumentáció/felhasznaloi_dokumentacio.pdf fájlt.

35

található

Felhasználói

EREDETISÉGI NYILATKOZAT

Alulírott Urszin Dávid; Neptun-kód: TDWT4W a Miskolci Egyetem Gépészmérnöki és Informatikai Karának végzős Programtervező informatikus szakos hallgatója ezennel büntetőjogi és fegyelmi felelősségem tudatában nyilatkozom és aláírásommal igazolom, hogy Logikai játékok nyerő stratégiáinak keresése című szakdolgozatom/diplomatervem saját, önálló munkám; az abban hivatkozott szakirodalom felhasználása a forráskezelés szabályai szerint történt. Tudomásul veszem, hogy szakdolgozat esetén plágiumnak számít: -

szószerinti idézet közlése idézőjel és hivatkozás megjelölése nélkül;

-

tartalmi idézet hivatkozás megjelölése nélkül;

-

más publikált gondolatainak saját gondolatként való feltüntetése.

Alulírott kijelentem, hogy a plágium fogalmát megismertem, és tudomásul veszem, hogy plágium esetén szakdolgozatom visszautasításra kerül.

Miskolc, 2015. június 12.

…….……………………………….… Hallgató

36

1. A szakdolgozat módosítása:

szükséges (a módosítást külön lap tartalmazza) nem szükséges (a megfelelő rész aláhúzandó)

Miskolc, _____________ tervezésvezető aláírása 2. A tervezést ellenőriztem:

(1)

___________________________________

(2)

___________________________________

(3)

___________________________________

(4)

___________________________________ dátum, tervezésvezető aláírása

beadható

3. A szakdolgozat

nem adható be Miskolc, _____________ tervezésvezető aláírása … szövegoldalt,

4. A szakdolgozat

… db rajzot, … db CD mellékletet …egyéb mellékletet tartalmaz. 5. A szakdolgozat bírálatra:

bocsátható nem bocsátható

A bíráló neve, címe:

________________________________________________

Miskolc, _____________ tanszékvezető aláírása 6. Osztályzat:

a bíráló javaslata: ___________________________________ a tanszék javaslata: ___________________________________ a Záróvizsga Bizottság döntése: _______________________

Miskolc, _____________ a Záróvizsga Bizottság elnökének aláírása

37