Lab 1: 8-puzzle (fr: taquin)

What's an 8-puzzle?

The 8-puzzle is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The object of the puzzle is to place the tiles in order by making sliding moves that use the empty space, reaching the configuration below

Goal state:
┏━━━┳━━━┳━━━┓
┃ 1 ┃ 2 ┃ 3 ┃
┣━━━╋━━━╋━━━┫
┃ 4 ┃ 5 ┃ 6 ┃
┣━━━╋━━━╋━━━┫
┃ 7 ┃ 8 ┃   ┃
┗━━━┻━━━┻━━━┛

Practice with the 8-puzzle, try solving the instance below (with your own, non-artificial, intelligence):

• Online Game

Install Rust

The project is a Rust project, and you will need to have Rust installed on your machine to run it (it is not preinstalled).

Installation instructions are available on the Rust website.

Get acquainted

Get the code from the repository: https://github.com/arbimo/insa-4ir-ai-lab1-template

The code already contains a number of files:

• src/board.rs: the board representation, together with the actions that can be performed on it
• src/main.rs: the main file, where you can test your code
• src/search.rs: placeholder for the search algorithm
• src/heuristic.rs: placeholder for the heuristic function used by the search
• src/min_heap.rs: a very simple min heap implementation that you can use

Understanding the board representation

If you run the test suite with cargo test, you will see that the board representation is not complete yet and has a few tests that fail.

• ▢ complete the test_position and test_apply unit tests in board.rs
• ▢ implement the is_valid_plan method (so that the corresponding test passes)

#![allow(unused)]
fn main() {
match board.apply(Direction::Down) {
    Some(new_board) => { /* do something with new_board */ },
    None => { /* the action is not valid */ }
}
}

Solving your first 8-puzzle

• ❓What is the sequence of moves to reach the goal state from the following position? (hint: you only need 4)

┏━━━┳━━━┳━━━┓
┃ 1 ┃ 2 ┃ 3 ┃
┣━━━╋━━━╋━━━┫
┃ 4 ┃ 8 ┃ 5 ┃
┣━━━╋━━━╋━━━┫
┃   ┃ 7 ┃ 6 ┃
┗━━━┻━━━┻━━━┛

• in the main.rs file, implement the main function to:
  • ▢ create the board above
  • ▢ create the plan (sequence of actions) to reach the goal state
  • ▢ validate the plan (use the is_valid_plan method)
  • ▢ simulate the plan with the play method

Uninformed search (Dijkstra)

At this point we will try to implement an AI to solve the 8-puzzle. This means, that for any initial state, we want to find the sequence of moves to reach the goal state. We are interested in finding the shortest sequence of moves. We will therefore assume that each action has a cost of 1.

• ▢ implement the search method in search.rs, not using any heuristic (it is a Dijkstra algorithm)

#![allow(unused)]
fn main() {
let path_costs: HashMap<Board, u32> = HashMap::new();

// associates the board with a path cost of 9 (replacing any previous value)
path_costs.insert(board, 9);

// get the path cost of a board
// the result would be Some(9) for the board inserted above
// but None for a board that was not inserted before
let optional_cost: Option<&u32> = path_costs.get(&board);
// when you have an option that you know will contain something,
// you can use the unwrap method (that will panic if the option is None)
let cost: &u32 = optional_cost.unwrap();

// In Dijskstra's algorithm, it will often be the case that you know a value is present.
// In this case, you can use the index notation to directly access the value
// Note: it will panic if nothing is there
let cost: u32 = path_costs[&board];
}

• ▢ test it on different instances of the 8-puzzle:
  • INSTANCES in board.rs gives a number of initial states with a known distance to the goal.
• ▢ use the statistics explore the evolution of the runtime and the number of nodes explored with the distance to the goal

cargo run --release

Informed, optimal search (A*)

• ▢ in the heuristic.rs file, implement the estimate method for the hamming distance
• ▢ modify the search method to use the heuristic (taking an additional parameter heuristic: &Heuristic)
• ▢ compare the performance of the search with the heuristic to the blind search (at this point, printing output in a form that you can copy-paste in a spreadsheet is a good idea)

• ▢ repeat with the Manhattan distance heuristic

Suboptimal search

• ▢ implement weighted A* search
  • given the similarity with the A* algorithm, you can probably do it by generalizing the search method in search.rs and have A* and Weighted-A* only differ by the parameters passed to the search method

Going further

• counting states: propose and implement a method to count the number of states that can be lead to the goal states

  • there is an argument that there is only 9!/2 reachable states for the 8-puzzle (but doing the math is probably harder than counting them)

• enumerating: how many states are there at distance 17 from the goal state?

• unreachable states: can you find a state that is not reachable from the goal state?

• generating instances: propose a way to generate random solvable instances of the 8-puzzle

  • you can use the rand crate for getting random numbers.

• larger boards: make the puzzle more challenging by increasing the size of the board (4x4)

  • the size of the board is controlled by the N constant in board.rs
  • modifying it should be easy enough but will invalidate all the predefined boards defined for testing
  • careful: the state space is much larger, you cannot expect to fit it all in memory (for the larger instances, you can consider memory-frugal variants such as IDA*)