Laitoksen blogissa käsitellään ajankohtaisia tietojenkäsittelytiedettä tai laitosta koskevia asioita. Blogia toimittaa provokatorisistakin kirjoituksistaan tunnettu professori Jukka Paakki. Kommentointi ja keskustelu on toivottavaa ja suorastaan pakollista.

International department blog

Summer Trip to Porvoo, 14 August 2015
The CS Blog Task Force
10
1

Shakkibotit kilpasilla – voittajan kommentit

Osana syksyn Johdatus tekoälyyn -kurssia järjestettiin kurssin opiskelijoiden kesken shakkiturnaus. Tehtävä oli toteuttaa yksi tärkeimmistä shakkialgoritmin eli "shakkibotin" osista eli heuristinen arviointikriteeri, joka liittää annettuun pelitilanteeseen numeerisen arvion siitä, kumpi pelaaja on niskan päällä. Heuristiikka on tarpeen, koska shakkipelissä ei kaikkia mahdollisia pelejä ehditä käydä läpi niiden suuren määrän takia. Turnauksessa opiskelijoiden toteuttamat heuristiikat kytkettiin valmiiseen alpha-beta -karsintaa käyttävään runkoon ja niitä peluutettiin keskenään.

Pelien nopeutukseksi ja myös siksi, ettei valmista ratkaisua voisi löytää niin helposti, turnauksessa pelattiin rajoitettua Los Alamos -shakkia, jossa laudan koko on 6 x 6 ruutua ja nappuloista lähetit puuttuvat kokonaan.

Turnauksessa pelasi yhteensä 50 shakkibottia ja pelejä kertyi useita tuhansia. Voittajaksi selviytyi shakkibotti Woody pisteillä 1143. Toiseksi sijoittui SlowThinker, 1069 pistettä, ja pronssisijalle Dezgeg-o-bot pisteillä 943. Pistemäärät perustuvat ns. Elo-rankingsysteemiin, jota käytetään myös oikeiden shakkipelaajien rankkaamiseen. (Fun fact: Suomen miesten jalkapallojoukkue on FIFA:n listalla, joka ei perustu Elo-rankingiin, sijalla 88, mutta vaihtoehtoisella Elo-rankingiin perustuvalla listalla sijalla 58!) Turnauksen ideasta ja toteutuksesta kiitokset viime vuoden kurssilla mukana olleelle Tuomas Tynkkyselle, joka keksi pystyttää turnauspalvelun laitoksen users-palvelimelle, josta kilpailevat botit ohjataan pelaamaan Ukko-klusteriin. (Tämä selityksenä mahdolliselle klusterin normaalia suuremmalle kuormalle viime viikkoina.)

Voittajabotti Woodyn takaa löytyy Joonas Järvenpää. Koska Woody itse keskittyy sataprosenttisesti pelaamiseen, Joonas vastasi ystävällisesti sen puolesta muutamaan kysymykseen, jotka alkavat perinteiseen urheilujournalismitapaan:

Joonas, shakkibottisi Woody voitti turnauksen. Miltä nyt tuntuu?

— Kyllähän tämä ihan positiiviselta tuntuu. Yritin parhaani.

Kilpailu oli melko tiukka ja aluksi vaikeaksi vastukseksi osoittautunut viime vuoden kurssin opetustiimin kehittämä Deep Glue -botti jätettiin lopulta sijalle 13 (820 pistettä). Oletko aikaisemmin toteuttanut shakkialgoritmeja?

— En ole itse aikasemmin koodaillut shakkiohjelmaa, mutta olen koodannut jotain minimax-ohjelmia. Mutta shakissa on tietysti omat säännöt ja ohjelma tarvitsee aika paljon spesifistä tietoa. Tässä tehtävässä toteutettiin ohjelmaan vain oma arviointifunktio. Jos koko ohjelman tekisi alusta asti, merkittävimpiä vaivannäön kohteita olisi etenkin siirtogeneraattorin koodaaminen.

— Nyt valmiina annettu hakualgoritmi tutkii siirrot evaluontifunktion pisteytyksen mukaan. Siinä mielessä hyvä arviointiheuristiikka auttaa alpha-beta-karsintaa, millä on aikarajojen takia vaikutusta.

Edellinen kommentti aikarajoista liittyy siihen, että turnauksessa käytettiin aikarajaa, jonka rikkoutuessa peli julistettiin tasapeliksi. Ajasta puheen ollen, kuinka paljon käytit aikaa shakkibotin virittelyyn.

— Varmaan yhtä paljon kuin muihin kurssin laskuharjoitustehtäviin yhteensä. Noin 10-15 tuntia. Kun tehtävä oli palautettu, en kuitenkaan jatkanut botin virittelyä, joten seuraavillekin tehtäville jäi aikaa.

Voitko kuvailla Woodyn yleistä ideaa?

— Aluksi pitänee todeta, että staattisella evaluointifunktiolla on vain hyvin vähän vaikutusta shakkiohjelman vahvuuteen. "Oikean" shakkiohjelman vahvuus syntyy etenkin siitä, miten järkevästi se pystyy karsimaan (prune) ja laajentamaan (expand) tutkittavaa pelipuuta. Minimax-haku vakiosyvyyteen ja sen jälkeen staattinen evaluointi on hyvin heikko strategia, koska tällöin voi jäädä huomaamatta esim. seuraavalla siirrolla tapahtuva matti.

— Woody meneekin tavallista evaluointifunktiota pidemmälle ja generoi kulloisenkiin pelitilanteeseen mahdolliset siirrot, jolloin esim. matti huomataan hieman aiemmin. Lisäksi nappulat saavat pisteitä siitä, että ne voivat siirtyä mahdollisimman moneen paikkaan ja uhkaavat vastapuolen nappuloita. Tornit saavat lisäpisteitä siitä, että ne ovat samalla rivillä ja niin edelleen.

Pelaatko muuten itse shakkia?

— En pelaa itse shakkia säännöllisesti, mutta olen seurannut tietokoneshakin kehitystä melko pitkään.

Yleisemmin tekoälystä: oletko opiskellut tai harrastanut aikaisemmin tekoälyä vai oliko Johdatus tekoälyyn ensimmäinen kerta, kun tutustut aiheeseen?

— Tekoälyn opiskelemisen aloitin aikoinaan Russellin ja Norvigin Artificial Intelligence: A Modern Approach -kirjasta. Sitä olen täydentänyt lukemalla satunnaisesti wikiartikkeleita ja tutkimalla joidenkin ohjelmien lähdekoodeja. Esimerkiksi muutama vuosi sitten ensimmäisen kerran julkaistu avoin Stockfish-shakkiohjelma on huomattava tapaus. Ehkä ensimmäistä kertaa avoimen lähdekoodin shakkiohjelma on maailman kolmen vahvimman joukossa. Stockfishia on ollut kehittämässä myös yksi suomalainen.

— Shakkiohjelmista kiinnostuneen kannattaa tutustua myös Micro-Max -nimiseen ohjelmaan. Se on mahdollisimman pienikokoinen ohjelma, joka pelaa kokoonsa nähden yllättävän hyvin.

— Minimaalisen, ainakin kohtalaisesti pelaavan shakkiohjelman pienin koko on mielenkiintoinen kysymys. Tätä ongelmaa kuvaa käsittääkseni Kolmogorov-kompleksisuus, jolla mitataan merkkijonon tai ohjelman tiiveintä mahdollista esitystä. On kuitenkin osoitettu, että Kolmogorov-kompleksisuutta on mahdoton tarkasti laskea, koska voidaan vain määritellä jokin kohtalaisen tiukka yläraja esimerkin kautta. Micro-Max on vain noin 1200 tavua, mikä osoittaakin shakin kaikkien sääntöjen ja minimax-haun mahtuvan yllättävän pieneen tilaan.

Hyvä huomio! (Lisätietoa Kolmogorov-kompleksisuudesta voi muuten opiskella syventävällä kurssilla Informaatioteoreettinen mallintaminen, jonka Jyrki Kivinen opetti juuri periodissa I.) Onko joku kurssin muista tehtävistä jäänyt erityisesti mieleen shakkitehtävän lisäksi?

— Kurssilla on kokeiltu muun muassa A* -reitinetsintää, minimax-algoritmeja, kuvantunnistusta erilaisilla menetelmillä ja Mindstorms-robottien ohjelmoimista. Aika usein menetelmät osoittautuvat näppäriksi joissain tekoälyn haasteissa, mutta helposti löytyy tapauksia, joissa menetelmien käytännön rajat tulevat vastaan. Mindstorms on ihan näppärä saada nopeasti toimimaan, mutta sensorit ja moottorien kontrollointi on rajoittunutta.

Aiotko jatkaa shakkitekoälyn tai muun tekoälyn parissa, esim. valitsemalla jatkossa aiheeseen liittyviä kursseja?

— Tekoälyn opiskelua aion jatkaa ainakin jossain muodossa, koska algoritmit ja koneoppiminen vaikuttaa mielenkiintoiselta suuntautumisalalta vaikka ihan sovellutuksien takia.

Haluatko lähettää muita terveisiä lukijoille?

— Turnaus oli ihan hauska, eipä tässä muuta.

Kiitos haastattelusta, Joonas.

Lopuksi mainittakoon vielä, että vaatimattomana Joonas ei halunnut haastattelussa tuoda esiin sitä, että myös kakkoseksi tullut botti SlowThinker oli hänen käsialaansa.

Pelitekoälykilpailua tullaan luultavasti näkemään lisää periodissa II, kun Mikko Sysikasken vetämä tekoälyohjelmointihaasteita tarjoava kurssi AI Odyssey 2012 käynnistyy. Sen tiimoilta kannattaa seurailla opiskelu-uutisia laitoksen verkkosivulla.

25.10.2012 Kuva ja teksti: Teemu Roos

Vaikka kommentoida voi anonyymisti, niin toiveena on että oman nimen laittaisi viestin loppuun tai kommentoisi sisäänkirjautuneena, jolloin käyttäjätunnus näkyy viestin alussa.

Lisää kommentti

CAPTCHA
Tämä kysymys esitetään kirjautumattomille käyttäjille, jotta lomakkeen automatisoitu käyttö voitaisiin estää.
14 + 5 =
Ratkaise tämä pieni laskutehtävä ja anna vastaus. Esim. 1+3, anna 4.

Kommentit

Onkohan se ihan sallittua

Onkohan se ihan sallittua generoida lisää syvyyttä pelipuuhun evaluaattorissa.

-Mikko Översti

 

Teemu Roos on laitoksen dosentti, vanhempi tutkija HIIT:ssä, vieraileva tutkija Cambridgen yliopistossa sekä monessa muussa mukana. Hänen tutkimusalaansa on informaatioteoria, data-analyysi sekä koneoppiminen.

  

 

04.02.2013 - 11:08

Nyt kaikki pelaamaan akateemista Bullshit-bingoa!

25.10.2012 - 12:36

Osana syksyn Johdatus tekoälyyn -kurssia järjestettiin kurssin opiskelijoiden kesken shakkiturnaus. Tehtävä oli toteuttaa yksi tärkeimmistä shakkialgoritmin eli "shakkibotin" osista eli heuristinen arviointikriteeri, joka liittää annettuun pelitilanteeseen numeerisen arvion siitä, kumpi pelaaja on niskan päällä. Heuristiikka on tarpeen, koska shakkipelissä ei kaikkia mahdollisia pelejä ehditä käydä läpi niiden suuren määrän takia.

07.09.2012 - 13:15

Kansainvälisiä esikuvia seuraten on Suomeen nyt saatu Julkaisufoorumihankkeen tuloksena tieteellisten julkaisukanavien ensimmäinen laatuluokitus. Yhteensä noin 22 000 tieteellistä julkaisukanavaa (lehdet, kongressisarjat, kirjankustantajat) on luokiteltu kolmeen laatuluokkaan (tasot 1, 2, ja 3) eli perustasoisiin, johtaviin (noin 15 % kaikista) ja korkeimman tason (noin 5 % kaikista) tieteellisiin julkaisukanaviin. Luokitustyö tehtiin 23 tieteenalakohtaisessa arviointipaneelissa Tieteellisten Seurojen Valtuuskunnan organisoimana.

31.05.2012 - 17:11

Tiedekunta laski keväällä tilastoja jatko-opintojen kestosta ja tohtorien iästä. Hyvä uutinen: tietojenkäsittelytieteessä tohtorin tutkintoon kuluva aika on 5.3 vuotta (mediaani), ei siis ihan hirmuisesti enemmän kuin tavoitteena oleva 4 vuoden aika. Huono uutinen: väittelyyn kuluva aika ei ole yrityksistä huolimatta lyhentynyt 12 viime vuoden aikana (ks. kuva). Pienistä lukumääristä johtuvaa vaihtelua on toki ollut, muttei selvää muutossuuntaa.

14.03.2012 - 19:09

Tämä artikkeli on pitkälti oman turhautumiseni purkamista, koska erityisesti viimeisen reilun vuoden aikana opiskelijoiden laiskuus ja viitsimättömyys tuntuvat saavuttaneen aivan uusia huippuja. Vaikka tämä artikkeli onkin vain ihan ikioma mielipiteeni, olen keskusteluissa muiden opettajien kanssa havainnut, että heidän kokemuksensa ovat vahvasti samansuuntaisia.

02.02.2012 - 13:17

Lyhyesti

Stanfordin yliopisto järjesti syksyllä 2011 kolme MOOC-kurssia (massive open online course), joille voi osallistua kuka tahansa. Kurssit käsittelivät tekoälyä, koneoppimista ja tietokantoja. Kahdesta ensinmainitusta luvattiin HY:n tietojenkäsittelytieteen laitoksen opiskelijoille opintopisteitä.

04.10.2011 - 18:12

Perusohjelmointikurssien tavoite ei oikeasti ole jonkun yksittäisen ohjelmointikielen kieliopin oppiminen ja sen mahdollinen soveltaminen. Kaiken alkuvaiheen opinnoissa tehdyn ohjelmoinnin taakse on piilotettu huomattavasti yleishyödyllistä harjoittelua.

25.08.2011 - 16:26
Laajassa ”trendence Graduate Barometer” –kyselyssä selvitetään säännöllisesti eurooppalaisten yliopisto-opiskelijoiden näkemyksiä heidän opinnoistaan sekä heidän tulevalle työuralle asettamiaan odotuksia. Vastikään on julkaistu viimeisimmän, syksyllä 2010 toteutetun selvityksen tulokset. Kyselyyn osallistui yhteensä 310 945 opiskelijaa 24 maasta ja 1077 yliopistosta. Suomesta mukana oli mm. 568 kandidaatti-, maisteri- ja tohtoriopiskelijaa Helsingin yliopistosta. Koska selvityksen kohdealueina ovat taloustieteet, (tieto)tekniikka ja luonnontieteet, olivat Helsingin yliopiston edustajat pääasiassa matematiikan ja tilastotieteen (65,8 %) sekä tietojenkäsittelytieteen (36,2 %) opiskelijoita.
13.06.2011 - 14:41

Ulkomainen kollegani ihmettelee suuresti joitakin laitoksemme käytäntöjä, joita hän ei millään pysty ymmärtämään. Kun hän päätyy toistuvasti tivaamaan käytäntöihin hyviä perusteluja minulta, olen joutunut yllätyksekseni tunnustamaan, että en lopulta osaa selittää, miksi niihin on ajauduttu.

18.05.2011 - 11:50

Kuten saimme 12.5. lukea laitoksen pääuutisista, on Helsingin yliopisto ränkätty maailmanlaajuisesti sijoille 51-100 tietojenkäsittelytieteessä. Onko rakas laitoksemme siis maailman huipulla vai mutasarjassa?

02.05.2011 - 16:32

Teknologiateollisuuden 100-vuotissäätiö on myöntänyt laitoksen RAGE-tutkimusryhmälle kolmeksi vuodeksi rahoitusta ketterän opetuksen kehittämiseen ja tutkimiseen. Mutta mitä on ”ketterä opetus”, ja onko laitoksen opettajilla oikeutusta käyttää ohjelmistokehittäjien pyhää varattua sanaa ”ketterä” omiin tarpeisiinsa?

13.04.2011 - 15:18

Laitosta ei – ainakaan meidän omasta mielestämme – tunneta riittävän hyvin. Suurin syyllinen on tietenkin asiantuntematon valtamedia, joka säännön mukaan unohtaa meidät silloin kun se alan tutkimuksesta tai opetuksesta jotain uutisoi.

Syndicate content