Mesterséges Intelligencia I. kötelező program 1.
Feladat kiírás
A feladat az Othello (más neveken Reversi, Fonákollós, Színcserélő) játékot játszó ágens írása. A játékot egyik oldalán világos, a másikon sötét korongokkal játszuk, egy 8x8-as táblán. Az egyik játékos színe a világos, a másiké a sötét. Sötét kezd. A játék célja, hogy a saját színű korongokkal a lehető legtöbb mezőt foglaljuk el a táblán, az ellenfél korongjainak közrefogásával és átfordításával. A pontos szabályok a következők: 1. A kezdőállást az 1. ábra szemlélteti. 2. A játékosok felváltva helyeznek korongokat a saját színükkel felfelé a tábla valamely szabad mezőjébe, sötét kezd. 3. Közrefogáson azt értjük, hogy a lehelyezett korong vízszintes, függőleges vagy átlós irányban egy vonalban van egy másik, saját színű koronggal, és közöttük megszakítás nélkül csak az ellenfél korongjai vannak. 4. Csak olyan mezőbe helyezhető korong, ahol az ellenfél legalább egy korongját az éppen lehelyezett korong és valamelyik, a táblán lévő, saját színű korong közrefogja. 5. Minden, a lehelyezéssel közrefogott korongot át kell fordítani, minden irányban. 6. Ha egy játékos nem tud lépni, akkor megint a másik játékos jön. De ha tud lépni (azaz van lépés ami eredményez átfordítást) akkor kötelező lépni. 7. A játéknak akkor van vége ha egyik játékos sem tud lépni. A végeredmény a táblán levő korongok megszámolásával adódik.
1. ábra. Kezdőállás
2.
Fejlesztés és kiértékelés
A következő fejezetben összefoglaljuk a fejlesztéssel és a kiértékeléssel kapcsolatos tudnivalókat.
2.1.
Kiértékelő rendszer
A megoldást Java programozási nyelven kell elkészíteni. A könnyebb fejlesztés és kiértékelés megvalósítása érdekében közreadunk egy keretrendszert, ami egyben egy osztály könyvtár is. A keretrendszer alapvető feladata, hogy levezényelje az egyes meccseket (ellenőrizze a lépések helyességét, az időkorlátok betartását, stb...). A közreadott rendszer egyben egy osztálykönyvtár is, hiszen tartalmazza azt az interface-t (Player interface), amelyet a megoldásoknak meg kell valósítaniuk. Az említett keretrendszer, annak forráskódja és néhány példa implementáció elérhető a http://www.inf.u-szeged.hu/~jelasity/mi1/mi-kotprog.zip címen. A könnyebb érthetőség kedvéért tekintsünk egy példa fejlesztés-kiértékelés ciklusra: 1. Töltsük le és tanulmányozzuk a közreadott keretrendszert, a valamint a benne elérhető Player interface-t. Értsük meg a meccs lejátszásának mikéntjét az említett interface szemszögéből. Ehhez nagy segítség a javadoc-ban elérhető dokumentáció. 2. Implementáljuk a stratégiánkat Java programozási nyelven. Például: import szte.mi.*; public class h241696 implements Player { public void init( int order, long t, Random rnd ) { // ... } public Move nextMove(Move prevMove, long tOpponent, long t ) { // ... } } 3. Fordítsuk le azt. A fordítás során a class-path-ban szerepelnie kell a keretrendszernek. Például: javac -cp "./mi-kotprog.jar;." h241696.java 4. Az elkeszült stratégiát próbáljuk ki, valamelyik közreadott stratégia ellen a keretrendszer használatával. Például (egy sorban): java -Xmx1024M -cp "./mi-kotprog.jar;." szte.mi.OthelloGame h241696 szte.mi.RandOthelloPlayer
Érdemes több tesztet végezni! 5. Ha megfelelőnek ítéljük a stratégiánkat, akkor töltsük fel a Bíró rendszerbe, különben iteráljunk a forráskód változtatásától.
2.2.
Követelmények a megoldással szemben
A megoldást tartalmazó forráskódnak minden körülmények között ki kell elégítenie a következő követelményeket: • A stratégiánkat tartalmazó osztálynak meg kell valósítania a Player interface-t, ami a keretrendszer részét képezi. • A megoldást tartalmazó osztálynak részletes magyar osztálydokumentációt kell tartalmaznia, javadoc formátumban, illetve a kód dokumentációja is magyar kell hogy legyen. • A kód nem használhat a keretrendszeren kívül semmilyen más osztálykönyvtárat. • A stratégiát leíró osztály nevének meg kell egyeznia a hallgató h-s azonosítójával (kis h betűvel). • A megoldást tartalmazó osztály nem lehet csomagban. • A megoldásban nem lehet képernyőre írás. • A megoldás nem nyithat meg file-t, nem indíthat új szálat. • Az implementált metódusoknak minden esetben vissza kell térniük. (Nem szerepelhet benn exit hívás például.) A megoldásnak az szte.mi.RandOthelloPlayer-t és az szte.mi.GreedyOthelloPlayert le kell győzni a következő arányban: 10 játékból legalább 8-szor kell nyerni mindkét ellenféllel szemben, és a 10 játékból 5-ször az egyik, 5-ször a másik játékos kezd. Összesen tehát 20 meccs kerül lejátszásra. Ha ez sikerül, akkor a gyakorlaton szerezhető pontszámokból 10 pont megvan! Néhány szabályt nagyon szigorúan fogunk venni tekintettel a magas létszámra. A kötelező program nem kerül elfogadásra (ami a kurzuson bukást jelent) ha: • a benyújtott ágens nem vagy helytelenül implementálja az interfészt • a futás során hiba lép fel (végtelen ciklus, kivételdobás, stb.) • az ágens érvénytelen lépést választ • a forráskódban nincs kielégítő magyar nyelvű osztálydokumentáció és forráskód dokumentáció (azért magyar, hogy nehogy kísértésbe essünk letöltögetésre)
• a programozói munka nem a hallgató saját munkája (természetesen ötleteket lehet és ajánlott keresgélni); ez esetben a bukáson felül további következményekkel is kell számolni! Vannak megbízható eszközeink a plágium kiszűrésére, nem érdemes kísérletezni. • bármilyen "hack"-et találunk ami a kiértékelő nem rendeltetésszerű használatából fakadóan jogosulatlan előnyt eredményez.
2.3.
Bíró rendszer
A kötelező programok tényleges kiértékelését a bíró rendszer végzi. Ha sikerült elkészíteni egy megfelelőnek ítélt stratégiát, akkor a bíró rendszerbe (https://biro.inf. u-szeged.hu/) történő bejelentkezés után, fel kell tölteni a forráskódot. A feltöltött forráskódnak ki kell elégíteni az előző fejezetben ismertetett követelményeket! A feltöltés után a bíró rendszer a következők szerint jár el: 1. A feltöltött forráskódon egy előzetes ellenőrzést hajt végre, hogy az kielégíti-e az előzőekben ismertett követelményeket. Ha nem elégíti ki azokat, akkor a beküldés sikertelen, máskülönben a kiértékelés folytatódik. 2. A rendszer lefordítja a feltöltött forrást. A fordítás a ’Kiértékelő rendszer’ c. fejezetben látott példa szerint történik. Ha nem sikerült lefordítani a kódot, akkor a beküldés sikertelen, máskülönben a kiértékelés folytatódik. 3. A rendszer 10 alkalommal meghívja a kiértékelő keretrendszert a ’Kiértékelő rendszer’ c. fejezetben szereplő példában látottak szerint a RandOthelloPlayer stratégia ellen. A feltöltött megoldás váltakozva fekete illetve fehér játékosként szerepel. Ha sikerül a megoldásunknak legalább 8 alkalommal győznie, akkor eggyel nő a pontjaink száma és a kiértékelés tovább halad. Ha hiba történt bármelyik meccs során, akkor a beküldés sikertelen. 4. A rendszer hasonlóan meghívja a kiértékelőt 10-szer a GreedyOthelloPlayer stratégia ellen. A feltöltött megoldás váltakozva fekete illetve fehér játékosként szerepel. Ha sikerül a megoldásunknak legalább 8 alkalommal győznie, akkor eggyel nő a pontjaink száma és a kiértékelés tovább halad. Ha hiba történt bármelyik meccs során, akkor a beküldés sikertelen. 5. A bíró rendszer elérhetővé teszi a webes felületen az elért pontszámunkat és a kiértékelés során készített jelentést. Egy beküldés akkor tekinthető elfogadottnak, ha legalább 2 pontot ad a bíró rendszer. Ezesetben a hallgató teljesítette az első forduló minimális követelményeit. Fontos megjegyezni, hogy bizonyos esetekben a kiértékelés hosszú ideig tart. Ezalatt a bíró rendszer webes felületén semmi információt nem látunk. Ez normális működés! Ha ezalatt frissítjük a böngészőt és újraküldjük az adatokat, akkor az új próbálkozásnak minősül!
Másik fontos észrevétel, hogy a beküldési határidőhöz közeledve egyre terheltebb szokott lenni a rendszer. Ekkor egy-egy feltöltés hosszabb időt is igénybe vehet. A fejlesztés során ezzel mindenki kalkuláljon! (Természetesen a keretrendszer processzor időt mér a futás során, így a terheltség nem jelenti azt, hogy kevesebb idő jut az egyes stratégiáknak arra, hogy végigjátszák a meccset.)
2.4.
Korlátok, határidők
Az első fordulóval kapcsolatban az alábbi korlátok, határidők élnek: • Egy meccs 40 másodpercig tart, így egy játékos összesen 20 másodperccel rendelkezik, egy Core 2 Duo 2.8GHz-es gépen. • A meccsek során a teljes keretrendszer számára 1024MB memória áll rendelkezésre. • A bíró 1.6-os Java verziót használ. • 10 próbálkozás áll a hallgatók rendelkezésére. • A beküldési határidő 2008. december 2. 00:00:00.
Hasznos és jó munkát kívánunk!
