T: tema · Z: kodu büyüt · S: konuşmacı notları · F: tam ekran · Esc: genel bakış · ⌂ ders haritası
OYUNLARDA YAPAY ZEKÂ · HAFTA 6
Oyun Ağaçları
Minimax, alfa-beta, Monte Carlo ağaç araması — rakip de düşünüyorsa
PRESS ▶ TO START

Bu derste oyunun haritası 🗺️

  1. Oyun ağacı nedir? — hangi oyunlar, ne kadar büyük?
  2. Minimax — “rakibim en iyisini oynayacak” varsayımı (XOX’ta yenilmez YZ)
  3. Alfa-beta budaması — aynı sonucu çok daha az işle bulmak
  4. Derinlik ve değerlendirme — satranç ve Dört Bir Arada gibi büyük oyunlar
  5. MCTS — rastgele oyunlarla akıllı karar (Go, strateji oyunları)
  6. Kod — minimax, alfa-beta, MCTS + üç laboratuvar
  7. Tarihten — Turing, Deep Blue’nun “hatası”, Chinook, AlphaGo’nun 37. hamlesi
  8. Kütüphaneler — python-chess, Stockfish, OpenSpiel, easyAI, chess.js
🎮 Bu dersin sonunda…

…XOX’ta asla kaybetmeyen bir YZ yazabilecek, alfa-beta budamasını elle izleyebilecek, Dört Bir Arada için değerlendirme fonksiyonu tasarlayabilecek, MCTS’nin nasıl çalıştığını anlatabilecek ve bir masa/kart oyununa rakip YZ ekleyebileceksiniz.

🤔 ISINMA: XOX’TA HİÇ KAYBETMEDİNİZ Mİ?

Bir hamle yapmadan önce kafanızdan ne geçiyor? “Ben buraya koyarsam o şuraya koyar, sonra ben şuraya…”

  • Bu cümle bir ağaç: her hamle bir dal, her dalın altında rakibin olası cevapları.
  • Önemli varsayım: rakip aptal değil. Size en çok zarar verecek cevabı verecek. Siz de ona.
  • XOX’ta bu ağacın tamamını gezmek mümkün: bilgisayar hiç kaybetmez. Satrançta mümkün değil; nasıl idare edildiğini göreceğiz. Go’da daha da zor; orada zar atarak düşünen bir yöntem çıktı: MCTS.

🎯 Bu konu için bilmeniz gerekenler

Yeşil = gerekli · kesikli = faydalı ama şart değil. Tıklayınca ilgili sunuma gider.

İkili Arama Ağaçları (ağaç, özyineleme)Y5 · GOAP (durum uzayında arama)
Algoritma Analizi (üstel büyüme)Hash Tabloları (geçiş tablosu)Y4 · Utility (değerlendirme = puan)
Neden?Oyun ağacı bir ağaçtır ve minimax özyinelemeli bir yürüyüştür. Y5’te “bir hedefe ulaşmak için” arama yaptık; şimdi aramada bir rakip var. Ağaçların neden bu kadar büyüdüğünü anlamak için üstel büyüme fikri yeter.
🧰 Kodlamadan korkuyorsanızBu sunumda her algoritmanın canlı bir oyunu var: önce oynayın, sonra kodu okuyun. Kendi oyununuza rakip eklemek için hazır kütüphaneler (easyAI, OpenSpiel, Stockfish) kullanılabilir; asıl iş oyununuzun kurallarını “hamleleri listele / hamle yap / bitti mi?” fonksiyonlarına ayırmaktır.

Mini sözlük

game tree · plyoyun ağacı · yarım hamleDüğüm = konum, dal = hamle · bir oyuncunun tek hamlesi
branching factordallanma katsayısıBir konumdaki ortalama hamle sayısı (satranç ~35, Go ~250)
zero-sum · perfect informationsıfır toplamlı · tam bilgiliBirinin kazancı diğerinin kaybı · iki taraf da her şeyi görür
minimax · MAX / MIN—MAX puanı en büyüklemeye, MIN en küçüklemeye çalışır
evaluation functiondeğerlendirme fonksiyonuOyun bitmeden bir konuma “ne kadar iyi” puanı veren tahmin
horizon effectufuk etkisiArama derinliğinin hemen ötesindeki felaketi görememek
alpha-beta pruningalfa-beta budamasıSonucu değiştiremeyecek dalları hiç incelememe
iterative deepening · transposition tableyinelemeli derinleştirme · geçiş tablosu1, 2, 3… derinlikte ara · görülen konumları hash tablosunda hatırla
MCTS · playout · UCB1 / UCTMonte Carlo ağaç araması · rastgele oyun · güven sınırıRastgele oyunlarla istatistik toplayan arama · keşif/sömürü dengesi formülü
LEVEL 0
Oyun ağacı nedir?
hangi oyunlar, ne kadar büyük?
  • oyun ağacı nedir?
  • minimax
  • alfa-beta budaması
  • derinlik ve değerlendirme
  • Monte Carlo ağaç araması
  • kod ve laboratuvarlar
  • tarihten hikâyeler
  • kütüphaneler ve entegrasyon

Hangi oyunlar için?

tam bilgili (her şey görünür)eksik bilgili (gizli bilgi)
şanssızXOX, satranç, dama, Go, Dört Bir Arada, Mangala, Othello → minimax / alfa-beta / MCTSStratego, Savaş gemileri → çıkarım + arama
şanslı (zar, kart çekme)Tavla → zar düğümlü minimax (expectiminimax)Okey, poker, Hearthstone → bilgi kümeli MCTS, CFR
  • Bu sunumun çekirdeği: iki oyunculu, sıra tabanlı, sıfır toplamlı, tam bilgili oyunlar.
  • Video oyunlarında: masa/kart oyunu uyarlamaları, sıra tabanlı taktik (XCOM benzeri), strateji oyunlarının kampanya kararları, bulmaca çözücüler.
🇹🇷 MangalaTürkiye’de okullarda da oynanan Mangala, mancala ailesinden tam bilgili, şanssız bir taş oyunu. Minimax ile güçlü bir rakip yazmak için ideal bir proje (son bölüm).

Ağaçlar ne kadar büyük?

oyundallanmabüyüklükdurum
XOX≤ 9255.168 farklı oyunçözülmüş: berabere
Dört Bir Arada≤ 7~4,5 × 10¹² konumçözülmüş (1988): başlayan, ortadan başlarsa kazanır
Dama (İngiliz)~10~5 × 10²⁰ konumçözülmüş (2007): berabere
Satranç~35~10¹²⁰ olası oyun (Shannon sayısı)çözülmemiş
Go (19×19)~250~10¹⁷⁰ konumçözülmemiş
⚠️ Üstel büyümeDallanma b, derinlik d ise yaprak sayısı yaklaşık bd. Satrançta 6 yarım hamle: 35⁶ ≈ 1,8 milyar konum. Evrendeki atom sayısı ~10⁸⁰; satranç ağacının yanında küçük kalır.
Ne yapacağız?
  • Küçük oyunlar: ağacın tamamı (minimax)
  • Daha büyük: budama + sınırlı derinlik + tahmin (alfa-beta + değerlendirme)
  • Çok büyük, tahmin zor: örnekleme (MCTS)

Çizimle: ağaçlar kaç basamaklı?

çubuk boyu = sayının kaç basamaklı olduğu (10 üzeri kaç)XOX255.168 oyun (≈ 10⁵)Dört Bir Arada4,5 × 10¹² konum (≈ 10¹³)Dama5 × 10²⁰ konum (≈ 10²¹)Satranç10¹²⁰ oyun Go (19×19)10¹⁷⁰ konum evrendeki atom sayısı ≈ 10⁸⁰yeşil: çözülmüş (sonuç kesin biliniyor)kırmızı: çözülmemiş

Bir sayının büyüklüğünü basamak sayısıyla çizdik; yine de satranç çubuğu evrendeki atomların çok ötesine taşıyor. XOX’tan Go’ya her adımda yalnızca birkaç kat değil, onlarca basamak büyüyor. Bu yüzden büyük oyunlarda ağacın tamamına hiçbir zaman bakılamaz: budama, sınırlı derinlik ya da örnekleme şart.

Quiz 1 · oyun ağacı
Dallanma katsayısı 30 olan bir oyunda 4 yarım hamle derinliğe kadar kaç yaprak vardır (yaklaşık)?
30⁴ = 30 · 30 · 30 · 30 = 810.000. Derinliği bir artırırsanız 24 milyon olur: bu yüzden “biraz daha derin bakmak” çok pahalıdır ve budama bu kadar önemlidir.
LEVEL 1
Minimax
rakibim en iyi cevabı verecek
  • oyun ağacı nedir?
  • minimax
  • alfa-beta budaması
  • derinlik ve değerlendirme
  • Monte Carlo ağaç araması
  • kod ve laboratuvarlar
  • tarihten hikâyeler
  • kütüphaneler ve entegrasyon

Önce küçük bir oyun: üç kapı, cimri bekçi 🚪💰

Kural iki cümle: Siz bir kapı seçersiniz. Kapının ardında üç sandık vardır ve bekçi size içlerinden en az altın olanı verir (sandıkların içini ikiniz de görüyorsunuz). Hangi kapıyı seçerdiniz? Önce tahmin edin, sonra oynatın.

Aynı oyun, “oyun ağacı” olarak

kapı oyunundaoyun ağacındaXOX’ta
🧑 sizMAX ▲: puanı büyütmek isterX oynayan
💂 bekçiMIN ▼: puanı küçültmek isterO oynayan rakip
🚪 kapı seçmekbir hamle (dal)boş kareye X koymak
📦 sandıkyaprak: oyunun sonu+1 kazandım · 0 berabere · −1 kaybettim
“bekçi en azı verir”MIN düğümü = çocukların en küçüğürakip benim için en kötü cevabı verir
“en iyi kapıyı seçerim”MAX düğümü = çocukların en büyüğüen iyi hamlemi oynarım

Gerçek oyunlarda ağaç daha derindir: ben, rakip, ben, rakip… Kural değişmez: benim sıramda en büyük, rakibin sırasında en küçük. “Mini-max” adı buradan gelir.

3 🧑 sen (MAX) 322 🚪 A🚪 B🚪 C 31282461452 📦 sandıklar (yapraklar) · ▽ bekçi (MIN) en küçüğü alır

Minimax fikri

  • İki oyuncu: MAX (biz, ▲) puanı büyütmek, MIN (rakip, ▼) küçültmek istiyor.
  • Yapraklar oyun sonu: kazandım +1, kaybettim −1, berabere 0 (ya da bir puan).
  • Değerler aşağıdan yukarı taşınır: MIN düğümü çocuklarının en küçüğünü, MAX düğümü en büyüğünü alır.
  • Kökte en büyük değerli çocuğa giden hamleyi oynarız.
Neden “rakip en iyisini oynar”?Güvenli varsayım: rakip iyi oynarsa bile garanti ettiğimiz sonucu alırız; kötü oynarsa daha da iyisini. Minimax, “en kötü durumda en iyi” sonucu seçer.
3 3 2 2 3128 246 1452 MAX: en büyüğü seçMIN: en küçüğüyapraklar (oyun sonu puanları)

Bu ağaç Russell & Norvig’in “Artificial Intelligence: A Modern Approach” kitabındaki klasik örnek. Sol hamle, rakip ne yaparsa yapsın en az 3 garanti eder.

Minimax adım adım

Kapı oyununun aynısı, bu kez bilgisayarın yaptığı sırayla: ağaç soldan sağa, önce derine gezilir; bir yaprağa varınca sayı yukarı taşınır. Turuncu düğüm = şu an bakılan yer, yeşil = değeri kesinleşti. “İleri ▶|” ile tek tek ilerleyin ve her adımda sıradaki sayıyı önce siz söyleyin.

XOX: asla kaybetmeyen rakip ❌⭕

  1. Köşeye oynayın. Boş karelerdeki sayılar YZ’nin her olası hamlesinin minimax değeri: kaç kare “kaybettirir” (kırmızı −)?
  2. YZ’yi yenmeye çalışın. Hata payı %0 iken mümkün mü? (Değil: XOX çözülmüş bir oyun.)
  3. Hata payını %30 yapın. Artık kazanabiliyor musunuz? Zorluk ayarı böyle yapılır: kusursuz YZ eğlenceli değildir (Y1, Y17).
  4. “alfa-beta”yı kapatıp açın: YZ’nin incelediği düğüm sayısı ilk hamlede kaç kat değişiyor?
  5. Değerler neden +9, +7 gibi? Derinlik cezası: YZ çabuk kazanmayı, mecbursa geç kaybetmeyi tercih eder (10 − derinlik).
🔎 DEMODA DENEYİN
  1. Köşeye oynayın. Boş karelerdeki sayılar YZ’nin her olası hamlesinin minimax değeri: kaç kare “kaybettirir” (kırmızı −)?
  2. YZ’yi yenmeye çalışın. Hata payı %0 iken mümkün mü? (Değil: XOX çözülmüş bir oyun.)
  3. Hata payını %30 yapın. Artık kazanabiliyor musunuz? Zorluk ayarı böyle yapılır: kusursuz YZ eğlenceli değildir (Y1, Y17).
  4. “alfa-beta”yı kapatıp açın: YZ’nin incelediği düğüm sayısı ilk hamlede kaç kat değişiyor?
  5. Değerler neden +9, +7 gibi? Derinlik cezası: YZ çabuk kazanmayı, mecbursa geç kaybetmeyi tercih eder (10 − derinlik).

🔗 Başka gözle: etkileşimli anlatımlar ve yazılar

Aynı konuyu başka bir anlatımla, kendi elinizle oynayarak görmek çok işe yarar. Kartlar yeni sekmede açılır; çoğu İngilizce ama görsel ve etkileşimli.

🔗 The Evolution of Trust
Nicky Case
Tekrarlanan mahkûm ikilemi; strateji, evrim ve oyun kuramı oynanabilir bir hikâye olarak.
🔗 cp-algorithms
cp-algorithms.com
Algoritmaların matematiksel ve kod düzeyinde ayrıntılı anlatımı (geometri, graf, veri yapıları).
Quiz 2 · minimax
Bir MIN düğümünün çocuklarının değerleri 7, 3, 9. MIN düğümünün değeri nedir ve neden?
MIN düğümünde sıra rakiptedir ve rakip bizim puanımızı en aza indirmek ister: 3. Ortalama almak, rakibin rastgele oynadığını varsaymak olurdu (bu, zarlı oyunlardaki “şans düğümü”nün yaptığı şeydir).
LEVEL 2
Alfa-beta budaması
aynı cevap, çok daha az iş
  • oyun ağacı nedir?
  • minimax
  • alfa-beta budaması
  • derinlik ve değerlendirme
  • Monte Carlo ağaç araması
  • kod ve laboratuvarlar
  • tarihten hikâyeler
  • kütüphaneler ve entegrasyon

Bütün sandıkları açmak şart mı? ✂

Aynı üç kapı. A kapısı 3 altın garanti etti. B kapısında açtığınız ilk sandıktan 2 çıktı: bekçi buradan en fazla 2 verir, yani B artık A’yı geçemez. B’nin kalan sandıklarında ne olduğunu bilmeye gerek var mı?

Alfa-beta: “bu dala bakmaya gerek yok”

  • α (alfa): MAX’ın şimdiye kadar garanti ettiği en iyi değer (alt sınır).
  • β (beta): MIN’in şimdiye kadar garanti ettiği en iyi değer (MAX için üst sınır).
  • Bir düğümde α ≥ β olursa, kalan çocuklar sonucu değiştiremez: budanır ✂.

Örnekteki ikinci MIN düğümü: ilk çocuğu 2. MIN bu dalda en fazla 2 verecek. Ama MAX solda zaten 3 garanti etti. Bu dalın geri kalanı ne olursa olsun MAX onu seçmez → 4 ve 6’ya bakmaya gerek yok.

Kapı oyununun diliyleα = “şu ana kadar bulduğum en iyi kapı kaç altın garanti ediyor?” (az önce: 3). β = “bekçi bu kapıdan en fazla kaç verir?” (B’de ilk sandıktan sonra: 2). Bekçinin verebileceği en fazla, elimdeki garantiyi geçemiyorsa (β ≤ α) o kapının kalan sandıkları açılmaz.

Alfa-beta adım adım ✂

Sıralama her şeydir

  • Alfa-beta her zaman minimax ile aynı sonucu verir; sadece daha az düğüm inceler.
  • Ne kadar budayacağı, hamleleri hangi sırayla denediğinize bağlı. En iyi hamle önce denenirse budama en fazladır.
  • Knuth & Moore (1975): en iyi sıralamada incelenen yaprak sayısı yaklaşık bd/2. Yani aynı sürede iki kat derin bakabilirsiniz!
satranç, b ≈ 35, d = 6yaprak sayısı
minimax35⁶ ≈ 1.838.265.625
alfa-beta (en iyi sıra)≈ 2 · 35³ ≈ 85.750
İyi sıralama nasıl yapılır?
  • Oyun bilgisi: Dört Bir Arada’da orta sütunlar önce; satrançta taş alan hamleler önce.
  • Bir önceki aramanın en iyi hamlesi önce (yinelemeli derinleştirme ile birlikte).
  • “Katil hamleler”: başka dallarda budamaya yol açmış hamleler önce.

Dört Bir Arada demosunda “hamle sıralaması” kutusunu kapatıp açarak düğüm sayısını karşılaştırabilirsiniz.

🎬 Ara: minimax ve alfa-beta, 11 dakikada

Algorithms Explained — minimax and alpha-beta pruning
Sebastian Lague · 11 dk · YouTube’da aç

Az önce kapı oyunuyla kurduğumuz iki fikrin aynısı, bu kez satranç benzeri bir oyunun ağacı üzerinde ve çok temiz çizimlerle. Videodaki beyaz düğümler bizim MAX’ımız (siz), siyahlar MIN (bekçi).

🤔 İzlerkenVideoda budanan ilk dal hangisi ve neden? Aynı durumu kapı oyununda hangi senaryoda gördük? Videonun sonunda hamle sıralaması için ne öneriliyor?
Quiz 3 · alfa-beta
Alfa-beta budaması açıkken YZ’nin seçtiği hamle, budamasız minimax’ın seçtiğinden farklı olabilir mi?
Alfa-beta kayıpsız bir optimizasyondur: kökün değeri birebir aynıdır. (Eşit değerli birden çok hamle varsa hangisinin “ilk bulunduğu” farklı olabilir ama değer aynıdır.) Sıralama sadece hızı etkiler.
LEVEL 3
Derinlik ve değerlendirme
ağacın sonuna gidemiyorsak?
  • oyun ağacı nedir?
  • minimax
  • alfa-beta budaması
  • derinlik ve değerlendirme
  • Monte Carlo ağaç araması
  • kod ve laboratuvarlar
  • tarihten hikâyeler
  • kütüphaneler ve entegrasyon

Sınırlı derinlik + değerlendirme fonksiyonu

  • Ağacın sonuna (oyun sonuna) inemiyorsak, d yarım hamle sonra dururuz ve konuma bir tahmini puan veririz.
  • Claude Shannon (1950): satranç için taş değerleri — piyon 1, at/fil 3, kale 5, vezir 9 — ve hareket serbestliği gibi ölçütler.
  • Dört Bir Arada: her 4’lük pencerede kendi 3’lüm (+5), 2’lim (+2), rakibin 3’lüsü (−4); orta sütundaki taşlar (+3). (Demodaki fonksiyon tam olarak bu.)
  • Değerlendirme fonksiyonu YZ’nin oyun bilgisidir: arama ne kadar derin olursa olsun, kötü bir değerlendirme kötü oynatır.
Ufuk etkisi (horizon effect)4 yarım hamle bakan bir YZ, 5. yarım hamlede vezirini kaybedeceğini görmez. Daha kötüsü: kaçınılmaz kaybı “ufkun ötesine” itmek için anlamsız hamleler yapabilir (ör. bir piyonu feda ederek veziri bir hamle daha “kurtarır”).
ÇarelerSakinlik araması (quiescence): taş alışverişi sürerken durma, sakin bir konuma kadar devam et. Seçmeli uzatma: şah, tehdit gibi durumlarda derinliği artır.

Gerçek motorların üç hilesi

Yinelemeli derinleştirmeÖnce derinlik 1, sonra 2, 3, 4… Süre bitince en son tamamlanan derinliğin cevabını oyna. Gereksiz gibi görünür ama sığ aramalar hamle sıralaması için bilgi verir; toplam maliyete etkisi küçüktür (son katman baskındır). Oyunlarda “düşünme süresi” böyle ayarlanır.
Geçiş tablosuAynı konuma farklı hamle sıralarıyla ulaşılır (e4 sonra d4 = d4 sonra e4). Hesaplanan konumları bir hash tablosunda sakla: tekrar gelince hazır cevabı kullan. Hash Tabloları sunumunun en güzel uygulamalarından!
Zobrist hashHer (taş, kare) çiftine rastgele 64 bitlik bir sayı ver; konumun hash’i, üzerindeki taşların sayılarının XOR’u. Bir hamle = iki XOR: hash’i sıfırdan hesaplamak gerekmez. 1970’ten beri bütün satranç motorlarında.

Bugünün en güçlü motoru Stockfish hâlâ alfa-beta tabanlıdır; 2020’den beri değerlendirme fonksiyonu küçük, hızlı bir sinir ağı (NNUE). Leela Chess Zero ise AlphaZero gibi MCTS + büyük sinir ağı kullanır.

Dört Bir Arada: alfa-beta’ya karşı oynayın 🔴🟡

  1. Derinlik 1 ile oynayın, sonra 5, sonra 7. YZ hangi derinlikte üçlü tuzaklarınızı görmeye başlıyor?
  2. Her YZ hamlesinden sonra üstteki sayılara bakın: her sütunun alfa-beta değeri. “KAZAN/KAYIP”: YZ kesin sonucu gördü.
  3. “Hamle sıralaması”nı kapatıp derinlik 6–7’de düğüm sayısını ve süreyi karşılaştırın.
  4. YZ’ye başlatın, ilk hamleyi nereye yapıyor? (Çözüm: başlayan oyuncu orta sütunla başlarsa kusursuz oyunda kazanır.)
  5. Derinlik 7’de bile bazen “aptalca” hamleler mi görüyorsunuz? Bu, ufuk etkisi ve değerlendirme fonksiyonunun sınırıdır.
  6. 🔗 Kusursuz oyuncuyla kıyaslayın: connect4.gamesolver.org her sütun için “kaç hamlede kazanılır/kaybedilir”i gösterir. Satranç için: Lichess analiz tahtası (tarayıcıda Stockfish).
🔎 DEMODA DENEYİN
  1. Derinlik 1 ile oynayın, sonra 5, sonra 7. YZ hangi derinlikte üçlü tuzaklarınızı görmeye başlıyor?
  2. Her YZ hamlesinden sonra üstteki sayılara bakın: her sütunun alfa-beta değeri. “KAZAN/KAYIP”: YZ kesin sonucu gördü.
  3. “Hamle sıralaması”nı kapatıp derinlik 6–7’de düğüm sayısını ve süreyi karşılaştırın.
  4. YZ’ye başlatın, ilk hamleyi nereye yapıyor? (Çözüm: başlayan oyuncu orta sütunla başlarsa kusursuz oyunda kazanır.)
  5. Derinlik 7’de bile bazen “aptalca” hamleler mi görüyorsunuz? Bu, ufuk etkisi ve değerlendirme fonksiyonunun sınırıdır.
  6. 🔗 Kusursuz oyuncuyla kıyaslayın: connect4.gamesolver.org her sütun için “kaç hamlede kazanılır/kaybedilir”i gösterir. Satranç için: Lichess analiz tahtası (tarayıcıda Stockfish).
LEVEL 4
Monte Carlo ağaç araması
değerlendirme bilmiyorsak: rastgele oyna, istatistik tut
  • oyun ağacı nedir?
  • minimax
  • alfa-beta budaması
  • derinlik ve değerlendirme
  • Monte Carlo ağaç araması
  • kod ve laboratuvarlar
  • tarihten hikâyeler
  • kütüphaneler ve entegrasyon

Go’nun sorunu ve MCTS’nin fikri

  • Go’da dallanma ~250 ve iyi bir değerlendirme fonksiyonu yazmak çok zor: “bu konum ne kadar iyi?” sorusuna ustalar bile sezgiyle cevap verir.
  • Fikir: konumu değerlendirmek yerine oradan rastgele binlerce oyun oynat. Kazanma oranı = konumun değeri. (Monte Carlo: kumarhanesiyle ünlü şehir; rastgele örnekleme yöntemlerinin adı.)
  • Akıllı kısım: oyunları umut vadeden dallara daha çok, ama arada az denenmiş dallara da harca. Bunun için bir ağaç büyütülür.
  • 2006: Rémi Coulom “Monte Carlo Tree Search” adını verdi (Crazy Stone); aynı yıl Kocsis & Szepesvári UCT formülünü yayımladı. Go programları birkaç yılda amatör ustalar seviyesine çıktı.
1 · Seçim 2 · Genişletme 3 · Simülasyon 4 · Geri yayılım UCB1’i en büyükçocuğa in (ağaçta) yaprağa yeni birçocuk ekle oyunun sonuna kadarrastgele oyna sonucu yol boyuncayukarı yaz (N, W) 7/12 5/8 2/4 3/5 0/0 kazanç / ziyaret

Önce basit hâli: hangi lokanta daha iyi? 🍜

Yeni bir şehre taşındınız; üç lokanta var ve hangisinin iyi olduğunu bilmiyorsunuz. 100 akşam yemek yiyeceksiniz. Bildiğiniz iyi yere mi gitmeli, yoksa az denediğinize bir şans daha mı vermeli? Üç stratejiyi sırayla oynatın ve memnun kalınan akşam sayılarını karşılaştırın.

UCB1: keşif mi, sömürü mü?

Seçim adımında her çocuk için:

$$\text{UCB1} = \underbrace{\frac{w}{n}}_{\text{ne kadar iyi}} + c\,\underbrace{\sqrt{\frac{\ln N}{n}}}_{\text{ne kadar az denendi}}$$

A: 6/80,75 + 0,76 = 1,51B: 1/20,50 + 1,52 = 2,02N = 10, c = √2 · mavi = kazanma oranı (sömürü), turuncu = keşif payı → B seçilir
  • w/n: o hamlenin kazanma oranı → sömürü (iyi olana yüklen)
  • ikinci terim: ebeveyn N kez ziyaret edildi, bu çocuk sadece n kez → keşif (az denenene şans ver)
  • c: dengeyi ayarlar; teoride √2 ≈ 1,41, pratikte deneyerek
  • Hiç denenmemiş çocuk (n = 0): önce o denenir
🎰 Çok kollu haydutKumarhanede 7 slot makinesi var, hangisinin daha çok ödediğini bilmiyorsunuz. Hep en iyi bildiğinizi çekerseniz, daha iyi bir makineyi hiç keşfedemeyebilirsiniz. Hep rastgele çekerseniz, iyi makineyi bildiğiniz hâlde para kaybedersiniz. UCB1 bu “çok kollu haydut” (multi-armed bandit) probleminin klasik çözümüdür; MCTS her ağaç düğümünü ayrı bir kumarhane gibi görür.
Oyunda başka nerede?Sturtevant (Game AI Pro 2, 25. bölüm): UCB1’i arama dışında da kullanmak mümkün; ör. bir dövüş oyununda hangi düşman stilinin bu oyuncuya karşı işe yaradığını oynadıkça öğrenmek.

MCTS’ye karşı oynayın 🎲

🎬 Ara: MCTS adım adım, elle

Monte Carlo Tree Search
John Levine (Strathclyde Üniversitesi) · 16 dk · YouTube’da aç

Seçim, genişletme, simülasyon ve geri yayılım adımlarının küçük bir ağaç üzerinde elle, sayılarla yapılışı. Lokanta örneğindeki UCB puanının ağacın her düğümünde nasıl kullanıldığını gösterir.

🤔 İzlerkenİlk dört yinelemede hangi düğümler seçiliyor ve neden? Hiç denenmemiş bir düğümün UCB puanı neden sonsuz? Lokanta örneğinde bunun karşılığı neydi?

MCTS: güçlü ve zayıf yanlar

👍 Güçlü
  • Değerlendirme fonksiyonu gerekmez: sadece kurallar ve oyun sonu.
  • Her an durdurulabilir (anytime): 100 ms verirseniz 100 ms’lik, 1 sn verirseniz daha iyi cevap. Zorluk ayarı = simülasyon sayısı.
  • Asimetrik büyür: umut vadeden dallar derin, kötüler sığ.
  • Eksik bilgili oyunlara uyarlanabilir (Information Set MCTS: kart oyunları).
👎 Zayıf
  • Taktik tuzaklar: tek bir doğru cevabı olan keskin konumlarda rastgele oyunlar yanıltıcıdır (Dört Bir Arada demosunda düşük simülasyonla görün).
  • Hızlı ve doğru bir ileri model ister: oyun durumunu kopyalayıp binlerce kez simüle edebilmelisiniz. Grafikle iç içe yazılmış oyun kodunda bu zor!
  • Rastgele oyunlar gerçekçi değilse sonuçlar yanlıdır; “akıllı” simülasyon politikaları gerekir.

AlphaGo’nun sırrı: MCTS’nin rastgele simülasyonlarını ve seçimlerini sinir ağlarıyla yönlendirmek (bir ağ “iyi hamleler”, diğeri “konum değeri” tahmin eder). Y13’te öğrenme tarafını göreceğiz.

Quiz 4 · MCTS
MCTS’de c (keşif katsayısı) çok büyük seçilirse ne olur?
c büyükse UCB1’in keşif terimi baskın olur: az denenmiş her hamle cazip görünür ve arama genişliğine yayılır. c çok küçükse ilk şanslı sonucu veren hamleye takılır kalır. İyi c değeri oyuna göre deneyerek bulunur.
LEVEL 5
Kod ve laboratuvarlar
bir oyun arayüzü, üç algoritma
  • oyun ağacı nedir?
  • minimax
  • alfa-beta budaması
  • derinlik ve değerlendirme
  • Monte Carlo ağaç araması
  • kod ve laboratuvarlar
  • tarihten hikâyeler
  • kütüphaneler ve entegrasyon

🎒 Ön bilgi: oyunu “kurallar”a ayırmak

Arama algoritması oyunun grafiğini bilmez; sadece şu dört soruyu sorar:

Moves(state)yapılabilecek hamleler
Apply(state, m) / Undohamleyi yap / geri al
IsOver(state)oyun bitti mi, kim kazandı?
Evaluate(state)bitmediyse tahmini puan

Bu dört fonksiyonu yazdığınız an minimax, alfa-beta ve MCTS oyununuzda çalışır. Oyunun durumunu salt veri (dizi, sınıf) olarak tutun; GameObject’lere, animasyonlara bağlamayın.

🎒 Kopyalamak mı, geri almak mı?Her dalda tahtanın kopyasını almak kolay ama yavaş (çok bellek). Yapıp geri almak (make/unmake) hızlıdır; satranç motorları böyle yapar. Demodaki Dört Bir Arada YZ’si taşı bırakıp aramadan sonra geri alıyor.
🎒 NegamaxMAX ve MIN için ayrı kod yazmak yerine: “benim için değer = −(rakip için değer)”. Tek fonksiyon, işaret değiştirerek. Kod örneklerinde bunu kullanıyoruz.

Minimax + alfa-beta (negamax biçimi) (1/2)

Minimax + alfa-beta (negamax biçimi) (2/2)

“100000 + depth”: kazanç ne kadar yakınsa o kadar iyi (kalan derinlik büyük). Böylece YZ kazanabilecekken oyunu uzatmaz.

MCTS (UCT): 40 satırlık kodun tamamı (1/2)

MCTS (UCT): 40 satırlık kodun tamamı (2/2)

Son satıra dikkat: en yüksek kazanma oranı değil, en çok ziyaret edilen hamle seçilir. Az denenmiş bir hamlenin %100 oranı şans eseri olabilir; çok ziyaret, çok güven demektir.

🎒 Kod sözlüğü

interface IGamearayüz“Bu metotları sağlayan her sınıf bir oyundur” sözleşmesi; arama algoritması sadece bunu bilir
out int winnerçıkış parametresiFonksiyon bool döndürürken ikinci bir değeri de geri verir
int.MinValue + 1en küçük tam sayı−∞ yerine; +1, işaret çevrilince taşmayı önler
-negamax(...)işaret çevirmeRakip için iyi olan, benim için kötüdür
math.inf · Infinitysonsuzα ve β’nın başlangıç değerleri
max(liste, key=...)anahtarla en büyükUCB1 değeri en büyük çocuğu seç
math.logdoğal logaritma (ln)UCB1 formülündeki ln N
game.copy()kopyaSimülasyon gerçek oyunu bozmasın

🌱 Isınma kodu: bu düğümün değeri ne?

Minimax’ın tek kuralı: sıra bizdeyse en büyüğü, rakipteyse en küçüğü. Ders kitabı ağacının alt satırı [3, 12, 8] → 3, [2, 4, 6] → 2, [14, 5, 2] → 2; kök [3, 2, 2] → 3.

🌱 Isınma kodu: ağaç ne kadar büyük?

Üstel büyümeyi parmaklarınızla hissedin: leafCount(30, 4) = 810.000, leafCount(30, 5) = 24 milyon. Bir for döngüsü ya da b ** d yeter. Satranç motorlarının neden budamak zorunda olduğunun cevabı bu sayı.

🧪 Canlı laboratuvar: değerlendirme fonksiyonu

Başlangıç kodu “taban YZ” ile aynı: sadece orta sütunu sayıyor. İki YZ de derinlik 3 alfa-beta. 4’lük pencerelerde kendi 3’lünüze (+5), 2’linize (+2), rakibin 3’lüsüne (−4) puan verin; 8 oyunluk turnuvayı kazanın. Sağda iki YZ sürekli maç yapıyor.

🐍 Laboratuvar: minimax

Ders kitabı ağacı (AIMA) kökte MAX iken 3, MIN iken 2 vermeli. Testlerde farklı derinlik ve dallanmada rastgele ağaçlar ve bir yaprağı doğrudan kök olan ağaç da var.

🐍 Laboratuvar: UCB1

Formül: w/n + c·√(ln N / n). Hiç ziyaret edilmemiş çocuk için None döndürün (gerçek kodda “önce bunu dene” = sonsuz). math.log doğal logaritmadır.
LEVEL 6
Tarihten hikâyeler
Turing’den AlphaGo’ya
  • oyun ağacı nedir?
  • minimax
  • alfa-beta budaması
  • derinlik ve değerlendirme
  • Monte Carlo ağaç araması
  • kod ve laboratuvarlar
  • tarihten hikâyeler
  • kütüphaneler ve entegrasyon

Kâğıt üzerinde satranç: Turing ve Shannon (1948–1952)

TurochampAlan Turing ve David Champernowne 1948’de bir satranç programının kurallarını tasarladı: Turochamp. O dönemin hiçbir bilgisayarı onu çalıştıramıyordu. Turing 1952 yazında programı elle, adım adım “çalıştırarak” Alick Glennie’ye karşı oynadı ve kaybetti. Kayıtlara geçen ilk bilgisayar satranç oyunu, bilgisayarsız oynandı.
Shannon 1950Claude Shannon “Programming a Computer for Playing Chess” makalesinde minimax’ı, değerlendirme fonksiyonunu (taş değerleri) ve iki stratejiyi tanımladı: A = her hamleye belli derinliğe kadar bak (kaba kuvvet), B = sadece umut vadeden hamlelere derin bak (seçici). Olası satranç oyunu sayısı için verdiği ~10¹²⁰ tahmini bugün “Shannon sayısı” olarak bilinir.
Alan Turing, 16 yaşında
Alan Turing (16 yaşında) · kamu malı, Wikimedia Commons
Claude Shannon
Claude Shannon · Konrad Jacobs, CC BY-SA 2.0 de

70 yıldır satranç motorlarının iskeleti Shannon’ın makalesindeki şemadır; değişen arama hızı, budama ve değerlendirme fonksiyonunun kalitesi.

Derin hikâye: Deep Blue ve 44. hamle (1997) ♟️

  • IBM’in Deep Blue’su, özel satranç yongalarıyla saniyede yüz milyonlarca konumu inceleyen dev bir alfa-beta makinesiydi. 1996’da Kasparov’a maçı kaybetti; 1997 rövanşında 3½–2½ kazandı.
  • Rövanşın ilk oyununun 44. hamlesinde Deep Blue, Kasparov’a anlamsız görünen bir kale hamlesi yaptı ve kısa süre sonra oyunu bıraktı.
  • Kasparov bu hamleye takıldı: “Makine bu kadar derin bir şey nasıl görebilir?” Sonraki oyunlarda Deep Blue’nun insan müdahalesiyle oynadığından şüphelendi; psikolojik olarak dengesi bozuldu.
  • Yıllar sonra ortaya atılan iddia (Nate Silver’ın “The Signal and the Noise” kitabıyla yayıldı): o hamle bir yazılım hatasının sonucuydu. Deep Blue iyi bir hamle belirleyemeyince “güvenli mod”a düşüp rastgele bir yasal hamle yapmıştı.
Deep Blue dolabı, Computer History Museum
Deep Blue’nun iki dolabından biri (Computer History Museum) · James the photographer, CC BY 2.0
⚠️ Efsane mi, gerçek mi?Hata iddiası Deep Blue ekibinden Murray Campbell’a dayandırılır; Wikipedia da “iddia edilen” (allegedly) der. Kasparov’un maçı bu yüzden kaybettiği ise tartışmalı: sonraki analizler daha çok Kasparov’un alışılmadık hatalarına işaret eder. Bunu kesin bir gerçek olarak değil, güzel bir uyarı olarak anlatın.
💡 DersOyuncular, YZ’nin anlamadıkları hamlelerine derin bir anlam yükler (Y1: zekâ yanılsaması). Bir hata, dâhice görünebilir.

Chinook ve Marion Tinsley: dama çözüldü (1990–2007)

  • Alberta Üniversitesi’nden Jonathan Schaeffer’ın ekibi Chinook’u yazdı: açılış kitabı, derin alfa-beta, iyi bir değerlendirme ve 8 taşa kadar bütün oyun sonlarının veritabanı.
  • Rakibi Marion Tinsley, tarihin en büyük dama oyuncusu sayılır. 1992 maçını Tinsley 4–2 kazandı (33 beraberlik).
  • 1994 rövanşında altı berabere oyundan sonra Tinsley pankreas kanseri nedeniyle maçtan çekildi; Chinook insanlara karşı dünya şampiyonluğu kazanan ilk program oldu — ama Tinsley’i hiç yenemedi. Tinsley 1995’te öldü.
  • Schaeffer, Chinook’u yarışmalardan çekip damayı çözmeye karar verdi. 2007’de Science dergisinde yayımladılar: iki taraf kusursuz oynarsa dama berabere biter.
💡 Ders“Oyunu çözmek” = her konumun kusursuz oyundaki sonucunu bilmek. XOX ve Dört Bir Arada çözüldü; dama 18 yıllık hesaplamayla çözüldü; satranç ve Go’nun çözülmesi bugünkü bilgisayarlarla mümkün görünmüyor. Bu yüzden onlarda sezgisel (değerlendirme, örnekleme) yöntemlere muhtacız.

📸 Lee Sedol – AlphaGo, 2. oyun (2016)

Lee Sedol – AlphaGo 2. oyunun kaydı
Oyun kaydı: Wesalius, Wikimedia Commons, CC BY-SA 4.0

Bütün oyunun kaydı: taşların üstündeki sayı hamle sırası. AlphaGo siyah, Lee Sedol beyaz.

Sağ tarafta, O10 noktasındaki siyah 37: beşinci sıraya yapılan bir “omuz vuruşu”. Go’da yüzyıllardır “beşinci sırada omuz vuruşu yapılmaz” diye öğretilir; yorumcular önce hata sandı.

Yüzlerce hamle sonra bu taşın sağ taraftaki savaşı AlphaGo lehine çevirdiği anlaşıldı. AlphaGo’nun kendi tahmini: bir insanın bu hamleyi oynama olasılığı yaklaşık on binde bir.

Sonraki slayt hikâyenin geri kalanı ve arkasındaki teknik: MCTS + sinir ağları.

AlphaGo ve 37. hamle (2016) ⚫⚪

  • DeepMind’ın AlphaGo’su, dünyanın en iyilerinden Lee Sedol ile beş oyunluk maç yaptı ve 4–1 kazandı.
  • 2. oyun, 37. hamle: AlphaGo beşinci sıraya bir “omuz vuruşu” yaptı. Yorumcular önce hata sandı; profesyonellerin aklına gelmeyecek bir hamleydi. Michael Redmond (9 dan) hamleyi “yaratıcı” ve “benzersiz” diye niteledi; Lee cevap vermek için alışılmadık uzun süre düşündü.
  • 4. oyun, 78. hamle: Lee Sedol’un hamlesi AlphaGo’yu şaşırttı ve AlphaGo maçtaki tek oyununu kaybetti. Bu hamle de Go dünyasında “tanrısal hamle” olarak anıldı.
  • Teknik olarak: MCTS + hamle olasılıklarını ve konum değerini tahmin eden derin sinir ağları. 2017’de AlphaZero, insan oyunu görmeden sadece kendine karşı oynayarak satranç, shogi ve Go öğrendi.
🎬 İzleyinAlphaGo — The Movie (tam belgesel, Google DeepMind). Lee Sedol’un 78. hamle anı ve ekibin tepkisi, yapay zekâ tarihinin en duygusal sahnelerinden.
SonrasıLee Sedol 2019’da profesyonel Go’dan emekli olurken, YZ’nin “yenilemeyecek bir varlık” olduğunu söyledi. Bugün Go oyuncuları YZ ile antrenman yapıyor ve 37. hamle tarzı hamleleri insan oyununa taşıdılar.

Video oyunlarında arama

Total War: Rome II (2013)Creative Assembly, kampanya yapay zekâsının “görev yönetimi” kısmında MCTS tabanlı bir planlayıcı kullandı: az sayıda ordu/kaynak çok sayıda göreve nasıl dağıtılır? Arama uzayı büyük, yol bulma sorguları pahalı; MCTS sabit bir en kötü durum süresi sağladı (Yannakakis & Togelius ders notlarından).
Berlin ve Xenonauts 2Gijs-Jan Roelofs (Game AI Pro 3, 28. bölüm): Risk benzeri Berlin’de MCTS, utility + davranış ağacı tabanlı en iyi hiyerarşik YZ’ye karşı %73 galibiyet, %15 beraberlik aldı ve oyuncuların yeni stratejilerine elle ayar yapılmadan uyum sağladı. Aynı teknikler XCOM benzeri Xenonauts 2’de denendi.
Kart oyunlarıEksik bilgili oyunlarda “bilgi kümeli MCTS” (ISMCTS): rakibin elini bilmediğiniz için olası elleri örnekleyip her biri için arama yapar. Mobil kart oyunlarında ticari olarak kullanıldı (ör. AI Factory’nin Spades’i üzerine yayımlanmış AIIDE 2013 çalışması).
Platform oyunu bile!“Monte Mario” (Jacobsen, Greve, Togelius, 2014): Mario’yu MCTS ile oynatmak. A* bu ortamda neredeyse kusursuzdu; ama hamlelerin %20’si rastgele bozulunca A* çöktü, MCTS çok daha iyi dayandı. Belirsizlik varsa örnekleme kazanır.
LEVEL 7
Kütüphaneler ve entegrasyon
kendi oyununuza rakip eklemek
  • oyun ağacı nedir?
  • minimax
  • alfa-beta budaması
  • derinlik ve değerlendirme
  • Monte Carlo ağaç araması
  • kod ve laboratuvarlar
  • tarihten hikâyeler
  • kütüphaneler ve entegrasyon

🧰 Kütüphaneler ve araçlar

adplatformne yapar / sınırlarınasıl eklenir
python-chessPython · açık kaynakSatranç kuralları, hamle üretimi, PGN/FEN, UCI motorlarıyla (Stockfish) konuşma. Kendi motorunuz için hazır kurallar.pip install chess
StockfishC++ motor · açık kaynak (GPL)Dünyanın en güçlü açık kaynak satranç motoru (alfa-beta + NNUE). Oyununuza UCI protokolüyle ayrı bir süreç olarak bağlanır. Zorluk: “Skill Level” ve düşünme süresi.İndir, UCI ile çalıştır; lisans koşullarına dikkat
chess.jsJavaScript · açık kaynakTarayıcıda satranç kuralları, hamle doğrulama; arama yok — üstüne kendi alfa-beta’nızı yazarsınız.npm install chess.js
easyAIPython · açık kaynakİki oyunculu oyunlar için küçük çerçeve: oyununuzu bir sınıf olarak tanımlarsınız, Negamax/SSS* hazır gelir. Dört Bir Arada, Nim örnekleri.pip install easyAI
OpenSpielPython/C++ · açık kaynak (DeepMind)Onlarca oyun (Go, poker, tavla…) ve algoritma: minimax, alfa-beta, MCTS, CFR, AlphaZero tarzı öğrenme. Araştırma ve deney için.pip install open_spiel
LudiiJava · ücretsizBinden fazla geleneksel oyun (mancala türleri dahil) ve genel oyun oynayan YZ’ler (MCTS). Oyun tanımı dili ile kendi oyununuzu yazıp YZ’ye oynatabilirsiniz.Sitesinden indir
Kendi kodunuz (Unity/Godot)her motorMasa oyunu uyarlamalarında en yaygın yol: oyun durumunu saf C#/GDScript sınıfı yapıp bu sunumdaki negamax’ı ya da MCTS’yi yazmak. Motorlarda yerleşik oyun ağacı araması yok.—

Chessprogramming wiki, arama tekniklerinin (sıralama, geçiş tablosu, Zobrist, sakinlik araması) en kapsamlı ücretsiz kaynağıdır; satranç dışı oyunlar için de geçerlidir.

🧩 Oyununuza arama tabanlı rakip eklerken

  1. Kuralları görselden ayırın: GameState saf veri; Moves, Apply/Undo, Winner. Görsel katman sadece bu durumu çizer.
  2. Önce doğruluk: rastgele hamle yapan bir YZ ile binlerce oyun oynatıp kural hatası arayın (bir tür otomatik test).
  3. Sonra arama: küçük oyunda minimax, büyükte alfa-beta + değerlendirme ya da MCTS.
  4. Zaman bütçesi: aramayı ana iş parçacığını dondurmadan yapın (Unity: coroutine/Job/Task; tarayıcı: Web Worker). Yinelemeli derinleştirme ile süre dolunca dur.
  5. Zorluk: derinlik, simülasyon sayısı, bilerek hata (demodaki gibi), “en iyi 3 hamleden rastgele”.
Eğlenceli rakip ≠ en güçlü rakipKusursuz bir XOX YZ’si oyuncuyu sıkar. Y17’de dinamik zorluğu göreceğiz; arama tabanlı YZ’lerde en kolay düğme: arama bütçesi.
⚙️ PerformansTahtayı bit maskeleriyle tutmak (bitboard), hamleleri sıralamak ve geçiş tablosu çoğu zaman algoritmayı değiştirmekten daha çok hız kazandırır. Önce ölçün (Y18).

🤖 Bu konuyu bir YZ kod asistanıyla yazarken

Sık yapılan hatalar — kontrol edin
  • Undo’yu unutmak ya da eksik yapmak: tahta bozulur, YZ “hayalet taşlar” görür
  • Kazanç puanını derinlikten bağımsız vermek: YZ kazanmayı erteler
  • Alfa-beta’da α ve β’yı negamax’ta yer değiştirmeden geçirmek
  • MCTS’de kazancı yanlış oyuncu açısından yazmak (YZ rakibi için oynar!)
  • Değerlendirme fonksiyonunu oyuncudan bağımsız yazmak (hep oyuncu 1’e göre)
İyi bir istek (prompt) örneği

“Unity 6, C#. Dört Bir Arada (6×7) için saf C# bir GameState sınıfı yaz (bit maskesiz, int[42] yeterli): Moves (orta sütun önce), Apply, Undo, Winner. Negamax + alfa-beta ile derinlik sınırlı arama ve yinelemeli derinleştirme ekle; süre bütçesi 200 ms, ana iş parçacığını dondurmamak için Task.Run kullan. Değerlendirme: 4’lük pencerelerde 3’lü +5, 2’li +2, rakip 3’lü −4, orta sütun taşı +3. Kazanç 100000 + kalan derinlik. Rastgele oyunlarla 1000 maç oynatıp Undo’nun tahtayı bozmadığını doğrulayan bir test de yaz.”

  • Oyun kurallarını (hamleler, kazanma, beraberlik) siz net yazın; asistan bunları sık atlar
  • Negamax mı ayrı MAX/MIN mi istediğinizi, kazanç puanının derinlikle nasıl ölçekleneceğini belirtin
  • Undo’nun doğru çalıştığını test eden bir kod isteyin
  • Aramayı ana iş parçacığı dışında, süre sınırlı yapmasını isteyin

🔬 Araştırma ucu

AlphaZero → MuZeroAlphaZero kuralları bilip kendine karşı oynayarak öğrendi. MuZero (2020) kuralları bile bilmeden, oyunun bir modelini öğrenip onun içinde MCTS yaptı; Atari oyunlarında da çalıştı. “İleri model” sorununu öğrenmeyle çözmek.
Genel oyun oynamaTek bir YZ’nin daha önce görmediği oyunları kuralları okuyarak oynaması (General Game Playing, GVGAI yarışmaları, Ludii). MCTS bu alanın ana aracı, çünkü değerlendirme fonksiyonu gerektirmez.
Dil modelleri ve masa oyunlarıBüyük dil modelleri satranç gibi oyunlarda sıklıkla kural dışı hamleler önerir; bu yüzden oyunlarda LLM’i bir arama motoruna “danışan” ya da hamle açıklayan bir yardımcı olarak kullanmak daha güvenlidir (Y14).

💬 Tartışma soruları

Yanınızdakiyle 2 dakika konuşun, sonra sınıfça tartışalım
  1. XOX’u asla kaybetmeyen bir rakibe karşı oynamak eğlenceli mi? Demodaki “hata payı” kaydırıcısını bir oyunda zorluk seviyesi olarak sunsaydınız kolay/orta/zor için hangi değerleri seçerdiniz?
  2. Deep Blue’nun 44. hamlesi belki de bir hataydı ama Kasparov onu deha sandı. Bir oyunun YZ’si “hata yapınca” oyuncuların bunu strateji sandığı bir an hatırlıyor musunuz?
  3. Satrançta iyi bir değerlendirme fonksiyonu yazmak kolay (taş say), Go’da çok zor. Sevdiğiniz bir sıra tabanlı oyun için “bu konum ne kadar iyi?” sorusuna üç ölçüt yazın.
  4. Bir strateji oyununun YZ’si 10 hamle ilerisini kusursuz görseydi, hile yapmadan bile oyuncular ona “hileci” der miydi? Neden?

🚀 Proje ve araştırma önerileri

  1. [kolay] Kusurlu XOX — p5.js’te XOX + minimax; üç zorluk: kusursuz, %20 hata, “en iyi 2 hamleden rastgele”. Arkadaşlarınızla test edin: hangisi en eğlenceli?
  2. [kolay] Nim / çubuk oyunu — easyAI ile Nim; sonra aynı oyunu kendi minimax’ınızla yazıp karşılaştırın.
  3. [orta] Mangala YZ’si 🇹🇷 — Mangala kurallarını saf veri olarak yazın; alfa-beta + değerlendirme (hazinedeki taş farkı, sıradaki tekrar hakkı). Unity ya da web arayüzü.
  4. [orta] Dört Bir Arada turnuvası — Sınıfça değerlendirme fonksiyonu yarışması: bu sunumdaki laboratuvarın genişletilmiş hâli, derinlik sabit.
  5. [zor] Tavla: expectiminimax — Zar düğümleri ekleyerek minimax’ı genişletin (21 farklı zar sonucu ve olasılıkları). Derinlik 2 bile ne kadar pahalı?
  6. [araştırma] Okey için ISMCTS — Okey’de rakip elleri bilinmiyor: olası elleri örnekleyen MCTS ile basit bir okey botu. Kural tabanlı bota karşı kazanma oranı?
  7. [araştırma] MCTS vs alfa-beta — Aynı oyunda eşit süre bütçesiyle iki yöntemi yarıştırın; tahtanın büyüklüğünü (Dört Bir Arada 6×7 → 8×9) arttırdıkça hangisi öne geçiyor?

Neler öğrendik? 🎒

  • Oyun ağacı: konumlar ve hamleler; büyüklük ≈ bd.
  • Minimax: rakip en iyisini oynar; MAX en büyük, MIN en küçük.
  • Alfa-beta: aynı sonuç, çok daha az düğüm; iyi sıralamayla ~bd/2.
  • Derinlik + değerlendirme, ufuk etkisi, yinelemeli derinleştirme, geçiş tablosu, Zobrist.
  • MCTS: seçim, genişletme, simülasyon, geri yayılım; UCB1.
  • Hikâyeler: Turochamp, Shannon, Deep Blue’nun 44. hamlesi, Chinook ve Tinsley, AlphaGo’nun 37. hamlesi.
  • Oyunlar: Total War: Rome II, Berlin, Xenonauts 2, kart oyunları.
  • Araçlar: python-chess, Stockfish, chess.js, easyAI, OpenSpiel, Ludii.
  • Sonraki bölüm: hareket — önce steering davranışları.

🎮 Bu sunumdaki oyunlar

Adı geçen oyunu tanımıyorsanız: oyuncuların kullandığı wiki sayfası ve oyunu kısaca gösteren bir video. ▶ video slaydın üstünde açılır (Esc ile kapanır); 🎯 işaretli bağlantılar doğrudan bu sunumdaki konuya gider.

Hearthstone 2014 · dijital kart oyunu
Warcraft evreninde sıra tabanlı kart oyunu; rakibin elini göremezsiniz.
📖 wiki.gg wikisi · ▶ video 1:12
XCOM: Enemy Unknown 2012 · sıra tabanlı taktik
Uzaylı istilasına karşı küçük bir mangayı yönetirsiniz; her atış bir yüzde.
📖 Fandom wikisi · ▶ video 1:39
Total War: Rome II 2013 · strateji
Sıra tabanlı kampanya ile gerçek zamanlı dev savaşları birleştiren strateji oyunu.
📖 Fandom wikisi · ▶ video 2:50

Kaynaklar: videolar 🎬

Algorithms Explained — minimax and alpha-beta pruning
Sebastian Lague Coding Adventure: Chess
Sebastian Lague Monte Carlo Tree Search
John Levine Search: Games, Minimax, and Alpha-Beta (MIT 6.034)
MIT OpenCourseWare AlphaGo — The Movie (tam belgesel)
Google DeepMind This game theory problem will change the way you see the world
Veritasium

📄 Akademik okumalar

Shannon 1950 · Programming a Computer for Playing Chess (Philosophical Magazine 41)
Minimax, değerlendirme fonksiyonu, A/B stratejileri.
Knuth & Moore 1975 · An Analysis of Alpha-Beta Pruning (Artificial Intelligence 6(4))
Alfa-beta’nın en iyi durumda b^(d/2) analizi.
Kocsis & Szepesvári 2006 · Bandit Based Monte-Carlo Planning (ECML 2006)
UCT: UCB1’in ağaca uygulanması.
Coulom 2006 · Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search (Computers and Games 2006)
MCTS adının doğduğu makale (Crazy Stone).
Browne vd. 2012 · A Survey of Monte Carlo Tree Search Methods (IEEE TCIAIG 4(1))
Alanın en çok atıf alan taraması.
Silver vd. 2016 · Mastering the game of Go with deep neural networks and tree search (Nature 529)
AlphaGo.
Schaeffer vd. 2007 · Checkers Is Solved (Science 317)
Damanın çözümü (Chinook proje sayfası).
Roelofs 2017 · Pitfalls and Solutions When Using MCTS for Strategy and Tactical Games (Game AI Pro 3, Bölüm 28)
Strateji oyunlarında MCTS: Berlin, Xenonauts 2.
Sturtevant 2015 · Monte Carlo Tree Search and Related Algorithms for Games (Game AI Pro 2, Bölüm 25)
UCB1’den UCT’ye, oyun içi kullanım fikirleri.

Kaynaklar: okuma 📚

NEXT LEVEL ▶
Steering Davranışları
Craig Reynolds’ın kuşları: ara, kaç, dolaş, kalabalıkta yürü
SONRAKİ SUNUM ▶