Robomoku: Amőbázó Lego MindStorm robot

Robotika beadandó, 2003-2004. második félév

Lőrentey Károly, Nagy András, Pehartz Gábor

Mozi!

Tekintse meg akciófilmünket!

Ha tetszik, le is töltheti! A filmet eredeti hossza (harminchárom perc!) miatt négyféle rövidített változatban bocsátottunk az Ön rendelkezésre:

• Négyszeres gyorsítás (3p 37mp, 24Mb)
• Tízszeres gyorsítás (1p 27mp, 9.5Mb)
• Százszoros gyorsítás (executive summary, 9mp, 1.1Mb)
• Eredeti változat (hosszú téli estékre, 33p 50mp, 153Mb)

Rövidfilmek

• Lépéskeresés
• Lépegető robot
• A magasabbrendű emberi intelligencia mesterlépése
• A robot felismeri a lépést
• A robot egy lépése közelről
• A magasabbrendű emberi intelligencia idejében felismeri a veszélyt
• A robot cselhez folyamodik
• A magasabbrendű emberi intelligencia csúfosan veszít

Képek

Hardver

A robot lényege egy egymásra merőleges tengelyeken mozgatható író/olvasó fej, melyet egy leereszthető filctoll és egy fényérzékelő segítségével implementáltunk. A fej mozgását a rajta és a mozgó kereten elhelyezett fogaslécek segítik elő, melyek az alattuk lévő meghajtott fogaskerekeken görgethetők. A fej mindenkori aktuális helyzete a mozgatómotorok végső áttéte után behelyezett mozgásérzékelők segítségével kérdezhető le. (Az érzékelők konzisztensebben működnének, ha közvetlenül a motorra, vagy az első áttét után volnának bekötve. Ennek implementációját a nyájas olvasóra bízzuk.)

A leeresztett filctoll a talapzat erre kialakított sík felületére elhelyezett papírlapon nyomot hagy. A robot a felhasználó által besatírozott területet a fényérzékelő segítségével tudja felismerni.

A robotot teljes egészében egyetlen autonóm vezérlő egység irányítja. A mozgatandó szerkezetek jelentős tömege miatt ehhez nem elegendő a ceruzaelemek által nyújtott energia, így a robot csak külső tápellátással működik megbízhatóan. (Az írófejet mozgató bonyolult mechanizmus ellensúlyozására mozgó ellensúlyok elhelyezésére is szükség volt.)

A robot működését a satírozáson kívül egy kézzel működtethető kapcsológomb segítségével befolyásolhatjuk. A kapcsoló lenyomásával indíthatjuk el a játékot, és minden lépés után a kapcsoló lenyomásával jelezhetjük, hogy a robot következik. A kapcsoló egy kis cselre is lehetőséget ad: ha a beolvasás fázisa közben nyomvatartjuk, akkor ezzel kikapcsoljuk a fényérzékelőt, így elkerülhetjük a tévesen felismert lépésekből eredő időveszteséget. Hasonlóan, ha a robotot a kapcsoló lenyomása közben kapcsoljuk be, kihagyhatjuk a tábla megrajzolását.

A fej pontos pozícionálását megnehezíti a hardver egyik kellemetlen jellegzetése, miszerint a mozgásérzékelő lépéshatárai más-más elmozdulásoknál jelentkeznek az egyik és a másik forgásirányban. Ennek következménye, hogy az író/olvasó fej balra és jobbra mozogva más-más táblafelosztást használ, ami néha félreolvasásokhoz vezethet.

Szoftver

A robotot vezérlő programot a BrickOS szabad forrású LEGO MindStorms operációs rendszer segítségével írtuk meg, C++ programozási nyelven, a GCC fordító keresztfordítási lehetőségeit kihasználva.

A vezérlő program üzemmódjai:

1. Bekapcsolás után a robot kalibrációs üzemmódban van. A fej ekkor nullpozícióból mindkét tengelyen ütközésig elmozdul. (Az ütközés a mozgásérzékelő figyelésével könnyen felismerhető.) A teljes elmozdulás mértékéből a robot kiszámolja a leendő tábla méreteit.
2. A kalibráció után a tábla megrajzolása következik. A fej leeresztett tollal ütközéstől ütközésig tartó párhuzamos vonalakat rajzol, előbb függőleges, majd vízszintes irányban. Az egymást metsző vonalakból kialakul a pálya négyzetrácsa.
3. Ezután a robot a kapcsoló lenyomására várakozik. A felhasználó a lépésének megtétele (egy négyzet besatírozása) után a gomb lenyomásával jelzi, hogy a gép következik. A legelső lépés kihagyható, ha a felhasználó azt szeretné, hogy a robot kezdjen; minden más esetben kötelező pontosan egy négyzetet besatírozni.
4. A gomb lenyomásakor a robot a pálya cikkcakkszerű bejárásával megkeresi az újonnan besatírozott négyzetet. Ha ilyet talál, az ellenőrzés céljából nullpozícióba mozog, majd közvetlen pozícionálással megpróbálja ismét beolvasni. Ha ez az ellenőrzés nem jár sikerrel, akkor a megelőző sortól kezdve újrakezdi a beolvasást, egyébként a robot az 5. üzemmódba kerül. Ha a pálya végére érve egyáltalán nem találkozik új satírozással, (és nem a legelső lépést kereste) akkor a robot visszaugrik a 3. üzemmódba.
5. Ha sikerült beolvasni a felhasználó lépését, a robot kiszámolja az optimális következő lépést, odapozícionálja az író/olvasó fejet, majd egy kis rombusz rajzolásával megjelöli azt.
6. Ha bármelyik lépés után a robot felismeri, hogy valamelyik játékosnak sikerült öt darab egymás melletti négyzetet megszereznie, akkor a játék véget ér. A robot ezt a nyertes kilététől függő hangjelzéssel jelzi.

A tulajdonképpeni amőba-algoritmust egy egyszerű maximumkeresési feladatra vezettük vissza, a GNU Emacs editor gomoku.el programja alapján. Az algoritmus ötlete egyszerű: a tábla minden pontjára megkeresi, hogy mely olyan öt négyzetből álló vonalak metszik, melyek csak egyetlen játékos négyzeteit tartalmazzák. Minden ilyen vonalhoz egy pontértéket rendelünk, melyet a következő táblázatból olvashatunk le:

Üres vonal:	7
Egy saját négyzet:	15	Egy ellenséges négyzet:	35
Két saját négyzet:	400	Két ellenséges négyzet:	800
Három saját négyzet:	1800	Három ellenséges négyzet:	15000
Négy saját négyzet:	100000	Négy ellenséges négyzet:	800000

A következő lépéshez mindig azt a négyzetet választjuk, melyre a pontértékek összege a legmagasabb. Ez az egyszerű algoritmus (a fenti táblázattal) egy gyakorlatlan játékos számára meglepően nehéz ellenfélnek bizonyulhat.

A forráskód letölthető.

Az amőbajátékról érdekes információkat olvashatunk a http://renju.nu/r1rulhis.htm oldalon.