Given your requirements, I would recommend against backtracking the way I've already layed out. The way I've explained it keeps everything on the stack, and so backtracks without extra data structures, which is very generic. A different approach is to search by maintaining a collection of in-memory states, a function to compute the possible next states from a given state, and a heuristic function that tells us if a given state is likely to go anywhere.
A user in another post (viewtopic.php?f=2&t=868&start=0) asked about how he could implement a board AI for a simple tic-tac-toe game. I gave him this code to illustrate how a simple search goes. You might find that discussion relevant.
Code: Select all
(defpackage :tictac
(:use :common-lisp))
(in-package :tictac)
;; Using a vector to represent the board makes access
;; easier and faster e.g. (elt *board* (+ (* 3 x) y))
(defun make-board () (make-array 9 :initial-element nil))
(defun empty-board-p (board) (every #'null board))
;; +search-depth+ controls recursion depth.
(defconstant +search-depth+ 4)
;; Gen-next takes a current board position, and must generate
;; all valid positions that can be made from it. Because its
;; NIL, the game will assume there are never any valid
;; positions, and will be over very soon.
(defun gen-next (board our-turn-p) (declare (ignore board our-turn-p)) nil)
;; A board-score of 0 is neutral. Use negative numbers to communicate
;; a board is BAD, and positive to communicate a board is good.
(defun board-score (board) (declare (ignore board)) 0)
;; Score calculates the boards score then adds the score for the
;; boards children (upto +search-depth+ deep) to produce the
;; branches total score.
(defun score (board depth)
(let ((score (board-score board)))
(if (= depth +search-depth+)
score
(loop for child in (gen-next board (evenp depth)) ;; Even-p means its our move, odd means theirs.
do (incf score (score child (1- depth)))
finally (return score)))))
;; Choose computes the children for a board and runs SCORE on each
;; one. It returns the board with the highest score, or NIL if
;; there where no boards.
(defun choose (board)
(caar (sort (loop for child in (gen-next board t) collecting (cons child (score child 0))) #'> :key #'cdr)))
;; AI will return the next board or NIL if the game is over.
(defun ai (board) (format t "~%I'm thinking...") (choose board))
The function CHOOSE arranges all the possible next states by their score and takes the best one, which is generally what you want. With slighly different code, you could display the next-states to the user and let him pick one.