AI 2

What is the minimax value of a node in a two-player zero-sum game?

The minimax value is the best guaranteed outcome assuming both players play optimally. MAX nodes take the maximum of children, and MIN nodes take the minimum.

How does the minimax algorithm work?

It recursively explores the game tree, alternating between maximizing and minimizing layers, and backs up utility values from the leaves.

What is alpha-beta pruning?

An optimization of minimax that eliminates and skips branches that cannot affect the final decision using alpha (best for MAX) and beta (best for MIN).

When can alpha-beta pruning occur?

When α ≥ β, meaning the current branch cannot improve the outcome.

What is Monte-Carlo Tree Search (MCTS)?

An algorithm that uses random simulations to estimate the best move through selection, expansion, simulation, and backpropagation.

What is expectiminimax?

An extension of minimax that handles chance nodes by taking expected values (averages based on probabilities).

What does “valid” mean in logic?

it is true in all possible models.

What’s an example of valid

P ∨ ¬P

What does “satisfiable” mean?

It is true in at least one model.

What’s an example of “satisfiable”

A∨B

What does “unsatisfiable” mean?

It is false in all models.

What’s an example of unsatisfiable

A∧¬A

What is propositional logic?

A system of logic using variables that can be true or false combined with logical connectives.

What is a model in propositional logic?

An assignment of true/false values to all variables.

What’s an example of a model in propositional logic

{P = True, Q = False}

What is Modus Ponens?

If P and P → Q and P are true, then Q must be true.

What’s an example of modus ponens

If it rains, ground is wet. It rained. Therefore, ground is wet.

What is forward chaining?

A data-driven inference method that starts with known facts and applies rules to derive new facts.

What’s an example of forward chaining

Knowing A and A => B, we add B to our facts

What is backward chaining?

A goal-driven method that starts with a query and works backward to see if it can be proven.

What’s an example of backward chaining?

To prove B, check if A is true and A => B exists

What is unit propagation?

If a clause has only one literal (unit clause), that literal must be assigned true.

What’s an example of unit propagation?

In (P) ∧ (¬P ∨ Q), P must be true

What is pure literal elimination?

If a variable appears only as positive or only negative, it can be assigned a value that satisfies all clauses.

What is entailment?

this means that one thing follows from another:

KB ⊨ α

Knowledge base KB entails sentence α if and only if α is true in all worlds where KB is true.

What’s an example of entailment

p |= p ∨ q

What is a Horn clause?

A disjunction of literals of which at most one is positive.

What’s an example of a horn clause

¬A ∨ ¬B ∨ C

How does forward chaining work?

Repeatedly apply inference rules to known facts until no new facts can be derived or the goal is reached.

How does model checking work?

It checks all possible truth assignments to see if a statement is always true.

How does backward chaining work?

Start with a goal and recursively break it into subgoals until known facts are reached.

How does resolution work?

It combines clauses to eliminate variables and derive new clauses until a contradiction is found.

Give an example of Modus Ponens.

If it rains → ground is wet. It rains. Therefore, the ground is wet.

Show forward chaining to prove KB ⊨ x₄:

x₁

x₃

x₁ ∧ x₂ → x₄

x₃ → x₂

x₁ and x₃ are known.

From x₃ → x₂, infer x₂, add to facts

Now {x₁, x₂} are true. We have x₁ ∧ x₂ → x₄. Since both premises are met, add x₄ to facts.

How do you translate English into propositional logic?

Example: “If it rains, the ground is wet” becomes R → W.

How do you convert A → B into CNF?

Rewrite as ¬A ∨ B.

Give an example of a branching rule for DPLL. Explain the motivation behind it.

Degree Heuristic; motivation is to reduce the search space by failing early (pruning) or satisfying the most difficult constraints first.

What is the factored representation for CSP states?

A representation using a set of variables (X₁, X₂,…), a set of domains (D₁, D₂,…), and a set of constraints defining allowed value combinations.

Give an example of factored representation for CSP

X ∈1,2,3

Y ∈1,2,3

Constraint: X ≠ Y

What is cutset conditioning?

instantiate (in all ways) a set of variables such that the remaining constraint graph is a tree

What is forward checking in CSP?

After assigning a variable, eliminate inconsistent values from neighboring domains.

What is AC-3 for enforcing arc-consistency?

More rigorous version of forward checking. It ensures that for every value in Domain(X), there is some value in Domain(Y) that satisfies the constraint. It repeats this until no more values can be deleted.

Example of forward checking.

If X = 1 and X ≠ Y, then remove 1 from Y’s domain.

How do you select an attribute for splitting in decision-tree-learning?

Use information gain; choose the attribute that reduces entropy the most

What is entropy?

A measure of impurity: H(S) = -Σ p_i log₂ p_i.

What is entropy when data is perfectly split (50/50)?

Entropy = 1.

How can overfitting be prevented in Decicion-Tree-Learning?

Pruning, limiting depth, requiring minimum samples, or cross-validation.

What does it mean for a target function to be realizable in the context of supervised learning?

The "true" relationship between inputs and outputs can be perfectly represented by the model class (e.g., a linear relationship can be represented by a linear model).

What does it mean for a target function to be nonrealizable in the context of supervised learning?

the model class is too simple to represent the true function

What does it mean for a target function to be redundant in the context of supervised learning?

Extra features that do not affect the outcome.

What is ensemble learning?

Combining multiple models to improve performance.

Give an example of ensemble learning.

Random Forest combines many decision trees and uses voting.