Arimaa
Az Arimaa kétszemélyes absztrakt stratégiai táblás játék, mely sakk-készlettel is játszható. Az Arimaa bizonyítottan „ellenállóbb” a számítógéppel szemben, mint a sakk, azaz nehezebb jól játszó programot írni rá, a kitalálásának ez volt a kezdeti célja.
| Arimaa | |
 | |
| Kezdőállás nincs, az alapsorokban a figurák elhelyezési sorrendje kötetlen | |
| Név | Arimaa |
| Műfaj | stratégiai |
| Játékos | 2 |
| Tábla | 8×8 mező, ebből négy kiemelt |
| Figurák | 16-16, sakk-készlettel is játszható |
| Kitaláló | Omar Syed, 2002 |
| Számítógépes változat | van |
Történet
szerkesztésAz Arimaa-t Omar Syed mesterséges intelligenciával foglalkozó számítógépes mérnök találta fel. Syedet Kaszparovnak a Deep Blue elleni veresége inspirálta arra, hogy egy olyan játékot készítsen, ami hagyományos sakk-készlettel játszható, a számítógépeknek nehéz nyerni benne, és szabályai olyan egyszerűek, hogy négyéves fia, Aamir is megérti őket (az „Arimaa” tulajdonképpen „Aamir” visszafelé, plusz egy „a” betű). 2002-ben Syed közzétette az Arimaa szabályait, és meghirdetett egy 10000$-os díjat, amit 2020-ig évente megpróbálhat elnyerni az első számítógépes program (ami olcsó, bárki számára elérhető hardveren fut), ami képes legyőzni egy erős emberi játékost egy legalább hat játékból álló sorozatban.[1] A szabadalmat a Syedek megkapták az Arimaa szabályaira, és a játék neve is védett (lásd lejjebb).
Szabályok
szerkesztésAz Arimaa-t 8×8 mezős táblán játsszák, négy megkülönböztetett mezővel, ezek a csapdák, konkrétan a c3, f3, c6 és f6 mezők a szokásos jelölésben. A két játékos, Arany és Ezüst tizenhat-tizenhat figurát irányít. Ezek a következők (a „legerősebbtől” a leggyengébbig): egy elefánt (
), egy teve (
), két ló (
), két kutya (
), két macska (
) és nyolc nyúl (
). Játszható sakkfigurákkal, sakktáblán is, ez esetben a megnevezett állatok helyettesítője sorrendben: király, vezér, bástya, futó, huszár és gyalog.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| A játékosok kezdéskor tetszés szerint helyezik el figuráikat a saját soraikban. |
A játék célja egy saját nyúl eljuttatása az ellenfél alapsorába. Így Arany nyer például, ha egy arany nyulat juttat a nyolcadik sorra, Ezüst pedig ha az elsőre visz egy ezüst nyulat. Mivel azonban nehéz eljuttatni egy nyulat a célhoz, amíg tele van a tábla, egy közbenső cél az ellenfél bábuinak foglyul ejtése a csapdamezőre lökésükkel vagy húzásukkal.
A játék üres táblával kezdődik. Arany valamilyen elrendezésben elhelyezi tizenhat arany figuráját az első és második soron. Ezután Ezüst is lerakja a tizenhat ezüst bábut tetszés szerint a hetedik és nyolcadik soron. A jobb oldali ábra egy lehetséges kezdőállást mutat.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Miután a figurák felkerültek a táblára, a játékosok felváltva lépnek, Arany kezd. Egy kör egytől négy lépés végrehajtásából áll. Egy lépésben egy saját bábu a tőle balra, jobbra, előre vagy hátra levő, üres mezőre léphet, kivéve a nyulat, ami nem léphet hátrafelé. Egy kör lépései megtehetők egy figurával vagy bárhogyan szétoszthatók több között is. A körnek meg kell változtatnia a játék állását, tehát nem lehet például lépni egyet előre, majd hátra, azaz tulajdonképpen passzolni a kört.
A második diagram, ugyanebből a játékból, segít megérteni a lépés többi szabályát.
Egy játékos felhasználhat két lépést arra, hogy elmozdítsa az ellenfél egyik bábuját egy erősebb saját figurájával, amely szomszédos vele a négy irány valamelyikében. Például egy saját kutya elmozdíthatja az ellenfél nyulát vagy macskáját, de kutyáját, lovát, tevéjét vagy elefántját nem. Az erősebb bábu húzhatja vagy lökheti az ellenfél gyengébb figuráját. Húzásnál az erősebb bábu egy üres mezőre lép, a gyengébb pedig az eddig általa elfoglalt helyre mozdul. A d5-ön álló ezüst elefánt például léphetne a d4-re (vagy a c5-re, vagy az e5-re), és áthúzhatná az arany lovat a d6-ról a d5-re. Lökéskor a gyengébb bábu egy szomszédos, üres mezőre kerül, a helyére pedig az erősebb figura lép. A d3-on álló arany elefánt átlökhetné a d2-n álló ezüst nyulat az e2-re, majd elfoglalhatná a d2-t. Figyeljük meg, hogy a d2-n levő nyulat nem lehet a d1-re, c2-re vagy a d3-ra lökni, mert azok a mezők nem üresek.
Saját bábukat nem lehet így elmozdítani. Ezenkívül egy figura nem lökhet és húzhat egyszerre. Például a d3-as arany elefánt nem lökheti a d2-es ezüst nyulat az e2-re és húzhatja a c3-as ezüst nyulat a d3-ra egyszerre. Egy elefántot nem lehet elmozdítani, mivel nincs nála erősebb figura.
Egy olyan bábu, amely szomszédos az ellenfél egy erősebb figurájával, bénult, hacsak nem szomszédos egy saját színű bábuval is. A bénult figurákkal tulajdonosuk nem léphet, de az ellenfél elmozdíthatja őket. Egy bénult figura megbéníthat egy nála is gyengébbet. Az a7-en álló ezüst nyúl bénult, de a d2-n levő szabadon mozoghat, mert szomszédos egy másik ezüst figurával. Hasonlóan, a b7-es arany nyúl bénult, de a c1-es arany macska nem az. Az a6-on és b6-on álló kutyák nem bénítják meg egymást, mert egyforma erősek. Elefántot nem lehet megbénítani, mert nincs nála erősebb, de egy elefánt lehet blokkolva (azaz körülvéve az ellenfél figuráival úgy, hogy nem képes semerre sem mozdulni).
Ha egy bábu csapdamezőre kerül, foglyul esik és lekerül a tábláról, kivéve, ha áll mellette saját színű bábu. Ha ezüst jönne, foglyul ejthetné a d6-os arany lovat, ha a c6-ra lökné a d5-ön álló elefántjával. Egy csapdamezőn álló figura akkor is foglyul esik, ha az összes saját színű szomszédja máshová kerül. Így ha a c4-es ezüst nyúl és a c2-es ezüst ló elmozdul, önkéntesen vagy az ellenfél által, a c3-n álló ezüst nyúl foglyul esik.
Fontos, hogy egy figura önként is léphet csapdamezőre akkor is, ha ott foglyul esik. Egy húzás második lépése is befejezhető, ha a húzó bábu az elsőben foglyul esik. Például ha Ezüst jönne, léphetne az f4-es nyúllal a g4-re, majd az ezüst lóval az f2-ről az f3-ra, amitől a ló foglyul esik, és mégis áthúzhatná az arany nyulat az f1-ről az f2-re, a ló lépésének részeként.
Az ábrázolt állásban, ha Arany köre következne, három lépésben nyerhetne: az a6-os kutya átlökheti az a7-es nyulat a8-ra, és amint a kutya az a7-en van, feloldja a b7-en álló, bénult nyulat, amely a b8-ra léphet a győzelemért.
A játék befejezésének több módja is van azon kívül, hogy egy nyúl eléri az alapvonalat. (Zárójelben ezek gyakorisága látható.)[2]
- (2,2%) Ha egy játékos körének kezdetekor nincs lépésre lehetőség, mert minden saját színű figura bénult vagy blokkolt, a játékos veszít.
- (0,2%) Ha ugyanaz az állás háromszor egymás után előfordul úgy, hogy ugyanaz a játékos következik, az a játékos veszít, akinek a köre ezt a helyzetet okozta. Itt csak a kör végi állások számítanak, nem az egyes lépések végén előfordulók. (Ebben a szabályban eredetileg nem számított, ki következik, de Syed 2005. május 28-án megváltoztatta, hogy jobban hasonlítson a sakk ismétlési szabályára.)
- (0,0%) Ha mind a tizenhat nyúl foglyul esik, a játék döntetlen. (Kieséses bajnokságokon, ahol a döntetlen nem megengedett, Syed úgy határozott, hogy az ellenfél mind a nyolc nyulának elfogása is győzelmet jelent, de 2006 szeptemberéig ennek a változtatásnak nem volt jelentősége.)
Végezetül, ha az ellenfél egyik nyulát a célvonalra mozdítja, majd ugyanabban a körben elviszi onnan, a játék folytatódik.
Stratégia és taktika
szerkesztésA témába való bevezetéshez lásd az angol nyelvű Arimaa Wikikönyv taktikai és stratégiai fejezeteit.
Az Arimaa és a számítógépek
szerkesztésTöbb szempont is nehezíti a számítógépes programok dolgát abban, hogy megverjék a jól játszó embereket. Mivel nagy erőfeszítések folytak jó sakkszámítógépek kifejlesztésére, fontos megérteni, hogy a sakknál használatos technikák miért kevésbé hatékonyak az Arimaa esetében.
A legjobb sakkprogramok ún. brute force-keresést alkalmaznak, és valamilyen szempontok alapján értékelik az állásokat. A sakkprogramok rengeteg lehetséges állást vizsgálnak meg, de az emberhez képest nem jók annak megítélésében, ki áll nyerésre egy lépéssor végén, hacsak nincs valamelyik félnek kevesebb figurája. Ugyanez igaz az Arimaa-programokra is, de ezek a gyakorlatban gyengébbek.
Amikor a brute force-ot az Arimaa-ra alkalmazzák, a keresés mélységét erősen korlátozza az egyes játékosok lehetséges lépéseinek óriási száma. Egy Arimaa-játékosnak közel annyi lehetősége van egy lépésben, mint egy sakkozónak egy körben. Így egy program, amely tizenhat rétegnyit képes előreszámolni, minden játékos nyolc körét előre látja a sakkban, de az Arimaa-nál ez körülbelül csak két körre (nyolc lépésre) elegendő.
A keresési mélységet sakkprogramoknál akár meg is lehet duplázni alfa-béta vágással, ami lehetővé teszi a program számára, hogy az egyik állást jobbnak tekintse a másiknál anélkül, hogy a gyengébb lépés minden lehetséges folytatását megvizsgálná. Ha az ellenfél egy válaszlépéssel „tönkreteheti” a lépést, a többi lehetőséget már meg sem kell vizsgálni, ami nagyon megnöveli a számítási sebességet. Az Arimaa-nál azonban a játékos csak négy lépésenként cserélődik, ami csökkenti a lehetséges rövidítések számát a lépésközpontú keresésél.
Ezenkívül az alfa-béta vágás hasznossága erősen függ attól, milyen sorrendben vesszük az egyes lépéseket. Először a jobbakat kell megvizsgálni, hogy a rosszabbakat elhanyagolhassuk. Például a sakkadási és foglyul ejtési/ütési lépések fontosak a vágás szempontjából, mert általában sokkal jobbak a többi lehetőségnél. Az Arimaa-ban ez a sebességnövekedés kisebb, mert a foglyul ejtések ritkák. Az Arimaa.com-on játszott értékelt játszmák lépéseinek csupán 3%-a végződik foglyul ejtéssel, szemben a sakk 19%-os ütési arányával.
A legtöbb Arimaa-állásban, főleg a játék elején, amikor még sok figura van a táblán, egy hozzáértő játékos képes elkerülni bábui foglyul ejtését a következő két körben. A sakkhoz képest az Arimaa mindkét játékos számára lehetővé teszi, hogy sokáig késleltesse a foglyul ejtést. A sakkban legtöbbször a 6. lépésben történik az első ütés, az Arimaa-ban ez a 12. körben történik. A küzdelem inkább a jó pozíciókért folyik, és az a célja, hogy egy későbbi állásra elkerülhetetlenné tegye a foglyul ejtést. Ez megnöveli annak jelentőségét, hogy el tudjuk dönteni, éppen ki áll jobban, a számszerű értékelésen kívül. Ezért a számítógépes programok erőssége (több millió állás megvizsgálása) nem olyan jelentős, mint a gyengeségük (annak megállapítása, ki áll jobban, a figurák számán túl).
Az Arimaa-programok gyengeségét a játék elején tovább növeli a kezdés módja. a sakkban minden játszma ugyanabból a pozícióból indul. Ha játék előtt létrehozunk egy adatbázist a szokásos nyitólépésekhez, sakkprogramjaink akár egy tucat kiváló lépést is megtehetnek, mire „gondolkodni” kezdenek. Az emberek is így csinálják, csak kisebb és kevésbé megbízható adatbázis áll a rendelkezésükre a megnyitáshoz, ami a sakkban az embert hátrányba juttatja. Ezzel ellentétben az Arimaa-ban több millió lehetséges felrakási mód van, még az első lépés megtétele előtt. Így gyakorlatilag nem lehet használható megnyitás-adatbázist létrehozni.
Ahogy a játék halad előre, a csapdák és a nyulak haladása miatt az állások egyre ritkásabbak és taktikusabbak lesznek. Az Arimaa-programok általában jobban játszanak az ilyen helyzetekben, mert észrevesznek olyan taktikai dolgokat, amelyeket az ember nem. Általában azonban az ilyen nyitott állások elkerülhetők védekező taktikával, és olyan stratégiai állások létrehozásával, amikben a számítógép rosszabbul játszik. Egy védekező taktikát játszó játékos védelmét megtörni szinte lehetetlen az Arimaa-ban, míg a sakkban ez „csak” nehéz. Az ilyen játékost apró, hosszú távon előnyös lépések felhalmozásával lehet legyőzni, amiben a programok nem túl jók.
Egy másik sakkprogramokban alkalmazott technika, ami az Arimaa-ban nem hatásos, a végjáték-adatbázis. A profi szintű sakkjátszmák néha tisztázatlan, kevés figurát felhasználó végjátékhoz vezetnek, például király és huszár király és futó ellen. Ilyen helyzetekben retrográd elemzéssel létre lehet hozni a helyes lépések listáját minden helyzetre. A programoknak ilyenkor csak az előre generált táblázatban kell megkeresniük a megfelelő állást az „újragondolás” helyett, ami ismét előnyt jelent az emberrel szemben. Az Arimaa ezzel ellentétben ritkán végződik ehhez hasonlóan. A cserék ritkábbak, mint a sakkban, így ritkán fordul elő, hogy a játék „letisztul”, és mégis eldöntetlen. Egy átlagos Arimaa-játszmában nyolc foglyul ejtés történik (a sakkban ez tizenhét), és az erős emberi játékosok képesek úgy legyőzni a legjobb Arimaa-programokat anélkül, hogy egy bábut is vesztenének (például a 2007-es „párbaj” ötödik játszmájában[halott link]). A 2007-es „levelező” bajnokság döntőjében[halott link] a játékosok egy foglyul ejtést tettek meg, ami áldozat volt a győzelemhez.
Omar Syed azt reméli, hogy mivel a hagyományos számítógépes játéktechnikák nem igazán hatékonyak az Arimaa esetében, a programozóknak mesterséges intelligencia-módszereket kell majd alkalmazniuk egy jó Arimaa-program létrehozásához. A világbajnokszintű sakkprogram létrehozása sok új technológiát hozott létre a sikeres játékhoz, de az előnymegállapításhoz szinte semmit nem tett hozzá; sőt, a sakkprogramokhoz kapcsolódó technikák némelyikét ki is zárták a mesterséges intelligencia némelyik definíciójából. Az Arimaa célja, hogy a játszásához szükséges technikák segítsék a mesterséges intelligencia kutatásának magasabb céljait.
Az ember-gép párbajban azt tartják szem előtt, hogy az MI-szoftverek, és ne a hardver fejlődését díjazza. Az évenkénti küzdelemben a programok az Omar által kiválasztott és rendelkezésre bocsátott gépeken futnak, aminek az a feltétele, hogy azok nem túl drága, gyári állapotú házi szintű személyi számítógépek legyenek. A kihívás tehát nem nyitott azok számára, akiknek drága, többprocesszoros gépek használatára lenne szükségük, mint a direkt erre a célra létrehozott szuperszámítógép, a Deep Blue; bár ez a hardvercentrikus megközelítés inspirálta az Arimaa feltalálását. Syed úgy hiszi, a szuperszámítógépek lehet, hogy már most is győzhetnének az Arimaa-ban brute-force módszerrel, és egyszer majd a személyi számítógépek is képesek lesznek erre.
A párbaj története
szerkesztés2004 óta minden évben megrendezésre kerül az Arimaa-párbaj, amelyben az év győztes szoftvere versenybe szállhat a kitűzött 10 000 dolláros pénzdíjért (2006 óta mindig) 3 Syed által választott, előkelően rangsorolt ember ellen. A harmadik mérkőzés előtt Syed megváltoztatta a szabályokat, miszerint a kihívónak mindhárom ember ellen nyernie kell, így próbálta csökkenteni az önkéntes védőkre nehezedő pszichológiai nyomást. A 2020-ig fennálló díj mellett Syed maga is felajánlott egy újabb összeget 2010-ig, valamint új támogatókat is sikerült megnyernie.
| Év | Díj | Kihívó | Fejlesztő | Védő játékos | A védő játékos helyezése | Eredmény | Megjegyzés |
|---|---|---|---|---|---|---|---|
| 2004 | $10,000 |
Bomb | David Fotland | Omar Syed | #1 | 0-8 | Syed nyúl-előnyt adott az utolsó játszmában. |
| 2005 | $10,000 |
Bomb | David Fotland | Frank Heinemann | #4 | 1-7 | Nem volt előnyadás |
| 2006 | $17,500 |
Bomb | David Fotland | Karl Juhnke Greg Magne Paul Mertens |
#1 #2 #6 |
0-3 0-3 1-2 |
Mertens teve-előnyt adott az utolsó játszmában, és vesztett. |
| 2007 | $17,100 |
Bomb | David Fotland | Karl Juhnke Brendan M Omar Syed N Siddiqui |
#1 #19 #20 #27 |
0-3 0-2 0-3 1-0 |
Juhnke kutya-, ló- és teve-előnyt adott. Syed macska-előnyt adott az utolsó játszmájában. Siddiqui helyettesített Brendan második játszmájában. |
| 2008 | $17,000 |
Bomb | David Fotland | Jean Daligault Greg Magne Mark Mistretta Omar Syed |
#1 #3 #16 #17 |
0-3 0-3 0-1 0-2 |
Nem volt előnyadás. Syed helyettesítette Mistretta-t az utolsó két játszmában. |
| 2009 | $16,500 | Clueless | Jeff Bacher | Jean Daligault Karl Juhnke Jan Macura Omar Syed |
#1 #2 #14 #18 |
0-2 1-2 1-2 0-1 |
Juhnke második játszmájában egy kutya előnyt adott és veszített. Daligault az utolsó játszmában lóelőnyt adott és nyert. Daligault-t első játszmájában Syed helyettesítette. |
| 2010 | $16,250 | Marwin | Mattias Hultgren | Greg Magne Louis-Daniel Scott Patrick Dudek |
#3 #10 #23 |
0-3 1-2 2-1 |
Scott a második játszmájában egy kutya előnyt adott és veszített. |
| 2011 | $11,000 | Marwin | Mattias Hultgren | Karl Juhnke Gregory Clark Toby Hudson |
#3 #7 #14 |
0-3 1-2 2-1 |
Juhnke utolsó játszmájában egy macska előnyt adott és veszített. |
| 2012 | $11,150 | Briareus | Ricardo Barreira | Jean Daligault "hanzack" Eric Momsen |
#1 #2 #5 |
0-3 0-3 3-0 |
hanzack utolsó játszmájában egy macska előnyt adott. |
| 2013 | $11,000 | Marwin | Mattias Hultgren | Mathew Brown Greg Magne Matthew Craven |
#4 #6 #31 |
0-3 0-3 1-2 |
Magne egy macska-, Brown egy ló előnyt adott utolsó játszmájában, mindketten nyertek. |
Az első öt alkalommal David Fotland, aki a Many Faces of Go játék fejlesztője, nyerte meg az Arimaa Computer Championship bajnokságot és ezzel megszerezte a jogot a részvételre. Azonban minden alkalommal alulmaradt az emberi játékosokkal szemben. 2009-ben több új program is megelőzte Fotland Bombját, a legerősebbnek a Jeff Bacher által fejlesztett Clueless bizonyult. A mesterséges intelligencia most is veszített, de ez volt az első program amely két játszmát is képes volt megnyerni.
2010-ben a Marwin névre hallgató Mattias Hultgren által fejlesztett bot elsőként győzött le egy játékost és nyert meg összességében három játszmát. A következő évben azonban már csak egy játszmát tudott nyerni, azt is előnyből. 2012-ben új számítógépnyertesként a Briareus nevű Ricardo Barreira által fejlesztett program az ötödiknek rangsorolt játékost 3-0-ra legyőzte. A díjat azonban nem tudta elnyerni, mert a többi 6 játszmáját elveszítette. 2013-ban pedig az emberi csapat ismét visszavágott 8 játszmát megnyerve, ezúttal újra Marwin ellen.
Eddig minden alkalommal egyre alacsonyabb besorolású játékosok voltak képesek helytállni az Arimaa Párbajban, ami azt sugallja, hogy az emberi játékosok egyre nagyobb előnyt élveznek a számítógépes programokkal szemben; bár ebben feltehetően az is közrejátszik, hogy egyre többen ismerkednek meg a játékkal, és egyre több játékos vehet részt a párbajban.
Szabadalmaztatás és védjegy
szerkesztésAz amerikai szabványügyi hivatal a US PAT No. 6,981,700 számú szabadalmat 2003. október 3-án jegyezte be és 2006. január 3-án hagyta jóvá a kérelmet. Omar Syed a szabadalom mellett bejegyeztette az "Arimaa" nevet is.
Syed állítása szerint nem akarja korlátozni a játék nem-kereskedelmi célú felhasználását és ezért létrehozta az ún. "Arimaa Public License" licencet. Syed közleménye szerint „az Arimaa-t a lehető leginkább közkinccsé akarja tenni, de továbbra is korlátozza a kereskedelmi felhasználását”.
Jegyzetek
szerkesztés- ↑ Syed, Omar, Syed, Aamir (2003). „Arimaa – a New Game Designed to be Difficult for Computers”. International Computer Games Association Journal 26, 138-139. o.
- ↑ Arimaa szerver játékarchívuma Archiválva 2007. november 16-i dátummal a Wayback Machine-ben 2006 decemberében az ember-ember játékok kimenetele: 1653 a cél elérésével, 38 az ellenfél lépésének lehetetlenné tételével, 4 az állás megismétlésével, 0 pedig döntetlennel végződött.