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
The CS Blog Task Force
The CS Blog Task Force
The CS Blog Task Force
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.
- Turnaus
- Wikipedia: Los Alamos -shakki
- Micro-Max
- Stockfish
- FIFA ranking (jalkapallo)
- Vaihtoehtoinen Elo-ranking (jalkapallo)
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.
Onkohan se ihan sallittua
Onkohan se ihan sallittua generoida lisää syvyyttä pelipuuhun evaluaattorissa.
-Mikko Översti