WordChess · Notatka z terenu o złożoności

Kombinatoryczny ocean

Szachy są naszym punktem odniesienia dla głębokości. Cicha decyzja projektowa sprawia, że WordChess jest jeszcze głębsze.

01 · Miara gry

Głębokość to rozgałęzienia, a nie pionki

W 1950 roku Claude Shannon, ojciec teorii informacji, oszacował, ile różnych partii szachów jest możliwe. Jego odpowiedź, około 10120, stała się liczbą Shannonai od tamtej pory stanowi punkt odniesienia dla naszej intuicji.1 To jest liczba tak ogromna, że wstydliwie przytłacza fizyczny wszechświat, który zawiera zaledwie około 1080 atomów.6 Można by dać każdemu atomowi własną szachownicę i wciąż nie wystarczyłoby plansz, by rozegrać wszystkie partie.

Szachy zasługują na to uczciwie. Już od otwarcia Biały ma 20 ruchów; Czarny odpowiada 20, a po jednej wymianie istnieje już 400 pozycji. Po sześciu półruchach liczba przekracza 119 milionów; do dziesiątego osiąga 69 bilionów.4 Gracze nazywają to współczynnikiem rozgałęzienia, czyli liczbą legalnych wyborów w każdej turze. W szachach wynosi on średnio około 35.2 Ta skromna liczba, mnożona ruch po ruchu, jest silą napędową tajemnicy gry. W ciągu pierwszych dwudziestu ruchów generuje rzędu 1060 partii. Głębia szachów nie bierze się z figur. Bierze się z rozgałęzień.

02 · Otwarcie, policzone

Czterysta, albo bilion

Wczesne liczby ruchów w szachach są znane dokładnie. W WordChess są to szacunki, ale obie gry rozchodzą się tak szybko, że różnica jest nie do przeoczenia już w ciągu jednej tury.4

Rozłączne sekwencje gier po N pełnych ruchach (obaj gracze)
Po ruchuSzachy, dokładnie 4WordChess, szacunek 7
1400~1012
2197,281~1018
3119,060,324~1024
484,998,978,956~1030
569,352,859,712,417~1036

Liczby dla szachów to dokładne liczby generowanych ruchów (perft).4 Liczby dla WordChess zakładają około miliona legalnych otwierających ustawień na stronę i konserwatywne tysiąc na dalszych etapach, patrz uwaga metodologiczna.

03 · Jedna decyzja, która zmienia wszystko

Każdy gracz trzyma całą torbę

WordChess wygląda na łagodniejszego kuzyna, grę słowną na siatce, bliższą krzyżówce niż walki nożami. To wrażenie jest całkowicie mylne, a powodem jest pojedynczy wiersz w jego zasadach: każdy gracz trzyma cały pulę stu kafelków.7

Nie ma siedmioelementowego stojaka, nie ma szczęścia w losowaniu, nie ma czekania na samogłoskę. W dowolnej turze gracz sięgnąć może po niemal dowolne z 148,941 słów w słowniku, słowa o długości do dwudziestu pięciu liter, i poszukać gdzieś miejsca, by je umieścić.7 Scrabble, ograniczony swoimi siedmioma losowymi kafelkami, oferuje współczynnik rozgałęzienia w przybliżeniu 35, mniej więcej tyle, co w szachach.5 WordChess całkowicie eliminuje to wąskie gardło.

Skutek jest gwałtowny. Sam pierwszy ruch otwiera drogę do gdzieś między jednym a dwoma milionami legalnych posunięć, czyli słowa, orientacji i miejsca na otwartym planszy 25×25. Gdy obaj gracze wykonają po jednymruchu, gra rozgałęzi się na około bilion pozycji. Szachy, po tym samym wymianie, mają czterysta.3

Zasady są prostsze. Przestrzeń możliwości – nie.

04 · Drabina potęg

Gdzie mieszkają liczby

Każdy szczebel jest dziesięciokrotnie wyższy niż ten poniżej. W tej skali pierwsze dwadzieścia ruchów w WordChessie wznosi się czysto ponad liczbę atomów we wszechświecie i ląduje dokładnie tam, gdzie znajduje się cała gra w szachy.1

Szachy WordChess Fizyczny punkt odniesienia
05 · Dwadzieścia ruchów

Cała partia szachów, przed obiadem

W miarę zapełniania się planszy współczynnik rozgałęzienia w szachach rośnie do ok. 35 i utrzymuje się na tym poziomie. W WordChess pozostaje w tysiącach, ponieważ każde już zagrane słowo staje się nowym kotwiczeniem, do którego można się przytwierdzić, a pełny pulik kafelków oznacza, że jedynym realnym ograniczeniem są przecięcia dozwolone przez słownik.7

Przewiń to do przodu. Przy celowo konserwatywnym tysiącu legalnych ruchów na turę WordChess osiąga 10120, liczbę Shannona, złożoność całej partii szachów, w ciągu swoich pierwszych dwudziestu ruchów. Pozwól na dziesięć tysięcy ruchów na turę, co wciąż jest rozsądne, a dwadzieścia ruchów zbliża się do 10160: margines czterdziestu do stu rzędów wielkości ponad szachy 1060.1

Zmniejsz szacunek, aż do założenia, że gracz znajduje tylko trzysta legalnych ruchów w turze, ułamek prawdziwej liczby, a dwadzieścia ruchów wciąż daje 1099. Nadal czterdzieści rzędów wielkości więcej niż w szachach. Wniosek przetrwa każdy pesymistyczny zastrzeżenie, jakie mu się poda.1

Uwaga o pewności

Liczby szachowe są produktem dziesięcioleci wyczerpujących obliczeń; są znane. Te z WordChess to staranne szacunki, wyprowadzone z jego rzeczywistych parametrów: planszy 25×25, słownika 148 941 słów i pełnego zestawu liter, i obarczone szerokimi przedziałami błędu. Nie budzi wątpliwości kierunek i skala różnicy. Każde założenie w tym tekście zostało wybrane konserwatywnie, a różnica wciąż jest ogromna.

06 · Dlaczego gra słowna wygrywa

Złożoność to liczba przyszłości rozgałęziających się z wyboru

Szachy cię ograniczają: skoczek porusza się jak skoczek, pionek pełznie o jedno pole, a twoje opcje, choć bogate, są skończone i znajome. WordChess daje ci cały język i całą planszę i prosi, byś dokonał wyboru. To jest kompromis, jaki zakłada projekt, i to jest powód, dla którego przyjazna siatka ukrywa kombinatoryczny ocean.

Żadna z tych rzeczy nie czyni WordChess trudniejszym do grania dobrze, większa przestrzeń przeszukiwania nie jest tym samym co głębsza strategia, a geniusz szachów polega na tym, ile znaczenia wyciskają z ich wąskiego rozgałęzienia. Ale każdy, kto wyobraża sobie grę słowną jako lżejszą opcję, ma matematykę dokładnie odwrotnie. Przez swoje pierwsze dwadzieścia ruchów WordChess sprawia, że wielka gra królów wygląda niemal na małą.

Źródła & metoda

Skąd pochodzą liczby

  1. Liczba Shannona (≈10120). Shannon, C. E. (1950). „Programming a Computer for Playing Chess.” Philosophical Magazine, Ser. 7, 41(314), 256–275. Szacunek: ~30 legalnych odpowiedzi na półruch w ciągu ~40 ruchów (80 półruchów), co daje 3080 ≈ 10120. Artykuł (PDF): vision.unipv.it/IA1/ProgrammingaComputerforPlayingChess.pdf. Przegląd: en.wikipedia.org/wiki/Shannon_number
  2. Współczynnik rozgałęzienia w szachach (≈35), długość gry (~70 półruchów), złożoność drzewa gry (10123) i przestrzeni stanów (1044). „Złożoność gry”, Wikipedia: en.wikipedia.org/wiki/Game_complexity
  3. Legalne pozycje szachowe ≈ 4,8×1044. Tromp, J. (2021). Chess Position Ranking, szacunkowo (4,48 ± 0,37)×1044 przy 95% poziomie ufności: github.com/tromp/ChessPositionRanking
  4. Dokładne liczby ruchów otwierających (perft): 20; 400; 8 902; 197 281; 4 865 609; 119 060 324; … 69 352 859 712 417. OEIS A048987, „Liczba możliwych partii szachowych na końcu n-tej ply”: oeis.org/A048987. Zapisano również jako „Perft Results”, Chess Programming Wiki: chessprogramming.org/Perft_Results
  5. Współczynnik rozgałęzienia w Scrabble (≈35) i siedmioelementowy zestaw kafelków. „Branching factor”, Wikipedia: en.wikipedia.org/wiki/Branching_factor. Rozmiar zestawu jest standardową regułą gry.
  6. Atomy we Wszechświecie obserwowalnym ≈ 1080. Standardowy kosmologiczny szacunek (często cytowany jako 1078–1082). „Observable universe, matter content”, Wikipedia: en.wikipedia.org/wiki/Observable_universe. Patrz też liczba Eddingtona: en.wikipedia.org/wiki/Eddington_number
  7. Parametry i szacunki WordChess. Zmierzono bezpośrednio z gry: plansza 25×25 (625 pól, 8 komórek blokujących), pełny pulik 100 kafelków trzymany przez każdego gracza oraz angielski słownik 148 941 słów (średnia długość 8,6 litery, najdłuższe 25). Wartości współczynnika rozgałęzienia i ruchów na 20 to szacunki rzędu wielkości obliczone na podstawie tych parametrów.
  8. Dalsza lektura na temat liczby Shannona, Chess -- z Wolfram MathWorld. mathworld.wolfram.com.
  9. Dalsza lektura na temat liczby Shannona, O liczbie pozycji w szachach bez promocji. doi.org.
  10. Dalsza lektura na temat złożoności gier, [1403.5830] Bejeweled, Candy Crush i inne gry typu Match-Three są (NP-)trudne. arxiv.org.
  11. Dalsza lektura na temat złożoności gier, Złożoność obliczeniowa gier i łamigłówek. ics.uci.edu.

Metoda. „20 ruchów” oznacza 20 ruchów każdego z graczy, czyli 40 półruchów, zgodnie z konwencją szachową. Szachy: liczba partii ≈ b40 przy b ≈ 30–35 → ~1060. WordChess: rozgałęzienie otwarcia oszacowane na podstawie (słów, które można zagrać przez środek planszy) × (liczba możliwych umieszczeń na słowo) ≈ 106 na stronę; późniejsze tury utrzymane na konserwatywnym poziomie 103–104 → b40 ≈ 10120–10160. Dolna granica 1099 wykorzystuje b = 300. Są to szacunki, a nie dowody; patrz „Uwaga o pewności”.

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