Lab: Informed Search and Heuristics

CSC261 - Artificial Intelligence - Weinman

Summary:

We explore a heuristic for the eight-puzzle problem in preparation for implementing A^* and a new heuristic.

Preparation

1. Open your Scheme environment and create a new Scheme file in your definitions pane in the same directory as your prior search files.
2. Add the preparations from the prior lab to your file:

   ;; Load definitions

   (load "problem.scm")

   (load "node.scm")

   (load "8puzzle.scm")

    

   ;; Define the problem

   (define eight-puzzle (eight-puzzle-problem))

Exercises

A: Eight puzzle heuristic

1. Let's create a more difficult problem with at most ten moves from the goal

   (define eight-puzzle-state (random-eight-puzzle-state 10))

   and display it.

   > (display (eight-puzzle-state-board-list eight-puzzle-state))
2. The function eight-puzzle-misplaced in the file 8puzzle.scm provides the simple heuristic h₁ of AIMA 3.6 (p. 103), which is the number of misplaced (out of position) tiles. Apply this heuristic to your state.

   > (eight-puzzle-misplaced eight-puzzle-state)
3. Create a search node for this state. Recall that that node-init requires a heuristic procedure, which we can now take to be eight-puzzle-misplaced.

   (define eight-puzzle-start-node

     (node-init eight-puzzle-state

                eight-puzzle-misplaced))
4. Query the path cost and (estimated) total cost of this start node.

   > (node-path-cost eight-puzzle-start-node)

   > (node-total-cost eight-puzzle-start-node)

   Make sure these two numbers make sense to you before moving on.
5. Using this heuristic function, generate the successors to your state.

   (define successors 

     (problem-expand-node eight-puzzle 

                          eight-puzzle-start-node

                          eight-puzzle-misplaced))

   Which successor would depth-first search expand next? Make sure your partner(s) agree about why.
6. Inspect the (estimated) total cost of all the successors

   > (map node-total-cost successors)

   1. Which successor would uniform-cost-search expand next?
   2. Which successor would A^* search expand next?

B: Hex turn representation

1. Make sure the hex turn procedures are available, define a size 4 version of the problem, and a do-nothing heuristic.

   (load "hexturn.scm")

   (define hexturn (hexturn-problem 4))

   (define zero-fun (lambda (x) 0))
2. Read the "Practica" section of the header in hexturn.scm to understand the Scheme-based state representation.
3. Define an initial state with a random board for the hex turn puzzle problem, as follows.

   (define hex-start (random-hexturn-puzzle 4))
4. Use the following expressions to explore the various elements available from a problem state. Evaluate each of them one at a time, making sure you understand each of them before proceeding.

   > (hexturn-moves hex-start)

   > (hexturn-goal hex-start)

   > (hexturn-color hex-start)

   > (hexturn-board-print (hexturn-num-rings hex-start)

                          (hexturn-board hex-start))

   > (hexturn-board-color (hexturn-num-rings hex-start)

                          (hexturn-board hex-start) 

                          (hexturn-goal hex-start))

   > (hexturn-board-color (hexturn-num-rings hex-start)

                          (hexturn-board hex-start) 

                          (cons 1 3))
5. Create a node for your hex turn puzzle state and generate its successors, just as you did for the eight-puzzle above (B.3), but using the uninformed heuristic zero-fun.

   (define hex-start-node _________)

   (define successors _________)
6. Inspect the actions corresponding to each successor.

   > (map node-action successors)

   What do you suppose these actions mean? Confirm your intuition with the instructor.

Lab Assignment