README.md

🕳️ _Matrix

Project _Matrix (Line-Matrix) is a comprehensive exploration of AI search algorithms, using the 8-Puzzle problem as a case study. The program includes implementations of famouse search algorithms, such as BFS, IDDFS, GBFS, and A* search algorithms, and a custom heuristic for A* and GBFS. The program was initially developed for the 20551 Introduction to Artificial Intelligence course at the Open University of Israel, and earned a perfect score of 100/100.

AI8Puzzle GTK GUI (C++)

---

• The 8-Puzzle Problem
  • States
  • Initial State
  • Actions and Transition Model
  • Goal States
  • Action cost
• Running the Program
• Technical Details
  • Node Class
  • Search Data Structures
  • Custom A* and GBFS Heuristics
  • Examples
• Acknowledgments
• License

---

New HUGE 8-Puzzle GUI

The 8-Puzzle Problem

The 8-Puzzle broblem is a classic AI problem, where the goal is to move the tiles from the initial state to the target state, using the minimum number of moves. The puzzle consists of a 3x3 grid with 8 numbered tiles and one empty space. The tiles are initially arranged in a random order, and the goal is to arrange them in ascending order, with the empty space at the bottom right corner, or at the top left corner (see wikipedia).

Example of 8-Puzzle: Movinge tile `1` from the top left corner, thand moving `4` to the middle

In the following section I will describe the main components of the problem as a search problem in a more formal way, accoding to the book "Artificial Intelligence: A Modern Approach", by Stuart Russell and Peter Norvig.

---

States

class State:
    def __init__(self, numbers: List[int], rows=3, cols=3):
        #...
        self.numbers = numbers
        self.rows, self.cols = rows, cols
        self.matrix = self._create_matrix(numbers, rows, cols)
    # ...
    def _create_matrix(self, numbers, rows, cols):
        return [[numbers[i * cols + j] for j in range(cols)] for i in range(rows)]

The State class is responsible for representing a state in the world. A state, in this specific problem, is a configuration of the puzzle. Each puzzle configuration, converting a linear array of tiles into a 2D matrix. This design choice simplifies both the visualization of the puzzle state and the implementation of moves within the puzzle space.

Initial State

Example of shuffled 8-Puzzle, GUI with `cubes` theme

def main():
    try:
        initial_numbers = [int(num) for num in sys.argv[3:]]
        # main constructing the first state
        initial_state = State(initial_numbers)
    except ValueError:
        print("All arguments must be integers.")
        sys.exit(1)

    print(BFS(initial_state))
    print(IDDFS(initial_state))
    print(GBFS(initial_state))
    print(AStar(initial_state))

The initial state, the one without a parent attribute, is defined based on the user input and starts as the tree root. The main function is responsible for parsing and initiating the initial_state instance, then it prints the result.

Actions and Transition Model

clicking the colored tiles will move them to the empty space

# ...
def generate_children(self):
    blank_x, blank_y = self.find_number_in_matrix(0)
    children = []
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        x, y = blank_x + dx, blank_y + dy
        if 0 <= x < self.rows and 0 <= y < self.cols:
            new_numbers = self.numbers.copy()
            blank_index, new_index = blank_x * self.cols \
                + blank_y, x * self.cols + y
            new_numbers[blank_index], new_numbers[new_index] =\
                new_numbers[new_index], new_numbers[blank_index]
            children.append(State(new_numbers))
    return children

The actions and transition mosdel as implemented inside the state class generate_children.

The State class also includes methods for generating children states, considering possible moves from the current state. This method implements the Actions and the transition model. I chose to implement them inside the State class to keep the idea of separated responsibility. That way, the SearchAlgorithm are only navigating the designed state space.

Goal States

Path to goal state of the 8-Puzzle

The problem includes two goal states, defined as plain List[int] to match the program initial_state input format.

TARGET_A = [0, 1, 2, 3, 4, 5, 6, 7, 8]
TARGET_B = [1, 2, 3, 4, 5, 6, 7, 8, 0]

Action cost

Each action performed by generate_children above cost 1, so 1 is the action cost of the problem. The cost is managed in the Node class which will be described below.

---

Running the Program

`theMatrix` theme GUI

The program supports both interactive GUI and command-line interfaces. Two GUI versions are available: one implemented in Python using the tkinter library, and another implemented in C++ using the GTK library. The Python version is more easy to use and has more features, while the C++ version offer cool visual effects and supports CSS styling.

• To run the C++ GUI, first make sure you have GTK installed. Then navigate to the directory containing AI8Puzzle and execute the following command in the terminal:

  ./make && ./main <-s number of tiles>

  The -s flag is optional and allows you to set the number of tiles in the puzzle (including the blank tile). The default is 9 tiles. The program will generate a random solvable puzzle and open a window where you can interact with the puzzle.

  
  `elegant` theme GUI

  The program will open a window where you can interact with the puzzle. You can move the tiles by clicking on them, or use the keyboard arrow keys. You can also use the following shotcuts:

  • ctrl + n - generate a new random puzzle (shuffled)
  • ctrl + s - solve the puzzle using the BFS algorithm
  • ctrl + r - reset the puzzle (default goal state)
  • ctrl + q - quit the program
  • ctrl + t - choose new theme from css file

  
  Menu (C++)

• To run the python GUI, first make sure you have tkinter installed. Then navigate to the directory containing Tiles.py and execute the following command in the terminal:

  python3 GUI.py

  

• To run the program in the command-line interface mode, navigate to the directory containing Tiles.py and execute the following command in the terminal:

  python3 Tiles.py <9 space-separated numbers representing the initial state>

  The program will print the results for each algorithm in the required format:

  <Algorithm name>
  <Explored count - numbur of expanded nodes>
  <Solution Path>

You can also use this simple tester program, which leverages the modular design of the searching algorithms to directly get the desired tests. The PuzzleTester class is implemented in PuzzleTester.py and can generate random solvable puzzles, test the algorithms, and print the results.

---

Technical Details

class SearchAlgorithm:
    class ExploredSet:
    # ... end of ExploredSet
    def __init__(self, initial_state, name=None):
        self.root_node = Node(initial_state)
        self.frontier = None
        self.explored = self.ExploredSet()
        self.name = name
        self.solution_node = None

Note the base class of SearchAlgorithm init method takes the initial_state as the argument and turns it into the Node class - see below.

For a self-exercise in python OOP programming, the search algorithms were designed as Classes, and not as simple methods. Each search algorithm is derived from the base class SearchAlgorithm, and includes member attributes for navigating the states space, including:

• root_node - instance of class Node from main

• frontier - specific derived instance of the fringe (see below)

• ExploredSet - Instance of a hashing table to hold the close set. ExploredSet is used to keep track of explored states, preventing re-exploration and aiding in efficient search. This structure helps deal efficiently with redundant paths.

---

Node Class

The node class is responsible for representing a node in the search tree. The program uses 2 types of nodes: a base Node class and a derived PriorityQueueNode class.

Each Node instance stores the current state, the parent node, and the path cost $g(n)$. In addition, PriorityQueueNode Class is a specialized version of the Node class, used in A*and GBFS, includes a priority attribute for the heuristic value $h(n)$. The design is matching the book data structure (see section 3.2.2) for a node, with some improvements, such as the PriorityQueueNode, which includes an attribute for its priority, and an override version of the __lt__ function ($<$). This implementation allows using the built in python data structure from module heapq, directly on Nodes instances, as will described now.

class PriorityQueueNode(Node):
    def __init__(self, node):
        super().**init**(node.state, node.parent)
        # The `priority` attribute stores the estimated cost form the `PriorityQueueNode` to the target
        self.priority = None

    def __lt__(self, other):
        return self.priority < other.priority

Note that other methods, such as back_track_h and check_h allow for testing the heuristic, enable back-tracking, and check if the heuristic is admissible and consistent for futu future development and testing.

---

Search Data Structures

The Frontier Class Acts as the fringe or the boundary between explored and unexplored states. It is a priority queue (minimum heap) in A* and GBFS, and a simple queue or stack in BFS and IDDFS, respectively. In BFS it's implemented as a FIFO queue, while in the IDDFS as a stack. In addition to its specific implementation, it is responsible for counting how many nodes expand using the explored_count.

The IDDFS also passes the max_length argument to its frontier and stores the explored_count while resetting its structures between the searches. Maximum depth was set to 40, and can be adjusted.

The BFSFrontier and IDDFSFrontier derived from the Frontier class, these are specialized for BFS and IDDFS algorithms, managing the order of node expansion. Note that all the frontier are implemented insdide the relevant search algorithm class, and not as a separate class. Note also for specific usage, like the IDDFS that uses the max_length argument to limit the depth of the search, and reset_data method to reset the structures between the searches and update the max_length and explored_count.

    class BFSFrontier(Frontier):
        # BFS remove from the list start in `return self.open_list.pop(0)`
        def remove_from_frontier(self):
            if self.open_list:
                self.explored_count += 1
                return self.open_list.pop(0)
            return None
        # ...

    class IDDFSFrontier(Frontier):
        # IDDFS removes from the back (stack) in `return self.open_list.pop()`
        def remove_from_frontier(self):
            if self.open_list:
                self.explored_count += 1
                return self.open_list.pop()
            return None
        #...
        def insert_to_frontier(self, node):
            # IDDFS als tracks the max depth in the insert method using the condidion
            if node.cost <= self.max_length+1:
                self.open_list.append(node)

class GBFS(SearchAlgorithm):
    class GBFSFrontier(Frontier):
        # ...
        def set_priority(self, node):
            return node.my_heuristic()

Note GBFSfrontier sets onle the heuristic to the prirrity, thus $f(n)=h(n)$.

class AStar(SearchAlgorithm):
    class AStarFrontier(Frontier):
        #...
        def set_priority(self, node: PriorityQueueNode):
            return node.cost + node.my_heuristic()

A* frontier adds the node.cost to its prirrity, thus $f(n)=h(n)+g(n)$.

Custom A* and GBFS Heuristics

The program also includes custom heuristics for A* and GBFS. The heuristics are implemented as methods inside the PriorityQueueNode class, and are used to calculate the estimated cost from the current state to the target state. The heuristics are used to guide the search algorithms in finding the optimal path to the target state.

To develop a consistent and admissible heuristic that differs from the traditional misplaced tiles or Manhattan distance measures, I have employed a custom modification of Cumulative Euclidean distances heuristic for A*. It eases the problem constraints by allowing vertical moves, matching the Relaxed Problem technique.

For more information about the heuristics, see the PriorityQueueNode class in Tiles.py.

Examples

Input for 30 moves solvable puzzles generated by the 'PuzzleTester':

back_track_h on A* with initial_state of [0, 1, 4, 6, 3, 2, 7, 8, 5]

---

Acknowledgments

• Inspired by the book "Artificial Intelligence: A Modern Approach" by Stuart Russell and Peter Norvig.
• Thanks to the Open University of Israel for the opportunity to work on this project.

---

License

This project is licensed under the MIT License - see the LICENSE file for details.