Arimaa (peli)

Historia

Arimaan kehitti Yhdysvalloissa asuva intialainen insinööri Omar Syed. Syedin inspiraationa oli Garri Kasparovin tappio Deep Blue -shakkitietokoneelle. Hän halusi kehittää pelin, jossa tietokoneet eivät pärjäisi ihmiselle pelkän laskentatehonsa ansiosta, mutta joka olisi myös tarpeeksi yksinkertainen hänen nelivuotiaan poikansa Aamirin ymmärtää (Arimaa onkin nimetty Aamirin mukaan – se on Aamir takaperin, johon on lisätty eteen yksi A-kirjain). Syed julkaisi arimaan säännöt vuonna 2002. Hän myös lupasi, että se, joka kehittää Arimaata pelaavan tietokoneohjelman, joka voittaa maailman kolme parasta ihmispelaajaa kolmen pelin otteluissa, saa kymmenen tuhannen dollarin palkinnon. Palkinto myönnetään, jos voitto tapahtuu ennen vuotta 2020.

Tietokoneiden kyvyttömyys

Monet osatekijät tekevät arimaasta vaikean tietokoneohjelmille. Koska vahvojen tietokoneshakkiohjelmien kehittämisessä on nähty niin paljon vaivaa, on tärkeää ymmärtää, miksi shakissa toimivat tekniikat eivät ole arimaassa yhtä tehokkaita.
Parhaat shakkiohjelmat käyttävät raakaa laskentavoimaa (brute-force-tekniikka) sekä materiaalitasapainoa painottavaa arviointifunktiota. Shakkiohjelmat tutkivat erittäin monia siirtoja, mutta ihmisiin verrattuna niiden arviointikyky siitä, kumpi siirtosarjan päätteeksi on voitolla, on huono, ellei toisella pelaajalla ole enemmän nappuloita kuin toisella. Arimaa-ohjelmat toimivat samalla periaatteella, mutta tulokset eivät käytännössä ole yhtä hyviä.
Kun brute-force-hakua käytetään Arimaassa, hakusyvyyttä rajoittaa mahdollisten siirtojen valtava määrä vuoroa kohden. Arimaassa pelaajalla on lähes yhtä monta vaihtoehtoa askelta kohden kuin hänellä on shakissa siirtoa kohden. Siten 16 puolisiirron syvyyteen hakeva shakkiohjelma näkee kahdeksan vuoron päähän shakissa, mutta vain kaksi siirtoa (kahdeksan vuoroa) arimaassa.
Brute-force-haun syvyys shakissa lähes kaksinkertaistuu käyttämällä alfa-beta-karsintaa, jonka avulla ohjelma voi todeta jonkin siirron olevan toista parempi käymättä heikomman siirron kaikkia jatkovaihtoehtoja läpi. Jos vastustaja voi murskata jonkin siirron jollakin tietyllä vastasiirrolla, muita vastasiirtoja on turha tutkia ja haku voidaan katkaista, mikä nostaa hakunopeutta merkittävästi. Arimaassa siirtovuoro kuitenkin vaihtuu neljän askeleen välein, mikä vähentää edellä kuvattujen katkaisusiirtojen määrää siirto siirrolta -haussa. Tosin järjelliset siirrot voidaan lähes aina siirtää usealla eri askelyhdistelmällä, minkä johdosta on järkevämpää valita brute-force-laskentaan, ja täten siis myös alfa-beta-karsintaan, perusyksiköksi (ply) koko neljän askeleen siirto eikä yksittäistä askelta. Järjellisiä siirtoja, joita ei voi nopeasti hylätä ja joiden kohdalla siis alfa-beta-karsinnasta on vain vähän hyötyä, Arimaassa on arviolta kymmenkertaisesti shakkiin verrattuna.
Alfa-beta-karsinnan hyödyllisyys riippuu voimakkaasti siitä, missä järjestyksessä se siirtoja tutkii. Hyvät siirrot täytyy tutkia ennen huonoja siirtoja, jotta huonot siirrot voitaisiin nopeammin hylätä. Esimerkiksi shakissa erityisesti shakkaaminen ja lyöminen ovat usein paljon muita siirtoja parempia. Arimaa-ohjelmissa alfa-beta-karsinta ei tarjoa vastaavaa hyötyä, sillä lyönnit ja maaliuhkaukset ovat harvinaisempia.  Vuoteen 2007 mennessä Arimaa.comissa pelatuissa pisteytetyissä peleissä vain kolme prosenttia siirroista johti lyömiseen, mikä on merkittävästi vähemmän kuin shakissa, jossa 19 prosenttia siirroista on lyöntejä.
Useimmissa arimaan sellaisissa tilanteissa, erityisesti pelin alussa, joissa laudalla on paljon nappuloita, taitava pelaaja voi välttää menettämästä nappuloita ainakin kahden vuoron ajan. Shakkiin verrattuna arimaa sallii kummankin pelaajan viivyttää lyöntejä pidempään. Shakin ensimmäisen lyönnin vuoron mediaani on 6, kun arimaassa se on vasta vuoro 12. Arimaassa kamppailu on asemallisempaa kuin shakissa ja sen idea on yrittää tehdä lyönneistä väistämättömiä tulevaisuudessa. Tämän vuoksi on tärkeää pystyä materiaalista riippumatta sanomaan, kumpi on voitolla. Niinpä tietokoneiden vahvuus, miljoonien asemien tutkiminen, ei ole yhtä merkittävä kuin niiden heikkous, voitolla olevan osapuolen päättäminen muilla kuin vain materiaaliin pohjautuvilla menetelmillä.
Arimaa-ohjelmien heikkous avauksissa korostuu entisestään, kun huomioidaan, että aloitusasemat ovat pelaajien valittavissa. Shakissa aloitusasema pysyy samana, joten ohjelmille on mahdollista tehdä etukäteen avauskirjastoja, joiden ansiosta ne tietävät parhaat linjat ja tekevät jopa yli kymmenen siirtoa ennen kuin alkavat "ajatella" itsenäisesti. Ihmisetkin opettelevat avauksia, mutta kykenevät siihen tietokoneita rajoitetummin. Arimaassa on kuitenkin miljoonia mahdollisia avausasemia, joten ohjelmilla ei aluksi ollut lainkaan avauskirjastoa. Viime vuosina avausasemien suhteen on opittu tiettyjä periaatteita, joiden perusteella mielekkäitä avausasemia on vain joitain kymmeniä, jotka nekin muistuttavat melko lailla toisiaan. Kuitenkin jo parin-kolmen siirron jälkeen jokaiseen siirtoon sisältyvien neljän askeleen ja avausasemien pienten eroavaisuuksien johdosta nappulat sijaitsevat käytännössä joka pelissä eri lailla, joten avausten ulkoa opettelusta ei ole hyötyä.
Pelin edetessä vaihdot ja jänisten eteneminen tekevät siitä avoimempaa ja taktisempaa. Näissä tilanteissa Arimaa-ohjelmilla on puolellaan se etu, että ne voivat nähdä taktisia vaihtoehtoja, joita ihmiset eivät huomaa. Konservatiivisesti pelaamalla ihmisten on kuitenkin yleensä mahdollista välttää avoimia asemia ja pitää peli strategisissa asemissa, joissa tietokoneet eivät pärjää. Konservatiivista pelaajaa vastaan aseman avaaminen on lähes mahdotonta, kun taas shakissa se on vain vaikeaa. Vahvasti puolustuskannalla oleva vastustaja voidaan voittaa vain kerryttämällä pieniä, pitkän tähtäimen voittoja, joita tietokoneohjelmat eivät ymmärrä kovin hyvin.
Eräs tietokoneshakissa käytetty, mutta arimaassa toimimaton tekniikka ovat loppupelitietokannat. Shakkipelit päätyvät toisinaan ratkaisun kannalta epäselvään tilanteeseen, jossa on vain vähän nappuloita jäljellä: esimerkiksi kuningas, ratsu ja sotilas vastaan kuningas ja torni. Takautuvaa analyysiä käyttäen on mahdollista rakentaa täydellinen taulukko oikeista siirroista tällaisissa tilanteissa. Ohjelman tarvitsee vain hakea oikea siirto tietokannasta sen sijaan että se joutuisi itse laskemaan, mikä antaa sille etulyöntiaseman ihmistä vastaan. Arimaa sen sijaan päätyy vastaavaan loppupeliin vain harvoin. Tasavahvojen nappuloiden vaihtaminen on arimaassa harvinaisempaa kuin shakissa, joten kun paljon nappuloita on lyöty, tilanne on epäselvä vain harvoin. Keskimääräisessä arimaa-pelissä tehdään vain kahdeksan lyöntiä (shakissa seitsemäntoista) ja parhaat ihmispelaajat voivatkin usein voittaa parhaat arimaa-ohjelmat menettämättä yhtäkään nappulaa kuten tapahtui vuoden 2007 haasteottelun viidennessä pelissä.
Koska perinteiset tekniikat, joilla tietokoneet pelaavat lautapelejä, toimivat arimaassa vain nimeksi, Omar Syed toivoo, että ohjelmoijat joutuisivat käyttämään tekoälytekniikoita luodakseen vahvan arimaata pelaavan ohjelman. Maailmanmestaruustason shakkiohjelmia kehitettäessä on keksitty useita hyviä pelitekniikoita, mutta nämä tekniikat eivät ole luonteeltaan tekoälyä. Gon tavoin parhaatkin  uudemmassa  konnektionistisessa tekoälytutkimuksessa käytetyt ja esimerkiksi backgammonissa parhaaksi osoittatuneet neuroverkkotekniikkaa käyttävät ohjelmat häviävät selvästi tavanomaista ohjelmointitekniikkaa käyttäville ohjelmille. Syedin tavoitteena on, että arimaata pelaamaan kehitetyt tekniikat auttaisivat tekoälytutkimusta yleisestikin. Toistaiseksi menestys tällä saralla on ollut vaatimatonta, itse asiassa ihmisten paremmuus ohjelmiin verratuna on jatkuvasti vain kasvanut.
Syed myöntää, että hänen ihminen vastaan kone -haasteensa luottaa vahvan ohjelman luomisen vaikeuteen. Vuosittaisessa haasteessa ohjelmia ajetaan tavallisilla, normaalitehoisilla Syedin valitsemilla kotimikroilla sellaisina kuin ne ovat kaupasta saatavilla. Haasteeseen ei voida osallistua ohjelmilla, jotka vaativat kalliita moniprosessorijärjestelmiä tai kokonaan omanlaistaan laitteistoa kuten Deep Blue -shakkitietokone, vaikka Deep Blue arimaan innoittajana olikin. Ohjelmien kehittämisessä voi silti käyttää suurempaakin laskentatehoa hyödyntäviä koneita.

Patentti ja tavaramerkki

Omar Syed pani Yhdysvalloissa patenttihakemuksen arimaasta vireille 13. lokakuuta 2003, ja se hyväksyttiin 3. tammikuuta 2006. Syedillä on myös Yhdysvalloissa tavaramerkki Arimaa-nimelle.
Syed on ilmoittanut, ettei hän halua rajoittaa Arimaan epäkaupallista käyttöä ja onkin julkaissut "The Arimaa Public License" -nimisen lisenssin tarkoituksenaan "tehdä Arimaasta mahdollisimman suurelta osin public domainia pelin kaupallisia käyttömahdollisuuksia silti suojellen". Tämän lisenssin piirissä ovat sekä patentti että tavaramerkki.