Arimaa

Az Arimaa egy két játékos által játszható táblajáték, ami a sakkhoz szükséges táblán, sakkbábukkal 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á.

Történet

Az Arimaa-t Omar Syed mesterséges intelligenciával foglalkozó számítógépes mérnök találta fel. Syedet Kaszparovnak az 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. A szabadalmat a Syedek megkapták az Arimaa szabályaira, és a játék neve is védett (lásd lejjebb).

Szabályok

Az Arimaa-t sakktáblán játsszák, négy megkülönböztetett kockával, 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 (). Ezeket jelölhetjük sorban a királlyal, a vezérrel, a bástyákkal, a futókkal, a huszárokkal és a gyalogokkal, ha sakktáblán játszunk.

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ítson egy ellenséges bábut egy erősebb saját figurával, ami szomszédos vele a nyolc 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 a gyengébb, ellenséges figurá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, ami valamilyen irányban (vízszintesen, függőlegesen, vagy átlósan) szomszédos egy erősebb, ellenséges figurá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 ellenséges figurákkal ú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 ez 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, ami 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%) 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 a nyolc ellenséges nyúl elfogása is győzelmet jelent, de 2006 szeptemberéig ennek a változtatásnak nem volt jelentősége.)

Végezetül, ha egy ellenséges nyulat a célvonalra mozdítanak, majd ugyanabban a körben el onnan, a játék folytatódik.

Stratégia és taktika

A 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

Tö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, ami 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 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ésben, 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, amiket 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). A 2007-es "levelező" bajnokság döntőjében 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ágbajnok-szintű 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áztartási 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, az 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

2004 óta minden évben megrendezésre kerül az Arimaa párbaj, amiben az év győztes szoftvere versenybe szállhat a kitűzött 10 000 $-os 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 $10,000 2020-ig Omar Syed részéről	Bomb	David Fotland	Omar Syed	#1	0-8	Syed nyúl-előnyt adott az utolsó játszmában.
2005	$10,000 $10,000 2020-ig Omar Syed részéről	Bomb	David Fotland	Frank Heinemann	#4	1-7	Nem volt előnyadás
2006	$17,500 $10,000 2020-ig Omar Syed részéről $5,000 2010-ig Omar Syed részéről $2,000 Paul Mertens részéről $500 Karl Juhnke részéről	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 $10,000 2020-ig Omar Syed részéről $5,000 2010-ig Omar Syed részéről $1,500 Paul Mertens részéről $600 Karl Juhnke részéről	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 $10,000 2020-ig Omar Syed részéről $5,000 2010-ig Omar Syed részéről $1,000 Paul Mertens részéről $1,000 Karl Juhnke részéről	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 bajoksá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 Bomb-já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 2 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 3 játszmát. A következő évben azonban már csak 1 játszmát tudott nyerni, azt is előnyből. 2012-ben új számítógép nyerteské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 programmal 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

Az 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".

Külső hivatkozások

• Hivatalos oldal
• David Fotland Arimaa programja
• The Arimaa Public License