Kirjautuminen

Haku

Tehtävät

Kilpailu

Ohjelmoi tekoäly!
Aikaa on 6.1. saakka.

Kilpailut: Lukupeli: tulokset

Järjestäjä: Metabolix

Kesällä 2014 Ohjelmointiputkassa pidettiin tekoälykilpailu. Aiheena oli kahden pelaajan Lukupeli. Pelissä tekoälyn pitää arvata luku väliltä 0–9 niin, että luku on pienempi kuin vastustajalla mutta kuitenkin mahdollisimman suuri; molemmat saavat pisteitä pienemmän luvun verran, ja lisäksi pienemmän luvun valinnut saa kolme lisäpistettä tai tasapelissä kumpikin yhden lisäpisteen. Ottelun voittamisesta sai myös huomattavan määrän lisäpisteitä; tarkempi laskukaava on kuvattu kilpailun säännöissä. Ottelun 1000 kierroksen aikana tekoälyllä oli mahdollisuus analysoida vastustajan tekniikkaa ja sopeutua siihen. Kilpailun aikana julkaistiin välituloksia, joita saattoi hyödyntää tekoälyn kehittämisessä.

Kilpailuun osallistui 32 ohjelmaa. Perinteisille pelialgoritmeille ei ollut juuri sijaa tässä kisassa, vaan kaikenlaiset kukat saivat kukkia: Kärjessä yksi hyödynsi kilpailun välitulosten siirtosarjoja ja todennäköisyyksiä, toinen analysoi jollain tasolla taktiikoita, kolmas yllätti pelaamalla ensimmäisen siirron jälkeen yleensä joko pelkkiä nollia tai pelkkiä yhdeksikköjä ja neljäs taas luotti vain yhden siirron mittaiseen muistiin kulloisestakin ottelusta. Muussa joukossa oli monenlaista yritelmää keskiarvoista pseudosatunnaislukuihin ja vakioriveistä erilaisiin hämäyksiin.

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. V, T ja H merkitsevät voittoja, tasapelejä ja häviöitä otteluissa. Pisteet ovat otteluissa kerättyjä pisteitä, ja tulos on säännöissä mainitulla kaavalla näistä laskettu kokonaispistemäärä.

sijatekoälykielitekijänimimerkkiVTHpisteettulos
1.PahaApinaPascal200111398887495776
2.R33LPythonAntti VainioAnaatti200111311987304596
3.HaistajaPythonChiman2218962456977454
4.prog09Cpr0l3191111129356681898
5.ThaiCurryBrainfuckLauri KenttäMetabolix21100865016542174
6.LuuuserC++Oskari MieskolainenOskuz20101821496225518
7.greedyPythonLari KoponenL2-K221100694816167734
8.KukkaJavaJesse NiininenFINDarkside21100565405883032
9.kompaC++Johannes Tuomelajohku901948748485843984
10.esim(useita)21100444765617624
11.ZZplNMQPerl19111567795446466
12.nnx9PythonMarkku JärvinenOldfield17113762195432322
13.LukuilijaC++Elias KosunenEki++17113740235384010
14.ElStupidoPythonqwerty1230216213807615311334
15.ElReinoCEino-Pekka Kantoreino15124833545147468
16.Simple1JavaTimo SakariTimmmo15106822855123950
17.ArvainC#Antti Airtoairtantt14017909985094724
18.ajvC#Aapo Vuoristoajv15115789535050646
19.ysimCLauri KenttäMetabolix00312209124860064
20.hop1FortranJali Heinonenjalski14017788954828458
21.MatildaCMarko Kurkinenmakumaku13117732584483532
22.hidariCLauri KenttäMetabolix11128865294333670
23.SiniC#Oskari MieskolainenOskuz60251288124159336
24.sqrtPythonJuha TeurokoskiTeuro10021648343635468
25.purkkaPython7024802523311928
26.RanTomiJavaTimo SakariTimmmo9022542613181950
27.jytkyC++Antti LaaksonenAntti Laaksonen7123732473157818
28.ArpojaJavaTuomas KarjalainenTuomasK30281023542914524
29.SafeApePythonVesipeto6025704242874800
30.High5CTimo SakariTimmmo10301175652807342
31.JHNAC++Juho Häkkinenjeeukko7024450092536582
32.dewabeC++Teemu Vartiainendewabe6025435712284034

Onnea voittajalle!

Tilastoja

Tekoälyt käyttivät eri aloituslukuja seuraavasti:

0123456789
11500311236

Koko kilpailun lukujakauma taas oli tällainen:

0123456789
569033900792872932349460575303723448314825895558831
57,4 %9,1 %2,9 %3,3 %4,6 %5,3 %2,4 %3,2 %5,9 %5,9 %

Kisassa pelattiin 189 kertaa 992:sta pelkkiä nollia sisältävä rivi, ja otteluista jopa 55 (11 %) sisälsi molemmilta pelaajilta pelkkiä nollia.

Kilpailussa jaetuista pisteistä kaikkiaan 38,9 prosenttia kertyi suoraan peleistä ja 61,1 prosenttia otteluvoitoista.

Oheisessa kaaviossa tekoälyjen väliset etäisyydet kuvaavat, miten paljon tekoälyjen tulokset eroavat toisistaan. Nähdään, että kärkijoukko on melko hajallaan muiden tekoälyjen seassa; kuvaajassa oikealla on heikommin menestyneitä ohjelmia, vasemmalla alhaalla nollapeleillä menestyneitä ohjelmia ja vasemmalla ylhäällä enemmän isommilla luvuilla pelanneita.

Kaavio ohjelmien tulosten samankaltaisuudesta

Pelit

Yksittäisten otteluiden tulokset kerrotaan erillisellä sivulla. Kaikkien otteluiden siirrot on koottu pakettiin.

Ohjelmat

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

PahaApina

Ensiksi tekoäly yrittää pelata suoraan tiedostosta luetun mallin mukaan niin kauan, kuin vastustajan rivi noudattaa täsmälleen tiedostoa. Tiedostossa on eräiden tekoälyjen vakiorivejä, joita vastaan on helppo valita paras luku. Lisäksi tiedostossa on röyhkeästi välituloksista poimittuja siirtosarjoja, joilla saadaan hyvät pisteet muutamaa vastustajaa vastaan. Datatiedostossa voi laittaa tämän ”apinamoodin” päälle tai pois; välituloksissa tekoäly ei apinoinut.

Jos mikään tiedoston peli ei sovi tilanteeseen täydellisesti, siirrytään karkeaan todennäköisyyslaskentaan. Tekoäly käyttää ennustamiseen viittä muuttujaa: kahden edellisen kierroksen siirtoja (2+2) ja neljän edellisen oman siirron keskiarvoa. Datatiedoston peleistä muodostetaan kustakin todennäköisyyskertoimet sille, kuinka nämä viisi muuttujaa yksitellen ennustavat vastustajan seuraavaa valintaa. Kertoimia päivitetään pelin kuluessa kertyvällä tiedolla, ja myös aivan perustilasta aloittavia kertoimia lisätään joka kierroksella. Kertoimista lasketaan vastustajan eri valinnoille todennäköisyys kertomalla kunkin viiden muuttujan antama kerroin keskenään. Sen jälkeen ohjelma valitsee todennäköisimmän luvun siitä mallista, joka olisi tähän mennessä ennustanut parhaiten.

Jos vastustaja pelaa paljon nollia, koetetaan houkutella yhdeksiköillä vastustajaa isompiin lukuihin, mutta jos vastustaja ei lähde mukaan, aletaan itsekin pelata nollia.

R33L
Antti Vainio
Anaatti

Tekoälyn pääperiaatteet ovat voiton tavoittelu ja hyvien pisteiden kerääminen, sekä häviöllä ollessaan lähinnä pisteiden maksimointi, minkä lisäksi tekoäly yrittää myös vaikuttaa vastutajan pelaamiin lukuihin.

Tekoäly pyörittää taustalla useita eri luvunvalitsinfunktioita, joiden tehokkuutta mitataan vastustajan valintojen perusteella. Käyttämällä kulloinkin parasta valitsinfunktiota, tekoälyn pitäisi pysyä voitolla ja saada varsin paljon pisteitä. Tämä taktiikka kuitenkin johtaa useimmiten pelkkien nollien pelaamiseen, minkä vuoksi pisteitä ei kerry kovinkaan paljon. Siksi tekoäly kokeilee välillä myös hyvin isojen lukujen pelaamista siinä toivossa, että vastustajakin valitsisi isompia lukuja, mikä johtaisi suurempaan pistesaaliiseen. Jos tämä taktiikka näyttää johtavan häviöön tai kerryttää vähemmän pisteitä kuin muuten, lopetetaan isojen lukujen pelaaminen.

Lopuksi, jos tekoäly huomaa olevansa liian pahasti häviöllä, se lopettaa voiton tavoittelemisen ja pyrkii vain pistesaaliinsa maksimointiin pelaamalla lähinnä ysejä.

Haistaja
Chiman

Pyöritetään eri periaatteilla toimivia tekoälyjä, jotka pelaavat peliä vastustajan näkökulmasta. Jos vastustajan oikea käytös sopii johonkin näistä riittävän hyvin, valitaan omaksi siirroksi kyseisen tekoälyn antaman siirron vastine. Muuten noudatetaan vakiosiirtosarjaa.

Tekoälyt perustuvat vastustajan matkimiseen, vastustajan edellistä siirtoa vastaan pelaamiseen, saman voittoisan siirron toistamiseen ja toistuvien siirtosarjojen analysointiin.

prog09
pr0l3
Aloittaa ykkösellä. Jos vastustaja aloittaa nollalla, kerää pisteitä pelaamalla yhdeksikköjä. Muuten yrittää voittaa pelaamalla nollia. Jos vastustaja pelaa alussa viisi samaa, alkaa pelata yhden pienempää kuin vastustaja (tai nollaa).
ThaiCurry
Lauri Kenttä
Metabolix
ThaiCurry valitsee yhtä pienemmän luvun kuin vastustaja viimeksi samassa tilanteessa. Jos muistissa ei ole nykyisen kaltaista tilannetta tai jos vastustajalta odotetaan nollaa, tekoäly valitsee turvallisesti nollan. Pelitilanne käsittää edellisen oman numeron.
Luuuser
Oskari Mieskolainen
Oskuz
Palauttaa yhtä pienemmän kuin vastustaja pari kierrosta takaperin.
greedy
Lari Koponen
L2-K2

Erittäin yksinkertainen ahne algoritmi. Pyrkii ensisijaisesti varmistamaan voiton (tai vähintään tasapelin) kustakin pelistä pelaamalla riittävän määrän nollia. Tämän tavoitteen ollessa turvattu maksimoi seuraavan siirron pisteiden odotusarvoa olettaen vastustajan pelaavan satunnaisesti jonkin edellisistä siirroistaan.

Koska ylläoleva kuvaus tuottaisi tekoälyn, joka pelaisi erittäin heikosti tiettyjä toistuvia kuvioita vastaan (kuten 09090909...), on tekoälyyn lisätty yksinkertainen sakkotermi näitä tilanteita vastaan. Tämä termi muuntaa tekoälyn pelitapaa hieman kohti esimerkkitekoälyä aina, kun se joutuu erikseen turvaamaan johtoaan pelaamalla nollan. Lähdekoodia tutkimalla voinee silti vielä keksiä, missä tilanteissa tämä sakkotermi ei ole riittävä.

Kukka
Jesse Niininen
FINDarkside
Ohjelma pelaa nollaa, ellei ole erittäin todennäiköistä, että suurempaa lukua pelaamalla voittaa (vastustaja pelaa vain yhtä lukua tai vastustajan pienin luku on suurempi kuin 1).
kompa
Johannes Tuomela
johku90
Tekoäly arvaa aina vähän pienemmän luvun, kuin vastustaja viimeistä edellisellä kerralla.
esimEsimerkki valitsee aina luvun 0.
ZZplNMQValitsee pienemmän kuin vastustajan pienin.
nnx9
Markku Järvinen
Oldfield

Hermoverkko määrittelee numeron väliltä 0–9 seuraavalla tavalla: Verkolle annetaan sisään jokaisen vuoron jälkeen kaksi vastapuolen viimeiseksi syöttämää numeroa. Jokainen vastapelaajan syöte, joka on enemmän kuin 0, muuttaa painojen arvoja. Neuronien arvo saadaan kertomalla vastapuolen syötteet painojen arvolla ja laskemalla kumpikin kerrottu luku yhteen. Näistä neuronien arvoista lasketaan sigmoidifunktion avulla 2 liukulukua. Jos ensimmäisen neuronin arvo on suurempi kuin toisen, tarkistetaan, voidaanko vähentää ensimmäisestä vastapuolen viimeksi syöttämästä 2; jos voidaan, vähennetään ja palautetaan saatu numero, muuten palautetaan alkuperäinen numero. Jos toisen neuronin arvo on suurempi (tai yhtäsuuri), tehdään toiselle vastapuolen viimeksi syöttämälle numerolle edellä kuvattu toimenpide.

Lisäominaisuutena: Jos vastapuoli pelaa samaa lukua 2 kertaa peräkkäin, oletetaan, että aikoo pelata saman luvun myös 3 kerran, ja vähennetään samasta luvusta 2 ja tulostetaan se, kunhan luku ei mene alle 0.

Lukuilija
Elias Kosunen
Eki++
Vastaus on yhden pienempi kuin vastustajan kolmen viimeisimmän vastauksen keskiarvo. Lisäksi vetää vähän väliä luvun hatusta, millä yrittää johtaa vastustajan systeemiä harhaan.
ElStupido
qwerty12302
Ohjelma ottaa muistiin vastustajan edellisellä kierroksella antaman luvun, vähentää siitä yhden ja antaa sen seuraavalla kierroksella. Ensimmäisellä kierroksella ohjelma antaa luvun yksi.
ElReino
Eino-Pekka Kanto
reino

ElReino suorittaa rinnakkain useita strategioita ja valitsee strategian kahden kriteerin perusteella: strategian piti tuottaa enemmän pisteitä itselle, ja sen pitää tuottaa eniten pisteitä edellisen kriteerin perusteella valituista strategioista.

ElReino koittaa valita luvun joka on yhtä pienempi vastustajan luvusta. Jos vastustaja pelaa nollalla niin silloin ElReinokin pelaa nollalla. ElReinon strategioihin kuuluu luvun seitsemän tai yhdeksän valitseminen, edellisen luvun valitseminen, luvun valitseminen joka olisi tuottanut edellisellä kierroksella eniten pisteitä tai luvun valitseminen vastustajan kymmenen edellisen siirron perusteella.

ElReino - Villin Lännen pelätyin tekoäly.

Simple1
Timo Sakari
Timmmo
Yksinkertainen algoritmi, joka pyrkii mimimoimaan tappiot ja mahdollisuuksien mukaan pelaamaan isommillakin. Hävityn vuoron jälkeen algoritmi pelaa aina nollan, muulloin se valitsee satunnaisesti jonkin vastustajan edellisistä numeroista, vähentäen tästä ykkösen. Algoritmi huomaa myös tilanteen, jossa otteluparin voitto tai tappio on varma, ja pelaa siinä tilanteessa yhdeksikköä pyrkien maksimoimaan loppupelin pistekertymän. Mikäli vastustaja haluaa pelata isoa peliä, algoritmi lähtee tähän mukaan maksimoiden samalla mahdollisuutensa saada hyvät pisteet.
Arvain
Antti Airto
airtantt
Valitaan luku siten, että vastustajan luvuista x% on ollut sitä suurempia. Kuitenkin pidetään omien lukujen keskiarvo riittävän suurena.
ajv
Aapo Vuoristo
ajv
Sisältää erilaisia yksinkertaisia taktiikoita. Pelin edetessä tutkii, mikä taktiikka olisi pärjännyt parhaiten, ja valitsee aina sen.
ysim
Lauri Kenttä
Metabolix
Tekoäly valitsee aina luvun 9. Logiikka on se, että tällä tavalla hyvä vastustaja alkaa valita aina luvun 8, jolloin tekoäly saa aina 8 pistettä ja kerää reilun määrän pisteitä, vaikka ottelut se tietenkin häviää.
hop1
Jali Heinonen
jalski
Opettaa Hopfield-neuroverkkoa aina vastustajan kolmella edellisellä siirrolla. Verkolta kysytään, mikä on vastustajan todennäköisin seuraava vastaus (pienin bittivirhe), ja vähennetään tästä luvusta yksi.
Matilda
Marko Kurkinen
makumaku
Ei mitään logiikkaa.
hidari
Lauri Kenttä
Metabolix
Ohjelma reagoi hitaasti vastustajan trendiin: se siirtyy joka kierroksen jälkeen omasta luvustaan aina noin puolet kohti vastustajan lukua.
Sini
Oskari Mieskolainen
Oskuz

Sini valitsee seuraavan luvun 3 algoritmin avulla:

  • Seuraava on vastustajan edellistä pienempi.
  • Vastustajan tulosteesta löytyy jokin selvä kuvio/toistuvuus.
  • Vastustajan seuraava luku on oma vanha.

Näistä käytettävä valitaan niiden tähänastista menestystä vertailemalla. Jos mikään ei ole menestynyt tarpeeksi hyvin, valitaan ”nollalinja”.

sqrt
Juha Teurokoski
Teuro

Tekoäly valitsee 20 ensimmäisen kierroksen aikana jakojäännöksen numeron yhdeksän kanssa. Tämän jälkeen tekoäly laskee vastustajan kymmenen viimeisimmän siirron keskiarvon, josta vähennetään numero yksi.

Ohjelman ensimmäisen version mukaan tullutta nimeä (neliöjuuri) en muuttanut, vaikka tätä tekoäly ei enää käytäkään.

purkkaJauhaa samaa pätkää.
RanTomi
Timo Sakari
Timmmo
Pikainen kyhäelmä, joka valitsee luvun pseudosatunnaisesti painottaen pienempiä numeroita. Nollalla suurin todennäköisyys.
jytky
Antti Laaksonen
Tekoäly valitsee luvun, joka on pienempi kuin vastustajan valitsemien lukujen keskiarvo siihen mennessä.
Arpoja
Tuomas Karjalainen
TuomasK
Arpoo vain satunnaislukuja ennalta määritetyllä siemenluvulla.
SafeApe
Vesipeto
Tekoäly matkii sitä, miten vastustaja on pelannut keskimäärin. Välillä tarjotaan keskiarvosta hieman suurempaa, jotta ei päädyttäisi ”nollapeliin”, jos vastustaja on ns. yhteistyöhaluinen. Yleensä kuitenkin tarjotaan hieman pienempää, jotta odotusarvo voitolle pitkällä tähtäimellä olisi positiivinen.
High5
Timo Sakari
Timmmo
Algoritmi tarjoaa 100 % todennäköisyysellä viitosta, siitä nimi High5 eli kotoisemin yläfemma. Tämä huumorilla väsätty ”äly” tulee todennäköisesti kamppailemaan kilpailun viimeisestä sijasta.
JHNA
Juho Häkkinen
jeeukko

Simppeli (ja huono), laskee keskiarvon ja vähentää yhden. Tarkistaa myös, onko luku sallittu. That's it! :D

P.S. Nimi on Juhon Huono Numeron Arvaaja.

dewabe
Teemu Vartiainen
dewabe
Oma numero on vastustajan numeroiden keskiarvo vähennettynä yhdellä.

Lopuksi

Kiitos kaikille osallistujille hyvästä kilpailusta, ja tervetuloa mukaan taas ensi kerralla.

Tietoa sivustosta