Define Transposition Table.
A hash-table of the evaluations for previous board states.
Define Quiescence Search.
A procedure to look for situations where no captures are imminent.
Define Alpha-Beta Pruning.
A procedure that returns the same move as MiniMax, but with efficiency benefits.
Define Weighted Linear Function.
Vector dot product of a weight vector and a state feature vector.
Define Terminal Test.
Function that indicates when the game is over.
Define Game Tree.
Tree where nodes are board game positions and edges are game moves.
Define The Perfect Opponent Assumption.
Assumes each player in a 2-player deterministic game will play to the best of their ability.
Define Mini-Max.
Optimal strategy for 2-player zero-sum games of perfect information, but impractical given limited time to make each move.
Define Heuristic Evaluation Function.
Approximates the value of a board state.
Define Dynamic Move Ordering.
Improves the effectiveness of alpha-beta pruning when it’s possible.
Define ply.
A move taken by a single player.
Define random-restart hill-climbing.
Repeated hill-climbing searches from randomly generated initial states until the goal state is reached.
Define Shoulder.
A plateau region in the state space landscape which has an uphill ascent.
Define Simulated Annealing.
A local search algorithm that accepts “downhill moves”, with a probability that decreases during the search.
Define Steepest Ascent Hill Climbing.
Considers multiple neighbouring states and selects the one that gives the best result.
Define Global Maximum.
The best possible state of a state space landscape with the highest value for the objective function.
Define The State Neighbourhood.
The neighbouring states for a given state (i.e., the current state).
Define The Ridge Problem.
A problem associated with Hill-Climbing.
Define The Travelling Salesman Problem.
An NP-hard touring problem in which each city must be visited exactly once.
Define Stochastic Hill Climbing.
Selects at random from uphill moves. The probability of selection varies with the steepness of the uphill move.
Define Annealing Schedule.
This pre-defines how a temperature parameter is set to decrease during the execution of an SA algorithm.
Define Local Search.
Iterative improvement algorithms that keep track of a single current state and try to improve it. Often used for optimisation problems where the path taken is irrelevant.
Define Genetic Algorithm.
A variant of stochastic beam search in which successor states are generated by combining two parent states, rather than modifying a single state.
Define The Objective Function.
A numerical measure of the quality of a state in the search space of a combinatorial optimisation problem.
