- Mini-max algoritması, karar verme ve oyun teorisinde kullanılan özyinelemeli veya geri izlemeli bir algoritmadır. Rakibin de en iyi şekilde oynadığını varsayarak oyuncuya en uygun hamleyi sağlar.
- Mini-Max algoritması oyun ağacında arama yapmak için özyinelemeyi kullanır.
- Min-Max algoritması çoğunlukla yapay zekada oyun oynamak için kullanılır. Satranç, Dama, tic-tac-toe, go ve çeşitli yedek oyuncu oyunları gibi. Bu Algoritma mevcut durum için minimum maksimum kararını hesaplar.
- Bu algoritmada oyunu iki oyuncu oynar; birine MAX, diğerine MIN denir.
- Rakip oyuncu maksimum faydayı elde ederken minimum faydayı elde ettiğinden, her iki oyuncu da bununla savaşır.
- Oyunun her iki Oyuncusu da birbirinin rakibidir; burada MAX maksimum değeri seçecek ve MIN minimum değeri seçecektir.
- Minimax algoritması, oyun ağacının tamamının keşfedilmesi için derinlik öncelikli bir arama algoritması gerçekleştirir.
- Minimaks algoritması ağacın uç düğümüne kadar ilerler, ardından özyineleme olarak ağacı geriye doğru izler.
MinMax Algoritması için sözde kod:
function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva
İlk arama:
Minimaks(düğüm; 3; doğru)
Min-Max Algoritmasının Çalışması:
- Minimaks algoritmasının çalışması bir örnek kullanılarak kolaylıkla açıklanabilir. Aşağıda iki oyunculu oyunu temsil eden bir oyun ağacı örneğini aldık.
- Bu örnekte biri Maximizer, diğeri Minimizer adında iki oyuncu var.
- Maximizer mümkün olan maksimum puanı almaya çalışacak ve Minimizer mümkün olan minimum puanı almaya çalışacaktır.
- Bu algoritma DFS'yi uygular, dolayısıyla bu oyun ağacında terminal düğümlerine ulaşmak için yaprakların arasından geçmemiz gerekir.
- Terminal düğümünde terminal değerleri verilir, böylece bu değerleri karşılaştırırız ve başlangıç durumu oluşana kadar ağacı geriye doğru izleriz. İki oyunculu oyun ağacını çözmenin ana adımları şunlardır:
Aşama 1: İlk adımda algoritma tüm oyun ağacını oluşturur ve terminal durumları için fayda değerlerini elde etmek üzere fayda fonksiyonunu uygular. Aşağıdaki ağaç diyagramında A'yı ağacın başlangıç durumu olarak kabul edelim. Diyelim ki maksimize edici en kötü durum başlangıç değeri =-sonsuz olan ilk dönüşü alacak ve minimize edici en kötü durum başlangıç değeri = +sonsuz olan bir sonraki dönüşü alacak.
Adım 2: Şimdi, ilk önce Maximizer için fayda değerini buluyoruz, başlangıç değeri -∞, dolayısıyla terminal durumundaki her değeri Maximizer'ın başlangıç değeriyle karşılaştıracağız ve daha yüksek düğüm değerlerini belirleyeceğiz. Hepsi arasında maksimumu bulacaktır.
- D düğümü için max(-1,- -∞) => max(-1,4)= 4
- E Düğümü için max(2, -∞) => max(2, 6)= 6
- F Düğümü için max(-3, -∞) => max(-3,-5) = -3
- G düğümü için max(0, -∞) = max(0, 7) = 7
Aşama 3: Bir sonraki adımda sıra simge durumuna küçültücüye gelir, böylece tüm düğümlerin değerini +∞ ile karşılaştıracak ve 3'ü bulacaktır.üçüncükatman düğüm değerleri.
- B düğümü için= min(4,6) = 4
- C düğümü için= min (-3, 7) = -3
Adım 4: Şimdi sıra Maximizer'a geldi ve yine tüm düğümlerin maksimum değerini seçecek ve kök düğüm için maksimum değeri bulacak. Bu oyun ağacında sadece 4 katman var dolayısıyla hemen kök düğüme ulaşıyoruz ama gerçek oyunlarda 4'ten fazla katman olacak.
- A düğümü için max(4, -3)= 4
Minimax iki oyunculu oyunun tüm iş akışı buydu.
Mini-Max algoritmasının özellikleri:
Minimax Algoritmasının Sınırlandırılması:
Minimax algoritmasının ana dezavantajı Satranç, go vb. gibi karmaşık oyunlar için gerçekten yavaşlamasıdır. Bu tür oyunların büyük bir dallanma faktörü vardır ve oyuncunun karar vermesi gereken birçok seçeneği vardır. Minimax algoritmasının bu sınırlaması şu şekilde geliştirilebilir: alfa-beta budama bunu bir sonraki başlıkta tartıştık.