**test-search.lisp**Test Cases for Search

**problems.lisp**Defining Problems**simple.lisp**Simple Search Algorithms**repeated.lisp**Search Algorithms That Avoid Repeated States**csp.lisp**Definition of CSPs (Constraint Satisfaction Problems).**ida.lisp**Iterative Deepening A* (IDA*) Search**iterative.lisp**Iterative Improvement Search Algorithms**sma.lisp****minimax.lisp**Deciding What Move to Make in a Game by Minimax or Alpha-Beta Search

**games.lisp**Game-Playing**prob-solve.lisp**Problem-Solving Environments

**cannibals.lisp**The Missionaries and Cannibals Domain**ttt.lisp**The Game of Tic-Tac-Toe**cognac.lisp**The Game of Cognac**nqueens.lisp**The N-Queens Puzzle as a Constraint Satisfaction Problem**path-planning.lisp**Path Planning in 2 Dimensions with Convex Polygonal Obstacles**puzzle8.lisp**The 8-Puzzle Problem**route-finding.lisp**Find a Route Between Cities on a Map**tsp.lisp**The Travelling Salesperson Problem (TSP)**vacuum.lisp**Definitions for Searching in the Vacuum-World Domain

**ps-agents.lisp**Problem-Solving Agents**ttt-agent.lisp**An Agent for Playing Tic-Tac-Toe

**problem** *type* (initial-state
goal
num-expanded
iterative?)

A problem is defined by the initial state, and the type of problem it is. We will be defining subtypes of PROBLEM later on. For bookkeeping, we count the number of nodes expanded. Note that the three other fields from the book's definition [p 60] have become generic functions; see below.

**successors** *method* ((problem
problem)
state)

Return an alist of (action . state) pairs, reachable from this state.

**goal-test** *method* ((problem
problem)
state)

Return true or false: is this state a goal state? This default method checks if the state is equal to the state stored in the problem-goal slot. You will need to define your own method if there are multiple goals, or if you need to compare them with something other than EQUAL.

**h-cost** *method* ((problem
problem)
state)

The estimated cost from state to a goal for this problem. If you don't overestimate, then A* will always find optimal solutions. The default estimate is always 0, which certainly doesn't overestimate.

**edge-cost** *method* ((problem
problem)
node
action
state)

The cost of going from one node to the next state by taking action. This default method counts 1 for every action. Provide a method for this if your subtype of problem has a different idea of the cost of a step.

**node** *type* (state
parent
action
successors
unexpanded
depth
g-cost
h-cost
f-cost
expanded?
completed?)

Node for generic search. A node contains a state, a domain-specific representation of a point in the search space. A node also contains bookkeeping information such as the cost so far (g-cost) and estimated cost to go (h-cost). [p 72]

**expand** *function* (node
problem)

Generate a list of all the nodes that can be reached from a node.

**create-start-node** *function* (problem)

Make the starting node, corresponding to the problem's initial state.

**solution-actions** *function* (node
&optional
actions-so-far)

Return a list of actions that will lead to the node's state.

**solution-nodes** *function* (node
&optional
nodes-so-far)

Return a list of the nodes along the path to the solution.

**solve** *function* (problem
&optional
algorithm)

Print a list of actions that will solve the problem (if possible). Return the node that solves the problem, or nil.

**print-solution** *function* (problem
node)

Print a table of the actions and states leading up to a solution.

**compare-search-algorithms** *function* (problem-fn
algorithms
&key
n)

Run each algorithm on N problems (as generated by problem-fn) and compare the results for nodes expanded and for path cost.

**print-structure** *method* ((node
node)
stream)

**display-expand** *method* ((problem
problem)
node)

Possibly print information when a node is expanded.

**general-search** *function* (problem
queuing-fn)

Expand nodes according to the specification of PROBLEM until we find a solution or run out of nodes to expand. The QUEUING-FN decides which nodes to look at first. [p 73]

**breadth-first-search** *function* (problem)

Search the shallowest nodes in the search tree first. [p 74]

**depth-first-search** *function* (problem)

Search the deepest nodes in the search tree first. [p 78]

**iterative-deepening-search** *function* (problem)

Do a series of depth-limited searches, increasing depth each time. [p 79]

**depth-limited-search** *function* (problem
&optional
limit
node)

Search depth-first, but only up to LIMIT branches deep in the tree.

**best-first-search** *function* (problem
eval-fn)

Search the nodes with the best evaluation first. [p 93]

**greedy-search** *function* (problem)

Best-first search using H (heuristic distance to goal). [p 93]

**tree-a*-search** *function* (problem)

Best-first search using estimated total cost, or (F = G + H). [p 97]

**uniform-cost-search** *function* (problem)

Best-first search using the node's depth as its cost. Discussion on [p 75]

**make-initial-queue** *function* (problem
queuing-fn)

**eliminate-returns** *function* (nodes)

Get rid of nodes that return to the state they just came from, i.e., where the last two actions just undo each other.

**eliminate-cycles** *function* (nodes)

Get rid of nodes that end in a state that has appeared before in the path.

**eliminate-all-duplicates** *function* (nodes
node-table)

Get rid of all nodes that have been seen before in any path.

**no-cycles-depth-first-search** *function* (problem)

Do depth-first search, but eliminate paths with repeated states.

**no-returns-breadth-first-search** *function* (problem)

Do breadth-first search, but eliminate immediate returns to a prior state.

**no-duplicates-breadth-first-search** *function* (problem)

Do breadth-first search, but eliminate all duplicate states.

**a*-search** *function* (problem)

Search the nodes with the best f cost first. If a node is ever reached by two different paths, keep only the better path.

**make-eliminating-queuing-fn** *function* (eval-fn)

**looping-node?** *function* (node
&optional
depth)

Did this node's state appear previously in the path?

**return-node?** *function* (node)

Is this a node that returns to the state it just came from?

**csp-problem** *type* (forward-checking?
legality-checking?
variable-selector)

A Constraint Satisfaction Problem involves filling in values for variables. We will use a CSP-state structure to represent this.

**csp-state** *type* (unassigned
assigned
constraint-fn
modified)

**csp-var** *type* (name
domain
value
conflicts)

**goal-test** *method* ((problem
csp-problem)
node-or-state)

STATE is a goal if all variables are assigned legally.

**successors** *method* ((problem
csp-problem)
s)

**csp-backtracking-search** *function* (problem
&optional
queuing-fn)

**csp-forward-checking-search** *function* (problem
&optional
queuing-fn)

**print-structure** *method* ((state
csp-state)
stream)

**csp-legal-statep** *function* (s)

**filter-domains** *function* (name
value
unassigned
constraint-fn)

**csp-modifications** *function* (s
&optional
variable-selector-fn)

**modify-assignment** *function* (s
var
name
new
assigned
constraint-fn)

**most-constrained-variable** *function* (vars)

**random-conflicted-variable** *function* (vars)

**min-conflicts-value** *function* (s)

**csp-empty-domainp** *function* (s)

**csp-legal-values** *function* (name
values
assigned
constraint-fn)

**csp-legal-assignmentp** *function* (name
value
assigned
constraint-fn)

**csp-explicit-check** *function* (name1
value1
name2
value2
constraints)

**csp-random-completion** *function* (s)

**csp-conflicts** *function* (var
vars
constraint-fn)

**tree-ida*-search** *function* (problem)

Iterative Deepening Tree-A* Search [p 107].

**dfs-contour** *function* (node
problem
f-limit)

Return a solution and a new f-cost limit.

**hill-climbing-search** *function* (problem
&optional
stopping-criterion)

Search by picking the best successor according to heuristic h. Stops according to stopping-criterion.

**simulated-annealing-search** *function* (problem
&optional
schedule)

Like hill-climbing-search, except that we pick a next node randomly; if it is better, or if the badness of the next node is small and the 'temperature' is large, then we accpet it, otherwise we ignore it. We halt when the temperature, TEMP, hits zero [p 113].

**random-restart-search** *function* (problem-fn
&optional
n)

Random-restart hill-climbing repeatedly calls hill-climbing-search. PROBLEM-FN should return a problem with a random initial state. We look at N different initial states, and keep the best solution found.

**hill-climbing-until-flat-n-times-search** *function* (problem
&optional
n)

Do hill climbing, but stop after no improvement N times in a row.

**local-minimum** *function* (current
next)

Stop when the next state is worse than the current.

**minimum-or-flat** *function* (current
next)

Stop when the next state is no better than the current.

**minimum-or-flat-n-times** *function* (n)

Return a function that stops when no improvement is made N times in a row.

**csp-termination** *function* (current
next)

**make-exp-schedule** *function* (&key
k
lambda
limit)

Return an exponential schedule function with time limit.

**tree-sma** *function* (problem
&optional
memory-size)

* tree-get-next-successor returns the next successor of n, if any (else nil)*

**tree-get-next-successor** *function* (n
q
memory-size
problem)

* tree-backup-f-cost updates the f-cost for a node's ancestors as needed*

**tree-backup-f-cost** *function* (node
q
&optional
was-open?)

* tree-prune-open removes the worst node from the open list.*
* The node is discarded from the open list, and its successors are*
* dumped to recycle memory. If the parent was closed, it must be*
* re-opened, with an updated f-cost (no need to do this until now*
* because it wasn't on the open list anyway). Closed parent or not,*
* the worstnode becomes an unexpanded successor of the parent. *

**tree-prune-open** *function* (q)

**tree-unexpand-successor** *function* (successor
parent)

**deepest-least-leaf** *function* (q)

**shallowest-largest-leaf** *function* (q)

**find-leaf** *function* (node)

**leafp** *function* (n)

**openp** *function* (n)

**minimax-decision** *function* (state
game)

Return the best action, according to backed-up evaluation. Searches the whole game tree, all the way down to the leaves. This takes too much time for all but the simplest games, but it is guaranteed to produce the best action.

**minimax-value** *function* (state
game)

**minimax-cutoff-decision** *function* (state
game
eval-fn
limit)

Return the best action, according to backed-up evaluation down to LIMIT. After we search LIMIT levels seep, we use EVAL-FN to provide an estimate of the true value of a state; thus the action may not actually be best.

**minimax-cutoff-value** *function* (state
game
eval-fn
limit)

**game-successors** *function* (state
game)

Return a list of (move . state) pairs that can be reached from this state.

**terminal-values** *function* (state)

Return the values of the state for each player.

**alpha-beta-decision** *function* (state
game
eval-fn
&optional
limit)

Return the estimated best action, searching up to LIMIT and then applying the EVAL-FN.

**alpha-value** *function* (state
game
alpha
beta
eval-fn
limit)

**beta-value** *function* (state
game
alpha
beta
eval-fn
limit)

* In the description of a game, a player is an atomic name: X or O,*
* or BLACK or WHITE. The current state is kept as an instance of*
* GAME-STATE (which we do not expect to create subtypes of).*
* We use GAME->ENVIRONMENT to turn an instance of a game into an*
* environment, which we can then run. The function RUN-GAME*
* provides a simple interface to do this. Corresponding to player X*
* there is an agent with name X who has an agent program that*
* chooses a move for X, given a game-state as the percept.*

**game** *type* (initial-state
best
worst)

A game is defined in terms of the starting position (the initial-state), the rewards for winning and losing, and three generic functions: LEGAL-MOVES: a list of moves that can be made in this state MAKE-MOVE: generate a new state GAME-OVER?: are we finished? You provide methods for these for each new subtype of game.

**game-state** *type* (board
players
scores
terminal?
previous-move)

Everything you need to know about the state of the game. The players are given as a list of names, with the player whose move it is first. A property list keeps the scores for each player. In some games, scores are accumulated as you go, in others a score is awarded only at the end.

**legal-moves** *method* ((game
game)
state)

Return a list of legal moves

**make-move** *method* ((game
game)
state
move)

Return the new state that results from making this move.

**game-over?** *method* ((game
game)
state)

Is the game finished?

**game-environment** *type* (game)

**game->environment** *function* (game
&key
agents)

Convert a game into an environment. AGENTS can be a list of agents or agent types.

**run-game** *function* (game
&key
agents)

Build an environment around this game, and run it.

**update-fn** *method* ((env
game-environment))

**performance-measure** *method* ((env
game-environment)
agent)

Look up the agent's score in the current state.

**get-percept** *method* ((env
game-environment)
agent)

We assume all agents can perceive the whole state.

**initialize** *method* ((env
game-environment))

Install an agent program (based on the agent's algorithm slot) in each agent. The program makes sure an agent only moves when it is its turn. Also initialize the name of each agent, and the environment's state.

**termination?** *method* ((env
game-environment))

**assign-agent-scores** *function* (state
env)

**legal-move?** *function* (move
state
game)

**current-player** *function* (game-state)

**previous-player** *function* (game-state)

**game-players** *function* (game)

**current-agent** *function* (env)

**agent-with-name** *function* (name
env)

**print-structure** *method* ((game
game)
stream)

**print-structure** *method* ((state
game-state)
stream)

**display-environment** *method* ((env
game-environment))

**problem-solving-environment** *type* (problem)

An environment in which to solve problems. The state of the environment is one of the states from the problem, starting with the initial state.

**get-percept** *method* ((env
problem-solving-environment)
agent)

All agents can access the complete state of the environment.

**update-fn** *method* ((env
problem-solving-environment))

Set the state to the result of executing the agent's action.

**performance-measure** *method* ((env
problem-solving-environment)
agent)

Score of 1 for solving problem; 0 otherwise.

**initialize** *method* ((env
problem-solving-environment))

Get the initial state from the problem, and supply agents with programs.

**problem-solving-program** *function* (search-algorithm
problem)

Given a search algorithm, return a program that at the start searches for a solution, then executes the steps of the solution, then stops.

**termination?** *method* ((env
problem-solving-environment))

Stop when the problem is solved, or when an agent says stop.

**problem->environment** *function* (problem
&key
algorithm)

Convert a problem into an environment. Then we can pass the environment to RUN-ENVIRONMENT, and the agent will search for a solution and execute it.

**print-structure** *method* ((env
problem-solving-environment)
stream)

**cannibal-problem** *type* nil

The problem is to move M missionaries and C cannibals from one side of a river to another, using B boats that holds at most two people each, in such a way that the cannibals never outnumber the missionaries in any one place. See [p 68].

**goal-test** *method* ((problem
cannibal-problem)
state)

The goal is to have no missionaries or cannibals left on the first side.

**successors** *method* ((problem
cannibal-problem)
state)

Return a list of (action . state) pairs. An action is a triple of the form (delta-m delta-c delta-b), where a positive delta means to move from side 1 to side 2; negative is the opposite. For example, the action (1 0 1) means move one missionary and 1 boat from side 1 to side 2.

**cannibal-state** *type* (m1
c1
b1
m2
c2
b2)

The state says how many missionaries, cannibals, and boats on each side. The components m1,c1,b1 stand for the number of missionaries, cannibals and boats, respectively, on the first side of the river. The components m2,c2,b2 are for the other side of the river.

**take-the-boat** *function* (state
action)

Move a certain number of missionaries, cannibals, and boats (if possible).

**cannibals-can-eat?** *function* (state)

The cannibals feast if they outnumber the missionaries on either side.

**ttt-game** *type* (n
k)

Define an NxN tic-tac-toe game in which the object is to get K in a row.

**make-ttt-game** *function* (&key
n
k
players)

Define an NxN tic-tac-toe game in which the object is to get K in a row.

**legal-moves** *method* ((game
ttt-game)
state)

List all possible legal moves.

**make-move** *method* ((game
ttt-game)
state
move)

Return the new state that results from making this move.

**game-over?** *method* ((game
ttt-game)
state)

Checks if the last player to move made a complete row, column, or diagonal of length k, or if the board is full. If so, assign scores and return true; otherwise return nil.

**check-k-in-a-row** *function* (board
x
y
n
k
dx
dy
player)

Does player have k in a row, through (x y) in direction (+/-dx +/-dy)?

**count-pieces-in-direction** *function* (board
x
y
n
dx
dy
player)

Count player's pieces starting at (x y) going in direction (dx dy).

**cognac-game** *type* nil

Define an NxN tic-tac-toe-like game. The object is to get K in a row.

**make-cognac-game** *function* (&key
n
k
players)

Define an NxN Cognac game in which the object is to get K in a row.

**legal-moves** *method* ((game
cognac-game)
state)

List all possible legal moves. Like tic-tac-toe, except in each column you can only move to the lowest unoccupied square.

**nqueens-problem** *type* (n
explicit?)

**make-nqueens-problem** *function* (&rest
args
&key
n
explicit?)

**nqueens-initial-state** *function* (n
&optional
explicit?
complete?)

**nqueens-constraints** *function* (n)

**nqueens-constraint-fn** *function* (var1
val1
var2
val2)

**path-planning-problem** *type* (scene)

A problem involving moving among polygonal obstacles in 2D space. A state is the current vertex.

**make-path-planning-problem** *function* (&key
scene)

Define a constructor to build a problem, using the scene properly.

**successors** *method* ((problem
path-planning-problem)
v1)

Return a list of (action . state) pairs, where the state is another vertex that is visible from the current vertex v1, and the action is a delta (dx dy) from v1 to the new one.

**edge-cost** *method* ((problem
path-planning-problem)
node
action
vertex)

The cost of an action is its distance.

**h-cost** *method* ((problem
path-planning-problem)
vertex)

The heuristic cost is the straight-line distance to the goal.

**vertex** *type* (xy
c-neighbor
a-neighbor
visible)

**print-structure** *method* ((v
vertex)
stream)

**line** *type* (xy1
xy2)

**polygon** *type* (vertices
n)

**scene** *type* (polygons
start
goal)

* Functions for testing whether one vertex is visible from another*

**vertices-visible-from** *function* (v1
scene)

Find all the vertices that can be seen from this vertex.

**vertices-in-view** *function* (v
scene)

Find all the other vertices that can be seen from v.

**visible-p** *function* (xy1
xy2
scene)

Predicate; return t iff xy1 is visible from xy2.

**line-intersects-poly?** *function* (line
poly)

Predicate; return t iff line intersects poly.

**intersects** *function* (l1
l2)

**create-scene** *function* (&key
start
goal
polygons)

START and GOAL are xy points; polygons is a list of lists of vertices.

**create-polygon** *function* (points)

***scene-4.17*** *variable*

The scene in Figure 4.17 [p 120] with 8 obstacles.

0 1 23 4 56 7 8

1 2 3 1*9^0 + 2*9^1 + 3*9^28 . 4 is represented by: + 8*9^3 + 0*9^4 + 4*9^57 6 5 + 7*9^6 + 6*9^7 + 5*9^8 = 247893796

***8-puzzle-goal*** *variable*

To be defined later

**8-puzzle-problem** *type* nil

The sliding tile problem known as the 8-puzzle.

**successors** *method* ((problem
8-puzzle-problem)
state)

Generate the possible moves from an 8-puzzle state.

**h-cost** *method* ((problem
8-puzzle-problem)
state)

Manhatten, or sum of city block distances. This is h_2 on [p 102].

**move-blank** *function* (state
from
to)

Move the blank from one square to another and return the resulting state. The FROM square must contain the blank; this is not checked.

**blank-square** *function* (state)

Find the number of the square where the blank is.

**random-8-puzzle-state** *function* (&optional
num-moves
state)

Return a random state of the 8 puzzle.

**random-move-blank** *function* (state)

Return a state derived from this one by a random move.

**neighbors** *function* (square)

The squares that can be reached from a given square.

**8-puzzle-legal-moves** *function* (square)

The moves that can be made when the blank is in a given square. This is a list of (direction destination-square) pairs.

**8-puzzle-location** *function* (square)

Return the (x y) location of a square number.

**8-puzzle-state** *function* (&rest
pieces)

Define a new state with the specified tiles.

**8-puzzle-ref** *function* (state
square)

Return the tile that occupies the given square.

**8-puzzle-print** *function* (state
&optional
stream)

**8-puzzle-display-fn** *function* (node
problem)

***8-puzzle-goal-locations*** *variable*

A vector indexed by tile numbers, saying where the tile should be.

**use-8-puzzle-goal** *function* (goal)

Define a new goal for the 8 puzzle.

**8-puzzle-goal-location** *function* (tile)

Return the location where the tile should go.

**9-power** *function* (n)

Raise 9 to the nth power, 0 <= n <= 9.

**misplaced-tiles** *function* (state)

Number of misplaced tiles. This is h_1 on [p 102].

**misplaced-tile?** *function* (state
square)

Is the tile in SQUARE different from the corresponding goal tile? Don't count the blank.

**route-finding-problem** *type* (map)

The problem of finding a route from one city to another on a map. By default it is a random map. A state in a route-finding problem is just the name of the current city. Note that a more complicated version of this problem would augment the state with considerations of time, gas used, wear on car, tolls to pay, etc.

**successors** *method* ((problem
route-finding-problem)
city-name)

Return a list of (action . new-state) pairs. In this case, the action and the new state are both the name of the city.

**edge-cost** *method* ((problem
route-finding-problem)
node
action
city)

The edge-cost is the road distance to the next city.

**h-cost** *method* ((problem
route-finding-problem)
city-name)

The heuristic cost is the straight-line distance to the goal.

**city** *type* (name
loc
neighbors)

A city's loc (location) is an (x y) pair. The neighbors slot holds a list of (city-name . distance-along-road) pairs. Be careful to distinguish between a city name and a city structure.

**road-distance** *function* (city1
city-name2)

The distance along the road between two cities. The first is a city structure, the second just the name of the intended destination.

**straight-distance** *function* (city1
city2)

Distance between two cities on a straight line (as the crow flies).

**find-city** *function* (name
map)

Look up the city on the map, and return its information.

**random-route-map** *function* (&key
n-cities
width
height
min-roads
max-roads)

Return a random map with n-cities in it, and some roads between them. Each city is connected to between MIN-ROADS and MAX-ROADS other cities. The default is from 2 to 5. The road between any two cities has a length of 1 to 1.5 times the straight-line distance between them.

**build-road** *function* (city1
city2)

Construct a road between two cities.

**number->name** *function* (i)

Turn an integer into a symbol. 1-26 go to A-Z; beyond that use Ci

***romania-map*** *variable*

A representation of the map in Figure 4.2 [p 95]. But note that the straight-line distances to Bucharest are NOT the same.

**romanian-problem** *type* nil

A route-finding problem on the Romania map, with random start and goal.

* Note: the TSP is NP complete in the general case, but there are some good*
* algorithms for finding approximate solutions, particularly when the*
* triangle inequality is satisfied (that the path from A->C is always*
* shorter than A->B->C). Many of these algorithms are based on the idea of*
* building a minimum spanning tree, converting it into a tour, and perhaps*
* modifying it. We don't go into that here (because we are more interested*
* in hooking up to the general search procedures than in special-purpose*
* algorithms), but note that our tsp-h heuristic function is a relaxed*
* version of a minimum spanning tree.*

**tsp-problem** *type* (map)

**make-tsp-problem** *function* (&key
map
start)

Constructor for TSP problems. The map must be a complete graph.

**edge-cost** *method* ((problem
tsp-problem)
node
action
state)

**h-cost** *method* ((problem
tsp-problem)
state)

A lower bound on the cost is the distance to ???

**successors** *method* ((problem
tsp-problem)
state)

Return a list of (action . state) pairs. Actions are just the name of the city to go to. You can only go to a city you haven't visited yet, unless you've visited them all, in which case you can only go back home.

**goal-test** *method* ((problem
tsp-problem)
state)

The goal is to leave no unvisited cities and get back to start.

**tsp** *type* (visited
to-visit)

A state for a TSP problem lists cities visited, and remaining to see.

**nearest-neighbor-distance** *function* (name
candidate-names
map)

Find among the CANDIDATE-NAMES of cities, the one that is closest to city NAME, and return the distance to it.

**path-lower-bound** *function* (city-names
map)

Find a lower bound for a path through these cities.

**random-tsp-map** *function* (&key
n-cities)

**check-tsp-map?** *function* (map)

**tsp-city-name** *function* (tsp-state)

The current city: the last one visited.

**tsp-start** *function* (tsp-state)

**vacuum-state** *type* (orientation
dirt
m
n
on
location)

***vacuum-home*** *variable*

**vacuum-problem** *function* (m
n
&optional
dirt
dirt-probability)

Create a Vacuum World problem.

**vacuum-initial-state** *function* (m
n
dirt
dirt-probability)

**vacuum-goalp** *function* (state)

Is this a goal state?

**vacuum-successors** *function* (state)

Return a list of (action . state) pairs.

**problem-solving-agent** *type* (algorithm)

An agent that applies a search algorithm to a problem to find a solution, and then follows the steps of the solution, one at a time, and then stops.

**game-agent** *type* (algorithm)

An agent that plays n-player games. The ALGORITHM slot is filled by a function that takes state and game arguments, and returns a move.

**random-game-agent** *type* nil

A game-playing agent that picks randomly from the legal moves.

**human-game-agent** *type* nil

A game-playing agent that asks the human user what to do.

**pick-random-move** *function* (state
game)

**ask-game-user** *function* (state
game)

**alpha-beta-ttt-agent** *type* nil

A game-playing agent that uses ttt-eval to do alpha-beta search.

**ttt-eval** *function* (state)

Evaluate a TTT board on a scale from -1 to +1.

AIMA Home | Authors | Lisp Code | AI Programming | Instructors Pages |