- 1964'te Nenad Petrović'in yayımladığı 218 hamlelik satranç pozisyonundan daha fazla hamle yapılabilen bir pozisyon bulunmuyor
- Tüm pozisyonları taramak pratikte imkânsız olduğundan, sınırı kanıtlamak için matematiksel optimizasyon ve bilgisayar destekli modelleme teknikleri kullanıldı
- Gereksiz taşların çıkarılması, kısmi taş yerleşimine izin verilmesi, rok kurallarının sadeleştirilmesi gibi yöntemlerle arama uzayı etkili biçimde daraltıldı
- Son aşamada Gurobi optimizasyon aracı ile 218 hamlenin üst sınır olduğu doğrulandı; 144 hamlelik (terfi/promosyon hariç) gibi kayıtlar da ayrıca doğrulandı
- Bu çalışma sayesinde satranç motoru ve sıkıştırma geliştiricileri, azami hamle sınırı konusundaki belirsizliği giderebilecek
Giriş: 218 hamlelik satranç pozisyonu tartışması
1964'te satranç kompozisyonu büyükustası Nenad Petrović 218 hamlelik bir pozisyon yayımladığından beri, bu rekoru kırma girişimleri sürdü. Yazar, bir bilgisayar bilimci olarak tüm pozisyonları bilgisayar aracılığıyla inceleyip bu soruyu kesin olarak kapatmayı amaçladı. Ulaşılabilir satranç pozisyonlarının sayısı yaklaşık 4.8 × 10^44 olsa da, böylesine devasa bir aramayı fiilen yapmak mümkün değil.
Matematiksel optimizasyonun devreye girmesi
Gereksiz taşları ve kombinasyonları en aza indirmek
- Satranç tahtasındaki siyah taşların ek olarak hamle sayısını artırdığı durumlar sınırlı
- Beyaz piyonların taş alabilmesini sağladıklarında veya rakip şah üzerindeki şah tehdidinden kaçınılmasına yardımcı olduklarında olduğu gibi
- Siyah taşların büyük kısmı çıkarılsa da azami hamle sayısı etkilenmiyor
- Taş sayısı izin verdiği sürece, siyah taşlar daha zayıf taşlarla değiştirilebiliyor ya da bazı kısıtlar (açmaza alma gibi) altında yerleşimleri ayarlanabiliyor
- Beyaz taşlarda ise durum tersine; en iyi pozisyonu kurmak için hepsini vezir gibi güçlü taşlarla değiştirmek yasa dışı pozisyonlar doğurabildiğinden daha ince ayar gerekiyor
Şah durumları ve hamle sayısı sınırı
- Siyah şahın şah çekilmiş durumda olması yasal bir pozisyon olmadığından dikkate alınmasına gerek yok
- Beyaz şah şah çekilmişken hareket seçenekleri ciddi biçimde kısıtlanıyor (en fazla 120 hamle); 218'e ulaşmak kesinlikle mümkün değil
- Bu nedenle arama yalnızca şah çekilmemiş pozisyonlarla sınırlandırılabiliyor
Kısmi taş yerleşimi ve matematiksel modelleme
Kombinatoryal karmaşıklığı azaltmak için kısmi (fractional) taş yerleşimi, hareketler ve bazı satranç kurallarının gevşetildiği bir model benimsendi
- Örneğin bir taşın %27,3 olasılıkla e4'te, %72,7 olasılıkla başka bir konumda bulunması gibi
- Bu yaklaşım, Gurobi gibi modern optimizasyon araçlarında tamsayılı doğrusal programlama (ILP, Integer Linear Programming) biçiminde uygulandı
- Başlangıçta bellek ve zaman sınırlarına takınıldı (yaklaşık 55 bin saniye sonra bellek yetersizliği)
- Arama uzayını sadeleştirmek için rok kuralları, şah tehdidi, açmazlar ve en passant koşulları gibi konularda ek basitleştirmeler uygulandı
Optimizasyon ve sonuç
Son aşamada, gereksiz kombinasyon aramalarını engelleyen yardımcı kısıtlar eklenerek model iyileştirildi ve Gurobi ile optimizasyon tamamlandı
- Üst sınır kademeli olarak 305 hamle → 271,67 hamle → 218 hamle olarak daraltıldı
- Temsil niteliğindeki 12 adet 218 hamlelik pozisyonun ulaşılabilir olduğu doğrulandı
- Bu pozisyonların, proof game yoluyla sorunsuz biçimde ulaşılabilen yasal pozisyonlar olduğu da kanıtlandı
Ayrıca, promosyon olmadan en fazla 144 hamle, yasa dışı pozisyonlarda en fazla 288 hamle ve ulaşılamayan yasal pozisyonlarda 271 hamlelik kayıtlar da doğrulandı
Sonuçlar ve önemi
- Bu çalışma sayesinde satranç motoru geliştiricileri ve sıkıştırma algoritması araştırmacıları, bellek tasarımı gibi konularda 256 hamlelik sınırın yeterli olduğundan emin olabiliyor
- Yasal bir yolla 218'den fazla hamle seçeneği sunan bir pozisyonun bulunmadığı matematiksel olarak kanıtlandı
SSS özeti
- Bir satranç oyunu 218 hamleden daha uzun sürebilir; ancak bu çalışma, 'tek bir turda mevcut seçenek sayısının' üst sınırını inceliyor
- Bazı pozisyonlar ulaşılamaz gibi görünse de, önceki hamlenin taş alma ile bitmesi gibi çeşitli yolların bulunduğu belirtiliyor
- Bu araştırma yöntemi, devasa kombinasyon uzayında 'kesinlikle imkânsız kombinasyonları' hızla eleyen matematiksel oracle tekniğini uyguluyor
- Kullanılan kod ve elde edilen kanıtların matematiksel geçerliliği de yayımlanarak güvenilirlik sağlanıyor
Gelecek çalışmalar ve ek araştırma önerileri
Bu teknik kullanılarak 'en fazla taş alma hamlesi', 'en fazla pat', 'en fazla şah', 'en fazla mat', 'en fazla iki hamlede mat' gibi çeşitli satranç problemleri de incelenebilir. Ancak bazı durumlarda ayrı ve yaratıcı optimizasyon algoritmaları gerekebilir.
Sonuç
- 218 hamle, bir satranç pozisyonunda tek turda yapılabilecek resmî azami hamle sayısı
- Pratik açıdan satranç yazılımı geliştiricileri ve araştırmacılar, yapıları 218'e (veya 256'ya) göre tasarlayabilir
- İlgili kod ve optimizasyon sonuçları GitHub üzerinde açık olarak yayımlandı
Referans
- Nenad Petrović'in 218 hamlelik pozisyonu, Jenő Bán'ın 144 hamlelik (promosyonsuz) kaydı gibi proof game ve pozisyon bağlantıları yer alıyor
- Ayrıntılı açıklama ve koda Github deposundan ulaşılabilir
1 yorum
Hacker News yorumu
Lichess'te 960 ya da Crazyhouse gibi varyantlardaki oyun seviyesi Chess.com'dan çok daha yüksek
Kelimenin tam anlamıyla absürt derecede iyi. Mümkünse bağış yapmanızı öneririm
İlginç olan şu ki, mixed-integer linear programming (MILP) çözücüleri bunu zaten destekliyor. Teknik terimle buna 'row generation' deniyor; bu genelde problemi matris biçiminde yazdığınızda, satırlar kısıtları ve sütunlar değişkenleri temsil ederken kullanılan bir ifade
(Dinamik olarak) yeni satırlar eklemek, yalnızca ihlal edildiğinde kısıt getirmekle aynı şey
Bu yaklaşım özellikle Traveling Salesman Problem çözümünde kullanılıyor
(Bu arada Wikipedia'da Column generation var ama row generation yok)
Satranç kurallarını gevşetmek ya da atlamak, değişken seçimimi de etkiledi. Matematiksel modellemeye girmeden önce lazy constraints gibi şeyleri denedim ama anlamlı bir hız artışı sağlamadı. Örneğin sadece beyaz şahın şah çekip çekmediğini dikkate almamak bile çok sayıda sadeleştirme sağladı
(Tartışmanın önkabulü: Gurobi'de hata yok ve yazarın problem tanımında ve uygulamasında da hata yok)
Gurobi'nin yerel bir maksimumda takılı kalma ihtimali var mı, yoksa gerçekten küresel optimumu mu kanıtladı diye merak ediyorum
Gurobi ve benim kodum amaçlandığı gibi çalışıyorsa ve satranç modelini sadeleştirirken mantıksal bir hata yapmadıysam, elde ettiğim sonuç "başlangıç pozisyonundan yasal bir hamle dizisiyle ulaşılabilen satranç pozisyonları arasında, mümkün olan yasal hamle sayısının en büyük değeri için hem alt hem üst sınır 218'dir" demek oluyor. Yani Gurobi, arama uzayının tamamı üzerinde sınır koyarak "bundan daha iyi bir durum yok" sonucunu kanıtlamış oluyor
Hesaplama açısından toplam problem uzayı daha önemli. Çünkü bir pozisyonun yasal olup olmadığına karar vermeden önce hepsinin "hesaplanması" gerekiyor. Yalnızca yasal pozisyonları dolaşmanın basit bir yolu yok
Bir tanıdığım sayesinde makalemin burada tartışıldığını öğrendim
Daha az açık bir başlık seçtiğim için özür dilerim, umarım şimdi daha nettir. Geri bildirimleriniz ve sıcak sözleriniz için teşekkürler
Benzer satranç gerçeklerinin ispatı hakkında başka sorularınız varsa onları da yanıtlayabilirim ^^
Teşekkürler
Tobi
Güncelleme: Makale, yaklaşık 8.7x10^45 ulaşılabilir satranç pozisyonu olduğunu söylüyor ve https://github.com/lechmazur/ChessCounter bunu bir üst sınır olarak veriyor
(Bu da yaklaşık 153 bite karşılık geliyor)
Ama verimli biçimde decode etmek için ChessPositionRanking projesinin önerdiği sayı olan (8726713169886222032347729969256422370854716254) değerinin log2 tavanı alınmalı, yani 153 bit gerekir. ChessCounter verimli decode kodu sağlamıyor
Kale/vezir/at da öyle ama satrançta alınmış olabilecekleri için 5 taşın her biri için toplam 65 durum gerekir
Fil ise karelerin yalnızca yarısına gidebildiği için her biri için 33 durum
Piyonlarda 4 farklı terfi, alınmış olma durumu ve koşullara göre değişmekle birlikte kabaca 20~30 pozisyon bulunur; toplamda piyon başına yaklaşık 290 durum eder
Böylece tek bir renk tarafı için tahta durumunu ifade etmek yaklaşık 112 bit ediyor; yuvarlayınca iki taraf birlikte 224 bit gerekiyor
En passant ve rok kısıtları (örneğin rok yapılamaması) yuvarlama içinde ek bit gerektirmiyor; bunlar sadece her taş için birkaç ek durum demek
Bu muhtemelen sabit uzunluklu bir tahta gösteriminde en sıkıştırılmış biçimdir
Seyrek bir gösterimde ise iki şahın her zaman var olduğu düşünülürse, yaşayan taşlar n basamaklı bir ondalık sayı ve konumlar için n+2 adet 64 bit sayı ile ifade edilebilir; rok, en passant vb. için de az miktarda ek bilgi gerekir. Taşların yaklaşık yarısının kalkmış olduğu ortalama durumda tahta durumunu temsil etmek yaklaşık 180 bit tutar
Hamle geçmişi de hamle başına yaklaşık 10 bit gerektirir (siyah/beyaz bir çifti için; tek bir ply 5 bit). Bu da yaklaşık 18 hamleye kadar yer bırakır. Bu, ortalama bir satranç oyununun orta noktasından biraz daha kısadır
Daha fazla sıkıştırmak için muhtemelen devasa boyutta bir sözlük uygulamak gerekir
Dolayısıyla tüm tahtayı sabit uzunlukta kodlarsanız 644=256 bit=32 bayt eder
Ya da yalnızca taşlar için değişken uzunluklu bir gösterimde her bir 64 karelik indeks 6 bit olur, yani adet10 bit gerekir
Örneğin başlangıç konumu 32*10=320 bit=40 bayttır
5.68e50 olan "general" gerçek üst sınır ve mümkün olan tüm terfilere izin veriyor
O piyonun yalnızca tek bir hamlesi var (yanındaki atı almak). Eğer o piyon olmasaydı dört beyaz vezir ve at b2'ye girebilirdi. Ama gerçekte siyah şah zaten mat olduğu için bu hamleler fiilen var olamaz
O e5'teki veziri başka bir yere koyup anında mat olmasını engellerken b2 karesini daha fazla açmak cazip geliyor
Not: O piyonun patı önlemek için orada hayatta kalması gerekiyor gibi görünüyor
Eğer siyahın sırası olsaydı da, e5'teki beyaz vezir yüzünden şah bağlı olduğundan (pin) yine hareket edemezdi. Eğer pin olmasaydı 4 hamlesi olurdu. Underpromotion da mümkün
Pozisyon White to move. b2 piyonu, beyaz vezir yüzünden şahı pinlemiş olmasa bile, siyah piyon hareket edemez
b2 piyonu, siyah şahı şah tehdidinden korumak için zorunlu. Aksi halde pozisyonun kendisi yasal olmaz
Her şeyi gerçekten çok dikkatli kontrol ettim; beyaz için 218'in üstüne çıkmaya yönelik denemelerin mümkün olmadığından emin olabilirsiniz. Yine de bu kadar çok kişinin makaleme ilgi göstermesi beni şaşırttı ve sevindirdi, haha ^^
Siyah piyonlardan birini beyaz ata çevirerek hamle sayısını artırmak mümkün görünebilir ama iki at da zaten mevcut ve tüm piyonlar da terfi etmiş durumda, dolayısıyla bu mümkün değil. (İki piyonu birden değiştirirseniz siyahın önceki hamlede bu pozisyona ulaşması imkânsız hale gelir)
Yazının tamamını okudun mu?
271 değil, 271.666... :) Bu değer, tüm kararların (0 veya 1) sürekli değerlere (0.0~1.0 ve aradaki her şey) gevşetildiği modelden geliyor. Yani bir taşın 0.23 kadar var olduğunu varsayabiliyorsunuz. Belirli bir hamlenin yapılabilirliğini de mesela 0.843 olarak ele alabiliyorsunuz.
Bu tür bir 'black magic' ile hesaplama çok daha hızlanıyor ve gerçekte var olandan daha fazla hamle sayısı üretebiliyorsunuz.
Bu yüzden bu yöntemi kullanarak olası kötü alt uzayları hızla eleyebiliyorsunuz. Bu teknikler olmadan tüm arama uzayını kaba kuvvetle taramak imkânsız olurdu
Bu arada, sanırım siyah piyonların başlangıç konumlarında olduğunu yanlış anlamışsınız. Aslında siyah piyon tahtanın karşı tarafına kadar ilerlemiş (beyaz tarafına)