Minimax Teoremi: "En Kötü Senaryoyu En İyiye Çevirmek" — von Neumann'ın Oyun Teorisinin Kalbi

İki kişi karşılıklı bir oyun oynuyor. Tek bir kazananı var; siz kaybederseniz rakibiniz tam sizin kaybettiğiniz kadar kazanır. Buna sıfır toplamlı oyun denir: ödüllerin toplamı sıfırdır.

Rakibiniz akıllı; her hamlesinde sizi alt etmeye çalışıyor. Siz de aynı şekilde. Her ikiniz de "rakibim en iyi hamleyi yapsa bile, benim en az kötü sonuçta kalmam için en iyi hamle nedir?" diye düşünüyorsunuz.

Bu, kötümser ama akıllı bir bakıştır: en kötü senaryoyu en iyi yap. Modern matematikte buna minimax stratejisi denir.

Aynı oyunda rakibinizin bakış açısı: "Mümkün olan en az kazandığım miktarı, en yüksek olabileceğine çıkar" — yani maximin stratejisi.

Şaşırtıcı sonuç (1928, John von Neumann): Sıfır toplamlı, sonlu, iki kişilik oyunlar için:

$\min_x \max_y f(x, y) = \max_y \min_x f(x, y)$

Yani minimax değer = maximin değer. Bu denge noktasına oyunun değeri denir; her iki oyuncunun "rasyonel" stratejilerle gerçekten kazanacakları/kaybedecekleri miktar bu sayıdır.

Bu eşitlik, modern oyun teorisinin doğum belgesidir.

Sade bir örnek

İki kişilik şu oyunu düşünün. Siz ya Sol ya Sağ seçeceksiniz; rakibiniz aynı anda ya Üst ya Alt seçecek. Sizin ödüller (rakip için ödüller bunların negatifi):

	Üst	Alt
Sol	+3	-1
Sağ	-2	+4

Eğer Sol seçerseniz, en kötü senaryoda $-1$ alırsınız (rakip Alt seçer). Sağ seçerseniz en kötü $-2$ (rakip Üst seçer). Yani siz, en kötü-en iyi'yi Sol ile elde edersiniz: değer $-1$.

Rakibin bakışı: Üst seçerse en kötü onun için $-3$ (sizin için $+3$); yani onun kazancı en az $-3$. Alt seçerse onun en kötü $-4$. Maksimini: $-3$ — Üst seçer.

İki tarafın da saf strateji ile maksimini ve minimaks değerleri aynı çıkmıyor: $-1$ ≠ $-3$. Bu, saf strateji ile dengenin sağlanmadığı durumdur.

Karışık (mixed) strateji ve teoremin asıl gücü

Von Neumann'ın 1928'deki büyük başarısı şuydu: eğer oyuncular rastgele strateji kullanabilirlerse (yani "%40 olasılıkla Sol, %60 olasılıkla Sağ" gibi), o zaman minimax = maximin her zaman sağlanır.

Yukarıdaki oyunu karışık stratejilerle çözelim. Diyelim siz Sol'u $p$ olasılıkla, Sağ'ı $1-p$ ile seçiyorsunuz. Rakip Üst'ü $q$, Alt'ı $1-q$ ile.

Beklenen kazancınız:

$E = 3pq + (-1)p(1-q) + (-2)(1-p)q + 4(1-p)(1-q)$

Bu fonksiyonu sizin için maksimuma, rakip için minimuma alalım. Türev sıfır koşulundan:

• Sizin optimal $p^* = 0{,}6$ (yani %60 Sol, %40 Sağ).
• Rakibin optimal $q^* = 0{,}5$.
• Oyunun değeri: $+1$.

Yani her iki tarafın da optimal karışık strateji oynaması durumunda, ortalama olarak siz $+1$ kazanırsınız, rakip $-1$ kaybeder. Bu, minimaks teoreminin somut bir uygulamasıdır.

Karışık stratejinin sezgisi: rakibinizin sizin hamlenizi tahmin etmesini önlemek için rastgele oynayın. Ama rastgelelik şanslı değil, hesaplı olmalı — doğru olasılıklarla.

Niçin önemli?

Minimax teoreminin değeri sadece teorik değil:

1. Modern oyun teorisinin temel taşı. Sonradan Nash dengesi (1950) iki kişiden çok oyunculara, sıfır toplamlı olmayan oyunlara genişledi. Ama temel mantık aynıydı.
2. Yapay zekâ: Satranç motorları (Stockfish, AlphaZero), Go AI (AlphaGo), poker AI (Pluribus) — hepsi minimax temelinde çalışır. "Rakibim en iyi oynarsa, benim en iyi cevabım nedir?" sorusu, her hamlede tekrar tekrar sorulur.
3. Karar teorisi: Belirsizlik altında karar verme; en kötü senaryoda en iyi olanı seçme yaklaşımı.
4. Ekonomi: Mekanizma tasarımı, müzayedeler, oligopol rekabeti.
5. Askeri strateji: Soğuk Savaş döneminde "mutual assured destruction" (karşılıklı kesin yok ediş) doktrini, minimaks tipi bir denge analizine dayanıyordu.

Minimax algoritması (oyun ağaçlarında)

Bilgisayar biliminde, minimax bir algoritma olarak yaygındır. Bir oyunun tüm olası hamleleri oyun ağacı olarak temsil edilir; her dalda bir hamle, sonraki dalda rakibin cevabı, vs.

Minimax algoritması:

1. Yaprak düğümlere (oyunun sonu) kazanç değeri ata: kazandık (+1), kaybettik (-1), berabere (0).
2. Bir önceki seviyede, eğer sıra sendeyse çocukların maximumunu seç; rakip sırasındaysa minimumunu seç.
3. Bu mantık ağacın kökünde yapılana kadar git.

Klasik basit oyunlarda (X-O, dama) tüm ağaç tamamen genişletilebilir. Karmaşık oyunlarda (satranç, Go) sınırlı derinlikle birleştirilmiş alfa-beta budama kullanılır.

1997'de IBM'in Deep Blue bilgisayarı, dünya satranç şampiyonu Garry Kasparov'u 6 maçlık seride 3.5-2.5 yendi. Deep Blue saniyede 200 milyon pozisyonu değerlendirebiliyordu; algoritması özünde minimax + alfa-beta + karmaşık değerlendirme fonksiyonu.

2016'da Google DeepMind'ın AlphaGo'su, en büyük Go şampiyonu Lee Sedol'u 4-1 yendi. AlphaGo daha modern bir yaklaşım kullandı (Monte Carlo Tree Search + sinir ağları), ama temel ilke yine "rakibim en iyi oynarsa, benim en iyi cevabım".

John von Neumann ve 1928

John von Neumann (1903-1957), Macar asıllı matematikçi-fizikçi. Minimax teoremini 1928'de kanıtladı; o sırada 25 yaşındaydı. Sonraki yıllarda Oskar Morgenstern ile birlikte 1944'te Theory of Games and Economic Behavior (Oyun Teorisi ve Ekonomik Davranış) eserini yazdı. Bu kitap, modern oyun teorisinin doğum belgesi sayılır.

Von Neumann'ın yetenekleri sıra dışıydı: aynı dönemde bilgisayar mimarisi (modern CPU'ların temel taslağı), kuantum mekaniğinin matematik temelleri, otomata teorisi üzerine de devasa katkılar yaptı. Aynı zamanda Manhattan Projesi'nin başlıca matematikçilerinden biri olarak atom bombasının tasarımına katkıda bulundu.

(Von Neumann için ayrı bir biyografik blog yazımız zaten var.)

Nash dengesi: minimax'in genelleştirmesi

John Nash (1928–2015), 1950'lerin başında minimax fikrini iki önemli yönden genişletti:

• İki kişiden çok oyunculara.
• Sıfır toplamlı olmayan oyunlara (yani kazanç ve kayıplar birbirini iptal etmiyor).

Nash dengesi, "hiçbir oyuncunun tek başına stratejisini değiştirerek daha iyi sonuç alamayacağı" bir durumdur. Bu, modern ekonomik teorinin temel kavramıdır (Nash 1994'te Nobel Ekonomi Ödülü aldı; hayatı A Beautiful Mind filminde anlatıldı).

Minimax, Nash dengesinin iki kişilik sıfır toplamlı oyunlar için özel hâlidir.

Bir hayat dersi

Minimax, "rakibim ne yaparsa yapsın, benim en iyi cevabım nedir?" sorusunun matematiksel formülasyonudur. Bu sezgi, satranç, satış pazarlığı, müzayede, politik müzakere — her yerde değerlidir.

Daha geniş bir hayat dersi: rastgelelik bazen bir silahtır. Eğer rakibiniz sizin hamlenizi tahmin edebiliyorsa zayıfsınız; ama rastgele oynarsanız (doğru olasılıklarla), tahmin edilmez olursunuz. Yüksek seviyede tenis, satranç, poker oyuncuları bu prensibi içgüdüsel olarak bilir.

Bir sonraki sefer bir karar verirken — özellikle bir rakibin olduğu bir karar — "en kötü senaryoyu en iyi yapma" çerçevesini deneyebilirsiniz. 1928'de Berlin'de bir Macar matematikçinin yazdığı denklem, hâlâ stratejik düşüncenin matematik temelidir.