Quick handwritten-style revision notes for later.
Covers the material after Beam Search: Multi-Agent Search → Minimax → Alpha-Beta → Depth-Limited Search → Game Heuristics → Expectimax → Logical Reasoning → Propositional Logic → Modus Ponens → Forward Inference → Soundness & Completeness.

---

1. Multi-Agent Search

Main idea

Before this, search was mostly:

I choose an action → I move → I keep searching

Now another agent also makes decisions:

ME → OPPONENT → ME → OPPONENT → ...

So I cannot just choose the best-looking final state. I have to think about what the other agent will do too.

Game types to remember

• Deterministic → no randomness
• Stochastic → randomness exists
• Perfect information → everyone sees the whole state
• Partial information → some information is hidden
• Zero-sum → one player’s gain is the other’s loss

For basic Minimax, we mostly think about:

2 players + deterministic + perfect information + zero-sum

---

2. Minimax

Core idea

Two players:

• MAX wants the score as large as possible
• MIN wants the score as small as possible

Golden rule

MAX node → take MAXIMUM child
MIN node → take MINIMUM child

Always solve bottom → up.

Example

              MAX
            /     \
          MIN     MIN
         /  \     /  \
        3    5   2    9

Left MIN:

min(3,5) = 3

Right MIN:

min(2,9) = 2

Root MAX:

max(3,2) = 3

So final value = 3.

My memory trick

MAX = me trying to get the biggest number
MIN = opponent trying to give me the smallest number

---

3. Why Minimax Is Expensive

If:

b = branching factor
m = depth

then the search can grow like:

1
b
b²
b³
...
b^m

Time is roughly:

O(b^m)

That gets huge very fast.

So we need Alpha-Beta Pruning.

---

4. Alpha-Beta Pruning

Main idea

Do Minimax, but stop exploring branches that cannot change the final decision.

Important:

Alpha-Beta gives the same root Minimax result. It just avoids useless work.

Alpha and Beta

α (alpha) = MAX's best value so far
β (beta)  = MIN's best value so far

Prune condition

α ≥ β  → PRUNE

Simple visual

              MAX
            /     \
          MIN     MIN
         /  \     /  \
        3    5   2    X

Left MIN gives:

min(3,5)=3

So MAX already has:

α = 3

Right MIN sees first child = 2.

MIN can only stay at 2 or become even smaller.

MAX already has 3, so MAX will never choose that right branch.

X = useless → prune it

Very important

Good child ordering → more pruning
Bad child ordering  → less pruning

Alpha-Beta does not always guarantee lots of pruning.

---

5. Depth-Limited Search

Even Alpha-Beta may still be too expensive for games such as chess.

So instead of searching until the game ends:

current state
   ↓
search
   ↓
search
   ↓
CUT OFF at depth d

At the cutoff:

if terminal → use actual utility
if not terminal → use heuristic estimate

So the idea is:

“I can’t see all the way to the end, so I estimate how good this position is.”

---

6. Game Heuristics / Evaluation Function

A game heuristic estimates how good a game position is.

Example idea:

score =
+ piece advantage
+ board control
+ safety
+ mobility
...

Often it can be a weighted sum:

score = w1(feature1) + w2(feature2) + ...

Do NOT confuse with A* heuristic

A* heuristic

h(n) = estimated remaining path cost

Game heuristic

estimated quality/value of the game state

Also:

• game heuristic does not need to be admissible
• game heuristic does not need to be non-negative

---

7. Expectimax

Why do we need it?

Minimax assumes the opponent is perfectly adversarial:

MIN always chooses the worst thing for me

But sometimes the world is random:

• dice
• random ghost behavior
• imperfect human player
• action failure

Then we use Expectimax.

---

Minimax vs Expectimax

MINIMAX
MAX → maximum
MIN → minimum

EXPECTIMAX
MAX    → maximum
CHANCE → expected value

Memory trick

Minimax = worst case
Expectimax = average / expected case

---

8. Chance Nodes + Expected Value

At a chance node:

Expected Value = Σ(probability × value)

Example from lecture

8    with p = 1/2
24   with p = 1/3
-12  with p = 1/6

Then:

EV = (1/2)(8) + (1/3)(24) + (1/6)(-12)
   = 4 + 8 - 2
   = 10

So chance-node value = 10.

Important mistake to avoid

If probabilities are not equal, do not take a simple average.

Example:

90% → 2
10% → 20

Wrong:

(2+20)/2 = 11

Correct:

0.9(2) + 0.1(20) = 3.8

---

9. Expectiminimax

Sometimes we have all three:

MAX
MIN
CHANCE

Example structure:

MAX
 ↓
CHANCE
 ↓
MIN
 ↓
CHANCE

Rule:

MAX    → max
MIN    → min
CHANCE → expected value

This is useful in games with both strategic players and randomness.

---

10. Alpha-Beta with Expectimax?

For the version taught in class:

ordinary Alpha-Beta pruning → NOT used for chance nodes

Why?

Because unseen outcomes can still change the expected value.

Chance
 /   \
2     ?

The ? could be huge, so we cannot safely ignore it using ordinary Minimax pruning logic.

---

11. New Topic: Logical Reasoning

Now the course changes from:

states + actions + costs

to:

facts + formulas + inference rules

Think:

Search model → "What action should I take?"
Logic model  → "What can I conclude from what I know?"

---

12. Knowledge Base (KB)

A knowledge base is a collection of statements/formulas assumed to be true.

Example:

Rain
Rain → Wet
Wet → Slippery

From these, we can derive new facts.

---

13. Proposition

A proposition is a declarative sentence that can be True or False.

Examples:

"It is raining."      ✓ proposition
"2 + 2 = 4."          ✓ proposition

Not propositions:

"Is it raining?"      ✗ question
"Close the door!"     ✗ command
"Hello!"              ✗ greeting

We usually represent propositions using symbols:

A, B, C, Rain, Wet, Hungry

---

14. Propositional Logic Connectives

¬A      = NOT A
A ∧ B   = A AND B
A ∨ B   = A OR B
A → B   = A implies B
A ↔ B   = A if and only if B

Quick memory:

¬  not
∧  and
∨  or
→  if...then
↔  both directions / iff

---

15. Syntax

Syntax asks:

Is the formula written in a valid form?

Valid examples:

¬A
(¬B → C) ∨ A

Invalid examples:

A ∨ → ∨ B
A + B
A¬B

Memory

Syntax = FORM / STRUCTURE

It does not yet ask whether the formula is true.

---

16. Implication Reminder

This one is easy to forget:

P → Q

Truth table:

P	Q	P → Q
F	F	T
F	T	T
T	F	F
T	T	T

Only one false case:

TRUE → FALSE = FALSE

Memory trick:

The promise is broken only when P happens but Q does not.

---

17. Modus Ponens

Very important inference rule:

P
P → Q
------
Q

Example:

Rain
Rain → Wet
-----------
Wet

It works by matching the form of formulas.

---

18. Forward Inference

Idea:

Keep applying inference rules until nothing new can be added.

Example KB:

Rain
Rain → Wet
Wet → Slippery

Step 1:

Rain + Rain→Wet
→ Wet

Now KB includes Wet.

Step 2:

Wet + Wet→Slippery
→ Slippery

Final facts include:

Rain
Wet
Slippery

Then no more rules fire → converged.

My memory

known fact
   +
matching rule
   ↓
new fact
   ↓
repeat

---

19. Soundness and Completeness

Soundness

Nothing but the truth.

If the inference system derives something, it should actually follow from the KB.

No wrong conclusions.

Completeness

The whole truth.

If something really follows from the KB, the inference system should be able to derive it.

No true conclusions missing.

Easy memory

SOUND    = no garbage
COMPLETE = nothing missing

---

20. Modus Ponens: Sound or Complete?

From the lecture:

Modus Ponens is sound ✓
Modus Ponens alone is not complete ✗

Meaning:

• whatever MP derives is safe / truth-preserving
• but MP alone cannot derive every possible entailed statement

---

21. Big Picture : Everything After Beam Search

BEAM SEARCH
   ↓
MULTI-AGENT SEARCH
   ↓
MINIMAX
MAX=max, MIN=min
   ↓
ALPHA-BETA
same answer, less work
   ↓
DEPTH-LIMITED SEARCH
stop early
   ↓
GAME HEURISTIC
evaluate cutoff state
   ↓
EXPECTIMAX
MAX=max, CHANCE=ΣpV
   ↓
EXPECTIMINIMAX
MAX + MIN + CHANCE
   ↓
LOGICAL REASONING
facts + formulas + rules
   ↓
PROPOSITIONAL LOGIC
¬ ∧ ∨ → ↔
   ↓
MODUS PONENS
P, P→Q ⇒ Q
   ↓
FORWARD INFERENCE
keep deriving
   ↓
SOUNDNESS / COMPLETENESS

---

22. Super-Short Revision Box

MINIMAX
MAX → max
MIN → min

ALPHA-BETA
α = MAX best so far
β = MIN best so far
α ≥ β → prune
same root result as Minimax

DEPTH LIMIT
cut off search → use game heuristic

GAME HEURISTIC
estimate state quality
not required to be admissible

EXPECTIMAX
MAX → max
Chance → Σ p(value)

EXPECTIMINIMAX
MAX + MIN + Chance

PROPOSITION
True/False declarative sentence

CONNECTIVES
¬ not
∧ and
∨ or
→ implies
↔ iff

IMPLICATION
only T→F is false

MODUS PONENS
P
P→Q
∴Q

FORWARD INFERENCE
keep applying rules until no new facts

SOUND
no false conclusions

COMPLETE
no valid conclusions missed

MODUS PONENS
sound ✓
complete alone ✗

---

Source note

These notes are based on the course lecture material from Day 4: Multi-Agent Search and Day 5: Expectimax + Logical Reasoning, continuing from the point after Beam Search in the earlier Day 3 notes.