SearchSearch for the path to the given goal stateGraph SearchAspects to evaluate a search algorithmSearch for the goal whichoptimizes an objective functionor certain evaluation measureSearch for the current bestbased on the most difficultopponentProblem Description Turn-TakingPlayers: Two vs MultipleUtility: Zero-sum vs NotDeterministic vs StochasticPerfect information vs Partially observableResource Unlimited AlgorithmsMini Max1Alpha-Beta Prunining1Nega-Scout1Special CasesStochasticMini-max with Chance nodes1Monte Carlo Simulation1Partial observableNash Equilibrium2Multiple playersProperty of Graph Separation2IDA*1Two search paradigm3Tree SearchThree sets2Frontier set (including both visited and unvisited nodes)Visited nodesUnvisited nodesSearch AlgorithmsUniformed Searchg(n): Uniform-cost search1Discussion on heuristics2f(n)=g(n)+h(n): A* search1Informed Searchh(n)1CompletenessTime complexitySpace complexityOptimalityBreadth-first search1Depth-first search1Depth-limited search1Iterative Deepening1Uniform-cost search1Reduce space complexityUse the current minimum of f(n) as limitAdmissible heuristicsConsistent heuristicsRelaxation: heuristic dominanceSub-problemHow to generate a heuristicDiscrete space: climbing1Continuous space: gradient descent1Beam Search3Meta-heuristicsΔE←Value(next)-Value(current) Simulated Annealing1Genetic Algorithm1Resource Limited AlgorithmsEvaluation functionHorizon effectVariant of Mini-max1