WordChess · Karmaşıklık üzerine bir saha notu

Kombinatorik Bir Okyanus

Satranç derinlik için referans noktamızdır. WordChess'i daha da derin kılan sessiz bir tasarım tercihi vardır.

01 · Bir oyunun ölçüsü

Derinlik, taşlarda değil dallanmada gizlidir

1950'de Claude Shannon, babası bilgi teorisi, nin babası, satrançta kaç farklı oyunun mümkün olduğunu tahmin etti. Cevabı, yaklaşık 10120, oldu Shannon sayısıoldu ve o günden beri sezgilerimizin temelini oluşturuyor.1 Bu, fiziksel evreni bile utandıracak kadar büyük bir rakamdır; evren yalnızca yaklaşık 1080 atom içerir..6 Her atoma kendi satranç tahtasını verdiğinizde bile, her oyunu oynamak için yeterli tahtanız olmazdı.

Satranç bunu dürüstçe hak eder. Açılıştan itibaren Beyazın 20 hamlesi vardır; Siyah 20 hamleyle karşılık verir ve tek bir değişimden sonra bile zaten 400 konum oluşur. Altı yarı hamlede sayı 119 milyonuaşar; onuncu hamlede 69 trilyona ulaşır..4 Oyuncular buna dallanma faktörüder; her turda yapılabilen yasal seçimlerin sayısıdır. Satrançta bu ortalama yaklaşık 35.2 'dir. Bu mütevazı sayı, hamleden hamleye bileşik olarak büyüdüğünde, oyunun gizeminin motoru haline gelir. İlk yirmi hamlede yaklaşık 1060 oyun üretir. Satrancın derinliğinin kaynağı taşlar değildir. Dallanmadır.

02 · Açılış, sayılarla

Dört yüz ya da bir trilyon

Satrançta erken hamle sayıları kesin olarak bilinir. WordChess'te bunlar tahminidir, ancak iki oyunun ayrışması o kadar hızlıdır ki fark tek bir tur içinde bile açıkça görülür.4

N tam hamleden (her iki oyuncu) sonra oluşan farklı oyun dizileri
Hamleden sonraSatranç, kesin 4WordChess, tahmini 7
1400~1012
2197,281~1018
3119,060,324~1024
484,998,978,956~1030
569,352,859,712,417~1036

Satranç rakamları kesin hamle üretim sayılarıdır (perft).4 WordChess rakamları, her taraf için yaklaşık bir milyon yasal açılış yerleşimi ve sonrasında muhafazakâr bir bin olarak varsayılır, bkz. yöntem notu.

03 · Her şeyi değiştiren tek karar

Her oyuncu tüm torbayı elinde tutar

WordChess, ızgarada bir kelime oyunu, bıçak savaşı yerine daha çok bir bulmacaya yakın görünen daha nazik bir kuzen gibi durur. Bu izlenim tamamen yanlıştır ve bunun nedeni kurallarındaki tek bir satırdır: her oyuncu yüz karalıktan oluşan tüm havuzu elinde tutar.7

Yedi karalık rafı yoktur, çekilişin şansı yoktur, bir ünsüz harf için beklenmez. Herhangi bir turda, bir oyuncu neredeyse her 148,941 sözlükteki kelimeye, yirmi beş harfe kadar uzun kelimelere uzanabilir ve bunları yerleştirecek bir yer arayabilir.7 Scrabble, rastgele yedi karalığıyla kısıtlanmış olarak, yaklaşık 35, satrançla aynı düzeyde bir dallanma faktörü sunar.5 WordChess bu darboğazı tamamen ortadan kaldırır.

Sonuç şiddetli. En ilk hamle, bir yerlere açılır bir ile iki milyon arasında yasal yerleşim, bir kelime, bir yön ve geniş açık 25×25 tahtada bir nokta. Her iki oyuncu da sadece bir kezhamle yaptığında, oyun yaklaşık bir trilyon konuma dallanır. Satranç, aynı değişimden sonra, dört yüz konuma sahiptir.3

Kurallar daha basit. İmkânlar uzayı değil.

04 · Güçler merdiveni

Sayıların yaşadığı yer

Her basamak, altındakinden on kat daha yüksektir. Bu ölçekte, WordChess'in ilk yirmi hamlesi, evrendeki atom sayısını rahatlıkla aşar ve tam olarak bir tam satranç oyununun oturduğu yere iner.1

Satranç WordChess Fiziksel referans
05 · Yirmi hamle

Öğle yemeğinden önce, bütün bir satranç oyunu

Tahta doldukça satrancın dallanma faktörü 35'e doğru yükselir ve bu seviyede kalır. WordChess'te ise bu değer binlerde kalır; her oynanan kelime, üzerine yeni bir çapa olarak tutunulacak bir nokta hâline gelir ve tam karolar havuzu, gerçek tek sınırın sözlüğün hangi kesişimlere izin verdiği olduğu anlamına gelir.7

Bunu ileriye doğru yürütün. Kasıtlı olarak muhafazakâr bir şekilde her hamlede bin yasal hareket varsayıldığında, WordChess 10120, Shannon'un sayısı, bir bütün satranç oyununun karmaşıklığına, ilk yirmi hamlesiiçinde ulaşır. Her hamlede on bin hareketi kabul edin, hâlâ makul bir değer, ve yirmi hamle 10160'ye doğru tırmanır: satrancın 1060.1

üzerine kırk ile yüz basamak mertebesinde bir fark. Tahmini, bir oyuncunun yalnızca üç yüz hamle başına yasal hamle, gerçek sayının küçük bir kesri ve yirmi hamle hâlâ 1099. Hâlâ satrançtan kırk katman büyük. Sonuç, elinizde bulundurabileceğiniz her pesimist varsayıma dayanıyor.1

Kesinlik üzerine bir not

Satrancın sayıları, onlarca yıllık kapsamlı hesaplamanın ürünüdür; bunlar bilinmektedir. WordChess'inki ise dikkatli tahminlerdir; gerçek parametrelerinden, 25×25'lik bir tahtadan, 148.941 kelimelik bir sözlükten ve tam havuz rafından türetilmiştir ve geniş hata paylarına sahiptir. Şüphe götürmeyen şey, farkın yönü ve ölçeğidir. Bu metindeki her varsayım muhafazakâr olacak şekilde seçilmiştir ve fark hâlâ devasa boyuttadır.

06 · Neden bir kelime oyunu kazanır

Karmaşıklık, bir seçimden kaç geleceğin dallanmasıdır

Satranç sizi kısıtlar: bir at at gibi hareket eder, bir piyon bir kare ilerler ve seçenekleriniz zengin olsa da sonlu ve tanıdıktır. WordChess size tüm dili ve tüm tahtayı verir ve seçmenizi ister. Tasarımın yaptığı ödünleşim budur ve dostça görünen ızgaranın altında kombinatorik bir okyanus gizli olmasının nedeni de budur.

Bunların hiçbiri WordChess'i oynamayı daha zorkılmıyor; daha büyük bir arama alanı, daha derin bir stratejiyle aynı şey değildir ve satrancın dahiliği, dar dallanmasından ne kadar çok anlam çıkardığıdır. Ancak bir kelime oyununu hafif seçenek olarak hayal eden herkes, matematiği tam tersine çevirmiştir. İlk yirmi hamlesinde WordChess, kraliyetlerin büyük oyununu neredeyse küçük gösterir.

Kaynaklar & yöntem

Sayıların nereden geldiği

  1. Shannon sayısı (≈10120). Shannon, C. E. (1950). "Programming a Computer for Playing Chess." Philosophical Magazine, Ser. 7, 41(314), 256–275. Tahmin: ~40 hamle (80 yarım hamle) boyunca yarım hamle başına ~30 yasal yanıt, bu da 3080 ≈ 10120. Makale (PDF): vision.unipv.it/IA1/ProgrammingaComputerforPlayingChess.pdf. Genel bakış: en.wikipedia.org/wiki/Shannon_number
  2. Satranç dallanma faktörü (≈35), oyun uzunluğu (~70 yarım hamle), oyun-ağacı (10123) ve durum-uzayı (1044) karmaşıklığı. "Oyun karmaşıklığı," Wikipedia: en.wikipedia.org/wiki/Game_complexity
  3. Yasal satranç pozisyonları ≈ 4.8×1044. Tromp, J. (2021). Chess Position Ranking, tahmini (4.48 ± 0.37)×1044 %95 güven aralığında: github.com/tromp/ChessPositionRanking
  4. Kesin açılış hamle sayıları (perft): 20; 400; 8.902; 197.281; 4.865.609; 119.060.324; … 69.352.859.712.417. OEIS A048987, "n'inci ply'nin sonunda olası satranç oyunlarının sayısı": oeis.org/A048987. Ayrıca "Perft Sonuçları" olarak tablo halinde sunulmuştur, Chess Programming Wiki: chessprogramming.org/Perft_Results
  5. Scrabble dallanma faktörü (≈35) ve yedi harfli raf. "Dallanma faktörü," Wikipedia: en.wikipedia.org/wiki/Branching_factor. Raf boyutu, oyunun standart bir kuralıdır.
  6. Gözlemlenebilir evrendeki atomlar ≈ 1080. Standart kozmolojik tahmin (genellikle 10 olarak alıntılanır78–1082). "Gözlemlenebilir evren, madde içeriği," Wikipedia: en.wikipedia.org/wiki/Observable_universe. Ayrıca Eddington sayısı hakkında bkz: en.wikipedia.org/wiki/Eddington_number
  7. WordChess parametreleri ve tahminleri. Oyundan doğrudan ölçülen değerler: 25×25'lik bir tahta (625 kare, 8 engel hücresi), her oyuncunun elde tuttuğu tam 100 harflik havuz ve 148.941 kelimelik bir İngilizce sözlük (ortalama uzunluk 8,6 harf, en uzun 25). Dallanma faktörü ve 20 hamle rakamları, bu parametrelerden hesaplanan büyüklük sırası tahminleridir.
  8. Shannon sayısı hakkında ek okuma, Chess -- Wolfram MathWorld'den. mathworld.wolfram.com.
  9. Shannon sayısı ve satrançta terfi olmadan pozisyon sayısı hakkında ek okuma. doi.org.
  10. Oyun karmaşıklığı hakkında ek okuma, [1403.5830] Bejeweled, Candy Crush ve diğer Match-Three Oyunları (NP-)Zordur. arxiv.org.
  11. Oyun karmaşıklığı hakkında ek okuma, Oyunların ve Bulmacaların Hesaplama Karmaşıklığı. ics.uci.edu.

Yöntem. "20 hamle", her oyuncu için 20, yani 40 yarı hamleyi ifade eder; bu, satrançta kullanılan konvansiyondur. Satranç: oyun sayısı ≈ b40 b ≈ 30–35 → ~1060. WordChess: açılış dallanması, (merkezden geçen oynanabilir kelimeler) × (kelime başına yerleşim) ≈ 106 taraf başına tahmin edilmiştir; sonraki turlar için muhafazakâr bir 103–104 → b40 ≈ 10120–10160değeri tutulmuştur. 1099 alt sınırı b = 300 kullanılarak hesaplanmıştır. Bunlar kanıtlar değil, tahminlerdir; "Kesinlik üzerine bir not" bölümüne bakınız.

Was this worth reading?
← Back to WordChess
PlayPendium · About · Contact · Privacy · Terms · Cookies · Accessibility · Copyright · Browse all games · Inspirations · © 2026