2.3.2014

Viikonloppu pelastettu

Ei ole tullut taas vähän aikaan kirjoitettua mitään, kun ei ole ollut tähdellistä asiaa ja mielikin on harhaillut koko viikon ajan yksinomaan vain siinä yhdessä tietyssä asiassa. Siis ohjelmoinnissa, vai mitä muuta perverssiä oikein kuvittelit... Sain viime viikolla eteeni pienen ohjelmointitehtävän ja kötöstelin sen maanantaina valmiiksi. Suoritukseksi riitti tosi puolivillainen toteutus, koska tehtävän tarkoituksena oli antaa lähinnä vain antaa esimakua haastavammista ohjelmointiprobleemista, joita on käsitelty muualla. Tuo tehtävä oli siis sellainen, että jos siinä käytetyn tekoälyn olisi halunnut saada toimimaan "oikealla" tavalla, niin siinä olisi riittänyt pohdittavaa pitemmäksi aikaa.

Olin lueskellut aikaisemmin eräästä materiaalinivaskasta juuri tuon kyseisen tyyppisen ongelman ratkaisemisesta. Tehtävänanto oli kyllä naamioitu siinä mielessä ovelasti, että jos en olisi lukenut tuota materiaalia aiemmin, niin tuskin olisin tiennyt miten tehtävä olisi pitänyt ratkaista "oikeasti". Mutta kun kerta olin aiemmin nähnyt ratkaisutavan tuon tyyppisen ongelmaan, niin en voinut vastustaa kiusausta. Tuo tehtävä oli ratkaistava oikealla tavalla eikä millään puolivillaisella näpertelyllä!

Ongelma riivasi mieltä niin paljon, että asiaa tuli mietittyä viikolla töissäkin sen verran, että saattoipa siinä sivussa mennä joku tunti vähän hukkaan virallisten töiden osalta. Iltaisin pohdiskelin ja koitin vääntää tuskassa koodia, kun netistäkään ei löytynyt suoraan mitään vastaavanlaisia toteutuksia. Nyt viikonloppuna sain sitten keskittyä ongelman ratkaisuun urakalla ja lopulta koko homma onnistui monen tuskailun jälkeen. Jos vertasi sitä ensimmäistä ratkaisua tähän varsinaiseen ratkaisuun, niin eroa tekoälyjen välillä oli kuin yöllä ja päivällä, varsinainen ratkaisu peittosi mennen tullen puolitekeleen. Minua aivan nauratti ja taisinpa vähän hymyillä kuin Hangon Keksi, kun näin tekoälyn toiminnassaan.

On tämäkin ohjelmointi hieman itsensä kiduttajan touhua. Kun tietää, että ongelmaan on ratkaisu mutta kun sitä toteutusta ei saa kaikesta yrityksestä huolimatta toimimaan oikealla tavalla, niin sitä tuntee itsensä kovin tyhmäksi ja tahtoo siinä turhautuneisuuskin nostaa päätään aika paljon. Toisaalta sitten kun se ongelma ratkeaa sillä, että kommentoi jonkin yksittäisen koodirivin pois sotkemasta ja homma lopulta toimii, niin voi sitä henkistä orgasmia sen jälkeen. Tuolla tavalla se meni nytkin mutta tulipahan opittua taas jotakin uutta ja hauskaa. :)

Niin loppuun vielä sellaista, että

SATASET PAUKKUU!

(mittariin pyörähti tämän kirjoituksen myötä luku 300)

4 kommenttia:

Vaeltaja kirjoitti...

Ihan uteliaisuudesta... Pystytkö yhtään valottamaan millainen tekoälyongelma tossa on kyseessä tarkkaan ottaen ja mitä menetelmää siihen sovelsit?

Urpo Turpo kirjoitti...

Lyhyesti sanottuna se ongelma oli niinkin yksinkertaiselta kuulostava kuin, että piti etsiä reitti paikasta A paikkaan B erilaisia sääntöjä noudattaen. Tuohon ongelmaan tepsi hyvin A*-haku.

Mitätön askel ihmiskunnalle, jättimäinen harppaus Urpo Turpolle.

Vaeltaja kirjoitti...

Jopas, ihan muistuu mieleen opiskeluajat ja yksi projekti missä värkkäsin jotain tämänsuuntaista itsekin. :)

Reitinhaku tietokoneella perustuu lähes aina graafeihin eli mahdollisten reittien mallintamiseen solmuilla ja niiden välisillä kaarilla. Graafialgoritmit ovat melko mielenkiintoinen osa-alue tietojenkäsittelyssä, joihin harvemmin törmää päivittäisiä ohjelmointijuttuja töissä tehdessä. Sanoisin, että iso osa koodarin hommia tekevistä tuskin edes tietää näistä mitään saatikka on joskus koodaillut jotain aiheeseen liittyvää. Toki kaverit, joilla on alan korkeakoulututkinto, ovat joutuneet myös graafien kanssa tekemisiin.

Hommahan menee niin, että perushakualgoritmeja graafeille on leveys- ja syvyyshaut. Näissä jokainen kaari on samanarvoinen, eikä mitään painoja (weight) niille lasketa. Dijkstra (eräs kuuluisimpia tietojenkäsittelijöitä koskaan) kehitti sitten näiden pohjalta algoritmin, jossa kaarilla on painot ja haku etenee sen mukaan mikä on siihen mennessä parhaalta näyttävä reitti (kustannusfunktion perusteella) sen sijaan, että vain mekaanisesti mentäisiin leveys- tai syvyyssuunnassa eteenpäin. Tällä tavoin löydetään lyhin mahdollinen reitti, kun perushaut löytävät vain jonkin satunnaisen reitin. A* on sitten modifikaatio edellisestä, joka lisää kustannusfunktioon heuristisen osan (esim. matka suoraan linnuntietä karttapulmissa). Päämääränä tässä on nopeuttaa hakua graafien ollessa suuria hyödyntämällä ongelmakohtaista lisäinformaatiota mutta itse tulos ja perusalgoritmi ovat samoja.

Kun graafi mallinnetaan vaikka tietokantaan tms., voidaan algoritmin suoriutumista parantaa asteittain tarkentamalla graafin painoja vastaamaan tosielämää. Itse tein Dijkstran algoritmilla erääseen peliin reitinhakualgoritmin, joka sitten tarkentui saadun palautteen perusteella juuri painoja säätämällä. Toki manuaalinen säätäminen soveltuu vain varsin pienille graafeille ja isompien tapauksessa optimointia voidaan tehdä vaikkapa hermoverkoilla, mutta tällöin puhutaan jo varsin mutkikkaasta systeemistä.

Jos sait tuosta toimivan systeemin aikaan, pystyisit varmasti tekemään normikoodarin hommiakin työksesi vallan hyvin. Ongelmana toki on, jos ei ole kauheasti näyttää osaamista paperilla työnantajilla (koulutus, työkokemus, sertifikaatit, isot projektit...). koska meillä Suomessa on usein pääpaino tuollaisilla seikoilla, vaikka näissä hommissa on mun mielestä usein tärkeämpää kyky oppia uutta, hakea tietoa, ratkoa ongelmia ja hallita analyyttinen ajattelu yleisellä tasolla. Ala kehittyy niin nopeasti, ettei vanhentuneesta työkaluosaamisesta ole kuin rajallinen hyöty uusien työkalujen parissa.

Urpo Turpo kirjoitti...

Noihin samaisiin hakualgoritmeihin tuli törmäiltyä, kun etsiskelin netistä tietoa. Ja löytyipä sieltä yksi hyvin tehty nettisivu, joka havainnollisti graafisesti haun etenemistä eri hakutavoilla. Siitä näki selkeästi, miten algoritmit etenivät ja miten nopeita ne olivat erilaisissa tilanteissa.

Luultavasti pystyisin tekemään jonkinasteisia koodihommia. En ole enää mikään aloittelija mutta taitoni ja ymmärrykseni eivät kuitenkaan riitä ihan aina kaikissa tilanteissa, joten se hieman hankaloittaisi asioita. Luultavasti ahkeralla harjoittelulla, opiskelemalla ja tietoa etsimällä taidot varmasti paranisivat aikaa myöten. Mutta siihen varmasti menisi melko pitkä aika varsinkin, kun ährää itsekseen ja kantapään kautta oppien.