;;; -*- Mode: Lisp; Syntax: Common-Lisp; -*- File: search/test.lisp

;;;; Test Cases for Search

(deftest search
  "Test the code for Solving Problems by Searching"
  "Start with a trivial version of the missionaries and cannibals puzzle."
  ((setq p1 (make-cannibal-problem 
	     :initial-state (make-cannibal-state :m1 2 :c1 1))))
  "We search for a solution node:"
  ((setq result (breadth-first-search p1)) *)
  "We can get information out of that solution:"
  ((solution-actions result) *)
  ((solution-nodes result) *)
  "Or we can use SOLVE to print the results nicely. By default, SOLVE
  uses A*-search, but you can give it another algorithm as the second arg."
  ((solve p1) *)
  "For the full 3 missionary and 3 cannibal problem, breadth-first-search"
  "is very inefficient.  Better to use something that handles repeated states,"
  "like A*-search or no-duplicates-breadth-first-search:"
  ((solve (make-cannibal-problem) 'A*-search) *)
  ((solve (make-cannibal-problem) 'no-duplicates-breadth-first-search) *)

  "Here is how to get a problem-solving agent to find the solution,"
  "and then go ahead and execute the actions that comprise the solution."
  ((run-environment (problem->environment p1)))

  "Now we look at the route-finding domain."
  "First, solve the Arad-to-Bucharest problem with A*-search:"
  ((solve (make-romanian-problem :initial-state 'Arad :goal 'Bucharest)) *)
  "Now turn it around:"
  ((solve (make-romanian-problem :goal 'Arad :initial-state 'Bucharest)) *)
  "Let's just see the actions:"
  ((solution-actions (A*-search (make-romanian-problem)))
   '(Sibiu Rimnicu Pitesti Bucharest))
  "Now on a random map:"
  ((solve (make-route-finding-problem)))

  "Here's how to compare several algorithms."
  ((setq searchers '(A*-search no-cycles-depth-first-search
			       no-duplicates-breadth-first-search)))
  ((compare-search-algorithms #'make-route-finding-problem searchers))
  ((compare-search-algorithms #'make-romanian-problem searchers :n 1))
  ((compare-search-algorithms #'make-cannibal-problem
			      '(no-returns-breadth-first-search A*-search
				no-duplicates-breadth-first-search)
			      :n 1))
  ((compare-search-algorithms #'make-romanian-problem
			     '(tree-A*-search A*-search tree-IDA*-search)
			     :n 1))
  "We'll look at the iterative improvement algorithms on a harder map problem."
  ((setq searchers '(A*-search hill-climbing-search
			       simulated-annealing-search)))
  ((compare-search-algorithms #'(lambda () (make-romanian-problem :goal 'Iasi))
			      searchers :n 1))
  "Let's take a look at the 8-puzzle:"
  ((solve (make-8-puzzle-problem)) *)
  ((compare-search-algorithms 'make-8-puzzle-problem '(A*-search) :n 2))
  "And the path-planning problem among polygonal obstacles:"
  ((solve (make-path-planning-problem :scene *scene-4.17*)))
  "Now the 8-queens problem"
  ((solve (make-nqueens-problem) 'csp-backtracking-search) *)
  ((compare-search-algorithms
    'make-nqueens-problem
    '(csp-backtracking-search csp-forward-checking-search)
    :n 1))
  "Here is the Travelling Salesperson Problem (TSP)."
  ((solve (make-tsp-problem)))
  ((compare-search-algorithms 'make-tsp-problem
			     '(A*-search greedy-search uniform-cost-search)
			     :n 5))
  "Now we test the environments for 2-player and 3-player games:"
  ((run-game (make-ttt-game)))
  ((run-game (make-cognac-game :players '(X O @))))
  "Now we see that 2x2 tic-tac-toe is a win for the first player, X."
  ((run-game (make-ttt-game :n 2) 
	     :agents '(alpha-beta-ttt-agent alpha-beta-ttt-agent)))
  "In a full 3x3 game, alpha-beta search (playing O) often wins."
  ((run-game (make-ttt-game) :agents '(random-game-agent alpha-beta-ttt-agent)))
  )