AI Midterm

Search algorithm

This takes a problem as an input and returns a solution or an indication of failure.

Search tree

This is commonly used to illustrate paths between states, towards a particular goal. It may contain multiple paths to any given state, but each node in the tree has a unique path back to the root.

Root

In a search tree, this corresponds to the initial state of the problem.

Nodes

In a search tree, these correspond to the states within the state space of the problem.

Edges

In a search tree, these correspond to the available actions relative to the problem.

Search data structure

This is required to keep track of the search tree.

Uninformed search

Involves algorithms that do not have any domain-specific knowledge and proceeds in a systematic way of exploring nodes in a predetermined order.

Breadth-first Search

This search process checks all the nodes per level, starting at the left working towards the right side of the tree, before searching the tree one level deeper.

Depth-first Search

The process starts at the root of the tree and down to the left branch until it gets to the bottom node. If the goal state is not reached, the process goes back up and tries the next branch.

Iterative Deepening Search

This search process combines many advantages of the depth-first and breadth-first search without storing all nodes in memory.

Bidirectional Search

It encompasses a distinctive process that simultaneously searches forward from the initial state and backwards from the goal state(s), with the anticipation that the two searches will meet.

Uniform-cost Search

This search process can be considered as a variant of the Dijkstra's algorithm where the search process spreads out in waves of uniform path-cost.

Informed search

Also known as heuristic search, involves domain-specific knowledge and allows access to additional information that improves the search process.

Best-first Search

On each iteration of this search algorithm, the node with the minimum evaluation function value is selected.

Hill Climbing Search

A search technique for finding the maximum or the minimum of an evaluation function that does not allow shifting back to previously suspended alternatives.

A* Search

The most common informed search technique that uses the evaluation function f(n) = g(n) + h(n).

Beam Search

A search technique that utilizes heuristics to trim the state space into a small number of nearly optimal alternatives based on a predetermined beam width.

Constraint Satisfaction

A search strategy that deals with constraints that are the same as the ones that can be encountered in the real world.

Game

An environment that involves a set of circumstances that can produce a particular result dependent on the actions of two or more players.

Players

These are the strategic decision-makers within the game.

Strategy

It is a complete plan of action of a player that considers the set of circumstances that may occur within the game.

Payoff

It is something quantifiable that a player can receive in arriving at a particular outcome.

Information Set

This encompasses the available information at a particular point in a game, which is commonly utilized in games that has sequential components.

Notion of Equilibrium

It is a point in a game where both players have made their decisions or moves and a particular outcome is reached.

A plausible move generator

Expands only selected moves when the number of permissible moves is too high to perform a full-width search.

A static evaluation function generator

Used to evaluate every move that is being made using heuristic knowledge.

Minimax strategy

A strategy for two player games where one player is identified as a maximizer (MAX) and the other as a minimizer (MIN).

Alpha-beta pruning

A minimax strategy with cut-offs that prunes large parts of the game tree that do not affect the outcome.

Knowledge

The body of facts, information, and skills acquired through experience or education.

Intelligence

The ability to acquire and apply knowledge and skills.

Knowledge representation

The concept of identifying ways to provide machines with the knowledge that humans possess so that AI systems can become better.

Domain-specific knowledge

Specialized knowledge required to perform a particular task.

Common sense knowledge

All other pieces of knowledge that help in reasoning other than domain-specific knowledge.

Procedural knowledge

The compiled or processed form of information related to the performance of some tasks (how to achieve something).

Declarative knowledge

Knowledge about facts and things, including logic-based and relational approaches.

Knowledge base

Contains a collection of information in a given field.

Inference engine

Acquires insights from the information housed in the knowledge base.

Knowledge representation scheme

A set of syntactic and semantic conventions used in describing various objects.

Logical representation

The most basic form of representing knowledge that uses a well-defined syntax with concrete rules.

Propositional logic

The study of propositions, where a proposition is a statement that can be either true or false.

Predicate logic

Allows complex facts about the world to be represented using predicates that depend on the value of variables.

Semantic or associative network

A structure that represents knowledge as a pattern of interconnected nodes and arcs.

Frame

A collection of attributes and associated values which describes an entity in the real world, consisting of slots and their values.

Production rules

Consist of condition-action pairs or if-then statements.