Pencarian Adversarial

Minimax Algorithm

Minimax adalah algoritma pencarian pada game tree untuk menentukan langkah optimal dalam permainan dua agen zero-sum. Pemain MAX berusaha memaksimalkan skor, sementara pemain MIN berusaha meminimalkan skor. Algoritma menelusuri seluruh game tree hingga kedalaman yang ditentukan, lalu memilih langkah dengan nilai tertinggi.

minimax(board, depth, isMax):
  if depth == 0 or terminal:
    return evaluate(board)
  if isMax:
    best = -infinity
    for each move:
      best = max(best, minimax(..., false))
    return best
  else:
    best = +infinity
    for each move:
      best = min(best, minimax(..., true))
    return best
                    

Alpha-Beta Pruning

Alpha-Beta Pruning adalah optimasi Minimax yang memangkas cabang game tree yang tidak akan memengaruhi hasil akhir. Alpha menyimpan nilai terbaik untuk MAX, Beta menyimpan nilai terbaik untuk MIN. Jika Beta lebih kecil atau sama dengan Alpha, cabang tersebut dipangkas dan tidak dieksplorasi lebih lanjut.

alphabeta(board, depth, alpha, beta, isMax):
  if depth == 0 or terminal:
    return evaluate(board)
  if isMax:
    for each move:
      alpha = max(alpha, alphabeta(...))
      if beta <= alpha: break
    return alpha
  else:
    for each move:
      beta = min(beta, alphabeta(...))
      if beta <= alpha: break
    return beta
                    

Cara Bermain

• Piece merah dikendalikan oleh pemain (Human)
• Piece putih dikendalikan oleh AI
• Klik piece untuk memilih, klik kotak tujuan untuk bergerak
• Capture bersifat wajib jika tersedia
• Piece yang mencapai baris ujung lawan menjadi King
• King dapat bergerak maju dan mundur
• Menang jika semua piece lawan habis atau tidak bisa bergerak

Tentang Project

• Mata Kuliah: Kecerdasan Buatan
• Program Studi: Teknik Informatika
• Universitas: Universitas Bale Bandung
• Dosen: Mohammad Bayu Anggara, S.Kom., M.Kom.
• NIM: 301240041
• Nama: Selsa Shafana Alfiyani
• Kelas: 4B