After trying to define what makes an adventure ‘Epic’, let’s take a look at the AI. The scope is somewhat bigger than just the epic adventures, this time we need to lay down the foundation for NPC AI driven quest/task/job/adventure generation first.

NPC AI In separation

Previously, I was writing on this blog about NPC AI based on Maslow’s Hierarchy of Needs. (In Hungarian, so I’m linking only the wikipedia now..) Simply put, this system defines the same levels in the same order for humans, as it is outlined in Maslow’s Hierarchy, then uses them to determine the next action for the NPC. Naturally, different races have their own structure, and make their decisions by their own needs.

While in theory this is a very good system, in practice it is not the best for the imminent action, when the entity is expected to react when – for example – it is attacked. Also, quest givers are usually not expected to have their own lives, or to do anything else than to interact with the player. It is actually better to have a simple state based system for reactions, and use the maslowian system for long term goals, and with that, quest generation.

Beside of the memory, and the sense of the environment, the entity needs a sense of future needs. Let’s take the blacksmith of the village, as an example, and analyse his long term needs.

On the lowest level, his everyday needs: Air, food, something to drink, other body functions, sex. For three of these functions – food, drink, sex – he can make long term plans. Having food in the storage, having some water in the pitcher, being in good terms with his wife, these are all things that he can and will do to keep the status quo.

One level up, safety. To prevent future accidents, he takes good care of his tools, and protective clothing – mittens, apron. He puts out the fire for the night so that the building won’t catch fire in the night. He locks the door so no-one steals his materials, tools. Safety is one of those things where you need to do a lot of things to prevent future bad things from happening.

Then the next level: “belongingness”. (I found this wonderful word on the wiki.. ) There are a lot of groups the smith belongs to. His family, his friends, the guild of craftsmen, the angling club (see below), the village, the country, humans.. Although the role of the entity is usually more significant in a smaller group, meaning that he is more important in his family than as a human, he has obligations in each group. He will earn money to be able to put bread on the table. He will go to the local pub and drink an ale with his friends, and if a friend needs a loan, he will give some money to them. And so on. The future need on this level of the hierarchy is to maintain social status and to provide safety for the group.

Esteem, the next level, is when our smith shows his ambition. He wants to be known for something: Be a good father, be a good friend, be the leader of the craft guild, the best smith in the country, etc. He is working hard on this, to earn reputation. In game terms, the previous level means that he works to keep neutral reputation in the groups he belongs to by fulfilling his role. This level means that he is working to increase his reputation beyond neutral.

And the last level is self actualization. As I mentioned above, he is a member of the angling club, because his hobby is fishing. He likes fishing, not just for the fish, but also for fulfilling his need of solitude, and the time he spends out at the lake. He plans for these fishing trips, checks his equipment, gets the right kind of lure, talks to other anglers about good places, big catches, etc.

As we can see, these levels are somewhat interconnected (work -> money -> food) and you can be in several states at once – you might be worried at once about getting food for tomorrow, and forgetting to lock the smithy door. Also, the degree of your need can vary, you might be worried about having food next week, but that is probably not as worrying as not having food for tomorrow; you can quantify the need as a percentage value, for example. Thus, a simple finite state machine would not be sufficient for this,  but a fuzzy logic system might work well. Aside of this, every NPC must have a definition of groups it is part of, as well as a “personality”, which would describe the importance of each levels for a given NPC. For example, we might have an NPC with a high importance for self actualization, and low importance for safety. Putting these two together the NPC is willing to go to prison to defend it’s art. (see Marquis de Sade) Personality also needs to define the occupation, hobby, and interests of the character. This importance of the need can be sometimes expressed as the speed the need raises – if the NPC eats more, it will need to store more food to have reserves for the whole month.

NPC generated quests

Now, let’s take a look at this system. What kind of quests can we generate based on this system? Let’s put together a few examples.

On the physiological level, the NPC might need help to gather food, get something to drink, or get sex. Also, the NPC may offer these things and is looking for someone to buy them. (this latter one is actually the second level, but connected to the needs of other NPC on the first level). Possible quests here is “get meat”, “help with the harvest”, “remove the troll from under the bridge which prevents us to get fresh water”, “get me a specific type of wine”. It’s important to realize, that we mix the levels here; the third one is safety as well as the basic need of drinking, and the fourth one is actually more like self actualization than basic need. The common point with all of these is that the NPC has a goal, but for certain reasons it requires help to achieve them – if it would be easy, the NPC would do it itself. A possible Epic quest on this level is to take food into a castle that is under siege and surrounded by enemies.

(I’d like to emphasize one thing here: There might be several different ways to actually solve these quests, and that is intentionally part of the system. The NPC doesn’t tell you which or how much animals you need to kill to get meat. It doesn’t tell you to kill the troll, if you scare it away for good, it can live with that. It doesn’t care about whether you steal the wine, buy it or take it out from your backpack.)

Second level: The source of the “Kill ten rats” type of missions. Defend, escort the npc, but also, help him to get materials for his everyday job, catch the robber who robbed him, etc, etc. Carrying items from point A to point B, including the safety of the item. Also, health is here, in this category, so a quest to find a rare herb to cure an illness will be generated on this level. Also, taking crafts into consideration, the NPC may even ask you to help him to repair his roof, for a reward, of course. Epic quest here is to save children from a burning house.

Third level: Carry messages, social interactions, solving group level issues. Diplomacy, quests related to emotions. Epic quest here is to prevent a war between two kingdoms.

Etc.

It is important to notice that the quests you get in the MMOs today are usually of the lower levels. Because NPCs doesn’t have real lives, they don’t have higher level needs. There are some quests when the male npc is in love with the female npc, and asks you to collect a bunch of flowers that he can then give to her, but, beyond the obvious question (“Why the hell don’t you go and pick those f*cking flowers yourself, mate?”) these are also really bad examples for the quests of the third level. Maslow’s hierarchy would allow much more than that.

In the next article, I’ll take a look at the problems of numbers – the need for simulating the crowd.

Is it possible to create an emergent system in an MMO where the interactions and needs of the NPCs (in the form of independent AIs) can lead to quests on the epic scale?

I don’t know the answer to that question, but I have a few thoughts about this topic, which might help the reader to come to their own conclusions.

So, what I want to talk about here are the following:

• What makes an adventure ‘Epic‘
• Requirements and limitations of the AI system
  • The NPC AI in separation
  • The problems with numbers
  • Simulation of the masses
  • Emergent behaviour
• The place of the epic adventure in the game

I might need to slice this up a bit and write a handful of articles instead of just one, but I hope it will worth reading them.

What makes an adventure ‘Epic’

To be somewhat cheeky, let’s say that from the Lotro perspective “epic quest” means that you have to travel four times as much as with a normal quest. Jokes aside, I’d rather not use existing MMOs as role models for this. Instead, let’s find some examples in literacy.

The first one being Beowulf. He is a scandinavian hero, who fights a demon, then the demons mother to save the people of a kingdom. Later, he becomes the king, and – as an old man – sets out to fight a dragon. He slays the dragon, and gets a mortal wound. On the wikipedia it is described as “Beowulf is considered an epic poem in that the main character is a hero who travels great distances to prove his strength at impossible odds against supernatural demons and beasts.” We can now see that Turbine got it right about the travelling part, but the impossible odds part is somewhat lacking.

The second one is a fantasy story. Fantasy literacy is usually full of epic adventures and pathos, so it’s a very good starting point. In our case, the one I want to use as an example is a part of the “Nine Prices in Amber”. Sorry for the spoilers, but be assured, when reading the whole series, you will still find a lot of wonders and surprises.

So, Prince Corwin, our main character – with the help of his brother – gathers an army to conquer the castle of his father from the usurper. To get to the castle, they need to go up a stair with a thousand steps to a plateau, where every step is defended by a soldier. At this point their army is already demolished, leaving only a handful mercenaries. The two brothers and their small company begin their ascent, the mercenaries first, then Corwin’s brother. The brother then falls down from the stairs, and Corwin throws a deck of magic cards after him – which would have been his only chance of survival. Corwin alone continues the fight, and actually makes it to the plateau, where he loses the fight, and gets imprisoned. (Believe me, the original is much more enjoyable than this succinct description of the events)

Why do I consider this epic? Well, looking into it, we find common elements – impossible task, long journey – and something that is also present in Beowulf, but less apparently: a just cause. Also, in both cases, there is the notion of self sacrifice – Beowulf dies for his people, Corwin saves his brother, and because of that he gets imprisoned. On the other hand, Beowulf’s story ends well – his death is not futile, in the end he saves his people from the dragon. (Corwin’s story doesn’t end here.. but his fate gets much worse by the end of the first book.)

I was thinking about a good third example (we need three of anything, because that is the magic number) and one good example I found is the biblical story of David and Goliath. I’m pretty sure everyone is familiar with it, but still, here’s a short recap: Goliath is a giant of a man, who is challenging the army of Saul for forty days. On the fortieth day, David, a boy, goes there for some reason, hears Goliath’s challenge, and answers it. Without wearing armour, he goes out to the field, and kills the giant using a sling and a stone. No long journey this time (I knew it’s not required! ) but again, impossible challenge, just cause. No self sacrifice either, not more than what the task requires, actually. What is particularly interesting here, is that David didn’t win because of his supernatural skill or strength. Instead, he used his wit to meet the challenge. Outsmarting your enemy is a common motive in the epic stories, let’s just think about the challenges of Hercules, or Loki, the trickster.

So, let’s collect the list:

• Just cause: The hero must have a motive that is not selfish, something that serves the public well-being
• Impossible challenge: Something that is (or seems) impossible for the average woman or man.
• Long journey: If travel itself is more than just a click of a button, a long journey can be the challenge in itself.
• Self sacrifice: Failure often means death
• Need of thinking: The solution might require more than physical prowess

In the context of MMOs, putting the player in mortal danger is not as serious as it is in real life – given that in most MMOs death is not much more than a temporary annoyance. One way to solve this problem is to exchange mortality with finality: the player can try to do the quest only once, and that’s it. Failing the quest is final, there is no retry. Also, physical prowess is an in-game feature, while the thinking is done by the player, sitting in front of the computer.

(Some might argue that completing an epic quest it’s only hard for the first player, then he writes everything down on the wiki, and everybody will be able to finish the quest easily after that. In our case it’s not a valid argument, because the quest is not scripted, it is emerging from the interaction of NPCs, thus it is never the same. But even in a scripted system you can say that the first one to solve this quest will get the epic reward, everyone else will get the normal reward. This is not a perfect solution, but this problem is not the one either that I want to solve.)

To put it simply, our emergent system must be able to

• Either identify quests/tasks/jobs/adventures for which several of the above are true
• Or specifically generate quests with the above-mentioned qualities

In the next few blog post I’ll look at the AI perspective, as well as how the epic adventure can be part of the game world. Stay tuned.

Az előző cikkben megemlítettem, hogy a Maslow hierarchia csak az épelméjű emberekre érvényes, más fajra, elmeállapotra egész másféle piramis lenne érvényes.
Na de milyen? Próbáljuk meg általánosítani a problémát: Mit lehet változtatni a piramison?

• Szintek elvétele
• Szintek áthelyezése
• Szintek duplikálása
• Szintek összevonása
• Szintek “erősségének” változtatása
• Szintek hozzáadása
• .. és a fentiek bekövetkezése/változása az idők folyamán…
• .. vagy valami esemény hatására

Nyilván van még más is, ami hirtelen nem jutott eszembe. De ez is bőven elég, ha arra gondolunk, hogy ezekből több is lehetséges 1xe. Egyet mondjuk helyből kiejtenék: Nem látom értelmét ebben a kontextusban a szintek duplikálásának.
Azt is fontos még itt leírni, hogy minél jobban eltér a piramis a miénktől, annál meglepőbb, elképzelhetetlenebb lesz a létrejövő élő(?)lény. Van egy fok, ami után gyakorlatilag már képtelenek vagyunk felfogni, hogy milyen is lenne..

Most pedig menjünk sorban:
Ha elveszünk egy szintet, érdekes élőlényt kapunk. Ha a tetejéről, akkor egy ősembert/elmaradott, törzsi embert kapunk. Felülről a második: antiszociális. Felülről a harmadik: szociopata. Felülről a negyedik: Erre már szavam sincs. Valaki, aki nem törődik a biztonságával; ez talán nem is olyan ritka, mint gondolnánk. Az igazán érdekes a legalsó szint elvétele lesz: Ha feltételezzük, hogy az egyed nem pusztul el ennek a szintnek az elvételétől, akkor valami szellemi parazitát, ködlényt vagy ilyesmit kapunk, aminek csak magasabb rendű szellemi tevékenységei vannak. Nem hangzik rosszul persze..
Azt le se írom, hogy több szint elvételével milyen kombinációkat kapunk, szerintem mindenki látja, milyen érdekes ez.

A szintek áthelyezése talán nem is annyira idegen a gondolkozásunktól. Ott van például az Alapítvány valamelyik részében a tudós, aki (külső behatásra) addig dolgozik, amíg belehal a munkába, etc. Ezt a változást el tudjuk képzelni, hogy milyen, sőt, úgy gondolom, hogy valahol része is a személyiségünknek. (pl. nem tudunk nyugodtani pisilni a vécén, ha nincs becsukva az ajtó, mert nem érezzük biztonságban magunkat) Hasonló a szintek összevonása is, ahol azt mondjuk, hogy valamely igényünk egyenértékűvé válik mással, például a security ugyanazon a szinten lesz, ahol az önmagunk megvalósítása. Ez a szituáció akkor lesz furcsa, ha két, nem egymás fölötti szintet vonunk össze, azaz az egyik szint igényei át is helyeződnek a piramison belül.

A szintek erősségének változását én úgy képzelem el, hogy az adott szint kielégítettségének magasabb szintet kell elérnie ahhoz, hogy a következő szinttel foglalkozhasson az egyed, azaz mondjuk nem fog a saját biztonságával törődni addig, amíg dugig nem ette magát. Ennek egy végletekig vitt változata, amikor azt mondjuk, hogy minden egyes szintet TELJESEN ki kell elégíteni ahhoz, hogy a következő szinttel foglalkozzunk. Ez azzal az érdekes viselkedéssel jár, hogy az egyed néha “elveszíti a fonalat”, abbahagyja, amit csinál, és valami másba fog – azaz egy alsóbb szint közben felmerülő igényét elégíti ki.

Ami számunkra már-már elképzelhetetlen, az egy új szint beiktatása a piramisba. Legjobban példákon keresztül tudjuk megérteni: a hím sáska feláldozza magát, hogy utódokat nemzzen. Ez így elég messze van a mi emberi gondolkozásunktól. Ezt én leginkább úgy tudnám megfogalmazni, hogy az utódnemzés szükséglete az fontosabb, mint a self security. De ennél sokkal furábbakat is el tudunk képzelni, mondjuk egy olyat, hogy “minden nap egyél egy virágot”, mint legalsó szint. Amíg ez nincs kielégítve, nem eszel, nem iszol, nem mész vécére.. Szar lesz neked télen. A lehetőségek itt végtelenek.

Azt, hogy időben, vagy egy esemény hatására megváltozik a piramis, jól tudjuk. Ha valaki nem halálos bűncselekmény áldozata lesz, utána jó eséllyel nőni fog a biztonság iránti igénye. Ahogy öregszünk, a szex szerepe egyre kisebb, majd gyakorlatilag teljesen eltűnik rá az igény. Ezt sem kell tovább ragozni.

Ez az egész ott válik érdekessé, amikor megfordítjuk a problémát. Ha nem azon gondolkozunk el, hogy a piramis változása milyen viselkedést indukál, hanem egy összetett viselkedési mintát próbálunk modellezni egy szükségleti piramissal. Ez egy olyan gyakorlat, amit a terjedelmessége miatt most nem fogok megejteni, de a következő bejegyzésből ki fog derülni, miért érdekes ez..

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.

Egy ideig nem írtam most. Ennek két oka volt: a költözés és a Google AI Challenge
Szombaton áköltöztünk. Három óra volt a cuccokat levinni a kocsihoz, átfuvarozni és felvinni az új lakásba, aztán kezdődött az otthoni pakolás. Estére sikerült a hálószobát olyanná varázsolni, hogy tudjunk benne aludni, és előszedni a legfontosabb dolgokat a mindennapos élethez. Másnap összeraktunk egy csomó bútort, pakoltunk, takarítottunk. Harmadnap visszamentünk a régi lakásba, ott is kitakarítottunk és összeszedtünk mindent, ami még ott maradt. Így telt el a hétvége, de gyakorlatilag azóta is folyamatosan dolgozunk a lakáson, illetve a költözéssel kapcsolatos problémákon, mint a parkolási engedély vásárlása, illetve a cím átíratása mindenhol. Már csak egy szobában vannak dobozok, zsákok és szétszedett bútorok, ami egészen kényelmes. Az is nagyon jó amúgy, hogy 25 percre van a hely a munkahelytől, az eddigi 1 óra fölötti bejáráshoz képest.
Az AI challenge érdekesen indult. A legutóbbi esemény óta nem voltam olyan nagyon lelkes, hogy megint résztvegyek, de a bátyáim beszélgetése alapján úgy gondoltam, ez érdekesebb lehet. Így aztán elkezdtem beleásni magam a problémába, és teljesen magával ragadott a probléma. Fogok írni majd egy másik blogbejegyzést is róla, mert érdekes dolgokat találtunk ki.

Egyszer egy palyazatra kezdtem el irni egy novellat Spiral cimmel, amit vegul nem fejeztem be. Nemreg megtalaltam a vinyomon egy takaritas alkalmaval, es ujraolvastam.

A tortenet a kozeli jovoben jatszodik, ennek megfeleloen megprobaltam nehany trendet megjosolni. Egy igen erdekes otlet, amit akar mar jelenleg is konnyen meg lehetne olvasni, egy hirolvaso agent.

A tortenetben a fohos elokap egy kis kutyut (kb. okostelefon) es elkezd rajta hireket olvasni. Az agent (bocs, nem akarom a ugynok vagy az agens szot hasznalni) pedig – on the fly – a fohos olvasasi szokasai es mas, kezzel hozzaadott kriteriumok alapjan atszinezgeti bizonyos hirek (valojaban focimek) hatteret, kiemelve azokat, amik erdekesek lehetnek.

Az alkalmazas technikai resze, eltekintve a szakertoi rendszer / AI vonulattol, aranylag konnyen megirhato lenne. Atszinezni a hattereket a szovegelemzes eredmenyetol fuggoen nem egy bonyolult dolog a html-ben.
Az agent lehetne egy bongeszoben futo – akar javascript alapu, vagy greasemonkey – kiegeszites, vagy egy webes app, ami egy sima formazo/rendezo filterkent mukodne, es egyebkent csak a normalis hirolvaso oldalunk tartalmat szurne at magan. Es termeszetesen hasznalhatnank pl. a google readerben felvett feed-eket alapul.

Ehhez valamennyire hasonlo – amennyit tudok rola – a reader-nek a magic alapu rendezese a google readerben. Alapvetoen csak ket problemam van vele: a sorrendet nem szeretem megvaltoztatni, raadasul az egesz eleg homalyos, nemigen van kozvetlen rahatasom arra, hogy miket szeretnek es nem szeretnek latni – eltekintve a like es not interested gomboktol, amik az egesz cikkre vonatkoznak, nem egy adott, specifikus, altalam meghatarozott temara.

Ha idom es kitartasom lenne, szerintem neki is allnek megirni ezt az alkalmazast. Erdekelnek az AI vonzatai, es hasznos tool is lenne.

Elgondolkoztam a minap azon, hogy hogyan kellene megoldani a “szovegdobozok automatikus elrendezese” funkciot. A feladat – mint azt mar rengeteg toolban lathattuk – nem trivialis. Reszben azert, mert mindenkinek masfele elrendezes a jo, reszben pedig azert, mert nehez szavakba onteni, hogy egy graf mitol “nez ki jol”.

Az elso megkozelitesem pusztan matematikai: megprobalom azokat a dobozokat kozepre hozni, amiknek sok kapcsolata van, es periferiara rakni azokat, amiknek keves. Mindezt azon feltetelezes alapjan, hogy sok kapcsolattal a fontos otletek rendelkeznek, es azokat megilleti a kozponti hely. A problema itt mindossze annyi, hogy a kesobbi boviteseknel siman van arra esely, hogy a fontos otletek tovabbi kapcsolatokat kapjanak, amihez viszont nem lesz eleg hely.

Elgondolkoztam azonban a jatekok AI-ahoz hasonlo, a felhasznalo viselkedeset figyelo es elemzo kodon is. Ez osszessegeben nyilvan hihetetlenul bonyolult, de aranylag konnyen ki lehet olyasmit deriteni, hogy az uj elemek letrahozasakor milyen tavol helyezi a felhasznalo az ujat a meglevoktol, valamint olyanokat is, hogy elre igazitva szereti a dolgokat, vagy csak ugy szethanyva, egymastol fuggetlenul. Egy erdekes gondolat ennek kapcsan, hogy ezt az extra infot le is kellene menteni a graf melle, amikor a felhasznalo menti azt, hiszen egyebkent ket szerkesztes kozott elveszne a history.. Ami viszont egybol elvezet a tobb felhasznalo altal mahinalt grafokhoz..

De eloszor is baby steps. Addig ugyse lesz szukseg erre a funkciora, amig nincs egy mukodo alkalmazas, mondjuk a v0.4.

For English please go here.

 

Az idei Google AI Challenge feladata, hogy irj egy botot, ami Tront jatszik. Mas botok ellen. Batyam, tudva, h erdekel az ilyesmi, adott egy linket.

Fejest ugrottam bele. Nem erdekeltek a strategiai guide-ok, mivel eleg jol ertek hozza, raadasul nem is nyerni akartam, hanem kicsit kiserletezgetni. Termeszetesen a kiserletezgetes egyik fokmeroje az, hogy milyen eredmenyt erek el, es ebben sokat segit, hogy folyamatosan versenyeztetik a botokat, bar a konkret verseny csak valamikor a honap vegen zajlik majd.

Nehany eve mar erlelgetem magamban a tobb retegu AI gondolatat, ahol a lenyeg az, hogy a donteshozas tobb, kulonbozo szerepkort illetve nezopontot megvalosito retegen fut keresztul, amik hozzaadnak es elvesznek lehetosegeket, illetve sulyozzak a meglevoket. (ertelemszeruen: az elso retegek osszegyujtik, az utana kovetkezoek megszurik oket.) Ezt az alap0tletet hasznaltam most fel, amikor megirtam a botomat.

Mivel stilusdijra is gyurok (nem mintha lenne ilyen) a botom kodja azt az elkepzelest tartja a kozeppontban, hogy a kiraly akar egy falat epiteni, es mindig, amikor elkeszul egy resze a falnak, akkor tanacskozik a tanacsosaival, hogy a kovetkezo lepest merre tovabb. A kovetkezo megjegyzesben mutatok erre kodot is, itt csak az alapstrukturat irom le:

- Az elso reteg a Master of War. Tisztaban van vele, hogy messzirol nem lehet harcolni, de tul kozel sem akar menni, igy aszerint sulyozza a lehetosegeket, hogy mindig egy bizonyos tavolsagra legyen a masik falepitotol. (elvegre ot szeretnenk letolni a terkeprol.)

- A masodik reteg (bar lehetne az elso is) a Master of Geography. O az, aki kikuldi a felderitoket, hogy kitalaljak, merre all sok hely a rendelkezesunkre. A korabbi valtozata csak felment a hegytetore es korulnezett egy latcsovel, de ez nem mukodott olyan jol, ugyhogy ot kirugta a kiraly.

- A harmadik reteg a Master of Spies. O az ellenfel mozgasat figyeli, es probalja kitalalni, hogy hogyan zarhatnank ot el magunktol.

A kiraly bolondjat kirugtak. O csak annyit akart, hogy februar 14-en rajzoljunk egy szivet, de ez nem tunt megvalosithatonak a rendelkezesre allo terulet jellege miatt.

Jelenleg a 91. vagyok a korulbelul 600-bol. Magyarazat a fenti diagrammhoz: Az elejen az alapcsomag volt csak benevezve, ami, ahogy nott a nevezok szama es megszulettek az elso igazi botok, szepen vesztett a helyezesebol. Feb 8-an beneveztem az elso kesz valtozatot a botombol (meg a regi Master of Geography-val) ekkor szepen felugrottam a 250. hely kornyekere. Ott el is vegetalgattam egeszen ma reggelig, amikor is feltoltottem az uj verziot – ami tegnap este kesz volt mar, de egy oran keresztul hiaba probaltam feltolteni, technikai okok miatt nem sikerult. Az uj verzio a felderitokkel lathatoan sokkal jobb eredmenyeket er el, miota feltoltottem, a 90-100. hely kornyeken vagyok.

Íme az első screenshot az “legközelebbi felé mozgunk és ha odaértünk, megállunk” viselkedéshez:

A kék az alapszín, a világoskék a megtett utat jelzi, a sárgák pedig a “végpontok”, ahol a kis szigetek megállapodtak. A következő kísérletben megpróbálok egy olyan vizsgálatot beillesztni, ahol a kis szigetek mindig a környéken lévő legnagyobb sziget felé igyekeznek..

Mondanom sem kell, ez a kép is nagyszerűen mutatja, hogy ebből a szabályrendszerből csak egy valamivel rendezettebb káosz alakul ki, de egészen távol van attól, hogy egy valódi sziget alakuljon ki..