Minimax Algoritması

Geçen gün üzerinde çalıştığım projede yolum “minimax algoritmasıyla” kesişti ve ben de bu konuyu araştırıp sizlerle paylaşmaya karar verdim. Minimax algoritması genellikle iki oyunculu ve bir oyuncunun kazancının diğer oyuncunun kaybı olduğu oyunlarda kullanılan bir karar verme algoritmasıdır. Minimax algoritması kaybı minimize etmek ve kazancı maksimize etmek için en iyi hamleyi bulmayı amaçlar.

İki oyuncudan biri yapacağı hamlelerde en yüksek kazancı elde etmeye (maksimize etmeye) çalışırken diğer oyuncu az önce bahsettiğimiz oyuncunun kazancını en aza indirgemeye (minimize etmeye) çalışır. Minimax algoritması da adını buradan alır. Bunları daha kolay düşünebilmek için bir karar ağacı oluşturabiliriz. Bu karar ağacında olası tüm hamleler ve puanları yazar. Örneğin kazanç durumuna 1 puan kayıp durumuna 0 puan vermek gibi. Maksimize edici oyuncu kendisi için en yüksek puanı seçerken minimize edici oyuncu karşı taraf için en düşük puanı seçer.

Algoritmamız karar ağacında olası tüm hamlelerin kazancını hesaplar ve en doğru alternatifi seçer. Kaç hamle ileriyi hesaplayacağına derinlik denir. Derinlik ne kadar fazlaysa o kadar iyi tahmin eder ancak derinlik ne kadar fazlaysa o kadar işlem gücü gerekir.

Karar ağacının sonundaki yani daha fazla hamle yapılamayacak durumlara “terminal düğümler” denir. Terminal düğümde oyunun sonucu (kazanç, kayıp, berabere) için bir puan verilir.

Daha sonra geriye doğru yayılım denen işlem gerçekleşir. Geriye doğru yayılım terminal düğümdeki puanın geriye doğru yayılmasıdır. Yani terminal düğümdeki puan üstteki düğüme aktarılır. Örneğin satranç oyununda bir mat durumu oluştuğunda terminal düğüme +10000 puan verelim. Bu puan karar ağacında geriye doğru yayılır ve üst düğümlere aktarılır. Diyelim ki bu puan 10 hamle geriye kadar taşınsın, o noktada seçilen hamleler ileride mat sonucunu getiren hamleler olacaktır.

Alfa Beta Budaması

Alfa-Beta budaması minimax algoritması için bir optimizasyon tekniğidir. Satranç gibi oyunlarda çok fazla olası hamle bulunduğundan dolayı bilgisayarlar için hesaplamak çok kaynak harcar. Bu sebeple alfa-beta budaması kullanılır. Karar ağacımızdaki bazı dalların sonucunu hesaplamak gereksizdir. Alfa-beta budaması ile bu dallar budanır.

Çalışma mantığına değinecek olursak; alfa ve beta olmak üzere iki değerimiz bulunur. Alfa o ana kadar ulaşılan en yüksek değerdir. Beta ise o ana kadar ulaşılan en düşük değerdir. Eğer bir dalda ulaşılabilecek değer elimizdeki alfa değerinden daha küçükse o dalı araştırmaya devam ederiz. Ancak elimizdeki alfa değerinden daha büyükse, bu dalın araştırılması gerekmez çünkü maksimizer oyuncu zaten bu daldan daha iyi bir değeri garantilemiştir ve minimizer oyuncu da bu dalı seçmez çünkü daha düşük değerleri seçmek isteyecektir. Burada karıştırmamız gereken iki durum var:

• Eğer bir dal mevcut alfadan büyükse alfa güncellenir.
• Eğer bir alt ağaç yeni alfa değerini daha da artıracak bir sonuç sunmuyorsa budanır.

Bunu bir örnek üzerinden açıklayalım:

Başlangıçta α = -∞ ve β = +∞ verelim.

B Düğümü:

• İlk yaprak: Değer = 3 Beta güncellenir: β = 3 (çünkü minimizer oyuncu şu anki en küçük değeri seçmek ister).
• İkinci yaprak: Değer = 5 Beta değişmez: β = 3

Bu durumda B düğümünden maksimizer oyuncu için 3 değeri geldi. α = 3 olarak güncellenir.

C Düğümü:

• İlk yaprak: Değer = 6 Beta güncellenir: β = 6.
• İkinci yaprak: Değer = 9 Beta değişmez: β = 6. α = 6 (çünkü 6 önceki alfa olan 3’ten daha büyük).

D Düğümü:

Şuan için α = 6 ve β = +∞

D Düğümüne bakıldığında:

İlk yaprak: Değer = 1

Beta güncellenir: β = 1.

Şimdi (β = 1 ≤ α = 6) koşulu sağlanır. Bu minimizer oyuncunun artık bu dalda daha iyi bir sonuç almasının mümkün olmadığını gösterir. Bu sebeple D düğümünün 2. yaprağı budanır. (β ≤ α koşulu sağlandığı için ikinci yaprağa bakılmıyor.)

Sonuç:

B: 3, C: 6, D: 1 bu durumda maksimizer oyuncu 6 değerini seçer çünkü bu tüm seçenekler arasında en yüksek değerdir.

Alfa-beta budaması, minimax algoritmasının aynı sonucu çok daha az düğüm inceleyerek bulmasını sağladı bu da zaman ve işlem gücünden tasarruf sağladı.

Not: Maksimizer oyuncu için β ≤ α olduğunda budama yapılır. Minimizier oyuncu için ise α ≥ β olduğunda budama yapılır. Ayrıca α maksimizer oyuncunun hamle yaptığı düğümlerde güncellenir, β ise minimizer oyuncunun hamle yaptığı düğümlerde güncellenilir.