Açılışta bana denk, oyun sonunda çaresiz bir satranç programı

Satranç programını 2007’de, lisedeyken yazdım. O sırada rekabetçi satranç oynuyordum, yani karşısına oturup ne kadar iyi oynadığını ölçecek biri hazırdı: ben. 2006 ve 2007’de Ulusal Bilgisayar Olimpiyatı kamplarına seçilmiştim — yılda 15 kişi alınıyordu — dolayısıyla algoritma yazmak o yaşta tanımadığım bir iş değildi.

Bir satranç programı satrancı bilmez, sayar. Elindeki tek yetenek şudur: bir pozisyondan çıkan bütün hamleleri üretmek, her birinin ardından rakibin en iyi cevabını varsaymak, sonra aynı işi bir kat daha derinde tekrarlamak. Minimax budur. Geri kalan her şey — alfa-beta budama, iteratif derinleştirme, hamle sıralaması, pozisyon hash’leme — aynı ağacın içinde daha derine inebilmek için harcanan çabadır.

Ağaç neden bu kadar pahalı

Bir pozisyondan onlarca yasal hamle çıkar. Her hamlenin ardından rakip için yine onlarca hamle çıkar. Bir kat daha derine bakmak hesabı ikiye katlamaz, onlarca katına çıkarır. Programın gücü doğrudan kaç kat derine inebildiğine bağlı olduğu için, bütün mühendislik bu çarpanı kırmaya çalışmaktan ibaret.

Alfa-beta budama, sonucu değiştiremeyeceği kesinleşmiş dalları hiç açmamaya yarar. Bir hamleye karşı rakibin, o hamleyi şimdiye kadar bulduğunuz en iyi seçeneğin altına düşüren tek bir cevabı varsa, o dalın geri kalanını incelemenin anlamı yoktur; kalan hamleler ne kadar iyi olursa olsun o dalı zaten seçmeyeceksiniz.

Buradaki asıl mesele algoritma değil, sıra. İyi hamleyi ilk denerseniz geri kalanların çoğu tek adımda elenir. Kötü hamleyi ilk denerseniz hiçbir şey elenmez ve düz minimax kadar iş yaparsınız. Yani budamanın hızı budama kodundan değil, hangi hamleyi önce deneyeceğinize dair tahminden gelir. Uyarlanabilir hamle sıralaması tam olarak bu tahmini iyileştirmek için vardı.

İteratif derinleştirme ilk bakışta israf gibi durur: önce bir kat derinlikte arıyorsunuz, sonra baştan iki kat, sonra baştan üç. Aynı işi tekrar tekrar yapıyorsunuz. İki nedenle işe yarıyor. Birincisi, süre dolduğunda elinizde her zaman oynanabilir bir hamle oluyor; arama yarıda kesilse bile bir önceki turun cevabı hazır duruyor. İkincisi, önceki turun sonuçları bir sonraki turun sıralamasını besliyor. Tekrar ettiğiniz iş, tekrar etmediğiniz işi ucuzlatıyor.

Pozisyon hash’leme ise ağacın aynı yaprağa farklı yollardan varmasıyla ilgili. İki hamleyi ters sırayla oynarsanız tahta çoğu zaman aynı yere gelir; program bunu bilmiyorsa aynı pozisyonu ikinci kez baştan hesaplar. Pozisyonları hash’leyip bir kez hesaplanmış sonucu saklamak, ağacın kendini tekrar eden kısmını ağaç olmaktan çıkarıp tabloya çeviriyor.

Ağacın ucundaki sayı

Bütün bu yöntemler tek bir şeyi büyütür: ne kadar derine bakabildiğinizi. Ama aramanın en ucunda birinin durup “bu pozisyon şu kadar iyi” demesi gerekiyor ve o kişi sizsiniz. Gelişmiş bir değerlendirme fonksiyonu yazmak, satranç hakkında bildiğinizi sandığınız her şeyi tek bir sayıya indirmeye çalışmaktır.

Bir tahtaya bakıp iyi ya da kötü demek insan için kolaydır. Aynı yargıyı yazıya dökmeye oturduğunuzda, bildiklerinizin ne kadar azının yazılabilir olduğunu görürsünüz. Programın oynadığı satrancın kalitesi, aramanın kalitesi kadar bu fonksiyonun kalitesiydi; derine inmek, ucundaki sayı yanlışsa yalnızca yanlışa daha emin varmanızı sağlıyor.

Ne kadar iyi oynadı

Açılışta ve orta oyunda benim kadar iyi oynuyordu. Bunu övünmek için değil, ölçüt olarak yazıyorum — ve zayıf bir ölçüt olduğunu biliyorum. Elimde bir puan, bir turnuva sonucu, başka bir programla oynanmış tek bir maç kaydı yok. Bugün geriye dönüp verebileceğim tek ölçü, o yıllarda kendi oynadığım seviyeydi.

Ölçünün zayıflığının bir sebebi daha var. Değerlendirme fonksiyonuna koyduğum şey benim satranç anlayışımdı. Kendi anlayışınızı kodladığınız bir rakiple oynadığınızda, aynı anlayışın iki kopyası karşı karşıya gelir: programın kör noktaları sizinkilerle aynı yerdedir. Böyle bir maç, programın ne kadar iyi olduğunu değil, sizinle ne kadar tutarlı olduğunu ölçer.

Oyun sonu neden çöktü

Program oyun sonunda rekabetçi değildi. Sezgi tersini söyler: tahtada taş azaldıkça iş kolaylaşmalı.

Orta oyunda tahta doludur. Alımlar, tehditler ve baskı, değerlendirme fonksiyonuna bakacak somut bir şey verir; alfa-beta da bu yoğunlukta çok sayıda dal keser. Oyun sonunda ise geriye birkaç taş kalır ama her biri tahtanın her yerine gidebilir. Kazanç ile beraberlik arasındaki fark çoğu zaman onlarca hamle ötededir ve arada gezinen bütün pozisyonlar birbirine yakın puanlanır. Değerlendirme fonksiyonunun ayırt edecek bir şeyi yoksa budamanın da budayacak bir şeyi kalmıyor. Arama uzayı tam da taşlar azaldığında elinizde büyüyor.

Bu problemin bilinen çözümü aramak değil, bakmak: az taşlı bütün pozisyonların sonucunu önceden hesaplayıp saklayan büyük bir oyun sonu veritabanı. Program o noktada hesaplamayı bırakır, tabloya bakar. Ben o veritabanını kurmadım. Kurmak ve saklamak pahalıya mal olacaktı, ben de o kısmı atladım.

Bunu bir uzlaşma olarak anlatmayacağım, çünkü değildi. Programın tavanını arama algoritması değil, yazmadığım tablo belirledi ve bunu atlarken de biliyordum. Kendi zamanından başka bütçesi olmayan bir lise öğrencisi için makul bir karardı. Sonucu da açık: uçtan uca satranç oynayan bir program yazmadım, iyi bir orta oyun programı yazdım.

Bugüne kalan iki şey

Birincisi sıralama meselesi. Alfa-beta’dan aldığım kazanç, budama kodunun kendisinden değil, hangi hamleyi önce deneyeceğime dair tahminden geliyordu. O günden beri bir eleme adımı kurduğumda hızın nereden geldiğine bakıyorum: çoğu zaman elemeyi yapan koddan değil, elemenin önündeki sıralamadan gelir. Sıralamayı iyileştirmek, elemeyi iyileştirmekten neredeyse her zaman daha ucuzdur.

İkincisi arama ile tablo arasındaki fark. Arama size genellik verir; her pozisyonda söyleyecek bir sözü vardır, ama derinleştikçe pahalılaşır. Tablo, aramanın ulaşamadığı yerde kesinlik verir, karşılığında bedeli önden ister. Zor problemlerin çoğu ikisini birden istiyor, ve asıl karar hangi kısmın hesaba hangi kısmın tabloya düşeceğidir. Ben o kararı 2007’de tabloyu hiç yazmayarak verdim; programın nerede biteceğini de o karar belirledi.

Geliştirirken çok eğlendim. Bunu yazmanın daha ağırbaşlı bir yolu yok: bir tahtayı sayıya çevirmeye çalıştığım o yıl, o zamandan beri yaptığım işlerin çoğuna şaşırtıcı derecede benziyordu.