Kilpailut: Älykäs ohjelma - tulokset

Ohjelmointiputkan syksyn 2006 kilpailussa oli tehtävänä luoda ohjelma, joka osaa täydentää säännöllisiä sarjoja älykkään tuntuisesti. Esimerkiksi ohjelmalle kerrotaan, että sarja alkaa A1, B2, C3, D4, jolloin ohjelma osaa jatkaa sarjaa E5, F6, G7. Kilpailun aihe osoittautui varsin haastavaksi, ja moni kilpailija luopui leikistä kesken. Valmistuneet ohjelmat ovat kuitenkin järjestään tasokkaita, ja kaikkia voi hyvällä syyllä kutsua älykkäiksi ohjelmiksi.

Ohjelmat ja tulokset

Kilpailuun osallistui seitsemän ohjelmaa, joista monen tekijä on tuttu nimi aiemmista kilpailuista. Kilpailussa ohjelmien ratkottavana oli 144 sarjaa, joista osa oli varsin helppoja, osa taas tietokoneelle hyvin haastavia. Kaksi ohjelmaa oli yli muiden: Jorma Sainion "aiq" ja Petteri Aimosen "zizzo" ilmoittivat oikean vastauksen yli kolmeen neljäsosaan sarjoista.

Seuraavan taulukon tuloksissa "pisteet" tarkoittaa oikein ratkaistujen sarjojen määrää. Oikeiden vastausten suhde sarjojen kokonaismäärään näkyy kohdassa "osuus". Erikseen on merkitty niiden sarjojen määrä, jotka ratkaisi oikein vain yksi ohjelma ("ainoa o.") tai joita vain yksi ohjelma ei osannut ratkaista ("ainoa v."). Tarkkoihin tuloksiin pääsee käsiksi linkeistä.

Voit kopioida kaikki kilpailuun osallistuneet ohjelmat lähdekoodeineen: alyo.zip (0,5 Mt).

Kilpailun sarjat

Seuraavilla sivuilla ovat kaikki kilpailun sarjat. Jokaisen sarjan kohdalla on kerrottu, mitkä ohjelmat osasivat ratkaista kyseisen sarjan. Sarjasta on näkyvillä ainoastaan sarjan alku, jonka myös ohjelmat saivat tietoonsa. Kokonaisen sarjan pystyy katsomaan merkitsemällä hiirellä sarjan jäljessä tulevan alueen. Näin voi kokeilla, olisiko itse osannut ratkaista sarjaa.

• sarjat 1 - 72
• sarjat 73 - 144
• sarjat tekstinä

Kilpailun säännöissä luvattiin, että kaikki sarjat ovat ihmiselle helppoja. Tämän varmistamiseksi Ohjelmointiputkan pitkäaikainen käyttäjä Jussi "Grey" Kingelin toimi kilpailun sensorina ratkaisten 20 sarjaa, jotka oli valittu vaikeimpien sarjojen joukosta. Kaikkiin sarjoihin löytyi yksiselitteinen vastaus, ja Kingelin ei luonnehtinut yhtäkään edes erityisen vaikeaksi.

Tilastoja

Sarjat oli valittu siksi onnistuneesti, että ohjelmien erot tulivat niiden ratkaisussa hyvin esille. 22 sarjaa oli niin helppoja, että kaikki ohjelmat ratkaisivat ne. 59 sarjaa ratkaisi vähintään viisi ohjelmaa. 11 sarjaa ratkaisi vain yksi ohjelma, ja 14 sarjaa olivat ylivoimaisia kaikille kilpailun ohjelmille. Keskimäärin sarjan oikean ratkaisun ilmoitti 3,8 ohjelmaa.

Seuraavaan kuvaan on järjestetty ohjelmat niin, että samoihin tehtäviin oikein ja väärin vastanneet ohjelmat ovat toisiaan lähellä. Näin muodostuu kolme ryhmittymää, jotka on merkitty eri värein. Läheisimmät ohjelmat olivat "aiq" ja "zizzo", kaukaisimmat taas "aiq" ja "alyhoi". Ohjelmista omaperäisin oli "RIVO", joka näkyykin kuvan laidalla.

Ohjelmien kuvaukset

Näin kilpailun osallistujat kuvailivat ohjelmiaan:

Jorma Sainion ohjelma "aiq":

Ohjelma ratkaisee sarjoja jakamalla ne osiin tai muuten yksinkertaistamalla niitä ja sitten kutsumalla itseään uudestaan saaduilla yksinkertaisemmilla sarjoilla. Erilaisia yksinkertaistamisalgoritmeja on ohjelmassa aika monta, ja niillä yritetään löytää ratkaisua siinä järjestyksessä, jossa ne epätodennäköisimmin antavat väärän vastauksen.

Yksinkertaistamisen jälkeen lopulta yleensä päädytään kirjainten tai numeroiden jonoihin, jotka ratkaistaan numeerisesti. Yleisimmin käytetty numeerinen ratkaisumenetelmä on ratkaista q[n] = a*q[n-1]+b sarja. Ohjelma sisältää myös muunlaisia ratkaisumenetelmiä, kuten esim. erotusjonon ratkaiseminen. Harvemmin käytettyjä ovat kertomajonojen ratkaisija ja lineaarikombinaatioden ratkaisija.

Kristian Laakkosen ohjelma "alyhoi":

Ohjelma on väsätty aika kiireessä, eikä siitä ollut alun perinkään tarkoitus tulla mikään kovin hankalia testisarjoja ratkova ohjelma. Ohjelman kehitys päättyi jossain syyskuun 20. päivän tienoilla, kun ajattelin, etten osallistuisikaan moisella roskalla kilpailuun. Nyt noin tunti ennen kilpailuajan umpeutumista aivot menivät sekaisin ja päättivät lähettää sittenkin tämän keskeneräisen version. Toivottavasti en huomenna kadu päätöstäni. Vain yksinkertaisimmat sarjat ratkeavat ohjelmalla.

Antero Korteilan ohjelma "Antero":

Väkisin tehty niin että ratkoo kaikki esimerkkisarjat. Tehokkaampi virittely jäi ajan puutteen vuoksi pois. Tämäkin tuli viime tinkaan.

Martin Pärtelin ohjelma "patterns":

Ohjelma etsii syötteen kirjaimien ja lukujen muodostamasta matriisista sääntöjä, joilla on seuraavat ominaisuudet: tieto siitä, käykö sääntö luvuille vai kirjaimille, alkukoordinaatit (rivi ja sarake), rivin muutos per askel, sarakkeen muutos per askel, rivin muutoksen muutos per askel, sarakkeen muutoksen muutos per askel ja rekursiokaava arvon laskemiseksi.

Esim. kirjainsääntö, jonka alkupiste on (0,0), rivin muutos +1, sarakkeen muutos 0, ja rekursiokaava lambda {|x| return x+2} selittäisi ensimmäisen sarakkeen kirjaimet syötteessä: A1, C3, D5, ??, ??.

Aluksi ohjelma etsii kaikki syötteeseen sopivat yksittäiset säännöt ja karsii niistä pois sellaiset, jotka eivät anna lisää tietoa. Tämä toimii varsin hyvin ja jopa melko nopeasti. Ohjelma osaa havaita aritmeettiset ja geometristen lukujonot sekä kirjoittaa niille rekursiokaavoja.

Seuraavaksi ohjelma yrittää (ajan ja hoksaamisen puutteen takia) melko sokeasti yhdistellä aikaisemmin löydettyjä sääntöjä, kunnes sääntöjen sokea kokeileminen johtaa tarvittavien tulosjäsenten löytämiseen. Yhdistetty sääntö toimii siten, että jokaisen askeleen jälkeen kaikki yhdistelmän säännöt "kloonautuvat" seuraavaa askelta varten. Näin jo parin säännön yhdistelmä kattaa helposti suuren osan syötteestä.

Ohjelma ei osaa käsitellä lainkaan sellaisia syötteitä, joiden jäsenten pituudet eivät ole vakioita tai aidosti kasvavia.

Sami Luostarisen ohjelma "Pölkky":

Ohjelmassa on erilaisia solver-yksiköitä, jotka yrittävät omalla yksinkertaisella tavallaan ratkaista annettua tehtävää. Osa yrittää ratkaista tehtävän suoraan, kun taas osa muokkaa tehtävää niin, että se olisi helpompi ratkaista. Näiden solvereiden yhteispelillä ja rekursiolla saadaan kohtalainen liuta ongelmia ratkaistua. Paljon voisi vielä parantaa, mutta katsotaan mihin tämä riittää.

Meitzin ohjelma "RIVO":

Ohjelman toiminta perustuu kahteen päätapaan ratkaista sarja. Ensin yritetään ratkaista sarja lukujen perusteella, ja mikäli tämä ei onnistu, jatketaan merkkijonoilla. Mikäli näistä kumpikaan ei tuota tulosta, kokeillaan ratkaisua toistoilla, mikä tarkoittaa, että sarjasta jätetään joka toinen, joka kolmas jne. jäsen pois, ja ratkaisua kokeillaan normaalisti.

Merkkijonoratkaisin osaa:

• ottaa jäsenestä merkkijonon: merkin tai merkkejä alusta / lopusta / keskeltä, toinen alusta / lopusta, joka toinen alusta...
• muuttaa merkkijonoa jollakin tapaa: lisäys / vähennys (A -> B), tuplaus, merkin lisäys / vähennys, rullaus peilaus...
• lisätä (mahdollisesti muutetun) merkkijonon johonkin kohtaan jäsentä: alkuun ja / tai loppuun ja / tai keskelle, korvaten, joka toinen alkuun...

Miinuspuolena ohjelma osaa ratkaista vain yhden jäsenen eteenpäin. Tämä johtuu ideasta, jossa poistetaan jäseniä, jolloin ratkaisu helpottuu huomattavasti. Tiettyjen sarjojen ratkaiseminen tehdään siis joissain tilanteissa monta kertaa täysin turhaan.

Petteri Aimosen ohjelma "zizzo":

Zizzo on rakennettu oliopohjaiseksi. Yksinkertaisimmat numeeriset sarjat, kuten aritmeettiset ja geometriset jonot, toimivat pohjana monimutkaisemmille solvereille. Siten vastaavia sarjoja, kuten 1,2,3 ja A,B,C, ei tarvitse ohjelmoida kahdesti. Lisäksi luokkapohjainen rakenne mahdollistaa ohjelman käyttämän ratkaisumallin helpon tutkimisen debug-ominaisuudella.

Ohjelmaa voi testata myös www-selaimella: http://kapsi.fi/~jpa/stuff/other/epsilon/zizzo.cgi

Pohdittavaa

Mitä älykkyyttä muka on tällaisten sarjojen ratkominen? Ohjelma voi päästä hyviin tuloksiin, kun sille vain opettaa yksi kerrallaan erilaisia sarjoja. Silloin ohjelma etsii annetusta sarjasta kaavamaisesti sille tuttuja malleja. Ohjelma ei ymmärrä, mikä on sarjan "idea", se vain tunnistaa sarjan rakenteen.

Jos älykkään ohjelman tekeminen on vaikeaa, niin vaikeaa on myös määritellä, mikä tekee ohjelmasta älykkään ja mitä yleensä on älykkyys. Onko ihmisen ajattelussa sellaisia toimintoja, joita ei voi ilmaista sanoin ja toteuttaa ohjelmallisesti? Onko ihminen loppujen lopuksi muuta kuin "älykäs ohjelma"?

Näitä kysymyksiä käsitellään Ohjelmointiputkassa myöhemminkin.

Lopuksi

Oliko kilpailun aihe kiinnostava? Oliko kilpailu hyvin järjestetty? Oliko kilpailuaika sopivan pituinen? Oliko testiaineisto onnistunut? Saiko kilpailun kulusta riittävästi tietoja? Mikä olisi seuraavan kilpailun aihe? Jos sinulla on vastauksia näihin kysymyksiin tai muita ehdotuksia, lähetä sähköpostia osoitteeseen antti.laaksonen@ohjelmointiputka.net.

Kiitokset kilpailun osallistujille! Ilman teitä ei kilpailuitakaan olisi.