Eight-puzzle - Classical Artificial Intelligence (AI)

Saturday 31st of December 2016 10:51:19 AM


  Toggle Advanced Options



Represent the search space in fact-retrieval and problem-solving tasks as networks

The eight-puzzle is a simple game which consists of eight sliding tiles, numbered from 1 to 8, placed in a '3 x 3' squared board. One of the cells is always empty, and any adjacent (horizontally and vertically) tile can be moved into the empty cell.

To solve eight-puzzle you will need an expansion function and find a way to measure between problem states and the goal state.

The goal in the eight-puzzle is to arrange the tiles in numerical order with the space in the middle and there are 16 configurations that satisfy this goal (since '1' can be in any of eight squares and the numbers can rise clockwise or counterclockwise).

The heuristic (suggested by Nilsson - 1980) uses the following measure of the distance between problem states and the goal: for each tile count how many tiles is is away from its destination; add to this measure 3 if the tile is in the center cell and add 6 if is is in the periphery and not followed by its successor.

An important concept in classical artificial intelligence (AI) is that we can represent the search space in fact-retrieval tasks and problem-solving tasks as networks.

A second approach is a type of program called a production system that employs pattern matching to perform reasoning tasks.

Essential LISP by John R. Anderson, Albert T. Corbett and Brian J. Reiser - page 251.

It's more than likely that the source below contains algorithmic errors.

Source code

EightPuzzle.java

/*
Copyright (c) 2010, Brett Alistair Kromkamp - brettkromkamp@gmail.com
All rights reserved.

Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list
of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright notice, this
list of conditions and the following disclaimer in the documentation and/or
other materials provided with the distribution.

Neither the name of the copyright holder nor the names of the contributors
may be used to endorse or promote products derived from this software without
specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

import java.applet.*;
import java.awt.*;
import java.awt.image.*;
import java.lang.Math.*;
import java.net.URL;
import java.net.MalformedURLException;

public class EightPuzzle extends java.applet.Applet implements Runnable {
    private static int[][][] matrix;
    private static boolean[] expNode;
    private static int[] distNode;
    private int xFind;
    private int yFind;
    private int moveCount;
    static final int COL = 3;
    static final int ROW = 3;
    static final int YCENTER = 1;
    static final int XCENTER = 1;
    static final int EXPTOTAL = 4;
    static final int NODETOTAL = 6;
    static final int NSUP = 0;
    static final int NSRIGHT = 1;
    static final int NSDOWN = 2;
    static final int NSLEFT = 3;
    static final int NSPROBLEM = 4;
    static final int NSGOAL = 5;
    static final int NSTEMP = 6;
    private Image tiles[] = new Image[8];
    private MediaTracker tracker;
    private Thread timer; // thread that controls the next move calculations
    
    private void copyNode(int destination, int source) {
        int i, j;
        for (i = 0; i < ROW; i++) {
            for (j = 0; j < COL; j++) {
                matrix[destination][i][j] = matrix[source][i][j];
            }
        }
    }
    
    private void expand(int expand) {
        tileFind(NSPROBLEM, 0);
        expNode[expand] = false;
        distNode[expand] = 255;
        switch (expand) {
            case NSUP: {
                if (yFind < (ROW -1)) {
                    copyNode(NSUP, NSPROBLEM);
                    matrix[NSUP][yFind][xFind] = matrix[NSUP][yFind +1][xFind];
                    matrix[NSUP][yFind +1][xFind] = 0;
                    expNode[NSUP] = true;Ei
                }
                break;
            }
            case NSRIGHT: {
                if (xFind > 0) {
                    copyNode(NSRIGHT, NSPROBLEM);
                    matrix[NSRIGHT][yFind][xFind] = matrix[NSRIGHT][yFind][xFind -1];
                    matrix[NSRIGHT][yFind][xFind -1] = 0;
                    expNode[NSRIGHT] = true;
                }
                break;
            }
            case NSDOWN: {
                if (yFind > 0) {
                    copyNode(NSDOWN, NSPROBLEM);
                    matrix[NSDOWN][yFind][xFind] = matrix[NSDOWN][yFind -1][xFind];
                    matrix[NSDOWN][yFind -1][xFind] = 0;
                    expNode[NSDOWN] = true;
                }
                break;
            }
            case NSLEFT: {
                if (xFind < (COL -1)) {
                    copyNode(NSLEFT, NSPROBLEM);
                    matrix[NSLEFT][yFind][xFind] = matrix[NSLEFT][yFind][xFind +1];
                    matrix[NSLEFT][yFind][xFind +1] = 0;
                    expNode[NSLEFT] = true;
                }
            }
        }
        if (expNode[expand] == true) {
            distNode[expand] = distanceEval(expand);
        }
    }
    
    private int distanceEval(int distanceExp) {    
        int i, j, distanceCount = 0, tileCounter = 0;
        int succ[][] = {{0, 1}, {0, 2}, {1, 2}, {0, 0}, {2, 2}, {1, 0}, {2, 0}, {2, 1}};
        for (i = 0; i < ROW; i++) {
            for (j = 0; j < COL; j++) {
                if ((i == YCENTER) && (j == XCENTER)) {
                    if (matrix[distanceExp][YCENTER][XCENTER] != 0) {
                        distanceCount += 3;
                    }
                    j++;
                    tileFind(NSGOAL, matrix[distanceExp][YCENTER][XCENTER]);
                    distanceCount += Math.abs(yFind - YCENTER);
                    distanceCount += Math.abs(xFind - XCENTER);
                }
                if (matrix[distanceExp][i][j] != 0) {
                    if ((matrix[distanceExp][succ[tileCounter][0]][succ[tileCounter][1]]) 
                            != (matrix[distanceExp][i][j] % 8) +1) {
                                distanceCount += 6;
                    }
                    tileFind(NSGOAL, matrix[distanceExp][i][j]);
                    distanceCount += Math.abs(yFind - i);
                    distanceCount += Math.abs(xFind - j);
                }
                tileCounter++;
            }
        }
        return distanceCount;
    }
    
    private void tileFind(int node, int tile) {
        boolean found = false;
        int i = 0, j = 0;
        while ((i < ROW) && (found == false)) {
            for (j = 0; j < COL; j++) {
                found = (matrix[node][i][j] == tile) ? true : false;
                if (found == true) {
                    break;
                }
            }
            if (found == false) {
                i++;
            }
        }
        yFind = i;
        xFind = j;
    }
    
    protected URL getURL(String fileName) {
        URL codeBase = getCodeBase();
        URL url = null;        
        try {
            url = new URL(codeBase, fileName);
        } catch (MalformedURLException e) {
            System.err.println("Invalid URL: " + url);
            return null;
        }
        return url;
    }
    
    public void init () {
        int i, j, counter, moveCount = 0;
        matrix = new int[NODETOTAL][ROW][COL];
        expNode = new boolean[EXPTOTAL];
        distNode = new int[EXPTOTAL];

        tracker = new MediaTracker(this);
        for (i = 1; i <= 8; i++) {
            tiles[i -1] = getImage(getURL("images/" + i + ".jpg"));
            tracker.addImage(tiles[i -1], 0);
        }
        
        int goalGrid[] = 
            {1, 2, 3, 
             8, 0, 4, 
             7, 6, 5}; // definition of goal-state
        int problemGrid[] = 
            {2, 8, 1, 
             4, 6, 3, 
             7, 0, 5}; // definition of initial problem-state
        for (i = 0, counter = 0; i < ROW; i++) {
            for (j = 0; j < COL; j++, counter++) {
                matrix[NSGOAL][i][j] = goalGrid[counter];
                matrix[NSPROBLEM][i][j] = problemGrid[counter];
            }
        }
    }
    
    public void paint(Graphics g) {
        int i, j;
        Dimension dim = getSize();
        int xOffset = dim.width / 3;
        int yOffset = dim.height / 3;
        if ((tracker.statusAll(false) & MediaTracker.ERRORED) != 0) {
            g.clearRect(0, 0, size().width, size().height);
            g.drawString("Please wait...", 0, size().height /2);
            return;
        }
        if (tracker.statusID(0, false) == MediaTracker.COMPLETE) {  
            moveCount++;
            for (i = 0; i < ROW; i++) {
                for (j = 0; j < COL; j++) {
                    if (matrix[NSPROBLEM][i][j] != 0) {
                        g.drawImage(tiles[matrix[NSPROBLEM][i][j] -1], 
                            (j * xOffset) +1, (i * yOffset) +1, this);
                    }
                }
            }
        }
    }
    
    public void run() {
        int solutionPath = NSTEMP, nodeMin, i, distance = 255;
        Thread me = Thread.currentThread();
        try {
            tracker.waitForID(0);
        } catch (InterruptedException e) {
            return;
        }
        while (timer == me) {
            try {        
                Thread.currentThread().sleep(1000);
            } catch (InterruptedException e) {
                break;
            }
            expand(NSUP);
            expand(NSRIGHT);
            expand(NSDOWN);
            expand(NSLEFT);
            nodeMin = NSUP; // debug
            distance = distNode[nodeMin];
            for (i = 1; i < EXPTOTAL; i++) {
                if (distNode[nodeMin] > distNode[i]) {
                    nodeMin = i;
                    distance = distNode[nodeMin];
                }
            }
            if ((nodeMin % 4) + 2 == solutionPath) {
                for (i = 0; i < EXPTOTAL; i++) {
                    if ((distNode[i] > distNode[nodeMin]) && (distNode[i] < 255)) {
                        nodeMin = i;
                    }
                }
            }
            solutionPath = nodeMin;
            copyNode(NSPROBLEM, nodeMin);
            repaint();
            if (distance == 0) {
                timer.stop();
            }
        }
    }
    
    public void start() {
        timer = new Thread(this);
        timer.start();
    }
    
    public void stop() {
        timer = null;
    }
}

TopicDB

TopicDB is a topic map-based graph (NoSQL) database.

TopicDB - Topic map-based graph database

Its (MIT-licensed) source code is available on GitHub and the accompanying Python package on Python Package Index (PyPI):

Story Engine

Story Engine is a collection of domain models and corresponding persistence-related command classes together with an accompanying set of API endpoints for the retrieval of a semantic description of 3D environments.

Semantic story engine

Its (MIT-licensed) source code is available on GitHub:







Google