n-Puzzle

14.5.2002

Juha Knuuttila

Simo Broman

Panu Ranta

Tiivistelmä

Olemme toteuttaneet 15-puzzle-pelin laajennuksen n-puzzlen Java-applettina. Pelilaudan koko voi olla 2x2, 3x3, 4x4 tai 5x5 ruutua. Ohjelmoimme peliin tekoälyn, joka hakee kulloisestakin alkutilasta optimiratkaisun. Optimiratkaisu on ratkaisupolku, jossa alkutilan ja tavoitteena olleen lopputilan välillä on tehty vähiten siirtoja. Ratkaisun haku tapahtuu A*-haulla. Toteutimme kolme eri heuristiikkaa vertaillaksemme heuristiikkojen vaikutusta ratkaisun haussa. Pelin mielenkiintoisuuden lisäämiseksi pelissä on mahdollista valita erilaisia tavoitetiloja. Tutkimme myös pelilaudan tavoitetilan vaikutusta ratkaisun nopeuteen. Appletti ratkaisee nopeasti 3x3-puzzlet, mutta suurempien pelien ratkaiseminen osoittautui liian vaativaksi. Muistin ja ajan käyttö riippui suuresti heuristiikan valinnasta.

1 Johdanto

N-puzzle on sliding block-puzzle, eli peli, jossa numerolaattoja koitetaan liikuttaa siten, että numerot saadaan pelilaudalla haluttuun järjestykseen. Pelilauta on neliönmuotoinen ruudukko, jossa on N numerolaattaa ja yksi tyhjä aukko. Pelin asetelman muuttaminen tapahtuu siirtämällä aukon kohdalle jokin sen naapurilaatoista eli aukon paikkaa liikuttamalla.

Ensimmäinen sliding block-puzzle keksittiin 1870-luvulla. Yhdysvaltalaisen Sam Loyd:in 4x4-kokoinen "Fifteen Puzzle" saavutti laajaa suosiota [1]. Pienempi 8-puzzle on ollut suosittu testiongelma tekoälytutkimuksessa hakualgoritmien arvioinnissa, sillä ongelma on täsmällisesti muotoiltavissa, deterministinen sekä sopivan vaikea toimiakseen tekoälyn testipenkkinä. Haarautumiskerroin on noin 3 ja tyypillisen ratkaisun pituus noin 20 askelta. Täysin ohjaamattoman haun täytyisi siis tutkia noin 3^20=3,5*10^9 tilaa löytääkseen lyhimmän ratkaisun. Silmukoita välttämällä hakuavaruus voidaan pienentää noin kahdeskymmenestuhannesosaan, sillä erilaisia pelilaudan tiloja pelissä on 9!/2=181 440 kpl. Tämäkin on paljon, joten heuristiikan ja algoritmin toteutuksen tehokkuus tulevat hyvin esille. Hakuavaruuden koko kasvaa suhteessa pelilaudan koon kertomaan. 3x3-kokoista suurempien pelien ratkaiseminen on jo hyvin hidasta.

2 Käsittely

2.1 Tekoälytekniikat ja teoria

2.1.1 A*-haku

Hakuongelman ratkaisussa tehokas ja yleinen algoritmi on A*-haku. A*-haku on paras ensin haku. Paras ensin haussa laajennetaan solmu, jonka arvotusfunktio on pienin. A*-haussa arvotusfunktio on muotoa f(n) = g(n) + h(n), missä kustannusfunktio g(n) mittaa jo generoidun polun kustannusta ja heuristiikkafunktio h(n) arvioi jäljellä olevaa kustannusta solmusta n tavoitteeseen. A*-haku on optimaalinen ja täydellinen, jos heuristiikkafunktio h(n) ei koskaan yliarvioi jäljellä olevaa kustannusta, eli heuristiikka on admissiibeli [2]. Hakualgoritmin täydellisyys tarkoittaa sitä, että algoritmi löytää polun alku- ja lopputilan välille, jos sellainen on olemassa. Optimaalisuus tarkoittaa sitä, että algoritmin löytämä polku on optimaalinen kustannusfunktion g(n) mielessä.

Algoritmin kulku alkaa annetusta alkutilasta. Solmut, joihin päästään tästä solmusta yhdellä siirrolla, lisätään löydettyihin solmuihin. Seuraavaksi laajennetaan eli otetaan käsittelyyn löydetustä solmuista se, jonka arvotusfunktio on pienin. Taas tämän solmun jälkeläiset, eli ne solmut joihin ko. solmusta päästään yhdellä siirrolla, lisätään löydettyihin solmuihin. Näin jatketaan, kunnes laajennetteva solmu on tavoitetila ja näin optimipolku on löydetty tai kaikki hakuavaruuden solmut on käsitelty.

2.1.2 A*-haku pseudokoodina

solution solve(gameBoard) {
    node = new Node(gameBoard);
    discoveredNodes.add(g(node) + h(node), node);

    for (;/*ever*/;) {
        if (discoveredNodes.isEmpty() == true) {
            return failure;
        }

        node = discoveredNodes.removeMin();

        if (node.goalTest(goalBoard) == true) {
            return solution;
        }

        newNodes = node.expand();

        while (newNodes.size() > 0) {
            newNode = newNodes.remove(0);
            discoveredNodes.add(g(newNode) + h(newNode), newNode);
        }
    }
}

2.1.3 A*-haun tehostaminen

Hakualgoritmia voidaan tehostaa karsimalla laajennettavien solmujen määrää. Silmukoita karsimalla eli estämällä laajentamasta uudelleen sellaista tilaa, jossa on jo oltu, voidaan laajennettujen ja löydettyjen solmujen määrää huomattavasti pienentää. Tämä on tehty siten, että solmua, jota vastaava tila on jo aiemmin löydetty, ei lisätä löydettyihin solmuihin. Solmua ei voida kuitenkaan karsia pelkästään samanlaisen pelilaudan konfiguraation perusteella. On mahdollista, että tiettyyn pelilaudan asemaan päästään erilaisia polkuja pitkin. Polku, jota pitkin asema ensimmäisen kerran löydetään, ei välttämättä ole lyhin. Tämä johtuu siitä, että heuristiikan arvioiman ja todellisen jäljellä olevan kustannuksen välinen erotus vaihtelee eri pelilaudan konfiguraatioiden välillä. Muutenhan ratkaisupolku löydettäsiinkin suoraan eikä mitään hakua tarvittaisi. Jos haun myöhemmässä vaiheessa löydetään sama asema uudestaan lyhyemmän polun päästä, ei tätä tilaa vastaavaa solmua voida jättää pois menettämättä myös mahdollisesti sen kautta kulkemaa optimipolkua. Riittävä ehto, joka takaa, että mahdollisia optimipolun solmuja ei jätetä pois karsittaessa samanlaisia pelilaudan asemia, on jättää pois vain ne solmut, joissa kertynyt kustannus on suurempi tai yhtä suuri kuin aiemmin löydetyn solmun kustannus. Intuitiivinen todistus tälle on seuraava:

Olkoon polku p lyhin pisteen B kautta kulkeva pisteiden A ja C välinen polku. Tällöin on olemassa lyhin pisteiden A ja B välinen polku ja tämä polku kuuluu polkuun p. Kun haetaan pisteiden A ja C välistä lyhintä polkua, voidaan siis jättää huomioimatta ei-optimaaliset osapolut A:sta B:hen menettämättä optimaalista polkua.

A*-haku on optimaalinen ja täydellinen. Kun karsitaan sellaisia solmuja, jotka eivät voi olla osana optimipolkua, kyse on vain hakuavaruuden supistamisesta, ja haku on edelleen optimaalinen ja täydellinen.

2.1.4 Heuristiikat

A*-haussa merkittävä osuus on arvotusfunktion laskennassa käytettävällä heuristiikalla. Tehokas heuristiikka ohjaa haun etenemistä kohti tavoitetilaa antamalla pieniä arvotusfunktion arvoja niille solmuille, joista luultavammin on alhaisempi kustannus tavoitetilaan. Toteutimme kolme heuristiikkaa (toteutukset liiteessä 2):

1. Displaced-heuristiikka. h(n) = poissa tavoitepaikaltaan olevien laattojen määrä.
2. Manhattan-heuristiikka. h(n) = poissa tavoitepaikaltaan olevien laattojen etäisyys oikeasta paikastaan. Etäisyys lasketaan siirtoina ylös/alas- ja oikealle/vasemmalle-suunnissa.
3. Suboptimal-heuristiikka. h(n) = Manhattan-heuristiikan antama arvo kerrottuna luvulla 2.

Heuristiikka 3 ei ole admissiibeli, vaan se saattaa arvioida jäljellä olevaa kustannusta todellista suuremmalla arvolla. Näin ollen heuristiikkaa käyttäen löydetty polku ei välttämättä ole optimaalinen.

2.2 Toteutuksen kuvaus

Ohjelma on toteutettu Java-ohjelmointikielellä (JDK 1.2). Se koostuu yhdeksästä luokasta, jotka on jaettu neljään pakettiin (puzzle, solver, board ja orderedlinkedlist).

Ohjelman toimivuus on varmistettu seuraavissa järjestelmissä.

• Solaris 8, Java 1.2.2
• IRIX 6.5, Java 1.3.1
• Windows 98, Java 1.3.1
• Windows 98, Java 1.4.0

2.2.1 Luokat

puzzle.Puzzle

Appletti. Pelin pääluokka, luo käyttöliittymän ja ratkaisimen sekä käsittelee käyttöliittymän välittämät tapahtumat.

puzzle.UserInterface

Käyttöliittymä. Toteutettu käyttäen Swing-komponentteja. Käyttöliittymä sisältää pelilaudan (gameBoard), jota pelaaja muokkaa ja laudan (goalBoard), joka näyttää millaiseksi pelilauta pitää muokata. Lisäksi joukko painikkeita ja valikoita, joilla pelaaja säätelee pelin asetuksia ja lautoja.

solver.Solver

Ratkaisin. Sisältää A*-haun, jonka lähdekoodi on liitteessä 1 ja kolme heuristiikkaa, joiden lähdekoodit ovat liitteessä 2.

Solve-metodi ratkaisee sille argumenttina annetun pelin ja palauttaa siirrot alkutilasta (gameBoard) lopputilaan (goalBoard). Löydetyt solmut lisätään järjestettyyn linkitettyyn listaan, josta voi poistaa pienimmän alkion vakioajassa. Listan pituus on tyypillisesti alle kymmenen elementtiä, joten myös lisääminen tapahtuu hyvin nopeasti vaikka lista sisältää usein tuhansia alkioita.

Löydettyjen solmujen karsiminen tapahtuu siis solmun sisältämän pelilaudan ja ratkaisupolun pituuden perusteella. Näistä muodostetaan avain (tiiviste, hash), joka lisätään hajautustaulukkoon. Aina ennen uuden solmun lisäämistä löydettyihin solmuihin tarkistetaan onko solmun avain jo hajautustaulukossa ja mikäli avain löytyy, niin solmua ei lisätä. Kun pelilauden sivun pituus on kaksi tai kolme, niin avaimen tyyppi on Long (64 bittiä). Suuremmilla pelilaudoilla käytetään tavutaulukkoa. Näin menetellään, koska yhden solmun kuluttama muisti halutaan minimoida. Avaimen esitys vaatii 9*3+6=33 bittiä 3x3-laudoilla ja 16*4+8=72 bittiä 4x4-laudoilla.

solver.Node

A*-haun solmu. Solmu sisältää pelilaudan, ratkaisupolun ja avaimen sekä lopetustestin.

solver.SolutionPath

Ratkaisupolku. Dynaaminen taulukko sisältää siirrot alkutilasta nykytilaan. Siirtoja voi lisätä, mutta ei poistaa. Polun pituuden ilmoittavan muuttujan tyyppi on byte (8 bittiä), joten ratkaisupolku ei voi olla pidempi kuin 127 askelta. Tämä ei ole käytännössä ongelma, koska näin pitkiä polkuja syntyy vasta ratkottaessa 5x5-pelejä. Muisti ja aika loppuvat kuitenkin ennen kuin polku kasvaa liian pitkäksi.

solver.HashKey

Hajautusavain. Konstruktori muodostaa tavutaulukko-avaimen argumenttina annetusta merkkijonosta.

board.Board

Pelilauta. Neliön muotoisen laudan sivun pituus on 2-5 laattaa. Laudassa on yksi tyhjä laatta ja muut laatat ovat numeroitu yhdestä n^2-1:teen, missä n on sivun pituus. Laatat voidaan asettaa laudalle kahdessa eri järjestyksessä. Laudan voi lisäksi peilata lävistäjän suhteen tai kiertää 90 astetta, joten erilaisia pelilautoja on yhteensä 64.

Laattojen vaihtoehtoiset järjestykset, Traditional ja Modern (3x3):

Traditional: 123      Modern: 123
             456              8 4
             78               765

orderedlinkedlist.orderedLinkedList

Järjestetty linkitetty lista. Listaan voi lisätä alkioita ja siitä voi poistaa minimialkion. Lista muodostuu elementeistä, jotka sisältävät alkioita. Yhdessä elementissä olevilla alkioilla on sama avain.

orderedlinkedlist.orderedListElement

Järjestetyn listan elementti. Sisältää kokonaislukuavaimen ja alkioita. Yhdessä elementissä olevilla alkioilla on sama avain.

2.2.2 UML: Luokkien väliset assosiaatiot

2.2.3 UML: Luokkien julkiset ja suojatut jäsenet

3 Yhteenveto

3.1 Tulokset ja niiden analysointi

Johtuen 2x2-lautojen triviaalista luonteesta sekä 4x4- ja 5x5-lautojen laskennallisesta vaativuudesta muistin ja käytetyn ajan suhteen, päätimme pitäytyä ainoastaan 3x3-laudoissa tuloksia analysoidessa. Testikoneena toimi 500 MHz Pentium III, 384 MB RAM. Tulokset saatiin ratkaisemalla sekä Manhattan- että Suboptimal-heuristiikoilla kaikki Traditional- ja Modern-pelit, ja Displaced-heuristiikalla joka 15. peli. Näin siksi, koska jokaisen pelin laskemiseen Displaced-heuristiikalla olisi kulunut useita vuorokausia.

3.1.1 Löydettyjen solmujen perusteella tehtävät tarkastelut

Ohjelman löytämän solmujen määrää eri pelin pituuksien funktiona tutkittiin ja tuloksista saatiin alla oleva kuvaaja. Kuvaaja on rajoitettu ylhäältä 100 000 solmuun, sillä Displaced-heuristiikka löysi enimmillään jopa 400 000 solmua, ja on tehottomuutensa vuoksi vähemmän kiinnostava vertailukohde kuin Manhattan ja Suboptimal.

Havaitaan, että Suboptimal-heuristiikalla solmuja löydetään huomattavasti vähemmän, mikä säästää aikaa ja muistia. Kaikista yksinkertaisin Displaced-heuristiikka taas tutkii hyvin monta solmua. On havaittavissa selvä eksponentiaalisen kasvun trendi löydettyjen solmujen määrässä Displaced- ja Manhattan-heuristiikoilla, kun ratkaisupolun pituus kasvaa. Manhattan-heuristiikalla löydettyjen solmujen määrä pysyy kuitenkin paremmin kurissa. Erityisen mielenkiintoisia poikkeamia tästä trendistä ovat esim. Manhattan-heuristiikalla saadut kaksi 31 askeleen ratkaisua. Myös eräs Suboptimal-heuristiikalla laskettu 34 askeleen ratkaisu herättää mielenkiintoa poikkeuksellisen vaativuutensa vuoksi. Nämä laudat löytyvät liitteestä 4. Intuitiivisestihan voisi kuvitella vaativuuden kasvavan ratkaisupolun pituuden funktiona, mutta näin ei näyttäisi ainakaan Suboptimal-heuristiikan tapauksessa käyvän.

Alla keskimääräiset ratkaisupolkujen pituudet.

Kummallakin maalilaudalla ratkaisupolun keskimääräinen pituus on Suboptimal-heuristiikalla suurin. Tämä on järkeenkäypää, kun muistetaan, että Suboptimal-heuristiikka ei ole admissiibeli. Manhattan- ja Displaced-heuristiikoilla ratkaisupolun pituus on prosentin tarkkuudella sama, mikä viittaa siihen, että joka 15. lauta on riittävän suuri otos pelejä. Mikäli Displaced-heuristiikalla oltaisiin laskettu kaikki pelit, ratkaisupolun pituuksien keskiarvo olisi luonnollisesti sama Manhattanilla laskettujen kanssa, sillä molemmat heuristiikat ovat admissiibeleitä.

Toinen mielenkiintoinen kysymys on, että vaikuttaako tavoitelaudan järjestys ratkaisun vaativuuteen. Käytettävissähän oli kaksi lautatyyppiä, Traditional ja Modern. Alla olevan perusteella vaikuttaisi siltä, että tavoitelaudan tyypillä on merkitystä.

Heuristiikasta riippumatta näyttäisi käyvän siten, että Traditional-tyyppisen laudan ratkaiseminen vaatii enemmän työtä. Intuitiivisesti ajatellen tämä ei ole täysin odottamaton tulos, sillä Modern-laudassahan on tavoitetilassa tyhjä kohta keskellä lautaa eikä reunassa mikä saattaa hieman helpottaa asiaa. Suboptimal-heuristiikan 39% ero näyttää suhteellisen pieneltä verrattuna esim. Manhattan-heuristiikan 75% eroon. Koska mukana analyysissä ovat kaikki mahdolliset pelit, ei kyse voi olla tilastollisesta sattumasta. Kahden lautatyypin välillä on selvästi havaittava ero.

3.1.2 Aikavaativuus

Vertaillaan vielä, kuinka paljon aikaa testikoneellamme keskimäärin kului eri heuristiikoilla 3x3-kokoisten Traditional-pelien ratkaisuun.

Kuten arvata saattaakin, ratkaisuun kulunut keskimääräinen aika noudattelee samaa linjaa kuin löydettyjen solmujen määrä. Manhattan-heuristiikalla keskimääräinen aika on jopa yli kolminkertainen verrattuna Suboptimaliin, joka on selvästi nopein heuristiikka. Käytetyllä testikoneella jopa Displaced-heuristiikan alle 3 sekuntia/peli pysyy vielä siedettävänä ratkaisuaikana.

3.2 Johtopäätökset käytettyjen tekoälytekniikoiden soveltuvuudesta n-Puzzlen ratkaisemiseksi

3x3-kokoisille laudoille esitetyt tekniikat soveltuvat varsin hyvin. Sekä Suboptimal- että Manhattan-heuristiikoilla on mahdollista ratkaista 3x3-lautoja erittäin nopeasti ja tehokkaasti, huomattavasti nopeammin kuin yksikään WWW:stä löytämämme 8-puzzle-appletti. Vaikka ohjelman laskenta on myös pitkälle optimoitua muistin suhteen, tulee sen suhteen ongelmia jo 4x4-laudoilla. 4x4-lautoja ei tämän päivän tavallisilla kotikoneilla vielä pysty luotettavasti ratkomaan, 5x5-laudoista puhumattakaan, sillä Manhattan-heuristiikka pelistä riippuen löytää luokkaa 400 miljoonaa solmua [1] 4x4-pelissä, mikä vie paljon aikaa ja muistia. Ratkaisuna tähän voisi olla muutkin lyhimmän polun haussa käytetyt informoidut hakumenetelmät. Erityisesti isommilla laudoilla (>=4x4) vaihtoehtoisia algoritmeja olisivat olleet rajoitetussa muistissa toimivat IDA* ja SMA* [2].

4 Lähdeluettelo

[1] Korf R. Recent Progress in the Design and Analysis of Admissible Heuristic Functions. University of California. 2000. [Viitattu 14.5.2002]. Saatavissa: http://rakaposhi.eas.asu.edu/korf-search.pdf.

[2] Syrjänen Markku. 2002. Kurssin T-93.440 opetusmonisteet, 1. erä. Edita Prima Oy. Espoo. 92 s.

5 Liitteet

5.1 Liite 1

A*-haun lähdekoodi.

public byte[] solve(Board gameBoard) {
    OrderedLinkedList discoveredNodes = new OrderedLinkedList();
    HashMap hashesOfDiscoveredNodes = new HashMap();
    Node node = new Node(gameBoard);

    gameBoard.resetOldEmpty();
    numberOfExpandedNodes = 0;
    numberOfDiscoveredNodes = 0;
    stopSolving = false;

    node.setKey(g(node) + h(node));
    discoveredNodes.add(node.getKey(), node);

    for (;/*ever*/;) {
        if (stopSolving == true) {
            return new byte[0];
        }

        if (discoveredNodes.isEmpty() == true) {
            return null;
        }

        node = (Node)discoveredNodes.removeMin();

        if (node.goalTest(goalBoard) == true) {
            return node.getPath();
        }

        Vector newNodes = node.expand();
        numberOfExpandedNodes++;
        numberOfDiscoveredNodes += newNodes.size();

        // add new nodes to discoveredNodes
        while (newNodes.size() > 0) {
            Node newNode = (Node)newNodes.remove(0);

            Object key = null;
            String keyString = newNode.getBoard().getPackedTiles() + 
                               newNode.getPath().length;

            // optimize memory usage
            if (goalBoard.getSize() <= 3) {
                key = new Long(keyString);
            } else {
                key = new HashKey(keyString);
            }

            // don't add nodes that are already there
            if (hashesOfDiscoveredNodes.containsKey(key) == false) {
                hashesOfDiscoveredNodes.put(key, null);
                newNode.setKey(g(newNode) + h(newNode));
                discoveredNodes.add(newNode.getKey(), newNode);
            }
        }
    }
}

5.2 Liite 2

Heuristiikkojen lähdekoodit.

// "Displaced" heuristic
private int h1(Node node) {
    byte[] game = node.getBoard().getTiles();
    byte[] goal = goalBoard.getTiles();
    int diff = 0;

    for (int i = 0; i < game.length; i++) {
        if (game[i] != goal[i]) {
            diff++;
        }
    }

    return diff;
}

// "Manhattan" heuristic
private int h2(Node node) {
    byte[] game = node.getBoard().getTiles();
    byte[] goal = goalBoard.getTiles();
    int[] temp = new int[game.length];
    int size = goalBoard.getSize();
    int diff = 0;

    for (int i = 0; i < game.length; i++) {
        temp[goal[i]] = i;
    }

    for (int i = 0, j = 0; i < game.length; i++) {
        j = temp[game[i]];
        diff += Math.abs(i%size - j%size);  // column
        diff += Math.abs(i/size - j/size);  // row
    }

    return diff;
}

5.3 Liite 3

Taulukko eri pituisten ratkaisujen lukumääristä Manhattan- ja Suboptimal-heuristiikoilla kun ratkaistiin kaikki 3x3-pelit (Traditional).

5.4 Liite 4

Mielenkiintoisia 3x3-pelilautoja (Traditional).

5.4.1 Manhattan-heuristiikka

647   Ratkaisun pituus 31 siirtoa, 40633 löydettyä solmua
85 
321

867   Ratkaisun pituus 31 siirtoa, 40793 löydettyä solmua
254
3 1

563   Ratkaisun pituus 30 siirtoa, 74691 löydettyä solmua
8 2
741

5.4.2 Suboptimal-heuristiikka

874   Ratkaisun pituus 40 siirtoa, 1768 löydettyä solmua
321
65

857   Ratkaisun pituus 40 siirtoa, 3318 löydettyä solmua
3 4
612

 83   Ratkaisun pituus 34 siirtoa, 19931 löydettyä solmua
652
741