;;; -*- 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 p (cannibal-problem :m 2 :c 1)))
  "Here are two equivalent ways to get at the solution"
  "(Note the default for SOLVE is iterative-seepening-search when there's no h)"
  ((solution-actions (iterative-deepening-search p)) *)
  ((solve p :print t) *)
  "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-problem p :display t))
  "To do the full M&C problem, we need to eliminate repeated states"
  ((setq p3 (cannibal-problem :m 3 :c 3)))
  ((solve p3 :print t :algorithm 'no-duplicates-breadth-first-search) *)
  "Now we look at the route-finding domain."
  "First, two equivalent ways to solve the Arad-to-Bucharest problem."
  "(Note the default for SOLVE is A*-search when there is an h-function.)"
  ((solve (romanian-problem) :print t) *)
  ((solution-actions (A*-search (romanian-problem)))
   '(Sibiu Rimnicu Pitesti Bucharest))
  "Now on a random map:"
  ((solve (route-finding-problem) :print t))
  "Here's how to compare several algorithms."
  ((setq searchers '(A*-search no-cycles-depth-first-search
			       no-duplicates-breadth-first-search)))
  ((compare-search-algorithms #'route-finding-problem searchers))
  ((compare-search-algorithms #'romanian-problem searchers :n 1))
  ((compare-search-algorithms #'cannibal-problem
			      '(no-returns-breadth-first-search
				no-duplicates-breadth-first-search)
			      :n 1))
  ((compare-search-algorithms 'romanian-problem
			     '(tree-A*-search A*-search tree-IDA*-search)
			     :n 1))
  "We'll look at the iterative improvement algorithms on harder map problems."
  ((setq searchers '(A*-search hill-climbing-search
					 simulated-annealing-search)))
  ((compare-search-algorithms #'(lambda () (romanian-problem :goal 'Iasi))
			      searchers :n 1))
  ((compare-search-algorithms 'random-romanian-problem searchers))
  "Let's take a look at the 8-puzzle:"
  ((solve (8-puzzle-problem) :print t) *)
  ((compare-search-algorithms '8-puzzle-problem '(A*-search) :n 2))
  "And the path-planning problem among polygonal obstacles:"
  ((setq p (path-planning-problem *scene-4.17*)))
  ((solve p :print t))
  "Now the 8-queens problem"
  ((solve (nqueens-problem 8) :algorithm 'csp-backtracking-search) *)
  ((compare-search-algorithms
    'nqueens-problem
    '(csp-backtracking-search csp-forward-checking-search)
    :n 1))
  "Here is the Travelling Salesperson Problem (TSP)."
  ((compare-search-algorithms 'tsp-problem
			     '(A*-search greedy-search uniform-cost-search)
			     :n 5))
  "Now we test the environments for 2-player and 3-player games:"
  ((play-game (ttt-game) :display t))
  ((play-game (cognac-game :players '(X O @)) :display t))
  "Now we see that 2x2 tic-tac-toe is a win for the first player, X."
  "(The default for generic-game-agent is to use minimax.)"
  ((play-game (ttt-game :m 2 :n 2)
	     :agent-types '(generic-game-agent generic-game-agent)))
  "In a full 3x3 game, alpha-beta search (playing O) often wins."
  ((play-game (ttt-game)
	     :agent-types '(random-game-agent alpha-beta-ttt-agent)))
  )