Kecerdasan Artifisial

Pertemuan 07

Review dan Latihan Komprehensif

Mata Kuliah: Kecerdasan Artifisial (AI401) | 3 SKS
Persiapan Ujian Tengah Semester (UTS)

📋 Agenda Review

Bagian 1: Konsep

  • P1: Agen Cerdas & PEAS
  • P2: Uninformed Search
  • P3: Informed Search

Bagian 2: Lanjutan

  • P4: Local Search
  • P5: Game Playing
  • P6: CSP

🎯 Fokus: Integrasi konsep dan latihan soal komprehensif

🗺️ Peta Konsep Materi UTS

Peta Konsep UTS

Gambar 1: Hubungan antar topik dalam materi UTS

📚 P1: Empat Pendekatan AI

Human-like Ideal/Rational
Thinking Cognitive Science Logic & Mathematics
Acting Turing Test Rational Agent ⭐

Acting Rationally adalah pendekatan dominan dalam AI modern - fokus pada tindakan optimal, bukan meniru manusia.

🤖 P1: Lima Jenis Agen

Jenis Agen State Goal Utility Learn
Simple Reflex ❌❌❌❌
Model-Based Reflex ✅❌❌❌
Goal-Based ✅✅❌❌
Utility-Based ✅✅✅❌
Learning ✅✅✅✅

→ Kompleksitas meningkat dari atas ke bawah →

📋 P1: Kerangka PEAS

Performance - Bagaimana mengukur kesuksesan?

Environment - Apa saja di lingkungan?

Actuators - Apa yang dapat dilakukan?

Sensors - Apa yang dapat dipersepsi?

Contoh Drone Pengintai:
  • P: Detection rate, coverage, survival
  • E: Airspace, target, ancaman, cuaca
  • A: Flight controls, camera, transmitter
  • S: Kamera, radar, GPS, altimeter

🌍 P1: 6 Karakteristik Lingkungan

Dimensi Spektrum Contoh
Observable Fully ↔ Partially Catur vs Poker
Deterministic Deterministic ↔ Stochastic Catur vs Backgammon
Episodic Episodic ↔ Sequential Klasifikasi vs Game
Static Static ↔ Dynamic Puzzle vs Real-time
Discrete Discrete ↔ Continuous Board game vs Navigasi
Agents Single ↔ Multi Sudoku vs Sepak bola

🧠 Quiz: Agen & Lingkungan

Pertanyaan: Robot vacuum yang mengingat posisi furniture dan area yang sudah dibersihkan memerlukan jenis agen minimal?

A. Simple Reflex Agent
B. Model-Based Reflex Agent ✅
C. Goal-Based Agent
D. Learning Agent

💡 Memerlukan internal state untuk "mengingat", tapi tidak perlu goal eksplisit.

🔍 P2: Formulasi Masalah Pencarian

  • State Space: Semua state yang mungkin
  • Initial State: State awal
  • Actions: Tindakan yang tersedia
  • Transition Model: Hasil dari action
  • Goal Test: Apakah sudah goal?
  • Path Cost: Biaya akumulatif

Contoh 8-Puzzle: State = konfigurasi tile, Action = geser tile, Goal = konfigurasi target

📊 P2: Perbandingan Uninformed Search

Kriteria BFS DFS UCS
Complete? Ya Tidak* Ya
Optimal? Ya (unit) Tidak Ya
Time O(bd) O(bm) O(b1+⌊C*/ε⌋)
Space O(bd) O(bm) O(b1+⌊C*/ε⌋)
Struktur Data Queue Stack Priority Q

b = branching factor, d = depth solusi, m = max depth

🔄 P2: BFS vs DFS Traversal

BFS vs DFS

BFS: Level-by-level (Queue) | DFS: Depth-first (Stack)

💰 P2: Contoh UCS

Graph:
S --2-- A --3-- G
|       |
4       1
|       |
B --2-- C

Ekspansi UCS:

  1. S (g=0) → A(2), B(4)
  2. A (g=2) → C(3), G(5)
  3. C (g=3) → B(5)
  4. B (g=4) → skip
  5. G (g=5) → GOAL!

Jalur optimal: S → A → G dengan cost 5

🎯 P3: Konsep Heuristik

Heuristik h(n) = estimasi biaya dari node n ke goal

Admissible

h(n) ≤ h*(n)

Tidak pernah overestimate

→ A* optimal

Consistent

h(n) ≤ c(n,a,n') + h(n')

Triangle inequality

→ A* lebih efisien

⭐ P3: Algoritma A*

f(n) = g(n) + h(n)

g(n) = biaya aktual dari start ke n

h(n) = estimasi biaya dari n ke goal

Algoritma Evaluasi Optimal?
Greedy Best-First f(n) = h(n) Tidak
UCS f(n) = g(n) Ya
A* f(n) = g(n) + h(n) Ya*

*Jika h admissible

🧩 P3: Heuristik untuk 8-Puzzle

h₁: Misplaced Tiles

Jumlah tile yang salah posisi

Admissible: ✅

Setiap tile minimal 1 move

h₂: Manhattan Distance

Σ |xi-xgoal| + |yi-ygoal|

Admissible: ✅

Lebih informatif (h₂ ≥ h₁)

💡 Heuristik yang lebih informatif → A* eksplorasi lebih sedikit node

🧠 Quiz: Pencarian

Pertanyaan: Jika h(n) = 2 × Manhattan distance, apakah A* dijamin menemukan solusi optimal?

A. Ya, karena Manhattan admissible
B. Tidak, karena h bisa overestimate ❌
C. Ya, jika graph tidak ada cycle
D. Tergantung branching factor

⚠️ h = 2 × Manhattan TIDAK admissible! Dapat overestimate actual cost.

🏔️ P4: Pencarian Lokal

Local Search: Hanya menyimpan state saat ini, bergerak ke neighbor yang lebih baik. Path tidak penting, hanya solusi.

Hill Climbing

  • Selalu ke neighbor terbaik
  • Cepat dan sederhana
  • ❌ Stuck di local optima

Simulated Annealing

  • Terima move buruk dengan P
  • P = eΔE/T
  • ✅ Dapat escape local optima

🌡️ P4: Simulated Annealing

Probabilitas terima move buruk:

P = eΔE/T

ΔE = f(next) - f(current) (negatif jika lebih buruk)

T = temperature (tinggi → eksplorasi, rendah → eksploitasi)

Contoh: ΔE = -7, T = 10
P = e-7/10 = e-0.7 ≈ 0.497 (49.7% diterima)

🎮 P5: Algoritma Minimax

Minimax: Algoritma untuk game adversarial two-player zero-sum. MAX memaksimalkan, MIN meminimalkan. 
function MINIMAX(node, isMaxPlayer):
    if terminal(node): return utility(node)
    
    if isMaxPlayer:
        return MAX(MINIMAX(child) for child in children)
    else:
        return MIN(MINIMAX(child) for child in children)

Kompleksitas: O(bm) - sangat mahal!

🌳 P5: Contoh Minimax

        MAX(?)
       /      \
    MIN(?)   MIN(?)
    /   \    /   \
   3     5  2     9

Evaluasi bottom-up:

  • MIN kiri: min(3, 5) = 3
  • MIN kanan: min(2, 9) = 2
  • MAX: max(3, 2) = 3

Nilai minimax = 3, MAX pilih cabang kiri

✂️ P5: Alpha-Beta Pruning

α (Alpha)

Nilai terbaik MAX

di sepanjang path

β (Beta)

Nilai terbaik MIN

di sepanjang path

Pruning Condition: Jika α ≥ β, potong sisa cabang!

Efisiensi: O(bm) → O(bm/2) dengan perfect ordering

🔍 P5: Alpha-Beta Ilustrasi

Alpha-Beta Pruning

Node dengan X tidak perlu dievaluasi (pruned)

🧠 Quiz: Game & Optimisasi

Pertanyaan: Alpha-beta pruning dengan perfect ordering pada game tree b=10, d=4. Berapa evaluasi yang dihemat?

Tanpa pruning: 104 = 10,000 evaluations

Dengan pruning: ≈ 2 × 102 = 200 evaluations

Penghematan: ~98%! (9,800 evaluations)

🧩 P6: Constraint Satisfaction Problems

CSP didefinisikan oleh:
  • Variables: X = {X₁, X₂, ..., Xₙ}
  • Domains: D = {D₁, D₂, ..., Dₙ}
  • Constraints: Batasan antar variabel
Contoh Map Coloring:
  • Variables: {WA, NT, Q, SA, NSW, V, T}
  • Domains: {Red, Green, Blue}
  • Constraints: Adjacent ≠ same color

🔗 P6: Arc Consistency (AC-3)

Arc Consistent: Untuk setiap nilai di Di, ada nilai di Dj yang memenuhi constraint (i,j) 
function AC-3(csp):
    queue = all arcs in csp
    while queue not empty:
        (Xi, Xj) = queue.pop()
        if REVISE(Xi, Xj):
            if Di empty: return false
            add (Xk, Xi) to queue for all k ≠ j
    return true

AC-3 mereduksi domain sebelum atau selama search

↩️ P6: Backtracking + Heuristics

Teknik Strategi Manfaat
MRV Pilih variabel dengan domain terkecil Fail-fast detection
LCV Pilih nilai yang least constraining Maximize flexibility
Forward Checking Hapus nilai inkonsisten setelah assign Early pruning

📝 P6: Contoh AC-3

CSP:

  • X: {1, 2, 3}
  • Y: {1, 2}
  • Constraint: X > Y

AC-3:

  • Arc (X,Y): X=1 → no support!
  • Remove 1 from D(X)
  • D(X) = {2, 3} ✓
  • D(Y) = {1, 2} ✓

Domain X berkurang dari {1,2,3} menjadi {2,3}

🧠 Quiz: CSP

Pertanyaan: Dalam backtracking dengan MRV, variabel mana yang dipilih pertama?

D(A) = {1, 2, 3, 4}
D(B) = {1, 2}
D(C) = {1, 2, 3}
D(D) = {5}
A. Variable A (domain terbesar)
B. Variable B
C. Variable C
D. Variable D (domain terkecil) ✅

MRV = Minimum Remaining Values → pilih domain terkecil

🎯 Panduan Pemilihan Algoritma

Algorithm Selection

📋 Tabel Keputusan Algoritma

Karakteristik Masalah Algoritma
Adversarial, zero-sum game Minimax, Alpha-Beta
Constraint satisfaction CSP + Backtracking
Optimisasi (path tidak penting) Hill Climbing, SA, GA
Path finding + heuristik A*
Path finding, perlu optimal UCS
Memori terbatas DFS, IDDFS

📊 Ringkasan Kompleksitas

Algoritma Time Space Complete Optimal
BFS O(bd) O(bd) ✅ ✅*
DFS O(bm) O(bm) ❌ ❌
UCS O(b1+⌊C*/ε⌋) O(b1+⌊C*/ε⌋) ✅ ✅
A* O(bd) O(bd) ✅ ✅**
Minimax O(bm) O(bm) ✅ ✅
Alpha-Beta O(bm/2) O(bm) ✅ ✅

*unit cost, **h admissible

⚠️ Kesalahan Umum

  1. Lupa update visited pada BFS/DFS
  2. A* pakai h(n) saja - seharusnya f(n) = g(n) + h(n)
  3. Urutan salah pada alpha-beta (kiri ke kanan!)
  4. Arah arc salah pada AC-3
  5. Manhattan distance: lupa absolute value
  6. Tidak propagate perubahan di CSP

📝 Format UTS

Topik Perkiraan Bobot Tipe Soal
Agen & PEAS (P1) 15-20% Analisis, identifikasi
Uninformed Search (P2) 15-20% Tracing algoritma
Informed Search (P3) 20-25% A*, desain heuristik
Local Search (P4) 10-15% Konseptual, iterasi
Game Playing (P5) 15-20% Minimax, alpha-beta
CSP (P6) 15-20% Formulasi, AC-3

🏋️ Latihan: A* Tracing

Soal: Gunakan A* dari S ke G dengan h yang ditunjukkan

S --1-- A --2-- G
|       |
3       1
|       |
B --1-- C

h(S)=4, h(A)=2, h(B)=3, h(C)=1, h(G)=0
Nodeghf
S044
A123 ✓
C213 ✓
G303 ✓

Path: S→A→C→G atau S→A→G (cost 3)

🏋️ Latihan: Minimax

          MAX
       /        \
     MIN        MIN
    / | \      / | \
   5  3  8    2  7  4

Solusi:

  • MIN kiri: min(5, 3, 8) = 3
  • MIN kanan: min(2, 7, 4) = 2
  • MAX: max(3, 2) = 3

Nilai minimax = 3, MAX pilih cabang kiri

🏋️ Latihan: CSP Formulasi

Soal: Formulasikan Sudoku 4×4 sebagai CSP!

Variables: 16 cell (Xij untuk baris i, kolom j)

Domains: {1, 2, 3, 4}

Constraints:

  • AllDiff per baris (4 constraints)
  • AllDiff per kolom (4 constraints)
  • AllDiff per kotak 2×2 (4 constraints)
  • Given values (unary constraints)

🧠 Quiz Komprehensif

Skenario: Robot penjinak bom harus menavigasi maze untuk mencapai bom sebelum meledak (time limit). Algoritma mana yang paling sesuai?

A. DFS (hemat memori)
B. BFS (complete)
C. A* dengan heuristik jarak ✅
D. Hill Climbing

A* optimal dan efisien untuk path finding dengan heuristik. Time-critical memerlukan solusi cepat dan optimal.

📐 Formula Penting

Konsep Formula
A* Evaluation f(n) = g(n) + h(n)
SA Acceptance P = eΔE/T
Manhattan Distance h = Σ|xi-xg| + |yi-yg|
Admissible h(n) ≤ h*(n)
Alpha-Beta Prune α ≥ β
BFS/DFS Complexity O(bd)

📝 Ringkasan

Pertemuan Topik Konsep Kunci
P1 Agen Cerdas PEAS, 5 jenis agen, 6 karakteristik
P2 Uninformed Search BFS, DFS, UCS
P3 Informed Search Heuristik, A*, admissibility
P4 Local Search Hill Climbing, SA, local optima
P5 Game Playing Minimax, Alpha-Beta Pruning
P6 CSP AC-3, Backtracking, MRV

📅 Pertemuan 8

UJIAN TENGAH SEMESTER (UTS)

Cakupan: Pertemuan 1-6

Persiapan:

  • ✅ Review semua modul
  • ✅ Latihan tracing algoritma
  • ✅ Pahami kapan pakai algoritma apa
  • ✅ Hafalkan formula penting

📚 Referensi

  1. Russell, S. & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th Ed.). Pearson. Chapter 1-6
  2. Poole, D.L. & Mackworth, A.K. (2023). Artificial Intelligence: Foundations of Computational Agents (3rd Ed.). Cambridge University Press.
  3. CS188 Berkeley AI Materials

Terima Kasih

🤖 Kecerdasan Artifisial

Pertemuan 07: Review dan Latihan Komprehensif - Persiapan UTS


Selamat belajar dan sukses UTS!