Minimax Algoritması (Minimax)

Minimax nedir?

Minimax, iki oyunculu ve sıfır toplamlı oyunlarda en iyi hamleyi seçmek için kullanılan klasik bir karar algoritmasıdır. Temel fikri tek cümle: en kötü senaryoda bile kaybını en aza indir.

Algoritma şunu varsayar — sen skoru maksimize etmeye (kazanmaya) çalışırken, rakibin skoru minimize etmeye (seni yenmeye) çalışıyor. İsim de buradan geliyor: biri maksimize eden, biri minimize eden taraf.

Satranç, tic-tac-toe, dama gibi sıra tabanlı ve tam bilgili oyunlarda kullanılır — yani her iki taraf da tahtanın tamamını görüyor, gizli bilgi yok.

Nasıl çalışır?

Algoritma bir oyun ağacı •olası hamlelerin dallanarak oluşturduğu ağaç yapısı• üzerinde çalışır. Kök düğüm mevcut durumdur; her dal olası bir hamleyi temsil eder. Ağacın seviyeleri sırayla değişir: bir seviyede sen (maksimize eden), sonraki seviyede rakip (minimize eden).

Hesaplama ağacın en altından geriye doğru ilerler. Her düğüm için o pozisyondan ulaşılabilecek en kötü sonucu bulur, sonra bu en kötü sonucu senin için mümkün olduğunca iyi yapan hamleyi seçer.

Oyunun sonuna kadar bakmak çoğu oyunda mümkün değil — dallar üstel büyür. Bu yüzden arama belirli bir derinlik •kaç hamle ileriye bakılacağı, ply cinsinden• ile sınırlanır.

Neden önemli?

Ham minimax pahalıdır: ağaç derinleştikçe düğüm sayısı patlar. İşte burada alpha-beta pruning •sonucu etkilemeyecek dalları budayarak aramayı hızlandıran teknik• devreye girer. Nihai sonucu hiç değiştirmeden gereksiz dalları eler ve aynı sürede çok daha derine bakmayı sağlar.

En ünlü örneği Deep Blue: 1997'de dünya şampiyonu Garry Kasparov''u yenen sistem en az 12 hamle ileriye bakıyordu.

Kullanım alanları

Sıra tabanlı oyun yapay zekaları, karar teorisi problemleri, rakip odaklı (adversarial) senaryolar. Modern oyun motorları minimax''ı çoğu zaman Monte Carlo Tree Search gibi tekniklerle birleştirir. Ama temel mantığı — "rakip en iyi oynayacak, sen de ona göre hazırlan" — hâlâ geçerli.