Bár a cím azt is sugallhatná, nem az elmebetegekről fogok írni. Nem is tudok annyit róluk, hogy érdemben tudjak a témáról nyilatkozni, de ha tudnék is, akkor sem hiszem, hogy akarnék.
Ez a bejegyzés inkább afféle esettanulmány arról, hogy a korábbi fejtegetéseimet hogy lehet a “gyakorlatba” átültetni.
A Google AI Challenge általában egy olyan feladat, ahol írni kell egy programot, ami más programok ellen játszik egy egyszerű játékot. Volt már Tron, volt Planet Wars, és nemsokára lesz egy hangyás. Ez utóbbi arról szól, hogy van egy terület, rajta néhány hangya, akik kaját keresnek, hogy szaporodjanak, és ha összetalálkoznak, akkor harcolnak. Bár ez nem a feladat része, én ebben a bejegyzésben arra fogok koncentrálni, hogy a hangyákat egyedként kezeljem, és az egyének viselkedéséből alakítsak ki egy csoportos stratégiát (a blogon már korábban említett emergence témaköre). Az egyének viselkedéséhez pedig egy szükségleti piramist fogok alkotni.

Hogy is lássunk hozzá? Négy lépésre lesz szükségünk:

1. A szabályok megértése
2. Célok meghatározása
3. Cél alapján a hozzá kapcsolódó szükséglet meghatározása
4. Szükségletek priorizálása és csoportosítása

Először akkor írjuk le, hogy mik a szabályok:

• Pontot ellenséges hangyák megölésért kapunk
• A hangya X távolságra lát
• A hangya Y távolságon belül harcol (X > Y)
  • A hangya akkor éli túl a harcot, ha hozzá képest Y távolságon belül több baráti hangya van, mint ellenséges
• Ha a kajához képest Z távolságon belül hangya van:
  • Ha egyféle, akkor olyan hangya lesz a kaja helyén
  • Ha többféle (azaz harci helyzet) akkor a kaja megsemmisül

Célok -> Szükségletek

• Minél több baráti hangyát szeretnénk -> Menjünk közel a kajához, ha látunk
• Minél nagyobb területet szeretnénk átfésülni kajáért -> Álljunk távolabb a többi hangyától
• Túl szeretnénk élni a harcot -> Ha kevesebben vagy ugyanannyian vagyunk, meneküljünk
• Szeretnénk ellenséges hangyákat ölni -> Járjunk csapatban
• Szeretnénk ellenséges hangyákat ölni -> Ha többen vagyunk, rohanjuk le
• Jobb, ha megsemmisül a kaja, mint ha ellenséges hangya lesz -> Előbb vagy egyszerre érjünk a kaja hatósugarába, mint az ellenséges hangya, ha van olyan
• Keressünk kaját -> Mozogjunk valamerre

És most jön a feladat legkomolyabb kihívása: a mérlegelés. Minden célra meg kell mondanunk, mennyire fontos, majd eszerint meg kell alkotnunk a piramist. Ki kell találnunk, hogy vannak-e olyan igények, amik egyenrangúak – egymástól függetlenek, de a fölöttük lévőknél fontosabbak – és ezeket egy szintre kell helyeznünk.
Az elsőre a legegyszerűbb módszer az összefésüléses priorizálás: fogok egy elemet, majd végignézem az eddig megalkotott prioritási listát, és megkeresem, melyik a legalsó elem, aminél még fontosabb, és az alá helyezem el. (ebben az elrendezésben alul lesz a lista legfontosabb eleme, ami megfelel a szükségleti piramis felépítésének)
Ezt nem lehet olyan nagyon látványosan megoldani egy ilyen bejegyzésben, úh inkább leírom az így kialakult listát (még1x: alul a fontosak):

• Mozogjunk valamerre
• Járjunk csapatban
• Álljunk távolabb a többi hangyától
• Menjünk közel a kajához
• Ha kevesebben vagy ugyanannyian vagyunk, meneküljünk
• Ha többen vagyunk, rohanjuk le
• Előbb, vagy egyszerre érjünk a kaja hatósugarába az ellenséges hangyával, ha van olyan

Miket vonhatunk össze:
“Előbb vagy egyszerre érjünk a kaja hatósugarába.. ” Ez fontosabb, mint a második, mivel annak egy speciális ágát fejti ki. Nem összevonhatóak.
“Ha többen vagyunk / Ha kevesebben vagy ugyanannyian vagyunk” – kezdődik a következő két sor. Mivel egymást kizáró a feltétel, ezek a sorok egymástól függetlenek, így összevonhatóak egy szintre. Mindkettő fontosabb, mint a következő.
“Menjünk közel/Álljunk távolabb/Járjunk csapatban” Kössük össze az élelemszerzést azzal, hogy “falkában” járunk. Így biztosítjuk, hogy nem kószál el egy hangyánk kajanyomot követve, de erre utaló mozgásával húzza maga után a csoport többi tagját is, így van esélye eljutni az ételhez akkor is, ha az egy kicsit kiesik a látóköréből.
“Mozogjunk valamerre” Már csak egy maradt, nevezzük ezt önmegvalósításnak

Hogyan viselkedik az egyedünk? Ha kaját és ellenfelet is lát, megbecsli, hogy van-e esélye a kajához előbb v 1xe odaérni az ellenséges hangyával. Ha igen, akkor elkezd teperni.
Ha nem így történik, akkor a harci szituációt értékeli ki: “van esélyem hangyát ölni és túlélni?”. Ha igen, megpróbálja, ha nem, olyan irányt választ, amerre a legnagyobb esélye van elkerülni a harcot.
A következő szempont az ételszerzés a falkával: Ha látunk valahol kaját, akkor megyünk arra, ha ez csapatban megoldható. Ne felejtsük el, hogy ide már úgy jutunk el, hogy megvizsgáltuk és elvetettük a kajáért harcolást. Laza falkát építünk, hogy sokat lássunk a területből, de legyen közel a védelem, ha kell.
Ha viszont semmi ilyesmi nincs, vagy több, egyformán jó megoldás közül választhatunk, akkor választunk egy irányt, és arra mozgunk.

A valós probléma egyébként ennél sokkal bonyolultabb, de ez már egy jó alapozás, amiből nyerő stratégiát lehet alkotni. Legközelebb valószínűleg arról írok majd, hogy miyen módon lehetne az MMO-kban hasznát venni ennek.

Multkor mar meseltem az AI Contest-rol. Most – kulon keresre – irok meg egy kicsit a botomrol, azon apropobol, hogy a tegnap beposztolt botom soha nem latott magaslatokba emelkedett: 371 is volt a rank-je. Ugy tunik, mar lassul a botok evolucioja, de az elso 500 mar annyira durvan eros, hogy kifejezetten munkas dolog oda bejutni. Az, hogy sikerult, nagy elmeny szamomra.
Hogyan is mukodik ez a bot? Az egyik legnagyobb erdekessege, hogy nem tarol allapotot, kiveve azt, hogy eppen hanyadik korben vagyunk. Minden kor elejen a rendelkezesre allo adatok alapjan ujraertekeli a teljes rendszert, es annak megfeleloen dont.
A legelso lepesben vegigfut a sajat bolygoimon, es elemzi a veszely merteket. Az algoritmus egyelore nagyon durva, sokat lehetne meg finomitani rajta, de hozzavetoleg kepes eldonteni, hogy a harom lehetosegbol mi tortenik eppen:

• Nincs veszely
• Van veszely, de onerobol meg tudjuk oldani
• Van veszely es segitseg kell

A kiertekeles utan megvizsgalja, hogy van-e lehetosegunk arra, hogy segitseget kuldjunk ezekre a bolygokra, majd ha ezt lerendezte, elkezdi az offenziv cselekveseket. A korabbi valtozatban egyebkent a bolygok csak magukat vedtek, most mar azonban egymast is, ez az, amit en korabban “aktiv vedelem”-kent aposztrofaltam, mig a legidosebb batyam ki nem talalta ra a nagyon talalo “NATO vedelem” kifejezest. Azota mar a kodban is ezt hasznalom
Az offenziv cselekvesekre visszaterve, ebbol is harom fele van (nem azert, mert imadom a harmas szamot, egyszeruen ennyit talaltam):

• Terjeszkedes
• Harc
• Zaklatas

A terjeszkedesi taktika az elejen fontos. Az ellenfellel azonos szamu sereggel, pontosan ugyanolyan poziciobol indulunk a palya egy masik pontjarol, es ebben a fazisban dol el, hogy ki szerez folenyt. A bot ebben a szakaszban nagyon erzekeny a betamadasokra, ugyhogy figyelni kell arra is, hogy a terjeszkedes rovasara ne hagyjuk vedtelenul a fobolygonkat. Erdemes az ellenfel taktikajat figyelnunk: Ha o arra hajt, hogy fuggetlen bolygokat foglaljon, mi is tegyunk igy. Ha bennunket tamad, vedekezzunk, es a folosleggel foglaljunk bolygokat, ha van erre lehetoseg.
Fontos szempont minden fazisban, hogy ha csak el tudjuk kerulni, ne kuldjunk messzire flottakat. Amig ugyanis ezek uton vannak, semmire nem jok, mig ha elfoglalunk veluk egy kozeli bolygot, ott is megkezdodik a termeles.
A terjeszkedesi fazis utan en a harci fazisba lepek. Ez mar arrol szol, hogy a seregek gyujtogetese helyett nekilatok az osszes extra egysegemet kitolni az urbe, a bolygoimon csak egy szukseges minimum vedelmet hagyva. Erre a megoldasra a kozepso batyam a “Mehraj technika” kifejezest hasznalja. Bar a seregek gyujtogetese ad egy extra vedelmi faktort a bolygoknak, a mehraj technika valamivel gyorsabb, mivel az elso seregek lenyegesen hamarabb ernek oda az ellenfelhez. Egyetlen ok miatt mondhatnank, hogy a sereggyujtes esetenkent jobb: kozelre tamadva nagy sereggel az ellenfelnek nincs ideje, hogy vedoseregeket kuldjon a bolygora.
A harmadik fazis, amit en meg senki masnal nem lattam ebben a formaban, az, amit en zaklatasnak hivok. Akkor lepek at ebbe az uzemmodba, amikor mind seregszamban, mind bolygotermelesben erosebb vagyok az ellenfelnel. A lenyege, hogy a bolygotermelesem egy reszet arra forditom, hogy az ellenfel termeleset lefoglaljam, azaz a legjobban termelo bolygoim azonnal tovabbkuldik a termelesuket az ellenfel legjobban termelo bolygoi fele, igy mindkettonk termelese lecsokken. Gondoljuk vegig ennek a hatasat: En rendelkezem mondjuk 30, az ellenfel 25 termelessel. A kulonbseg marginalis, 20%. Azonban, ha 15 termelest arra forditok, hogy az o termelesebol 15-ot levegyek, akkor nekem 15 marad, neki csak 10, azaz mar 50%-kal magasabb a termelesem. A megoldas itt is nagyon durva meg, sokat lehetne finomitani rajta, azonban igy is sok esetben garantalja azt, hogy amint az ellenfellel szemben folenybe kerulok, ott is maradok.
Nagyjabol ennyit kell most tudni rola. A kovetkezo lepesben tovabb finomitom a bolygok veszelyessegenek a felmereset, jo esellyel bevezetem az exposure szamolast, ami azt fogja megmondani, hogy egy bolygo mennyire van kiteve tamasasoknak – es ennek megfeleloen allapitom meg a vedelmi tartalekot. Valoszinuleg finomitok a zaklatasi taktikan is, es meg jobban fel fogom hasznalni a tartalekaimat a tamadasnal vagy a vedekezesnel. A kezdeti szakaszban bevezetem a veszelyeztetettseg figyeleset is.
Ahhoz kepest, hogy miota fejlesztem a botom, meg mindig eleg sok fejlesztesi/hangolasi lepes van. Az utolso beadasi hatarido November vege. Remelem addigra sikerul bejutnom legalabb az elso 200-ba.
Mint a fentiekbol kiderult, a ket batyam is jatszik. A kozepso batyam botja – nem keves munka aran – sokkal jobb, mint az enyem. A legidosebbe meg csak az 1200 koruli tartomanyban cirkal, de ha azt tekintjuk, hogy ez meg csak talan a harmadik vagy negyedik verzioja a botjanak, amit bekuldott, en latok benne fantaziat. Majd tudositok, ha lesz valami..

Februarban neveztem eloszor a Google AI challengre, amikor Tront jatszo botot kellett irni. Utolag atgondolva a dolgot, az a feladat nem is annyira az AIrol szolt, inkabb a min-max algoritmus ugyes implementalasarol. Ennek megfeleloen nem voltam tulzottan lelkes, amikor a batyam bejelentette, hogy megint van egy AI challenge, de azert megnezegettem, mi a lenyeg iden.
A mostani jatek szinten nagyon egyszeru elso latasra: Vannak bolygok, amik lehetnek a jatekose, az ellenfele, illetve fuggetlenek. Minden bolygon van egy bizonyos szamu hajo, es a jatekos es az ellenfel bolygoi folyamatosan termelik az uj hajokat a merettol fuggo mennyisegben. A bolygokrol el lehet kuldeni flottakat masik bolyogkra, akik vagy megtamadjak azt (ha ellenfel vagy fuggetlen) vagy csatlakoznak hozza (ha sajat).
Tobbfelekeppen lehet nyerni:
1: lenyomod az ellenfelet teljesen, azaz se bolyogja, se eppen repulo flottaja nincs
2: Ha lejar a kor limit (jelenleg 200) es neked tobb hajod van.
3: Ha az ellenfel rossz lepest ad ki, akkor azonnal vesztett, szoval ilyenkor is te nyertel..
Az utobbi ketto mod amugy dontetlent is eredmenyezhet.
Ez a jatek, bar elsore nagyon egyszerunek latszik, valojaban egeszen osszetett taktikakat igenyelhet, es nincs olyan algoritmus, amivel pikk-pakk meg lehetne nyerni.
Peldaul, azonnal kikuldesz minden hajot, vagy nehany koronkent egy nagyobb flottat? Mennyit tartasz a bolygokon? Figyeled-e az ellenfel mozgasat, vagy csak azzal foglalkozol, hogy te mit akarsz csinalni? A fuggetleneket tamadod, vagy az ellenfelet?
Az en elso botom annyira egyszeru volt, mint egy bot (pun intended). Egy bolygorol kuldtem ki hajokat, az osszes tobbi csak erre a bolygora kuldott minden termelest, meghagyva mindig a bolygon kb. 40 hajot. A “fo” bolygo meg kivalasztott a palyarol egy nagy bolygot, aztan odakuldott mindent, amig el nem foglalta. Biztos vannak olyan botok, akiket ezzel a taktikaval meg lehet verni, de nagyon hamar rajottem, hogy a hajoim folosleges utaztatasa eleg folosleges, inkabb minden bolygorol azonnal el kene kuldeni a termelest a celbolygora.
Innen indultam. Mostanra a kod sokszorosan bonyolultabb, a jatek allasatol fuggoen valtoztatja a taktikajat a bot, a bolygok figyelik, hogy tamadjak-e oket, es ha igen, akkor vedekeznek, etc. Nagyon tetszik a kihivas, rengeteget gondolkozom azon, hogy lehetne fejleszteni a taktikat meg, es nezem a meccseimet, hogy hogyan nyertem vagy miert vesztettem.
Akit erdekel, megnezheti az aktualis botom meccseit itt: Moonson

Egy tovabbi elonye a mostani versenynek, hogy ugy gondoltam, most a valtozatossag kedveert nem Javaban, hanem Pyhonban fogom a botom kesziteni. Korabban a python nyelvvel csak futolag talalkoztam, atolvastam egy konyvet, meg szuttyogtem kicsit a konzolon, de semmi komolyat nem alkottam benne. Ehhez kepest most egy csomo dolgot fel kellett hasznalom, amirol eddig csak halvany elkepzelesem volt, hogy jobb, okosabb, hatekonyabb kodot irjak.
Vicces, mennyire alkalmasak ezek a versenyek a programozas elsajatitasara. A kezdocsomagban kapsz egy kicsi programot, amit kedvedre modosithatsz. Kezdheted egy passziv bottal: semmi mas parancsot nem ad ki, csak a kor veget. Aztan mondjuk fogod a bolygok listajat, kivalasztasz egyet, es odakuldesz 50 hajot. Megnezed, hogy mi tortenik. Aztan tovabb, tovabb, mig a vegen mar lambdakkal es list comprehensionnel dobalozol, hogy egy sorban legyen meg az ellenfel ot legjobb bolygojanak a listaja.
Minden ismerosomnek nagyon ajanlom, aki erdeklodik a programozas irant. Jo kis ujjgyakorlat, kellemes kihivas, es bar gyozni szinte lehetetlen (nagyon okos csavok is jatszanak am) nagyon jo latni, amikor a botod nyer egy harcot.

The challenge this year is to create a bot which plays Tron against other bots. Random maps, random opponents.  My brother, knowing me, gave me a link.

I jumped to this opportunity. Of course. But let me get this clear: I never dreamed about winning. There are a lot of people out there who is better educated and smarter than me. On the other hand, this was the perfect playground to test some of my theories against other people.

I came up with the idea of multi layered AI a few years ago, but so far I never tried to create an actual program based on it. The essence of the idea is that a decision is made by going through several layers, which collect the possible decisions or filter them. (obviously collecting should come first)

Besides I was aiming at the (nonexistant) style prize, so that the abstraction of my code was a king who wants to build the longest wall. Every time when a section of the wall is complete, he asks the council which way to go next. Sadly I needed to abandon this, and create “ugly” code instead, because I didn’t have enough time.

So here is the basic structure of my first bot:

- The first layer is the Master of War. He knows that we need to go close to the “enemy”, so that we can close him out. On the other hand, he won’t let us to go too close, because that way the builders would clash.

- The second layer is the Master of Geography. He knows the lay of the land and can tell the king which way will lead the builders to a dead end. The first version of this Master was lazy and just looked around from the hilltop. So the king fired him and nominated a new one, who used scouts to look around.

- The third layer is the Master of Spies. He watches the enemy, keeps tabs of his movements and tries to predict which way he goes next.

- The Fool of the King was kicked out of the council. All he wanted was building a heart shaped wall on Valentines day, but we didn’t have the resources.

Based on the chances the King made a decision. (basically just took the one with the highest chance or picked one randomly from the one with the highest chances if there were more than one with the same chance.)

All in all, the bot was fairly successful, taking me the the first hundred, without using any specialized algorithm of game theory.

I hope next year it will be different. I’d like to see a game where your bot have to cooperate with other bots. That is not something that can be won by using pure mathematics. It’s much closer to real AI.