Satrancın oyun teorisi açısından neden özel bir oyun olduğunu, Zermelo teoremini, minimax algoritmasını ve satrancın yapay zeka ile ilişkisini öğreneceksiniz. Satranç, oyun teorisinin en saf uygulama alanlarından biridir.
Satranç, oyun teorisinin en klasik örneklerinden biridir. Şu özellikleriyle teorik analize uygundur:
Satranç, sonlu, iki kişilik, sıfır toplamlı, tam bilgili, deterministik bir oyundur. Bu özellikleriyle oyun teorisinin en temel modellerinden birini oluşturur.
Alman matematikçi Ernst Zermelo, satranç ve benzeri oyunlar üzerine yaptığı çalışmayla oyun teorisinin temel teoremlerinden birini ispatlamıştır.
Başka bir deyişle, satranç kesinlikle belirlenmiş (strictly determined) bir oyundur. Teorik olarak oyunun değeri ya +1 (Beyaz kazanır), ya -1 (Siyah kazanır), ya da 0 (beraberlik)'dır.
Zermelo teoremi satrancın teorik olarak çözülebilir olduğunu söyler. Ancak satrancın olası durum sayısı (~$10^{120}$) o kadar büyüktür ki, bu çözümü pratikte hesaplamak imkansızdır. Bu nedenle satranç pratikte "çözülememiş" bir oyundur.
Satranç, bir oyun ağacı (game tree) ile temsil edilir. Her düğüm bir pozisyonu, her dal bir hamleyi temsil eder.
| Özellik | Satranç Değeri |
|---|---|
| Oyun ağacının dallanma faktörü (ortalama) | ~35 hamle/pozisyon |
| Ortalama oyun uzunluğu | ~40 hamle (80 yarım hamle) |
| Toplam olası oyun sayısı | ~$10^{120}$ (Shannon sayısı) |
| Olası farklı pozisyon sayısı | ~$10^{40}$ |
| Geçerli pozisyon sayısı | ~$10^{15}$ - $10^{20}$ |
Claude Shannon, 1950'de satrancın olası oyun sayısını yaklaşık $10^{120}$ olarak hesaplamıştır. Bu sayı, evrendeki atom sayısından ($\sim 10^{80}$) çok daha büyüktür. Bu nedenle satrancın tam çözümü pratikte imkansızdır.
Satranç gibi oyunlarda en iyi hamleyi bulmak için kullanılan klasik yöntem minimax algoritması'dır.
▪️ Beyaz (maximizer) kazanma şansını maksimize etmek ister.
▪️ Siyah (minimizer) Beyaz'ın kazanma şansını minimize etmek ister.
▪️ Her pozisyonda, oyuncu kendisi için en iyi, rakibi için en kötü sonucu getiren hamleyi seçer.
Beyaz, kendi sırasında maksimum değeri veren hamleyi seçer. Siyah ise minimum değeri veren hamleyi seçer (çünkü Beyaz'ın değerini düşürmek ister).
Minimax algoritmasının pratikte kullanılabilmesi için alfa-beta budaması (alpha-beta pruning) ile optimize edilmesi gerekir.
Arama ağacında kötü hamleleri erken tespit ederek onların altındaki dalları keser. Bu sayede minimax ile tamamen aynı sonucu verirken çok daha az düğüm incelenir. İyi uygulandığında arama derinliği iki katına çıkabilir.
α (alpha): Şimdiye kadar bulunan Beyaz için en iyi garantili skor — Beyaz bundan daha kötüsünü asla kabul etmez.
β (beta): Şimdiye kadar bulunan Siyah için en iyi garantili skor — Siyah bundan daha kötüsünü asla kabul etmez.
Bir düğümde α ≥ β koşulu sağlandığı an, o dalın geri kalanını incelemeye gerek yoktur (rakip zaten bu yola girmez).
Aşağıda 3 derinlikli minimax ağacında alfa-beta budamasının nasıl çalıştığı gösterilmektedir. ✕ ile işaretli dallar hiç incelenmez.
[MAX]
/ \
[MIN] [MIN]
/ \ / \
[3] [5] [2] [✕ budandı]
Adım adım:
1. Sol MIN düğümü: 3 ve 5 görülür → MIN seçer: 3
→ α = 3 (Beyaz en az 3 garanti etti)
2. Sağ MIN düğümü inceleniyor:
– İlk çocuk: 2 → MIN buraya girebilir (2 < 3)
– α = 3 ≥ β = 2 koşulu sağlandı → kalan dallar budanır ✕
3. MAX sonuç: 3 (sağ tarafın geri kalanı hiç incelenmedi)
Minimax tüm düğümleri incelemiş olurdu. Alfa-beta budaması aynı sonuca (3) ulaşırken gereksiz dalları atlayarak çok daha hızlıdır.
Rastgele sıralı hamlelerle O(bd) yerine yaklaşık O(bd/2) düğüm incelenir (b: dallanma faktörü, d: derinlik). Satrançta bu, aynı sürede yaklaşık iki kat daha derin arama yapılabilmesi anlamına gelir. Hamleler iyi sıralandığında (önce güçlü hamleler) bu kazanım en üst düzeye çıkar.
Satranç programlarının kalbi, değerlendirme fonksiyonu (evaluation function)'dur. Bu fonksiyon, herhangi bir pozisyonun ne kadar iyi olduğunu sayısal olarak ifade eder.
| Taş | Standart Değer | Açıklama |
|---|---|---|
| ♙ Piyon | 1 | En düşük değerli taş |
| ♘ At / ♗ Fil | 3 | Hafif taşlar |
| ♖ Kale | 5 | Ağır taş |
| ♕ Vezir | 9 | En güçlü taş |
| ♔ Şah | ∞ | Kaybedilmemeli, sonsuz değer |
Modern satranç programları sadece taş değerlerine bakmaz: taş aktivitesi, piyon yapısı, şah güvenliği, merkez kontrolü, gelişim gibi pek çok faktörü de hesaba katar. Derin öğrenme tabanlı programlar (AlphaZero gibi) bu değerlendirmeyi kendi kendine öğrenir.
Değerlendirme fonksiyonunun ciddi bir zayıflığı vardır: arama belirli bir derinlikte durduğunda, ortada yarım kalmış taktiksel kombinasyonlar (taş alışverişi, şah baskısı) yanlış değerlendirilebilir. Bu soruna ufuk etkisi (horizon effect) denir.
Normal arama derinliğine ulaşıldığında, eğer pozisyon "hareketliyse" (taş alışverişi, şah tehdidi gibi kritik hamleler varsa) arama durdurulmaz; pozisyon sakinleşene kadar devam ettirilir.
Örnek: Vezir, bir piyonu alıyor gibi görünür (+1). Ama bir sonraki hamlede Siyah veziri alabilir (−9). Quiescence search bunu önceden görür ve bu hamleden vazgeçer. Aksi hâlde program büyük bir hata yapar.
| Özellik | Satranç | Genel Oyun Teorisi |
|---|---|---|
| Oyuncu sayısı | 2 (sabit) | n ≥ 2 |
| Toplam getiri | Sıfır toplamlı | Sıfır toplamlı veya değil |
| Bilgi yapısı | Tam bilgili | Tam / Eksik bilgili |
| Zaman yapısı | Sıralı | Sıralı / Eşzamanlı |
| Şans faktörü | Yok | Deterministik / Stokastik |
| Denge çözümü | Minimax / Nash | Nash / Alt oyun mükemmel |
| Pratik çözülebilirlik | Hayır ($10^{120}$ oyun) | Küçük oyunlar için evet |
Satranç gibi tam bilgili, sıralı, sıfır toplamlı oyunlarda Nash dengesi kavramı minimax çözümü ile örtüşür.
▪️ Satrançtaki her pozisyon, bir alt oyun olarak düşünülebilir.
▪️ Minimax çözümü, alt oyun mükemmel Nash dengesi (subgame perfect equilibrium) ile aynıdır.
▪️ Beyaz'ın optimal stratejisi, Siyah'ın optimal stratejisine karşı en iyi sonucu verir.
▪️ Teorik olarak, satrancın değeri (Beyaz kazanır mı, beraberlik mi?) bilinmiyor, ancak bir Nash dengesi vardır.
Aşağıdaki gibi basit bir son oyun pozisyonunu düşünelim (şah + piyon vs şah):
Beyaz: Şah e6, Piyon d5 | Siyah: Şah d8
Oyun teorisi analizi:
Minimax ağacı (basitleştirilmiş, 2 hamle derinliği):
[MAX: Beyaz +1]
/ \
d5-d6 (piyon ilerler) Şah f6 (yanlış)
| |
[MIN: Siyah] [MIN: Siyah]
/ \ |
Şd8-c8 Şd8-e8 Şd8-e8 engeller
| | |
d6-d7→d8=♕ d6-d7 bloke beraberlik [0]
Beyaz [+1] çözüm yok
Minimax değeri: d5-d6 → +1 (Beyaz kazanır)
Bu, satrancın küçük bir alt kümesinde oyun teorisinin nasıl kesin ve eksiksiz çözüm üretebildiğini gösterir. Tüm dal değerleri hesaplanır, Beyaz en yüksek değeri seçer.
Satranç, oyun teorisinin en saf uygulama alanlarından biridir.
▪️ Zermelo teoremi: Satranç kesinlikle belirlenmiş bir oyundur (ya kazanılır ya kaybedilir ya da berabere).
▪️ Minimax: Optimal hamleyi bulmanın matematiksel yöntemi.
▪️ Oyun ağacı: $10^{120}$ olası oyun (Shannon sayısı).
▪️ Değerlendirme fonksiyonu: Bir pozisyonun değerini hesaplar.
▪️ AlphaZero: Kendi kendine oynama (self-play) ile satrancı öğrenen yapay zeka.
▪️ Günümüzde satranç motorları insanüstü seviyededir (3600 Elo).