Kirjautuminen

Haku

Tehtävät

Kilpailu

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

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.

sijatekoälykielitekijänimimerkkipisteet
1.ShotgunJavaJorma SainioFooBat19098
2.Leikkuri09C++Toni HuttunenSeriffi18748
3.SaikyouJavaMarkku VelinenDzarg17363
4.SpockC++Mika UrtelaApodus17265
5.jousipalloPythonJouko JoensuuJogge17060
6.onnekasPythonChiman14945
7.Daeron_NGCTeemu KoskinenDaeron14326
8.setJavaAntti LaaksonenAntti Laaksonen13528
9.himmeliPythonXYZ12372
10.BrainluckBrainfuckTopi MustoDaeD12326
11.typerysPythonHarri NieminenMoiman10914
12.KiviKovaC++Leo LehikoinenLegutus10264
13.namelessPython8086
14.tekoalyC++7901
15.paperiaivoC++Ilari RichardtStyle7819
16.0xF4C++Kari RantanenGrandi6456
17.Code_395C++Sami KalliomäkiSami3455909
18.FAGGOTC#petrisi4856
19.u137PascalTeemu ValoUser1374619
20.EncephalonPythonFrozenball536
21.fooPythonJuho PinolaJP_94-1242
22.JokuihmeC++Lari SinisaloLr5-3376
23.KolykkoPHPTeemu Kukkolatesmu-6172
24.KaksariPythonOtto MartikainenMetalRain-7688
25.FailPHPJouni JoensuuJTJ-8994
26.MonkeyBotPythonLauri NiskanenApe-9255
27.r5nd0mPythonTeijo MursuZcMander-10064
28.palikkaC++Lari Vehkalampivehkis91-10073
29.JankenBPythonVili HietalaViltzu-10108
30.esim*-12759
31.byrokratPythonJussi KilpeläinenJuice-15283
32.PuudeliCNiko HämäläinenMilo-15575
33.kaikuBrainfuck-16320
34.tumpeloVB.NetMeitzi-21014
35.luuseriFreeBASIC-24803
36.RisaksiC++Toni MäkinenMasfonos-25204
37.NIGGERx2CPerttu Aholaceleron55-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:

Kivi 34,6 %, sakset 33,4 %, paperi 32,0 %

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.

Kaavio älyjen samankaltaisuudesta

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.

tekoalyTekoä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.
esimEsimerkkiä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.
kaikuKaiku 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.
luuseriLuuseri 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.
Tietoa sivustosta