Dama matematiksel olarak çözüldü mü? 18 yıllık hesaplama beraberliği nasıl kanıtladı ve oyuncular için ne anlama geliyor

Yüzyıllar boyunca kahvehanelerde, kulüplerde ve şampiyona salonlarında dama oynayan ustalar ile araştırmacılar aynı temel sorunun yanıtını aradı: Dama tahtasında oynanan bir partinin kaderi daha ilk hamlede matematiksel olarak çizilmiş midir? Altmış dört karelik tahta başına oturan iki usta hiçbir hata yapmadan hamleleri sıralarsa, ilk başlayan taraf kaçınılmaz bir üstünlük elde eder mi? İkinci oyuncu sürekli bir dezavantajın yükünü mü taşır? Yoksa oyun, iki tarafın kusursuz hamleleriyle mutlak bir dengede mi sonuçlanır?

2007 yılının Temmuz ayında prestijli bilim dergisi Science bünyesinde yayımlanan tarihi bir makale bu tartışmaları kesin bir sonuca bağladı^[1]. Alberta Üniversitesinden bilgisayar bilimci Jonathan Schaeffer önderliğindeki uluslararası bir araştırma grubu, 8×8 tahtada oynanan İngiliz damasının resmen çözüldüğünü duyurdu. 1989 yılında başlatılan ve 18 yıl süren aralıksız bir hesaplama maratonunun ardından Chinook adlı yazılım şu gerçeği matematiksel olarak kanıtladı: Her iki taraf da en iyi hamleleri yaptığında, geleneksel İngiliz daması zorunlu bir beraberlikle biter.

Bu bilimsel netice dama oyununu ortadan kaldırmadı. Aksine, oyun teorisinin “çözüm” kavramıyla neyi kastettiğini anlamak, online masalarda veya dost sohbetlerinde taş sürmenin neden hâlâ büyük bir zevk olduğunu açıkça gösterir.

Oyun teorisinde bir oyunun çözülmesi ne anlama gelir?

Gündelik dilde bir bilmeceyi çözmek, onu kolay kılan püf noktasını yakalamak demektir. Ancak yapay zekâ ve kombinatoryal oyun teorisinde bu kavram, 1994 yılında araştırmacı Victor Allis tarafından belirlenen kesin matematiksel temellere dayanır^[2]. Allis, tam bilgiye dayalı iki kişilik sonlu oyunları 3 farklı çözüm kademesine ayırmıştır:

1. Ultra zayıf çözüm. Oyunun başlangıç konumundan itibaren ilk oyuncunun mu, ikinci oyuncunun mu kazanacağını ya da oyunun berabere mi biteceğini ispatlayan, fakat bunu sağlayacak somut bir hamle dizisi veya algoritma sunmayan teorik kanıttır. Bunun en bilinen örneği Hex oyunudur: Oyun teorisi strateji çalma mantığıyla ilk oyuncunun teorik bir galibiyeti olduğunu kanıtlar, fakat geniş tahtalarda bu galibiyeti getiren hamleleri tek tek gösteremez.
2. Zayıf çözüm. Başlangıç konumundan itibaren rakibin atacağı her adıma karşı en azından beraberliği ya da galibiyeti garanti eden somut bir algoritma veya kanıt ağacı sağlayan çözümdür. Program, mantıksız ve ağır hatalardan doğan absürt pozisyonların kesin değerini hafızasında tutmayabilir; ancak başlangıç çizgisinden itibaren hiçbir koşulda mağlup edilemez. Dama tam olarak bu kategoridedir^[1].
3. Güçlü çözüm. Kural dahilinde ulaşılabilecek her bir tahta konumu için, daha önce yapılmış hatalara bakılmaksızın en doğru hamleyi ve matematiksel sonucu anında hesaplayan algoritmadır. Dörtlü dizmece oyunu olan Connect Four, 1988 yılında güçlü biçimde çözülmüştür: İlk oyuncu doğru hamlelerle her durumdan galibiyeti zorlayabilir^[2].

İngiliz daması güçlü değil, zayıf biçimde çözülmüştür; çünkü ortaya çıkabilecek her saçma sapan konumu hafızada saklamak astronomik bir depolama alanı gerektirirdi. Schaeffer ve ekibi, resmi başlangıç diziliminden varılacak sonuca odaklandı. Tahtada 32 koyu kare üzerinde 12 koyu renkli taş ile 12 açık renkli taş karşı karşıya gelir ve toplamda 24 taş oyuna başlar^[3].

18 yıllık dev hesaplama: Chinook damayı nasıl çözdü?

Damanın hesaplama evreni, dışarıdan görünen basit kuralların çok ötesindedir. Standart bir 8×8 tahta üzerinde oluşabilecek kurala uygun pozisyon sayısı yaklaşık 5 × 10^20 adettir^[1]. Bu sayı kabaca yarım kentilyon duruma karşılık gelir. Tek bir masaüstü bilgisayar bu durumları tek tek incelemeye kalksaydı, işlem binlerce yıl sürerdi.

Bu devasa arama uzayını dize getirmek için bilim insanları iki yönlü bir yöntem geliştirdi: Oyun sonlarından geriye doğru hesaplama yapmak ve açılıştan ileriye doğru arama ağaçları kurmak.

Geriye doğru analiz ve 39 trilyonluk oyun sonu kütüphanesi

Kanıtın en sağlam basamağını geriye doğru analiz yöntemi oluşturdu. Araştırmacılar ilk hamleden ileriye doğru belirsizliğe yürümek yerine, tahtada çok az taşın kaldığı kesin sonuçlu konumlardan geriye doğru hesaplamaya başladılar. Bir dama taşına karşı tek bir rakip taşın kaldığı konum matematiksel olarak anında beraberliktir. Köşede tek bir taşı sıkıştıran iki dama ise kesin galibiyettir.

Chinook, boş tahtaya adım adım taş ekleyerek kurallara uygun tüm konfigürasyonların değerini tespit etti. İncelenen bir konum bilinen bir galibiyet konumuna ulaşıyorsa o konum da kazanç hanesine yazıldı. Eğer kural dahilindeki tüm hamleler mağlubiyete çıkıyorsa kayıp olarak işaretlendi. En iyi hamleler dengeyi koruyorsa beraberlik tescillendi.

1989 ile 2007 yılları arasında yürütülen bu çalışma neticesinde, tahtada 10 veya daha az taşın kaldığı tüm pozisyonlar eksiksiz biçimde hesaplandı^[1]. Bu devasa oyun sonu veritabanı tam 39 trilyon farklı pozisyon içermektedir. Bir partide taş sayısı 10 adede veya altına indiğinde, Chinook artık varyant aramaz: Mutlak doğru hamleyi doğrudan disk belleğinden okur.

Açılıştan oyun sonuna uzanan kanıt köprüsü

10 taşlık kütüphane tamamlandıktan sonra çözülmesi gereken son mesele, 24 taşlık başlangıç konumundan bu 10 taşlık sınıra kadar uzanan kusursuz bir köprü inşa etmekti^[1].

Ekip, kanıt sayısı araması algoritmaları ile alfa-beta budama tekniklerini harmanladı. Bilgisayar, zorunlu taş değişimlerini ve sadeleşmeleri kovalayan hatlara öncelik tanıdı, zayıf hamlelerin hemen çürütüldüğü yan yolları ise süratle eledi.

Yüzlerce işlemcinin paralel çalıştığı bu arayış yıllar sürdü. Trilyonlarca gereksiz varyant ayıklandı ve on milyonlarca kritik düğümden meydana gelen teyit edilmiş bir kanıt ağacı çatıldı. Başlangıçtan çıkan her ana yol, ya aşılmaz bir savunma kalesine ulaştı ya da 39 trilyonluk beraberlik kütüphanesine doğrudan bağlandı. 2007 senesinde ispat tamamlandı: Dama matematiksel olarak beraberliktir^[1].

İnsan zekâsı algoritmaya karşı: Efsanevi Marion Tinsley

Makineler oyunu kuramsal olarak aydınlatmadan çok önce, bir insan yalnızca olağanüstü zekâsıyla bu kusursuzluğa inanılmaz derecede yaklaştı. Florida’da matematik profesörlüğü yapan Dr. Marion Tinsley, tüm zamanların en büyük dama oyuncusu olarak kabul edilir.

Tinsley’nin kariyeri akıl almaz bir başarı tablosudur. Seçkin turnuvalarda geçen 45 yıllık aktif spor hayatı boyunca Tinsley, oynadığı binlerce resmi partide yalnızca 9 mağlubiyet aldı^[1]. On yıllar boyunca dünya şampiyonluğu unvanını elinde tuttu, unvanı sadece rekabet heyecanı azaldığında kendi isteğiyle bıraktı. Chinook yazılımını insan dehasının en yüksek zirvesinde sınamak isteyen Jonathan Schaeffer, 1992 yılında Tinsley ile resmi bir dünya şampiyonluğu maçı organize etti.

1992 yılındaki bu randevu, insan sezgisi ile silikon çiplerin hesaplama gücü arasındaki en büyük yüzleşmelerden biri oldu. 39 zorlu parti boyunca Tinsley büyüleyici bir pozisyonel hâkimiyet sergiledi ve Chinook’u 4 galibiyet, 2 mağlubiyet ve 33 beraberlikle yendi^[1]. Bu sonuç, klasik bir zekâ oyununda bir bilgisayar programının hüküm süren bir insan dünya şampiyonuna karşı unvan maçına çıktığı ilk tarihi sınavdı.

1994 senesinde merakla beklenen rövanş maçı tertiplendi. 6 ardışık beraberliğin ardından Tinsley, aniden nükseden ciddi bir rahatsızlık nedeniyle maçtan çekilmek mecburiyetinde kaldı ve 1995 yılında hayatını kaybetti^[1]. Chinook, insan-makine dünya şampiyonu ilan edildi. Daha sonra Tinsley’nin hamlelerini inceleyen araştırmacılar çarpıcı bir gerçeği gördü: Tinsley’nin kararları, en karmaşık durumlarda dahi bilgisayarın kusursuz oyun sonu kütüphaneleriyle neredeyse birebir örtüşüyordu.

Oyunların karmaşıklık basamakları: Connect Four’dan satranca

Damanın çözülüşünün büyüklüğünü kavramak adına, onu diğer klasik zekâ oyunlarıyla kıyaslamak aydınlatıcıdır.

1950 senesinde matematikçi Claude Shannon, bilgisayar programcılığı üzerine kaleme aldığı öncü makalesinde satrancın hesaplama karmaşıklığını inceledi^[4]. Shannon, satrançta kurallara uygun pozisyon sayısının yaklaşık 10^44 olduğunu ve oynanabilecek oyun ağacı çeşitliliğinin en az 10^120 seviyesine vardığını hesapladı; bu büyüklük günümüzde Shannon Sayısı olarak anılır^[4].

Bu oyunların basamaklarını yan yana koyalım:

• Connect Four: 1988’de güçlü biçimde çözüldü^[2]. Trilyonlarca konuma sahiptir ve sıradan bir dizüstü bilgisayarda saniyeler içinde baştan sona çözülür.
• 8×8 İngiliz Daması: 2007’de yaklaşık 5 × 10^20 pozisyonluk uzayda zayıf biçimde çözüldü^[1]. 18 yıllık dağıtık küme hesaplaması ve 39 trilyonluk oyun sonu kütüphanesi gerektirdi.
• Satranç: Tamamen çözülmemiştir. 10^44 pozisyon ve 10^120 dallanma yoluyla^[4], satranç mevcut hesaplama kapasitelerinin fersah fersah ötesindedir. Günümüzde satranç oyun sonu tabloları sadece 7 taşa kadar hesaplanabilmiştir. 8 taşa çıkmak petabaytlarca depolama isterken, 32 taşlık oyunun tamamını klasik bilgisayarlarla çözmek imkânsız görünmektedir.
• 10×10 Uluslararası Dama: Çözülmemiştir. 100 karede yirmişer taşla oynanan bu türde durum uzayının 10^30 olduğu tahmin edilir. Uçan damalar ve çoğunluk taş alma zorunluluğu hesaplama ağacını olağanüstü biçimde genişletir.

Matematiksel çözüm damayı neden öldürmedi?

2007 yılındaki bilimsel duyuru basında geniş yankı bulduğunda, kimi çevreler damanın artık tükendiğini iddia etti. Bilgisayar oyunun beraberlikle bittiğini biliyorsa, insanların tahta başında taş sürmesinin ne manası kalmıştı?

Bu bakış açısı, insani mücadelenin ruhunu gözden kaçırır. Matematiksel bir çözüm, elli hamle boyunca sıfır hata yapan iki kusursuz varlığın karşılaşmasını anlatır. Ne var ki etten kemikten oyuncular hatasız birer hesap makinesi değildir. Hiçbir insan hafızasında 39 trilyon pozisyonu barındıramaz ya da zihninde milyonlarca dallı kanıt ağaçlarını taşıyamaz.

Tahta başında dama, kıyasıya bir taktik çekişmedir. Oyunun en can alıcı kuralı zorunlu taş alma ilkesidir: Bir taş alma imkânı doğduğunda hamleyi yapmak mecburidir. Bu kural, oyuncuların rakibi tuzaklı çaprazlara çekmek için kendi taşlarını feda ettiği ve ardından tahtayı süpüren çoklu atlayışlar sergilediği nefis kombinezonlara kapı aralar.

Pratikte sonucu üç temel unsur tayin eder:

1. Açılış hassasiyeti. Teorik ana yollar beraberliğe çıksa da yan patikalar ölümcül tuzaklarla doludur. İlk hamlelerde yapılacak küçük bir dikkatsizlik, iki hamle sonra geri dönülmez bir hezimete yol açabilir.
2. Konumsal manevra gücü. Merkezi tutmak, arka sırayı muhafaza etmek ve kenar kareleri yönetmek derin bir oyun anlayışı ister. Doğru dama stratejisi ilkelerini öğrenen oyuncular, yalnızca anlık taktiklerle yetinenleri daima saf dışı bırakır.
3. Oyun sonu titizliği. Taşlar eşitlendiğinde zaferi çoğunlukla muhalefet (opposition) kuralı belirler. Doğru kareden sapmak, kesin bir galibiyeti beraberliğe düşürebilir; bu incelikleri kapsamlı dama oyun sonu rehberimizde inceliyoruz.

Resmi turnuvalarda ezberlenmiş yollardan kaçınmak ve oyuncuları keşfedilmemiş alanlara yöneltmek için ilk hamleler kura ile belirlenir. Dama ölmemiştir; matematiksel kanıt, bu köklü oyunun iç mimarisinin ne denli dengeli olduğunu tescillemiştir.

Tahta başında insan zekâsının dinamizmi

Dama tahtasında teorik eşitlik, masa başındaki gerilimi hiçbir zaman azaltmaz. Aksine, iki oyuncu kısıtlı süre altında hamle ararken psikolojik baskı ve odaklanma belirleyici hâle gelir. Rakibin planını sezmek, savunmadaki ince çatlakları yakalamak ve taş değişimlerini doğru zamanlamak sürekli uyanık bir zihin ister. Kenar karelerin emniyeti ile merkez baskısı arasındaki denge, tahta üzerinde hassas bir terazi gibi işler. Rakip taşları kenara iterek hareket alanını daraltmak, çoğu zaman doğrudan taş kazanmaktan çok daha etkili bir stratejik üstünlük sağlar.

Turnuva deneyimleri göstermektedir ki matematiksel kesinlik oyunun sanatsal yönünü zedelemez; bilakis ona sağlam bir zemin sunar. Ustalar arasındaki her karşılaşma, insan karakterinin, stratejik sabrın ve mücadele azminin benzersiz bir ifadesi olarak parıldar.

Tahtada taşların sessiz yürüyüşü, derin bir hesaplama disiplini ile sezgisel yaratıcılığın buluşmasıdır. Teorik beraberliğin varlığı, masaya oturan oyuncuların kazanma arzusunu asla eksiltmez; aksine her başarılı manevrayı daha kıymetli kılar. Çünkü gerçek zafer, kusursuz bir algoritmayı taklit etmekte değil, rakibin karşısında kendi zihinsel sınırlarını aşabilmektedir.

İster resmi İngiliz daması kuralları metnini ilk defa okuyor olun, ister zengin dama varyantları dünyasını araştırın veya internette diğer oyuncularla online dama oyna seçeneğini değerlendirin; 64 karelik saha insan yaratıcılığına daima açıktır. Bilgisayarlar teorik son durağı haritalandırmış olabilir, fakat tahtadaki o heyecan dolu yolculuk her zaman oyunculara aittir.

Merak edilen sorular

Dama akla gelebilecek her hatalı hamle için çözüldü mü?

Hayır, İngiliz daması güçlü değil, zayıf biçimde çözülmüştür. Elde edilen kanıt, 32 koyu kareye dizilen 24 taşlık başlangıç konumundan itibaren kusursuz hamlelerle beraberliği garanti eder^[1]. Ayrıca 10 ve daha az taşa sahip tüm durumlar 39 trilyonluk kütüphaneyle bütünüyle çözülmüştür. Ancak çok sayıda taş varken karşılıklı ağır gaflarla oluşan absürt pozisyonların tümü tek tek haritalanmamıştır.

Bir insan bugün Chinook yazılımını yenebilir mi?

Açılış kütüphanesi ve 10 taşlık veri tabanı devrede olan tam donanımlı bir Chinook programını hiçbir insan mağlup edemez. Oyunun beraberlik olduğu ispatlandığından, en doğru hamleleri yapan makine asla kaybetmez. İnsan kusursuz oynarsa maç berabere biter; insan en ufak bir konumsal kusur işlerse makine hatayı değerlendirir ve kazanır.

İngiliz damasında siyah taşların bir avantajı var mıdır?

İngiliz damasında oyuna ilk olarak siyah başlar. İlk hamle avantajı siyaha merkezi kontrol etme inisiyatifi verse de, Schaeffer’ın kanıtı bu hamle üstünlüğünün doğru bir savunma karşısında galibiyete yetmediğini ortaya koymuştur^[1]. İki taraf da kusursuz oynadığında ilk hamle üstünlüğü erir ve oyun beraberlikle mühürlenir.

Kaynaklar

1. Schaeffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., Lu, P., & Sutphen, S. (2007). Checkers Is Solved. Science, 317(5844), 1518–1522.
2. Allis, L. V. (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. thesis, University of Limburg, Maastricht.
3. Boardgammon. “Checkers Rules: How to Play, Movement, and Captures.”
4. Shannon, C. E. (1950). Programming a Computer for Playing Chess. Philosophical Magazine, Ser. 7, 41(314), 256–275.
5. Boardgammon. “Checkers Crown: Play Online Checkers and Regional Draughts Variants.”
6. Boardgammon. “Play Checkers Online: Free Browser and Mobile Draughts.”
7. Boardgammon. “Checkers Variants: The Kinds of Draughts Played Around the World.”

Bir hata ya da kulağa tuhaf gelen bir ifade mi gördünüz? Bize yazın