🎯 Capaian Pembelajaran

Setelah pertemuan ini, mahasiswa mampu:

1. Memformulasikan game sebagai problem pencarian adversarial
2. Membangun dan menganalisis game tree
3. Mengimplementasikan algoritma Minimax
4. Menganalisis kompleksitas Minimax O(b^m)
5. Menerapkan Alpha-Beta Pruning untuk optimasi
6. Merancang fungsi evaluasi untuk game

📋 Agenda Hari Ini

🔄 Review: Pencarian Sebelumnya

🎮 Apa itu Pencarian Adversarial?

📊 Single Agent vs Adversarial

⚠️ A* tidak bisa digunakan langsung untuk game karena lawan akan menghalangi!

🌍 Aplikasi Pencarian Adversarial

📂 Klasifikasi Game

Gambar 2.1: Klasifikasi game berdasarkan karakteristiknya

🎲 Deterministik vs Stokastik

👁️ Perfect vs Imperfect Information

⚖️ Zero-Sum Game

♟️ Contoh Zero-Sum: Catur

🎯 Fokus Pertemuan Ini

Game dengan karakteristik:

• Two-player - Dua pemain bergantian
• Zero-sum - Keuntungan satu = kerugian lainnya
• Perfect information - Semua state terlihat
• Deterministic - Tidak ada keacakan

Contoh: Catur, Tic-Tac-Toe, Connect Four, Checkers

🌳 Game Tree

🏗️ Komponen Game Tree

❌⭕ Game Tree: Tic-Tac-Toe

Gambar 3.2: Sebagian game tree untuk Tic-Tac-Toe

📊 Kompleksitas Tic-Tac-Toe

• Branching factor rata-rata: b ≈ 5
• Kedalaman maksimum: m = 9
• Estimasi nodes: 5⁹ ≈ 2 juta
• Actual unique games: ~255,168

🎯 Algoritma Minimax

📈 Ilustrasi Minimax

Gambar 4.1: Propagasi nilai dari terminal ke root

📐 Definisi Formal Minimax

💻 Pseudocode Minimax

def max_value(state):
    if terminal_test(state):
        return utility(state)
    v = -infinity
    for action in actions(state):
        v = max(v, min_value(result(state, action)))
    return v

def min_value(state):
    if terminal_test(state):
        return utility(state)
    v = +infinity
    for action in actions(state):
        v = min(v, max_value(result(state, action)))
    return v
                

✏️ Contoh: Hitung Minimax

        A (MAX)
       /|\
      / | \
     B  C  D (MIN)
    /\  |  /\
   3  5 2 6  1
                

⏱️ Kompleksitas Minimax

📊 Fungsi Evaluasi

✅ Properti Fungsi Evaluasi yang Baik

1. Konsisten dengan utility - Setuju untuk terminal states
2. Cepat dihitung - Tidak terlalu kompleks
3. Reflektif - Nilai tinggi = peluang menang tinggi
4. Linear combination - Weighted sum dari features

♟️ Contoh: Evaluasi Catur

Material advantage adalah feature paling penting!

✂️ Mengapa Perlu Pruning?

Minimax mengevaluasi banyak node yang tidak perlu!

🔪 Alpha-Beta Pruning

📊 Ilustrasi Alpha-Beta

Gambar 6.1: Pruning terjadi ketika α ≥ β

⚡ Kondisi Pruning

💻 Pseudocode Alpha-Beta

def max_value(state, alpha, beta):
    if terminal_test(state): return utility(state)
    v = -infinity
    for action in actions(state):
        v = max(v, min_value(result(state, action), alpha, beta))
        if v >= beta: return v  # Prune!
        alpha = max(alpha, v)
    return v

def min_value(state, alpha, beta):
    if terminal_test(state): return utility(state)
    v = +infinity
    for action in actions(state):
        v = min(v, max_value(result(state, action), alpha, beta))
        if v <= alpha: return v  # Prune!
        beta = min(beta, v)
    return v
                

✏️ Contoh Alpha-Beta Pruning

           A (MAX)
         /   |   \
        B    C    D (MIN)
       /\   /\   /\
      3  5 6  2 1  8
                

1. B = min(3,5) = 3 → α = 3
2. C: cek 6, lalu 2. min = 2 (tidak dipilih, 2 < 3)
3. D: cek 1. 1 ≤ α(3)? Ya! → PRUNE 8! ✂️
4. A = max(3, 2, 1) = 3

Node 8 tidak perlu dievaluasi!

📊 Efisiensi Alpha-Beta

🎯 Perfect ordering = kedalaman pencarian 2x lipat!

📋 Teknik Move Ordering

Untuk mendekati efisiensi optimal:

1. Killer Move Heuristic - Simpan langkah yang menyebabkan cutoff
2. History Heuristic - Lacak langkah yang sering sukses
3. Iterative Deepening - Gunakan hasil pencarian dangkal
4. Transposition Table - Cache hasil evaluasi

🎲 Expectiminimax

🎯 Chance Nodes

Pada chance node, hitung expected value:

🎖️ Aplikasi: Simulasi Pertahanan

• Defender (MAX): Memilih posisi unit pertahanan
• Attacker (MIN): Memilih jalur serangan
• Utility: +1 jika pertahanan berhasil, -1 jika gagal

Minimax membantu menemukan strategi pertahanan optimal!

🔐 Aplikasi: Cyber Defense

🧠 Quiz Time!

Pertanyaan 1:

Dalam zero-sum game, jika MAX mendapat utility +5, berapa utility MIN?

💡 Zero-sum: U_MAX + U_MIN = 0

🧠 Quiz Time!

Pertanyaan 2:

Kapan Alpha-Beta Pruning melakukan pruning pada MIN node?

🧠 Quiz Time!

Pertanyaan 3:

Game Backgammon termasuk kategori:

💡 Ada dadu (stokastik), tapi semua bidak terlihat (perfect info)

📝 Ringkasan

📅 Pertemuan Berikutnya

• Formulasi CSP: variabel, domain, constraint
• Constraint Propagation (AC-3)
• Backtracking Search dengan heuristik
• Contoh: Map Coloring, Sudoku

📚 Referensi

1. Russell, S. & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th Ed.). Pearson. Chapter 5: Adversarial Search
2. Ertel, W. (2017). Introduction to Artificial Intelligence (2nd Ed.). Springer. Chapter 6.
3. CS188 Berkeley AI Materials: https://inst.eecs.berkeley.edu/~cs188/