WordChess · O notă de teren despre complexitate

Un ocean combinatoriu

Șahul este reperul nostru pentru adâncime. O alegere discretă de design face WordChess și mai profund.

01 · Măsurarea unui joc

Adâncimea este ramificarea, nu piesele

În 1950, Claude Shannon, tatăl teoriei informației, a estimat câte jocuri diferite de șah erau posibile. Răspunsul său, aproximativ 10120, a devenit numărul Shannon, și a ancorat intuiția noastră de atunci.1 Este o cifră atât de mare încât îl rușinează pe universul fizic, care conține doar aproximativ 1080 atomi.6 Ați putea da fiecărui atom propriul său șah, și tot n-ați avea destule șahuri pentru a juca fiecare partidă posibilă.

Șahul își câștigă acest titlu onest. Din deschidere, Albul are 20 de mutări; Negru răspunde cu 20, și există deja 400 poziții după o singură schimbare. La a șasea jumătate de mutare, numărul depășește 119 de milioane; până la a zecea, el ajunge la 69 de trilioane.4 Jucătorii numesc acest lucru factorul de ramificare, numărul de opțiuni legale la fiecare tură. În șah, acesta mediează aproximativ 35.2 Acest număr modest, compus mutare cu mutare, este motorul misterului jocului. În primele douăzeci de mutări, el produce, pe scară de mărime, 1060 partide. Sursa adâncimii șahului nu este piesele. Este ramificarea.

02 · Deschiderea, numărată

Patruzeci de mii, sau un trilion

Numărul de mutări din faza incipientă a șahului este cunoscut exact. În cazul WordChess, acestea sunt estimări, dar cele două jocuri diverg atât de rapid, încât diferența devine inconfundabilă în cadrul unei singure ture.4

Secvențe distincte de joc după N mutări complete (ambele jucători)
După mutareaȘah, exact 4WordChess, estimare 7
1400~1012
2197,281~1018
3119,060,324~1024
484,998,978,956~1030
569,352,859,712,417~1036

Cifrele pentru șah sunt numărări exacte ale generării de mutări (perft).4 Cifrele pentru WordChess presupun aproximativ un milion de plasări legale de deschidere pentru fiecare parte și o mie conservatoare ulterior, a se vedea nota metodologică.

03 · Decizia unică care schimbă totul

Fiecare jucător deține întreaga pungă

WordChess pare a fi rudă mai blândă, un joc de cuvinte pe o grilă, mai apropiat de un crucigrama decât de o luptă cu cuțitele. Această impresie este exact greșită, iar motivul este o singură linie din regulile sale: fiecare jucător deține întreaga rezervă de o sută de piese.7

Nu există un suport cu șapte piese, norocul deseurilor sau așteptarea unei vocale. În orice tură, un jucător poate alege aproape oricare dintre 148,941 cuvintele din dicționar, cuvinte de până la douăzeci și cinci de litere, și poate căuta un loc unde să le plaseze.7 Scrabble, limitat de cele șapte piese aleatorii, oferă un factor de ramificare de aproximativ 35, cam la fel ca în șah.5 WordChess elimină complet acel punct de blocare.

Consecința este violentă. Chiar prima mutare deschide calea către undeva între un și două milioane de plasări legale, un cuvânt, o orientare și un loc pe tabla vast deschisă de 25×25. Când ambele jucători au făcut doar o singurămutare, jocul s-a ramificat în ceva de ordinul unui trilion de poziții. Șahul, după aceeași schimbare de mutări, are patru sute.3

Regulile sunt mai simple. Spațiul posibilităților nu este.

04 · O scară a puterilor

Unde locuiesc numerele

Fiecare treaptă este de zece ori mai înaltă decât cea de dedesubt. Pe această scară, primele douăzeci de mutări din WordChess urcă curat peste numărul de atomi din univers și aterizează exact acolo unde se află un joc complet de șah.1

Șah WordChess Referință fizică
05 · Douăzeci de mutări

Un întreg joc de șah, înainte de prânz

Pe măsură ce tabla se umple, factorul de ramificare al șahului crește spre 35 și se menține la acest nivel. În WordChess, acesta rămâne în mii; fiecare cuvânt deja jucat devine un nou ancoraj la care se poate agăța, iar rezervorul complet de piese înseamnă că singura limită reală este care treceri permite dicționarul.7

Proiectați această cifră în viitor. La o mie de mutări legale pe tură, o valoare deliberat conservatoare, WordChess atinge 10120, numărul lui Shannon, complexitatea unui joc întreg de șah, în primele sale douăzeci de mutări. Permiteți zece mii de mutări pe tură, tot o valoare rezonabilă, și douăzeci de mutări urcă spre 10160: o marjă de la patruzeci la o sută de ordine de mărime peste cea a șahului 1060.1

Reduceți estimarea până când presupuneți că un jucător găsește doar trei sute mutări legale pe tură, o fracție din numărul adevărat, și douăzeci de mutări încă produce 1099. Încă patruzeci de ordine de mărime dincolo de șah. Concluzia rezistă oricărei ipoteze pesimiste pe care i-o poți oferi.1

O notă privind certitudinea

Numerele din șah sunt rezultatul a decenii de calcule exhaustive; ele sunt cunoscute. Cele ale WordChess sunt estimări riguroase, derivate din parametrii săi reali, o tablă de 25×25, un dicționar de 148.941 de cuvinte și setul complet de litere, și prezintă intervale de eroare largi. Ce nu este în discuție este direcția și scară diferenței. Fiecare ipoteză din acest articol a fost aleasă să fie conservatoare, iar diferența rămâne enormă.

06 · De ce un joc de cuvânturi câștigă

Complexitatea este numărul de viitoare care se ramifică dintr-o alegere

Șahul te constrânge: un cal se mișcă ca un cal, un pion avansează o singură casetă, iar opțiunile tale, deși bogate, sunt finite și familiare. WordChess îți oferă întregul limbaj și întreaga tablă și te întreabă să alegi. Aceasta este tranzacția pe care o face designul, și este motivul pentru care grila prietenoasă ascunde un ocean combinatoriu.

Niciuna dintre aceste lucruri nu face WordChess mai greu de jucat bine, un spațiu de căutare mai mare nu este același lucru cu o strategie mai profundă, iar geniul șahului constă în cât de mult sens extrage din ramificarea sa îngustă. Dar oricine își imaginează un joc de cuvinte ca opțiunea ușoară are matematica exact invers. Pentru primele sale douăzeci de mutări, WordChess face ca marele joc al regilor să pară aproape mic.

Surse & metodă

De unde provin numerele

  1. Numărul Shannon (≈10120). Shannon, C. E. (1950). „Programming a Computer for Playing Chess.” Philosophical Magazine, Ser. 7, 41(314), 256–275. Estimare: ~30 replici legale pe jumătate de mutare pe parcursul a ~40 de mutări (80 de jumătăți de mutare), dând 3080 ≈ 10120. Articol (PDF): vision.unipv.it/IA1/ProgrammingaComputerforPlayingChess.pdf. Prezentare generală: en.wikipedia.org/wiki/Shannon_number
  2. Factorul de ramificare la șah (≈35), lungimea partidei (~70 de jumătăți de mutări), arborele partidei (10123) și spațiul de stări (1044) complexitate. „Complexitatea jocului”, Wikipedia: en.wikipedia.org/wiki/Game_complexity
  3. Poziții legale la șah ≈ 4,8×1044. Tromp, J. (2021). Chess Position Ranking, estimat (4,48 ± 0,37)×1044 la 95% încredere: github.com/tromp/ChessPositionRanking
  4. Numărul exact al mutărilor de deschidere (perft): 20; 400; 8.902; 197.281; 4.865.609; 119.060.324; … 69.352.859.712.417. OEIS A048987, „Number of possible chess games at the end of the n-th ply”: oeis.org/A048987. De asemenea, tabulate ca „Rezultate Perft”, Chess Programming Wiki: chessprogramming.org/Perft_Results
  5. Factorul de ramificare al jocului Scrabble (≈35) și panoul cu șapte piese. „Factor de ramificare”, Wikipedia: en.wikipedia.org/wiki/Branching_factor. Dimensiunea panoului este o regulă standard de joc.
  6. Atomii din universul observabil ≈ 1080. Estimare cosmologică standard (citată frecvent ca 1078–1082). „Universul observabil, conținutul de materie”, Wikipedia: en.wikipedia.org/wiki/Observable_universe. Vezi și numărul Eddington: en.wikipedia.org/wiki/Eddington_number
  7. Parametrii și estimările pentru WordChess. Măsurate direct din joc: o tablă de 25×25 (625 de pătrate, 8 celule blocante), un rezervor complet de 100 de piese deținut de fiecare jucător și un dicționar englezesc de 148.941 de cuvinte (lungime medie 8,6 litere, cel mai lung 25). Valorile factorului de ramificare și ale mutărilor de 20 sunt estimări de ordin de mărime calculate din acești parametri.
  8. Citire suplimentară despre numărul Shannon, Șah – de pe Wolfram MathWorld. mathworld.wolfram.com.
  9. Citiri suplimentare despre numărul Shannon, Despre numărul de poziții în șah fără promovare. doi.org.
  10. Citiri suplimentare despre Complexitatea jocurilor, [1403.5830] Bejeweled, Candy Crush și alte jocuri Match-Three sunt (NP-)Grele. arxiv.org.
  11. Citiri suplimentare despre Complexitatea jocurilor, Complexitatea computațională a jocurilor și a puzzle-urilor. ics.uci.edu.

Metodă. „20 de mutări” înseamnă 20 pentru fiecare jucător, 40 de semi-mutări, conform convenției din șah. Șah: numărul de jocuri ≈ b40 cu b ≈ 30–35 → ~1060. WordChess: ramificația deschiderii estimată din (cuvinte jucabile care trec prin centru) × (plasări per cuvânt) ≈ 106 per parte; mutările ulterioare menținute la o valoare conservatoare de 103–104 → b40 ≈ 10120–10160. Plafonul inferior de 1099 folosește b = 300. Acestea sunt estimări, nu demonstrații; consultați „O notă privind certitudinea.”

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