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.
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.
| sija | tekoäly | kieli | tekijä | nimimerkki | V | T | H | aika/peli | pisteet |
|---|---|---|---|---|---|---|---|---|---|
| 1. | CowKing | C++ | Jorma Sainio | FooBat | 15 | 1 | 2 | 0,36 s | 14,98 |
| 2. | Rutto | C# | Tuomo Kuusela | 14 | 3 | 1 | 1,32 s | 13,92 | |
| 3. | NTNminmax | C++ | Joonatan Saarhelo | Joonazan | 11 | 2 | 5 | 3,27 s | 10,21 |
| 4. | Fredi | C++ | Mika Urtela | Apodus | 10 | 4 | 4 | 2,05 s | 9,74 |
| 5. | CJD | C++ | Lauri Kenttä | Metabolix | 9 | 0 | 9 | 0,00 s | 9,00 |
| 6. | rxa | VB.NET | Sami Riihelä | Rixa | 7 | 2 | 9 | 0,07 s | 7,00 |
| 7. | BitRape | PL/I | Jali Heinonen | jalski | 5 | 0 | 13 | 0,01 s | 5,00 |
| 8. | Otto | C++ | Oskari Mieskolainen | Oskuz | 2 | 2 | 14 | 0,00 s | 2,00 |
| 9. | esim | (useita) | 1 | 0 | 17 | 0,00 s | 1,00 |
Onnea voittajalle!
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.
| Co | Ru | NT | Fr | CJD | rxa | Bi | Ot | es | |
|---|---|---|---|---|---|---|---|---|---|
| CowKing | V | T | V | V | V | V | V | V | V |
| Rutto | V | V | V | V | V | V | V | V | V |
| NTNminmax | H | T | V | V | H | V | V | V | V |
| Fredi | H | T | T | T | V | V | V | V | V |
| CJD | H | H | H | H | V | H | V | V | V |
| rxa | H | H | H | H | H | T | V | V | V |
| BitRape | H | H | H | H | H | H | H | V | V |
| Otto | H | H | H | H | H | H | H | T | V |
| esim | H | H | H | H | H | H | H | H | V |
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. |
| esim | Esimerkki valitsee aina ensimmäisen mahdollisen siirron. |
Kiitos kaikille osallistujille. Kisaillaan uudestaan kesällä!