Minimax Algoritması Nedir?

Minimax algoritması, satranç, dama ya da XOX (tic-tac-toe) gibi iki oyunculu, sırayla oynanan ve bir tarafın kazancının diğerinin kaybı olduğu oyunlarda en iyi hamleyi bulmak için kullanılır. Adını iki oyuncunun hedefinden alır: bir oyuncu puanı en üst düzeye çıkarmaya (max), rakibi ise en aza indirmeye (min) çalışır.

Minimax algoritması nedir?

Algoritma, mevcut pozisyondan başlayarak olası tüm hamleleri ve rakibin bunlara verebileceği cevapları bir oyun ağacında temsil eder. Ağacın uçlarındaki pozisyonlar puanlanır. Ardından puanlar yukarı doğru taşınır: max sırasındaki düğümler çocuklarının en büyüğünü, min sırasındaki düğümler en küçüğünü alır. Kök düğümde en yüksek değeri veren hamle seçilir.

Nasıl çalışır?

Varsayımsal basit bir örnek: Senin A ve B olmak üzere iki hamlen var. A'yı oynarsan rakibin cevaplarına göre sonuçlar +3 ya da −2; B'yi oynarsan +1 ya da 0 olsun. Rakip en iyi oynayacağı için A'nın değeri −2, B'nin değeri 0 olur. Minimax, en kötü durumda daha iyi olan B'yi seçer.

Gerçek oyunlarda ağaç çok hızlı büyür; bu yüzden arama belirli bir derinlikte kesilir ve pozisyonlar bir değerlendirme fonksiyonuyla sezgisel olarak puanlanır.

Alfa-beta budama ve sınırlar

Alfa-beta budama, sonucu değiştiremeyeceği kesinleşen dalları hiç incelemeyerek minimax'ı aynı kararı verecek şekilde hızlandırır. Yine de dallanma sayısı çok yüksek olan Go gibi oyunlarda bu yaklaşım yetersiz kalır; bu tür oyunlarda Monte Carlo ağaç araması gibi yöntemler öne çıkmıştır. Minimax ayrıca rakibin kusursuz oynadığını varsayar; bu, zayıf rakiplere karşı fazla temkinli kararlara yol açabilir.