Introduction to
Artificial Intelligence
Chapter 2: Solving Problems
by Searching (4)
Heuristic Functions
Nguyễn Hải Minh, Ph.D
nhminh@fit.hcmus.edu.vn
Outline
1. The 8-puzzle problem
2. Relaxed problems
3. Pattern databases
4. Learning heuristics from
experience
7/12/2020 Nguyễn Hải Minh @ FIT 2
The (n2-1)-Puzzle problem
❑Slide the tiles horizontally or vertically into the empty
space until the configuration matches the goal state
❑States in (n2-1)-Puzzle problem: (n2)!/2
o 181,440 possible states for 8-Puzzle
o 1.05 x 1013 possible states for 15-Puzzle
7/12/2020 Nguyễn Hải Minh @ FIT 3
The 8-puzzle
❑One of the earliest heuristic problems
❑Average solution cost:
o 22 steps
o𝑏≈3
o A graph search: exhaustive search about 170k
states (see HW 3.4)
❑How about 15-puzzle?
o About 1013 states
→Need a good heuristic to find the shortest
solutions
→Never overestimates the number of steps to the
goal
7/12/2020 Nguyễn Hải Minh @ FIT 4
The 8-puzzle heuristics
❑Admissible heuristic: ℎ 𝑛 ≤ ℎ∗ (𝑛)
❑Which of the following heuristics is admissible?
• ℎ1 (𝑛) = total number of misplaced tiles
• ℎ2 (𝑛) = total Manhattan distance
• ℎ3 𝑛 = 0
• ℎ4 𝑛 = 1
• ℎ5 (𝑛) = ℎ∗ (𝑛)
• ℎ6 (𝑛) = min(2, ℎ∗ (𝑛))
• ℎ7 (𝑛) = max(2, ℎ∗ (𝑛))
7/12/2020 Nguyễn Hải Minh @ FIT 5
The 8-puzzle: Admissible heuristics
oℎ1(𝑆) = 8
oℎ2 𝑆 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18
→ True solution cost: ℎ∗ 𝑆 = 26
7/12/2020 Nguyễn Hải Minh @ FIT 6
Effective branching factor b*
❑The branching factor that an uniform tree of
depth d would have in order to contain N+1
nodes
∗ ∗2 ∗𝑑
𝑁+1=1+𝑏 +𝑏 + ⋯+ 𝑏
❑Measure is fairly constant for sufficiently hard
problems.
o Can thus provide a good guide to the heuristic’s
overall usefulness.
o A well-designed heuristic would have a value of b*
close to 1
7/12/2020 Nguyễn Hải Minh @ FIT 7
Search costs vs branching factors
7/12/2020 Nguyễn Hải Minh @ FIT 8
Dominance
❑If h2(n) ≥ h1(n) for all n (both admissible) then h2
dominates h1
o h2 is better for search
❑Typical search costs (average number of nodes
expanded):
➢ d=12 IDS = 3,644,035 nodes
A*(h1) = 227 nodes
A*(h2) = 73 nodes
➢ d=24 IDS = too many nodes
A*(h1) = 39,135 nodes
A*(h2) = 1,641 nodes
7/12/2020 Nguyễn Hải Minh @ FIT 9
Relaxed problems
❑A problem with fewer restrictions on the actions is called
a relaxed problem
❑The cost of an optimal solution to a relaxed problem is an
admissible heuristic for the original problem
n
Relaxed problem state-space
Original problem
S
state-space
Relaxed problems
❑Original problem:
o A tile canmove from square A to square B if A is horizontally or
vertically adjacent to B and B is blank
❑Relaxed problem:
a) A tile can move from square A to square B if A is adjacent to B.
b) A tile can move from square A to square B if B is blank.
c) A tile can move from square A to square B. Manhattan
distance
Misplaced
tiles
it is crucial that the relaxed problems generated by this technique can be
solved essentially without search
Relaxed problems
❑A collection of admissible heuristics: h1, h2, …, hm
→Composite heuristic function:
ℎ 𝑛 = max{ℎ1 𝑛 , ℎ2 (𝑛),…, ℎ𝑚 (𝑛)}
→ It is easy to prove that h is consistent. Furthermore, h
dominates all of its component heuristics
Pattern database
❑A subproblem of the 8-puzzle instance
❑Solution cost of this subproblem ≤ real cost of the
original problem
o Some cases, it is more accurate than Manhattan
distance
7/12/2020 Nguyễn Hải Minh @ FIT 13
Pattern database
❑Admissible heuristics can also be derived from
the solution cost of a subproblem of a given
problem.
❑This cost is a lower bound on the cost of the real
problem.
❑Idea of pattern databases:
o Store the exact solution costs for every possible
subproblem instance.
o The complete heuristic is constructed using the
patterns in the databases
7/12/2020 Nguyễn Hải Minh @ FIT 14
Heuristic from PDB
31 moves is a lower bound on the total number of moves
needed to solve this particular state
https://courses.cs.washington.edu/courses/cse473/12sp/slides/04-heuristics.pdf
7/12/2020 Nguyễn Hải Minh @ FIT 15
Heuristic from PDB
31 moves needed to solve red tiles
22 moves needed to solve blue tiles
→ Overall heuristic is maximum of 31 moves
https://courses.cs.washington.edu/courses/cse473/12sp/slides/04-heuristics.pdf
7/12/2020 Nguyễn Hải Minh @ FIT 16
Additive Pattern Databases
❑Count only moves of the pattern tiles, ignoring non-
pattern moves.
o If no tile belongs to more than one pattern, then we can
add their heuristic values.
o Manhattan distance is a special case of this, where each
pattern contains a single tile.
→Disjoint Pattern Databases
o The 7-tile database contains 58 million entries.
o The 8-tile database contains 519 million entries.
7/12/2020 Nguyễn Hải Minh @ FIT 17
Additive Pattern Databases
20 moves needed to solve red tiles
25 moves needed to solve blue tiles
→ Overall heuristic is 20+25=45 moves
7/12/2020 Nguyễn Hải Minh @ FIT 18
Performance
❑15 Puzzle:
o 2000x speedup vs Manhattan distance
o IDA* with the two DBs solves 15 Puzzles
optimally in 30 milliseconds
❑24 Puzzle:
o 12 million x speedup vs Manhattan
o IDA* can solve random instances in 2 days.
o Requires 4 DBs as shown
o Each DB has 128 million entries
o Without PDBs: 65,000 years
7/12/2020 Nguyễn Hải Minh @ FIT 19
Learning heuristics from experience
❑Experience means:
o e.g, solving lots of 8-puzzles
o Each optimal solution to an 8-puzzle problem
provides examples from which h(n) can be learned
❑Learning algorithms:
o Neural nets
o Decision trees
o Inductive learning
o …
7/12/2020 Nguyễn Hải Minh @ FIT 20
