Minimax Algoritması

Uygulama alanı oyun ağaçlarıdır. Kaybetme olasılığını minimuma indirirken kazanma potansiyelini maksimuma çıkarır. İki oyuncununda tüm olası hamlelerini içeren ağaç üzerinde çalışır. Algoritmanın performansı O(bⁿ) dir. Yani ağacın bütün düğümlerini kontrol eder. Her zaman max ile başlanır.

Max–> Bizim olası hamlelerimiz

Min–> Rakibin olası hamleleri

ALGORİTMANIN PSEUDO KODU

fonksiyon maxkök(durum,derinlik)
if oyunbittiyse OR derinlik<= 0

RETURN oyunsonucu

END IF

ELSE

max=-sonsuz

deger=minkök(durum,derinlik-1)

IF max<=deger

max=deger

END IF

END ELSE

RETURN max

END fonksiyon

fonksiyon minkök(durum,derinlik)

if oyunbittiyse OR derinlik<= 0

RETURN oyunsonucu

END IF

ELSE

min=+sonsuz

deger=maxkök(durum,derinlik-1)

IF min>=deger

min=deger

END IF

END ELSE

RETURN min

END fonksiyon

Algoritmayı ağaç üzerinde deneyelim:

Kök için max değere bakıyoruz. Çünkü max la başlamamız gerekiyor. Daha sonraki adımımızda min değere öncelik vererek yolumuza devam ederiz.

Minimax algoritmasına göre izlenecek yollar A-B-D-I