Kirjautuminen

Haku

Tehtävät

Kilpailu

Ohjelmoi tekoäly!
Tulokset on julkaistu.
Onnea voittajalle!

Kilpailut: Morabaraba: tulokset

Järjestäjä: Metabolix

Alkuvuonna 2014 Ohjelmointiputkassa pidettiin tekoälykilpailu. Aiheena oli morabaraba, kahden pelattava lautapeli, joka muistuttaa Suomessa tunnettua myllyä. Kaikki tekoälyt pelasivat vuorollaan kaikkia muita sekä itseään vastaan. Voittaja sai ottelusta yhden pisteen, mutta lisäksi molemmat pelaajat saivat hieman sakkoa hitaudesta. Käytännössä sakkopisteet eivät vaikuttaneet kilpailun tuloksiin, mutta niillä saatiin kannustettua kilpailijat tekemään nopeita tekoälyjä.

Kilpailuun osallistui yhdeksän ohjelmaa. Tällä kertaa erilaiset minmax-algoritmin toteutukset valtasivat tuloslistan kärkisijat ja yksinkertaisemmat arvailijat jäivät nuolemaan näppejään. Jäljempänä tällä sivulla on ohjelmien kuvauksia, ja tekoälyjen lähdekoodit voi ladata yhtenä pakettina.

Osallistujat ja tulokset

Alla ovat kaikki kilpailun osallistujat voittajasta alkaen. Taulukossa näkyvät voittojen (V), tasapelien (T) ja häviöiden (H) määrät sekä kertyneet pisteet.

Varsinaisten kilpailijoiden lisäksi kilpailussa oli mukana esimerkkiäly esim.

sijatekoälykielitekijänimimerkkiVTHaika/pelipisteet
1.CowKingC++Jorma SainioFooBat15120,36 s14,98
2.RuttoC#Tuomo Kuusela14311,32 s13,92
3.NTNminmaxC++Joonatan SaarheloJoonazan11253,27 s10,21
4.FrediC++Mika UrtelaApodus10442,05 s9,74
5.CJDC++Lauri KenttäMetabolix9090,00 s9,00
6.rxaVB.NETSami RiiheläRixa7290,07 s7,00
7.BitRapePL/IJali Heinonenjalski50130,01 s5,00
8.OttoC++Oskari MieskolainenOskuz22140,00 s2,00
9.esim(useita)10170,00 s1,00

Onnea voittajalle!

Pelit

Tässä taulukossa ovat kaikki pelatut pelit. Aloittaja lukee kunkin rivin alussa ja puolustaja ylärivillä. V-kirjain merkitsee aloittajan voittoa eli sitä, että pelin pistemäärä on suurempi kuin vastapuolen aloittaessa. H-kirjain tarkoittaa vastaavasti häviötä ja T-kirjain tasapeliä, joita tuli muutama, kun tekoälyt eivät saaneet lopuksi peliä päätökseen tarpeeksi nopeasti vaan jäivät siirtelemään nappuloita edestakaisin. Tulos on linkki sivulle, josta voi katsoa kyseisen pelin.

CoRuNTFrCJDrxaBiOtes
CowKingVTVVVVVVV
RuttoVVVVVVVVV
NTNminmaxHTVVHVVVV
FrediHTTTVVVVV
CJDHHHHVHVVV
rxaHHHHHTVVV
BitRapeHHHHHHHVV
OttoHHHHHHHTV
esimHHHHHHHHV

Ohjelmat

Ohjelmien lähdekoodit voi ladata yhtenä pakettina. Alla ovat tekijöiden omat kuvaukset ohjelmistaan.

CowKing
Jorma Sainio
FooBat

Perinteinen Negamax alfa-beta-karsinnalla ja transpositiotauluilla. Lisäksi höystettynä hiukan alkusiirtojen (5 siirtoa) ja golden path -pelipuun taulukoinnilla. Taulukoinnissa on käytetty 9 siirron laskentasyvyyttä ja pelilaudan 16 kertaista symmetriaa, mutta normaalin pelin aikana lasketaan vain 7 tai 5 syvyydellä.

Evaluaatiofunktio ottaa huomioon nappuloiden lukumäärät, kahden suorat ja niihin liittyvät hyökkäysmahdollisuudet ja mahdollisten hyökkäävien lehmien määrät sekä mahdollisten siirtojen lukumäärät, ja alkupelissä painotetaan hiukan keskirinkiä.

Rutto
Tuomo Kuusela

Pelilautaa säilytetään yhdessä 64-bittisessä ulong-tyyppisessä muuttujassa. Siirrot ja muu laudan käsittely tehdään bittitason operaatioina.

Siirtojen haussa on käytössä minmax-algoritmi, jossa on alpha-beta-karsinta. Siirrot joita algoritmi alkaa käydä läpi, järjestetään kahdella lajittelulla. Ensin siirretään ensimmäisiksi siirrot, jotka tekevät myllyn. Sen jälkeen siirretään ensimmäisiksi siirrot, jotka ovat aiemmin aihettaneet hakupuun karsinnan samalla tasolla.

Pelitilanteen arviointifunktiossa otetaan huomioon neljä asiaa: lehmien lukumäärät, muodostuneet myllyt, avoimien (seuraavalla siirrolla mahdollisesti täydentyvien) myllyjen määrä ja vapaa liikkumatila eli ruudut, joihin pelaaja voi siirtää.

Kun ollaan vielä lehmien asetteluvaiheessa ja syntyy avoin mylly, jossa keskimmäinen ruutu on vapaa, saa enemmän pisteitä kuin normaalisti avoimesta myllystä. Tällä on pyritty saamaan asetteluvaiheessa levittäytymistä aikaan, jotta ei myöhemmin niin helposti ajauduttaisi tilanteeseen, jossa hävitään peli sen takia, että ei voida siirtää.

Kun lehmiä on jäljellä enää kolme, vähennetään vastustajan avoimista myllyistä enemmän pisteitä kuin normaalisti, koska vastustajan mylly tässä tilanteessa tuo häviön.

Pelin ensimmäinen ja toinen siirto palautetaan taulukosta ilman laskentaa. Arviointifunktio käyttää välimuistia, kaikki lasketut pelitilanteet tallennetaan välimuistiin.

NTNminmax
Joonatan Saarhelo
Joonazan
Minmax, heuristiikka pitää ampumista ja voittamista hyvänä eikä arvioi asemia lainkaan. Sisältää hieman karsintaa: jos voi ampua, ei tutkita muita vaihtoehtoja.
Fredi
Mika Urtela
Apodus
Negamax, tiettyyn aseman leveyteen saakka ajankäytön tasaamiseksi. Käytössä myös transpositiotaulut ja kevyt avauskirjasto, ottaen aseman eri peilaukset, pyöritykset ja kiepautukset huomioon.
CJD
Lauri Kenttä
Metabolix

Tekoäly pisteyttää ruutuja yksinkertaisesti sen mukaan, montako omaa ja vastustajan nappulaa on jo valmiina myllyä varten. Lisäpisteitä saa, jos siirto purkaa oman myllyn, luo oman mylly tai estää vastustajan myllyn. Jos vihollisella on enää kolme lehmää, tekoäly tekee oman myllyn heti, kun voi. Jos taas omia lehmiä on kolme, tekoäly yrittää aina ensin estää vastustajan myllyn. Lisäksi ohjelma välttää aina paluuta vanhoihin tilanteisiin, jotta pelit eivät päättyisi tasan.

Yksinkertaisuuden vuoksi ohjelma ei huomioi, mitä siirtoja vastustaja todella voisi tehdä, joten se estää usein myös sellaisia myllyjä, joita vastustaja ei oikeasti pystyisi täyttämään.

rxa
Sami Riihelä
Rixa

Peli on mallinnettu ohjelmaan 24 paikkaluokkana, jotka ovat tietoisia viereisistä paikoista. Paikat on sijoitettu 20 myllyluokkaan. Paikat ja myllyt ovat omissa listoissaan. Listaa käydään läpi, kun sijoitusta, siirtoa tai ampumista valitaan.

Ohjelma laskee jokaiselle 20 myllylle arvon ja käyttää sitä valintaan. Arvo lasketaan kertomalla myllyn kolme paikkaa keskenään. Paikan arvo riippuu siitä, mikä paikan tila on: tyhjä on 1, oma lehmä on 3, toisen lehmä on -2.

Saman arvoisia myllyjä vertaillaan sen perusteella, mikä on viereisten paikkojen tila.

BitRape
Jali Heinonen
jalski
Nopeasti ja huonon ohjelmointitavan mukaan kirjoiteltu bittimerkkijonoja ja merkkijonohakua hyödyntävä toteutus. Logiikka on yksinkertainen: yrittää löytää siirron, jossa muodostuu eniten ja purkautuu vähiten myllyjä. Jos myllyjä ei löydy, yrittää löytää siirron, jonka avulla pystyy häiritsemään eniten vastustajan seuraavaa siirtoa.
Otto
Oskari Mieskolainen
Oskuz
Otto pisteyttää pisteet ja ammuttavat lehmät sen mukaan, kuinka helposti ne voivat muodostaa myllyn tai estää sen muodostumisen.
esimEsimerkki valitsee aina ensimmäisen mahdollisen siirron.

Lopuksi

Kiitos kaikille osallistujille. Kisaillaan uudestaan kesällä!

Tietoa sivustosta