Problem-Solving with AI
Getachew Mamo (Ph.D.)
November 16, 2025
Getachew M. Problem Solving November 16, 2025 1 / 40
Table of contents
1 Search Strategies and Problem-Solving Methods
2 AI Approaches to Solving Real-World Problems
3 Search in Games and Strategic Decision-Making
Getachew M. Problem Solving November 16, 2025 2 / 40
What is AI Problem Solving?
Many real-world problems can be formulated as search problems
Requires defining:
Alternative choices
Their consequences
Goal states
Examples: Navigation, game playing, puzzle solving
Key Insight
The first stage - defining choices and consequences - is often the most
challenging part and requires careful thinking.
Getachew M. Problem Solving November 16, 2025 3 / 40
Real-World Example: Navigation
Getting from point A to B using public
transport
Similar problems solved by:
Self-driving cars
Game-playing AI (chess, etc.)
Delivery route optimization
Figure: Navigation app solving
route finding
Getachew M. Problem Solving November 16, 2025 4 / 40
Multiple Paths to Solution
Path 2
Path 1
Start Goal
Path 3
Path 4
Figure: Multiple paths can lead to the same goal
Different solutions may vary in:
Time efficiency
Cost effectiveness
Resource usage
Reliability
Advanced search algorithms help find optimal paths
Getachew M. Problem Solving November 16, 2025 5 / 40
Two Main Problem Categories
Category 1: Single-Agent Planning
Static environments
Only one ”agent” making decisions
Examples: Navigation, puzzle solving
Focus: Find optimal sequence of actions
Category 2: Two-Player Games
Competitive environments
Two ”agents” competing against each other
Examples: Chess, checkers, Go
Focus: Strategic decision making considering opponent’s moves
Getachew M. Problem Solving November 16, 2025 6 / 40
Toy Problem: Chicken Crossing
Scenario: Robot must transport fox,
chicken, and chicken-feed across river
Constraints:
Fox eats chicken if left alone together
Chicken eats chicken-feed if left alone
together
Robot can prevent eating when
present Figure: Chicken crossing puzzle
Boat fits robot + 2 items setup
Getachew M. Problem Solving November 16, 2025 7 / 40
State Representation
Five movable objects: Robot, Boat, Fox, Chicken, Chicken-feed
Boat always with robot → 4 independent items
Each can be on Near (N) or Far (F) side
Total possible states: 24 = 16 combinations
State Notation
NNNN: All on near side
FFFF: All on far side (goal)
NFNF: Robot near, Fox far, Chicken near, Feed far
Getachew M. Problem Solving November 16, 2025 8 / 40
Valid States Analysis
State Robot Fox Chicken Feed
NNNN Near Near Near Near
NNNF Near Near Near Far
NNFN Near Near Far Near
NFNN Near Far Near Near
NFNF Near Far Near Far
FNFN Far Near Far Near
FNFF Far Near Far Far
FFNF Far Far Near Far
FFFN Far Far Far Near
FFFF Far Far Far Far
Table: Valid states after removing forbidden configurations
Forbidden States
States where fox-chicken or chicken-feed are left alone together: NFFN,
NFFF, FNNF, FNNN, NNFF, FFNN
Getachew M. Problem Solving November 16, 2025 9 / 40
State Transition Diagram
NNNN NNNF NNFN NFNN NFNF
FNFN FNFF FFNF FFFN FFFF
Figure: State transition diagram for chicken crossing
Getachew M. Problem Solving November 16, 2025 10 / 40
Solution Path
NNNN NNNF NNFN NFNN NFNF
FNFN FNFF FFNF FFFN FFFF
Figure: Optimal solution path highlighted
Getachew M. Problem Solving November 16, 2025 11 / 40
Solution
Solution Sequence
NNNN → FFFN → NFNN → FFFF
Take fox and chicken to far side
Bring chicken back to near side
Take chicken and feed to far side
Getachew M. Problem Solving November 16, 2025 12 / 40
Key Terminology
State Space
The set of all possible situations or configurations in a problem
Example: 10 valid states in chicken crossing
Navigation: All reachable locations from starting point
Transitions
Possible moves between states with a single action
Direct moves only (no multi-step sequences)
Can be symmetric or directional
Costs
Measures associated with transitions
Distance, time, resources, risk
Used to find optimal solutions
Getachew M. Problem Solving November 16, 2025 13 / 40
Problem Solving Process
1 Define State Space
Identify all possible configurations
Remove invalid/forbidden states
2 Identify Transitions
Determine possible moves between states
Assign costs if applicable
3 Define Goal State
Clear criteria for solution
4 Find Path
Use search algorithms
Consider optimality criteria
Getachew M. Problem Solving November 16, 2025 14 / 40
Table of contents
1 Search Strategies and Problem-Solving Methods
2 AI Approaches to Solving Real-World Problems
3 Search in Games and Strategic Decision-Making
Getachew M. Problem Solving November 16, 2025 15 / 40
The Origins of AI
AI’s Deep Roots
Artificial Intelligence is arguably as old as computer science itself. The
concept of automatic reasoning and intelligence predates modern
computers.
Early thinkers: Alan Turing, John McCarthy
Fundamental question: Can thinking be automated?
Turing’s insight: Computation = Automated reasoning
Getachew M. Problem Solving November 16, 2025 16 / 40
Alan Turing’s Contributions
Turing Machine (1936): Theoretical
model of computation
Programmable Computers: Same
hardware, different tasks
WWII Codebreaking: Practical
application at Bletchley Park
Turing Test (1950): Operational Theoretical Turing Machine
definition of intelligence
Getachew M. Problem Solving November 16, 2025 17 / 40
Example: Turing Machine Concept
Simple Turing Machine for Addition
Input: Two numbers in unary (e.g., 3 = 111, 2 = 11)
Tape: 111011 (3 + 2 separated by 0)
Rules: Replace 0 with 1, then remove last 1
Output: 11111 (5 in unary)
Read/Write Head
Move Left Move Right
Current Cell
0=3011=3012=3013=3014=3015=3016=3017=301
Tape Cells (Memory Storage)
Getachew M. Problem Solving November 16, 2025 18 / 40
Birth of Modern AI: 1956 Dartmouth Conference
John McCarthy’s Conjecture
“The study is to proceed on the basis of the conjecture that every aspect
of learning or any other feature of intelligence can in principle be so
precisely described that a machine can be made to simulate it.”
Father of AI: Coined term ”Artificial Intelligence”
Key Insight: Intelligence can be broken into mechanical steps
Philosophical Stance: Bypasses Chinese Room objections
Getachew M. Problem Solving November 16, 2025 19 / 40
Games as AI Testbeds
Why games became central to AI:
Well-defined rules and objectives
Controlled, restricted domains
Clear success metrics
Progressive complexity
AI
Game Progression
Getachew M. Problem Solving November 16, 2025 20 / 40
Historical AI Game Milestones
Game Year Significance
Checkers 1950s First board game AI
Chess 1997 Deep Blue beats Kasparov
Go 2016 AlphaGo defeats Lee Sedol
Poker 2017 Libratus beats professionals
Complexity Comparison
Chess: ≈ 1047 possible games
Go: ≈ 10170 possible games
Poker: Imperfect information challenge
Getachew M. Problem Solving November 16, 2025 21 / 40
Search in AI Problems
Search as Fundamental AI Technique
Many AI problems can be framed as search problems:
Finding optimal paths
Game move selection
Planning sequences of actions
Constraint satisfaction
Example
Route Planning:
States: Locations on map
Actions: Move between connected locations
Goal: Find shortest path from A to B
Getachew M. Problem Solving November 16, 2025 22 / 40
Example: Simple Pathfinding Problem
4
A B
1 2
C D E
3 2
Possible paths:
Problem: Find shortest path A→E A-B-D-E: 8
A-C-D-E: 6 ← Optimal
Getachew M. Problem Solving November 16, 2025 23 / 40
Minimax Algorithm
Game Theory Foundation
Two-player zero-sum games
Assumption: Opponent plays optimally
Goal: Maximize minimum guaranteed outcome
Example
Tic-Tac-Toe:
MAX player (X), MIN player (O)
Build game tree of possible moves
Propagate values from terminal states
Getachew M. Problem Solving November 16, 2025 24 / 40
Minimax Example
Max
3 1 4
Min Min Min
3 5 2 8 1 7 4 6
Minimax Calculation:
Min nodes choose minimum of children: Min1 = min(3,5,2) = 2
Min2 = min(8,1) = 1
Min3 = min(7,4,6) = 4
Root (Max) chooses maximum: max(2,1,4) = 4
Getachew M. Problem Solving November 16, 2025 25 / 40
Alpha-Beta Pruning
Optimizing Minimax
Alpha: Best already explored option for MAX
Beta: Best already explored option for MIN
Prune branches that cannot affect final decision
Example
Efficiency Gain:
Without pruning: Search entire game tree
With pruning: Skip irrelevant branches
Can double search depth in same time
Getachew M. Problem Solving November 16, 2025 26 / 40
Alpha-Beta Pruning Example
max(5,4)=5
MAX
α=-
β=+
min(5,6)=5 min(7,4)=4
MIN MIN
α=- α=-
β=+ β=+
PRUNED
5 6 7 5 No need to
4
evaluate
Getachew M. Problem Solving November 16, 2025 27 / 40
Alpha-Beta Pruning Example ...
Explanation:
Blue circles = MAX nodes (try to maximize score)
Red circles = MIN nodes (try to minimize score)
Green squares = Terminal nodes (final scores)
Red dashed line = Pruned branch (not evaluated)
After MIN node A returns 5, and MIN node B finds value 4, the third
branch (B3) is pruned because it cannot give a better value for MAX
After evaluating A1=5, A2=6: MIN(A)=5
After B1=7: MIN will be 7
After B2=4: MIN(B)4, which is worse than MIN(A)=5
B3 can be pruned - won’t affect MAX’s decision
Getachew M. Problem Solving November 16, 2025 28 / 40
From Classic Search to Modern AI
Evolution of Search Techniques
1950s-60s: Basic search algorithms
1970s-80s: Heuristic search, planning
1990s-2000s: Machine learning integration
2010s-present: Deep learning, reinforcement learning
Example
AlphaGo (2016):
Combines Monte Carlo Tree Search with neural networks
Learned from human games and self-play
Defeated world champion Lee Sedol 4-1
Getachew M. Problem Solving November 16, 2025 29 / 40
Real-World Applications
Planning & Scheduling: Game-Based Research:
Logistics and delivery routes Autonomous vehicles
Manufacturing processes Robotics navigation
Project management Cybersecurity
Resource allocation Drug discovery
Fundamental Principle
The same search concepts that power game AI underlie many practical
optimization and decision-making systems.
Getachew M. Problem Solving November 16, 2025 30 / 40
Table of contents
1 Search Strategies and Problem-Solving Methods
2 AI Approaches to Solving Real-World Problems
3 Search in Games and Strategic Decision-Making
Getachew M. Problem Solving November 16, 2025 31 / 40
The Game Scenario
We focus on two-player, perfect-information games.
Examples: Tic-Tac-Toe, Chess, Checkers, Go.
Players: Max (Maxine) and Min (Minnie).
Max aims to maximize the score.
Min aims to minimize the score.
O O
X X
O
The Puzzle: Why is Max (X) in despair? Min is about to get three O’s
on the top row, but Max can easily block it. Is there a deeper reason?
Getachew M. Problem Solving November 16, 2025 32 / 40
What is a Game Tree?
A game tree is a directed graph representing all possible game states.
The root node is the initial state (e.g., empty board).
Child nodes are states reachable by a legal move.
Leaf nodes are terminal states (win, lose, or draw).
Root
Child 1 Child 3
Leaf Child 2 Leaf
Leaf Leaf
Getachew M. Problem Solving November 16, 2025 33 / 40
Assigning Values to Outcomes
We assign numerical values to game outcomes:
Max wins: Value = +1
Min wins: Value = -1
Draw: Value = 0
Key Idea:
At Max’s turn, choose the move that maximizes the value.
At Min’s turn, choose the move that minimizes the value.
Getachew M. Problem Solving November 16, 2025 34 / 40
Sample Game Tree Analysis
1
Min
2 4
Max 3 Max
Max
5 6 7 8 9 10
Min Min Min Min Min Min
11 12 13 14 15 16 17 18
-1 -1 +1 -1 +1 -1 +1 -1
Colors: Orange = Min’s turn, Blue = Max’s turn, Green/Red =
Terminal state (Win/Loss for Max).
Goal: Min minimizes the score, Max maximizes it.
The optimal move for Min at the root (Node 1) is to choose Node 3
or 4, which guarantee a minimum score of -1, avoiding the +1
outcome
Getachew [Link] from Node 2. Solving
Problem November 16, 2025 35 / 40
Getachew M. Problem Solving November 16, 2025 36 / 40
Minimax Value Propagation
Step-by-step evaluation:
Level 2: Min nodes take the minimum of their leaf children
Node 5: min(−1, −1) = −1
Node 6: min(+1, −1) = −1
Node 7: min(+1, −1) = −1
Node 8: min(+1, −1) = −1
Node 9: min(+1, −1) = −1
Node 10: min(+1, −1) = −1
Level 1: Max nodes take the maximum of Min children
Node 2: max(−1, −1) = −1
Node 3: max(−1, −1) = −1
Node 4: max(−1, −1) = −1
Root (Node 1, Min):
min(−1, −1, −1) = −1
Final Result
Game Value = −1 ⇒ Min has advantage
Getachew M. Problem Solving November 16, 2025 36 / 40
The Minimax Algorithm
Minimax Principle
Max nodes: Choose the child with the maximum value.
Min nodes: Choose the child with the minimum value.
Algorithm Pseudocode
1 if maximizingPlayer: value = - for each child of node: value =
max(value, minimax(child, depth-1, False)) return value else:
value = + for each child of node: value = min(value,
minimax(child, depth-1, True)) return value
2
Getachew M. Problem Solving November 16, 2025 37 / 40
The Problem: Massive Game Trees
Game Branching Factor Nodes after 10 moves
Tic-Tac-Toe ≈4 ≈ 1 million
Chess ≈ 35 ≈ 2.7 quadrillion
Go ≈ 250 ≈ 1024
The Combinatorial Explosion
Chess: 3510 ≈ 2.7 × 1015 nodes
Go: 25010 ≈ 9.5 × 1023 nodes
Impossible to search entire trees for complex games!
Getachew M. Problem Solving November 16, 2025 38 / 40
Solutions for Massive Trees
Depth-Limited Search
Stop search at certain depth
Use heuristic evaluation function to estimate position value
Chess Heuristics Example
Material: Queen=9, Rook=5, Bishop=3, Knight=3, Pawn=1
Position: Control center squares
King safety: Keep king protected
Mobility: Number of legal moves
Real-World Success
IBM’s Deep Blue (1997) used depth-limited Minimax with
sophisticated heuristics
Defeated world champion Garry Kasparov
Getachew M. Problem Solving November 16, 2025 39 / 40
Exercise: Analyze the Original Position
O O X
X X
Given:
Max (X) must block top row → places X in top-right
Now it’s Min’s (O) turn
Build game tree from this position
Apply Minimax to find game value
Possible answers: +1 (Max wins), -1 (Min wins), 0 (Draw)
Getachew M. Problem Solving November 16, 2025 40 / 40