ICS 171: Homework #6

1. (40 points) Try to Solve your Towers of Hanoi problem (from assignment 2) with steepest ascent hill climbing search. You'll have to think of a heuristic, and define the functions (estimated-distance-from-goal state) and (cost-of-applying-operator Current-state operator) -- This last function should always return the value 1. Depending on the heuristic you use, you probably won't be able to solve it with this search method. If you can't find some other start state (e.g., almost all discs on the correct peg) so that you can solve it. The code is in heuristic-search.lisp

2. (60). EXTREMELY IMPORTANT The game connect four is played on a board that has 7 columns. There are 6 spaces on each column. The board is initially empty. Players take turns dropping one piece (an x or an o in our game) in a column. The piece falls to lowest unoccupied row. A player cannot move in a column if the top most row of that column already has a piece in it.

a. create a variable *start* and initialize it to an empty board
YOU MUST USE (make-array '(7 6) :initial-element nil)

b. Create a function to print the board. One possibility is:

(print-board *start*)

===============
| | | | | | | |
===============
| | | | | | | |
===============
| | | | | | | |
===============
| | | | | | | |
===============
| | | | | | | |
===============
| | | | | | | |
===============
 0 1 2 3 4 5 6

c. Write a function copy-board to create a new array with a copy of the board. The next function will need to call it.

d. Write a function (make-move board player i) that takes as input a board, a player (x or o) and i (a number from 0 to 6) and either returns nil if a player cannot move in column i, (because it is full), or returns a copy of the board with a new piece in the lowest available row of column i.

(print-board (make-move *start* 'x 3))

===============
| | | | | | | |
===============
| | | | | | | |
===============
| | | | | | | |
===============
| | | | | | | |
===============
| | | | | | | |
===============
| | | |X| | | |
===============
 0 1 2 3 4 5 6

(print-board 
   (make-move 
    (make-move 
     (make-move 
      (make-move 
       (make-move 
        (make-move 
         (make-move   *start* 'x 3)
         'o 3) 
        'x 3) 
       'o 3) 
      'x 3) 
     'o 2) 
    'x 4))

===============
| | | | | | | |
===============
| | | |X| | | |
===============
| | | |O| | | |
===============
| | | |X| | | |
===============
| | | |O| | | |
===============
| | |O|X|X| | |
===============
 0 1 2 3 4 5 6

e. Write a function (won? board player) which returns true if player x has 4 in a row on the board vertically, horizontally, diagonally up or diagonally down. Write a function (drawn? board) that returns true if there are no legal moves in connect four (i.e., the board is full). The file c4lines.lisp contains a list of all 69 possible lines. Be careful not to confuse rows and columns.