Kilpailut: Kivi, sakset, paperi: tulokset
Järjestäjä: Metabolix
Kesällä 2009 Ohjelmointiputkassa pidettiin kilpailu, jossa piti ohjelmoida tekoäly leikkiin kivi, sakset, paperi. Kaksi tekoälyä pelasi aina keskenään tuhat kierrosta, ja joka kierroksella voittaja sai ja häviäjä menetti yhden pisteen, ellei kierros ollut tasapeli. Satunnaislukujen arpominen pelin aikana oli kielletty.
Kilpailun puolivälissä pelattiin ottelut niiden 25 älyn kesken, jotka olivat siinä vaiheessa ilmoittautuneet, ja tekoälyjen siirtosarjat julkaistiin, jotta kilpailijat näkisivät älyjensä toimintaa käytännössä ja voisivat parannella älyjä. Välikierroksen jälkeen kilpailuun tuli vielä kymmenkunta uutta osallistujaa sekä jonkin verran päivityksiä vanhoihin tekoälyihin.
Kilpailuun osallistui lopulta 37 tekoälyä. Osa luotti ennalta valittuun siirtosarjaan tai helppoon taktiikkaan, osa etsi vastustajan siirroista yksinkertaista toistuvuutta, parhaat arvailivat valintoja paljon mutkikkaammilla menetelmillä. Keskitason yläpuolella tekoälyt sijoittuivat tasaisesti koko pisteskaalalle, kilpailun häntäpäässä taas oli suurempia eroja ja toisaalta monta hyvinkin tasaväkistä tekoälyä.
Osallistujat ja tulokset
Seuraavassa taulukossa ovat kaikki kilpailun osallistujat järjestyksessä kokonaispistemäärän mukaan. Varsinaisten kilpailijoiden lisäksi kilpailussa olivat mukana esimerkkiäly esim sekä yksinkertaiset tekoälyt kaiku ja luuseri. Näistä esim valitsi aina sen, jolla olisi edellisellä kierroksella voittanut, kaiku saman kuin vastustaja äsken ja luuseri sen, jolla olisi hävinnyt.
| sija | tekoäly | kieli | tekijä | nimimerkki | pisteet |
|---|---|---|---|---|---|
| 1. | Shotgun | Java | Jorma Sainio | FooBat | 19098 |
| 2. | Leikkuri09 | C++ | Toni Huttunen | Seriffi | 18748 |
| 3. | Saikyou | Java | Markku Velinen | Dzarg | 17363 |
| 4. | Spock | C++ | Mika Urtela | Apodus | 17265 |
| 5. | jousipallo | Python | Jouko Joensuu | Jogge | 17060 |
| 6. | onnekas | Python | Chiman | 14945 | |
| 7. | Daeron_NG | C | Teemu Koskinen | Daeron | 14326 |
| 8. | set | Java | Antti Laaksonen | Antti Laaksonen | 13528 |
| 9. | himmeli | Python | XYZ | 12372 | |
| 10. | Brainluck | Brainfuck | Topi Musto | DaeD | 12326 |
| 11. | typerys | Python | Harri Nieminen | Moiman | 10914 |
| 12. | KiviKova | C++ | Leo Lehikoinen | Legutus | 10264 |
| 13. | nameless | Python | 8086 | ||
| 14. | tekoaly | C++ | 7901 | ||
| 15. | paperiaivo | C++ | Ilari Richardt | Style | 7819 |
| 16. | 0xF4 | C++ | Kari Rantanen | Grandi | 6456 |
| 17. | Code_395 | C++ | Sami Kalliomäki | Sami345 | 5909 |
| 18. | FAGGOT | C# | petrisi | 4856 | |
| 19. | u137 | Pascal | Teemu Valo | User137 | 4619 |
| 20. | Encephalon | Python | Frozenball | 536 | |
| 21. | foo | Python | Juho Pinola | JP_94 | -1242 |
| 22. | Jokuihme | C++ | Lari Sinisalo | Lr5 | -3376 |
| 23. | Kolykko | PHP | Teemu Kukkola | tesmu | -6172 |
| 24. | Kaksari | Python | Otto Martikainen | MetalRain | -7688 |
| 25. | Fail | PHP | Jouni Joensuu | JTJ | -8994 |
| 26. | MonkeyBot | Python | Lauri Niskanen | Ape | -9255 |
| 27. | r5nd0m | Python | Teijo Mursu | ZcMander | -10064 |
| 28. | palikka | C++ | Lari Vehkalampi | vehkis91 | -10073 |
| 29. | JankenB | Python | Vili Hietala | Viltzu | -10108 |
| 30. | esim | * | -12759 | ||
| 31. | byrokrat | Python | Jussi Kilpeläinen | Juice | -15283 |
| 32. | Puudeli | C | Niko Hämäläinen | Milo | -15575 |
| 33. | kaiku | Brainfuck | -16320 | ||
| 34. | tumpelo | VB.Net | Meitzi | -21014 | |
| 35. | luuseri | FreeBASIC | -24803 | ||
| 36. | Risaksi | C++ | Toni Mäkinen | Masfonos | -25204 |
| 37. | NIGGERx2 | C | Perttu Ahola | celeron55 | -26461 |
Yksittäisten otteluiden tulokset on koottu erilliseen tekstitiedostoon.
Tilastoja
Tekoälyistä 12 aloitti kivellä, 11 saksilla ja 14 paperilla. Eri aseita tekoälyt käyttivät kokonaisuudessaan seuraavan kuvaajan mukaan:
Seuraavassa kuvaajassa älyt on järjestelty sen mukaan, miten paljon niiden tulokset vastaavat toisiaan. Hyvin menestyneet älyt ovat päätyneet oikealle, huonommin menestyneet vasemmalle. Toisiaan lähellä olevat älyt ovat voittaneet suunnilleen samoja vastustajia ja myös hävinneet samoille.
Tekoälyt ja ottelut
Tekoälyjen lähdekoodit voi ladata yhtenä pakettina. Kaikkien otteluiden siirrot on koottu myös pakettiin, ja lisäksi pelien kulusta on laadittu kuvaajia.
Osallistujilta pyydettiin tekoälyn saatteeksi myös pientä selostusta sen toimintaperiaatteesta. Näin he kertovat ratkaisuistaan:
| Shotgun Jorma Sainio FooBat | Shotgun ajaa kymmeniä historiaan ja statistiikkoihin perustuvia arvausalgoritmeja samanaikaisesti ja pitää kirjaa siitä, mikä näistä algoritmeistä pärjäisi parhaiten, mikäli se aina valittaisiin. Parhaan algoritmin valitseva metavalinta ei suoranaisesti valitse algoritmeistä sitä, joka voittaa eniten, vaan sen, joka tuottaa suurimman tilastollisen poikkeuman. Käytännössä on siis sama, voittaako, häviääkö vai pelaako algoritmi aina tasan; Shotgun kääntää tämän tilanteen aina voitoksi. Toimintaansa nopeasti vaihtavia botteja varten statistiikoissa ja metavalinnassa käytetään täydellisen historiamuistin lisäksi unohtavaa muistia eri unohdusnopeuksilla. Loppusanoiksi voidaan todeta vielä, että Shotgun beats rock, paper and scissors any day! Botin tekoon on käytetty joitakin ideoita aikaisemmista rps-kilpailuihin osallistuneista boteista. Lähinnä Iocaine Powder, joka osallistui 'The First International RoShamBo Programming Competition' -kilpailuun (http://www.cs.ualberta.ca/~darse/rsbpc1.html), on toiminut innoittajana metavalintaidean taustalla. |
| Leikkuri09 Toni Huttunen Seriffi | Tekoäly sisältää useita pelityylejä. Seuraavaan siirtoon valittava pelityyli olisi saanut parhaan tuloksen viimeisistä kymmenistä siirroista. Jokainen pelityyli siis suoritetaan, vaikkei sen siirtoa valittaisi. Jokaista pelityyliä tarkistellaan myöskin käänteisenä. Tappioiden välttämiseksi tuloksen ollessa alle -20 vastaukset arvotaan. Pelityylejä ovat mm. sekvenssihaku, sekvenssihaku muunnetuilla merkeillä, viimeisen siirron(oma/vastustaja) voittava siirto, n-merkin välein toistuvat siirrot. |
| Saikyou Markku Velinen Dzarg | Ohjelma ottaa muistiin kahdeksaa eri pituutta olevia siirtosarjoja (osassa molempien siirrot, osassa vain vastuksen). Kunhan yhdenkin sarjan perusteella löytyy ennustettavissa oleva vastuksen siirto, ohjelma siirtää voittavan siirron. Jos vastus ei siirrä ennakoidusti, sarjan esiintymislukumäärää lasketaan. Pisimmillä sarjoilla on painotuksessa isoin kerroin ja lyhimmillä pienin. Satunnaisesti (omalla seedatulla funktiolla) ohjelma siirtää, jos se ei pysty ennustamaan vastuksen siirtoa tai ajoittain häviöllä ollessaan harhauttaakseen vastustajaa. Välierässä Shotgunia vastaan murskatappion jälkeen piti lisätä myös raukkamainen ominaisuus, pysyvä satunnaistila, joka aktivoituu jos äly käy yli 30:llä häviöllä. |
| Spock Mika Urtela Apodus | Legendaarisen ohjelmoijan legendaarinen ohjelma käyttää useita pelaajamalleja ja suorittaa joka siirrolla mallinvalintaa. Mallinvalinta suoritetaan useiden eripituisten siirtohistorioiden perusteella. Tarkastelussa käytetään myös erittäin lyhyitä ajanjaksoja, jotta voidaan mukautua pelin aikana strategiaan vaihtaviin kilpailijoihin nopeasti. Jokaiselle pelaajamallille tarkistetaan kuudella eri strategialla, käyttäytyykö vastustaja jollakin tapaa kyseisen mallin mukaisesti. Malli, joka väittää ennustavansa kullakin ajanhetkellä vastustajaa tarkimmin jollakin strategiallaan valitaan seuraavan siirron ennustajaksi. |
| jousipallo Jouko Joensuu Jogge | Tekoäly tekee valintansa aikaisempien kierrosten perusteella yrittäen myös tutkia, millaista älyä tai älyttömyyttä on vastassa. |
| onnekas Chiman | Ohjelma pyörittää eri periaatteilla toimivia tekoälyjä, jotka pelaavat peliä vastustajan näkökulmasta. Jos vastustajan käyttäytyminen sopii johonkin näistä riittävän hyvin, ohjelma valitsee omaksi siirrokseen kyseisen tekoälyn antaman siirron vastineen. Muussa tapauksessa ohjelma pysyy etukäteen määritellyssä siirtosarjassa. |
| Daeron_NG Teemu Koskinen Daeron | Ohjelma ennustaa, mitä itse valitsisi vastustajan näkökulmasta, ja valitseekin toisin. |
| set Antti Laaksonen Antti Laaksonen | Tekoälyllä on kaksi tavoitetta: se pyrkii voittamaan heikot vastustajat ja antamaan hyville vastustajille mahdollisimman vähän pisteitä. Tekoäly yrittää arvata vastustajan valinnan tutkimalla pelihistoriasta, miten vastustaja toimi aiemmin vastaavassa tilanteessa. Jos tekoäly on liikaa häviöllä, se alkaa pelata satunnaisesti. |
| himmeli XYZ | Ohjelma etsii aikaisemmista eristä samanlaisia pelitilanteita ja laskee yleisimmän vastauksen jota tilanteessa on käytetty ja lopuksi vastaa sen mukaan. Ohjelma jäi aika pahasti kesken. Tarkoitus oli lisätä "älylle" hieman tilannetajua, eli kuinka toimitaan kun koko homma pissii pahasti. Ohjelma olisi mahdollisesti ruvennut painottamaan valintojaan vähiten käytettyihin vastauksiin. Tavoitteena on voittaa esimerkissä ollut "äly". |
| Brainluck Topi Musto DaeD | Tekoäly ennustaa kussakin tilanteessa vastustajan pelaavan saman siirron kuin se pelasi edellisellä kerralla tilanteessa, jossa oli sama kahden pituinen siirtohistoria (eli sama edellinen siirto ja sitä edellinen siirto sekä tekoälyltä että vastustajalta). |
| typerys Harri Nieminen Moiman | Tekoälyn toiminta perustuu satunnaisuuteen, mutta se ymmärtää myös yksinkertaista säännöllisyyttä. |
| KiviKova Leo Lehikoinen Legutus | Tekoäly pelaa satunnaisesti taulukoitujen arvojen mukaan, ellei se tunnista vastustajansa taktiikkaa (tai se on random). Mikäli vastustaja esimerkiksi laittaa koko ajan samaa, käyttää jotakin kuviota (esim. "KSPKSPKSP...") tai painottaa jotakin arvoa, niin tekoäly huomaa nämä ja tekee valinnan, joka voittaa edellyttäen, että vastustaja jatkaa samaan malliin. Tekoälyssä on myös ominaisuus "viisaiden" vastustajien varalle, jolloin äly menee random-tilaan, mikäli omat taktikoinnit eivät toimi niin kuin niiden pitäisi, esimerkiksi jos vastustaja käyttää hyväksi jotakin tiettyä älyn taktiikkaa. Tavoitteena onkin voittaa "älyttömät älyt" ja pelata sitten randomilla muita vastaan. |
| nameless | Ohjelma pitää kirjaa sitä vastaan pelattujen siirtojen historiasta ja pelaa niitä voittavia siirtoja. Näin on todennäköistä, että samoja lyhyitä siirtosarjoja toistava vastustaja saa usein köniinsä. Ohjelman hävitessä tai pelatessa tasan se hyppää toiseen kohtaan siirtohistoriassa, minkä takia sen siirrot eivät helposti ennustettavissa silloin kun se ei saa voittoja. Luultavasti ohjelmaa ei ole helppo päihittää kovin isolla erolla, mutta toisaalta se ei voita paljon paitsi hyvin heikkoja vastuksia vastaan. Nämä ominaisuudet on toteutettu niin, että siirtohistorian indeksiä kasvatetaan yhdellä kun ohjelma voitaa, muuten siinä hypätään tähän mennessä tulleiden voittojen ja ei-voittojen tulon verran eteenpäin. Jälkimmäinen luku muuttuu jatkuvasti, joten sitä ei ole helppo ennustaa. Laskut tehdään modulo historia nykyinen pituus, jotta merkkijonosta ei osoiteta ohitse. Aluksi arvoiksi on annettu kaksi voittoa ja kaksi ei-voittoa, sekä keksitty siirtohistoria "KPS", jotta ohjelman toiminta ei riipu liian selvästi vastustajan alkusiirroista. |
| tekoaly | Tekoälyn taktiikkana on aina valita se, jolla äsken olisi päässyt tiettyyn tulokseen (voittoon, häviöön tai tasapeliin). Alussa se valitsee välineen, jolla olisi viimeksi hävinnyt, mutta jos tämä taktiikka alkaa tuottaa enemmän häviöitä kuin voittoja tai jos tasapelejä tulee kovin paljon, se vaihtaa tavoitettaan eli alkaa pelata esimerkiksi valintoja, jotka olisivat viime kierroksella voittaneet tai tuottaneet tasapelin. |
| paperiaivo Ilari Richardt Style | KSP botti pyrkii tunnistamaan vastustajan taktiikan kolmella eri tavalla, ennen kuin "arvaa": 1) Tutkitaan kolmea viimeisintä siirtoa ja verrataan niitä koko pelin historiaan; jos yhtäläisyyksiä löytyy, etsitään yhtäläisyyttä seuraava siirto ja näin pyritään päättelemään seuraava siirto. 2) Sama kuin 1) mutta suuremmalla hakukohteella (5). 3) Pyritään 2 viimeisen siirron perusteella, tutkimatta menneisyyteen päätellä seuraava siirto, esim. KK -> K -> valitaan P. |
| 0xF4 Kari Rantanen Grandi | 0xF4 ei tähtää järjelliseen ajatteluun, vaikka vastustajan siirrot vaikuttavatkin sen valintoihin. Tavoitteena on enemmänkin vastustajan harhauttaminen kuin sen taktiikan analysoiminen. Haluan nähdä miten pitkälle tälläisellä räpellyksellä voi päästä. |
| Code_395 Sami Kalliomäki Sami345 | Tunnistaa sarjoja vastustajan toiminnasta ja toimii sen mukaan. Toimii erityisen hyvin esimerkkiälyä ja samaa sarjaa toistavia tekoälyjä vastaan. Tämän ei pitänyt olla minun varsinainen tekoäly vaan vain testiäly, mutta alkuperäinen suunnitelmani epäonnistui. |
| FAGGOT petrisi | Vastustajan pelistä haetaan toistuvia patterneja joiden perusteella valitaan oma käsi. |
| u137 Teemu Valo User137 | Analysoi vastustajan pelityyliä ja käyttää hitusen satunnaistaulua. Välierässä käytin tyhmää tapaa joka "uskoo" että vastustaja käyttää läpi koko pelin samaa tyyliä, nyt tämä ottaa huomioon vain 5 viimeistä siirtoa ja omaksuu vastustajan siirrot paremmin. |
| Encephalon Frozenball | Tekoäly koettaa ennustaa siirtohistorian perusteella. |
| foo Juho Pinola JP_94 | Tekoäly tulostaa vastauksensa joko vastustajan yksittäisen syötteen tai saman syötteen esiintymistiheyden mukaan tietyssä järjestyksessä. Älyssä on myös ominaisuus, joka tulostaa tietyin väliajoin ennalta määritetyn syötteen riippumatta vastustajan edellisistä siirroista. |
| Jokuihme Lari Sinisalo Lr5 | Tekoäly valitsee useimmiten sen kirjaimen, jolla voitto olisi tullut suurimmassa osassa tapauksia, ja välillä sen, jolla voittaa tämän logiikan valitseman voittavan vaihtoehdon. |
| Kolykko Teemu Kukkola tesmu | Perustuu todennäköisyyteen, pisteyttää voittaneet ja hävinneet valinnat sekä tasapelit ja valitsee yleisimmäin vaihtoehdon. Jos ei löydy selkeästi yleisintä vaihtoehtoa niin valitaan vuorotellen K, S ja P. |
| Kaksari Otto Martikainen MetalRain | Valitsee vuorotellen muun kuin vihollisen edellisen valinnan. |
| Fail Jouni Joensuu JTJ | Tekoäly valitsee vastuksensa todennäköisyydestä, jolla edelliset kierrokset olisi voitettu. Eli jo lähtökohtaisesti tällä tekoälyllä kisataan kilpailun viimeisestä sijasta. |
| MonkeyBot Lauri Niskanen Ape | MonkeyBot on tehty voittamaan esimerkkibotin taktiikka. Esimerkkibotti pelaa sellaisen vaihtoehdon, jolla olisi viime kierroksella voittanut. MonkeyBot puolestaa pelaa sen vaihtoehdon, jolla se voittaisi esimerkkibotin. Se siis valitsee sen, jolla voittaa, jos vastustaja pelaa sen, jolla olisi viimeksi voittanut. Yksinkertaisemmin MonkeyBot valitseen sen, joka olisi viimeksi hävinnyt. Tämän lisäksi se kerää tilastoa viideltä edelliseltä kierrokselta. Mikäli vastustaja on pelannut saman vaihtoehdon kolme kertaa tai useammin näillä kierroksilla, pelaa MonkeyBot sen, joka voittaa tämän toistuvan / painotetun valinnan. |
| r5nd0m Teijo Mursu ZcMander | Käyttää todennäköisyyksiä vastaukseen, vaikkei kuitenkaan ihan suoraan, vaan on nimenomaan suunniteltu pelaamaan sitä vastaan. |
| palikka Lari Vehkalampi vehkis91 | Äly laskee todennäköisyyslaskennalla, mikä siirto on vastustajan seuraava. Myös paria muuta kikkaa on käytetty mutta en osaa selittää miten ne toimivat. Tarkemmin ajateltuna tuo ei edes ole oikeaa todennäköisyyslaskentaa, mutta tosiaan en osaa selittää tuon älyn toimintaa... -.- |
| JankenB Vili Hietala Viltzu | "Päättelee", minkä vastustaja aikoo valita, ja valitsee sitten vastustajan voittavan asennon. |
| esim | Esimerkkiäly valitsee aluksi kiven ja myöhemmin aina sen välineen, jolla olisi voittanut edellisen kierroksen. |
| byrokrat Jussi Kilpeläinen Juice | Pääasiassa tekoäly pyrkii käyttämään primitiivisesti ja pseudosatunnaisesti kierroksen numeron ja vastustajan siirron avulla laskettua siirtosarjaa. Lisäksi tarkkaillaan, suosiiko vastustaja jotakin tiettyä siirtoa. Älyhän on mahdottoman typerä ja pikaisesti kyhätty, mutta osallistun ihan periaatteesta tällä bugisella räpellyksellä, kun aiemmin on putkan kisat jääneet välistä :) Äly tarjoaa paperia suunnilleen joka väliin, siksi nimesin sen byrokraatiksi. |
| Puudeli Niko Hämäläinen Milo | Ohjelma yrittää tutkia, käyttääkö vastustaja jotain selvää toistoliikettä (sama elementti uudelleen ja uudelleen, tai esimerkin mukainen kopiointi), jos ei, niin yrittää laskea jonkin sortin todennäköisyyttä seuraavalle lyönnille. Ja kun kaikki epäonnistuu, heitetään hatusta uusi arvo. |
| kaiku | Kaiku tulostaa aina saman merkin kuin vastustaja viimeksi. |
| tumpelo Meitzi | Vastaukset on etukäteen määrätty, ensimmäinen kolmannes vastataan sakset, sitten paperi ja lopuksi kivi. |
| luuseri | Luuseri valitsee aina sen, jolla olisi äsken hävinnyt. |
| Risaksi Toni Mäkinen Masfonos | Pelaa vain ja ainoastaan saksilla. |
| NIGGERx2 Perttu Ahola celeron55 | Perustaa valintansa yksinkertaisesti vastustajan eniten käyttämään valintaan. |