PlayPendium
WordChess · 关于复杂度的札记

组合的海洋

国际象棋是我们衡量深度的标杆。而一个不起眼的设计选择,让 WordChess 拥有远为庞大的可能对局空间。

本文以英文撰写和编辑。此中文版本由机器翻译生成;凡涉及准确性之处,以英文原文为准。 阅读英文原文 →

01 · 衡量一款游戏

深度在于分支,而不在于棋子

1950 年,信息论之父 Claude Shannon(克劳德·香农)估算了国际象棋可能有多少种不同的对局。他的答案大约是 10120,后来被称为香农数,并从此成为我们直觉的锚点。1 这个数字大到让物理宇宙都相形见绌——宇宙中只有大约 1080 个原子。6 即使给每个原子配一副棋盘,棋盘的数量也不足以下完所有的对局。

国际象棋的这个数字来得名副其实。开局时,白方有 20 种走法;黑方以 20 种走法应对,仅仅一个来回之后就已经有 400 个局面。走到第六个半回合,这个数字超过 1.19 亿;到第十个半回合,达到 69 万亿。4 棋手称之为分支因子,即每回合可选的合法走法数量。在国际象棋中,它平均约为 35。2 这个不大的数字,一步接一步地累乘,正是这项游戏神秘感的引擎。在前二十个回合中,它会产生约 1060 量级的对局。国际象棋深度的来源不是棋子,而是分支。

02 · 开局,一一清点

四百,还是一万亿

国际象棋早期的走法数量是精确已知的。WordChess 的则是估算值,但两款游戏分化得如此之快,只需一个回合,差距就一目了然。4

N 个完整回合(双方各走一步)后的不同对局序列数
回合数国际象棋,精确值 4WordChess,估算值 7
1400~1012
2197,281~1018
3119,060,324~1024
484,998,978,956~1030
569,352,859,712,417~1036

国际象棋的数字是精确的走法生成计数(perft)。4 WordChess 的数字假设每位玩家的第一回合约有一百万种合法摆放(因此双方各走一步后约为 1012),此后每回合保守地按一千种计算,参见方法说明。

03 · 改变一切的那个决定

每位玩家都握有一整套字母牌

WordChess 看起来像是更温和的表亲——一个在网格上玩的文字游戏,更像填字游戏,而不是一场刀光剑影的搏斗。这个印象恰恰大错特错,而原因就在规则中的一句话:每位玩家都持有一整套一百枚字母牌。7

没有七枚牌的字母架,没有抽牌的运气,也不用苦等一个元音。在任何回合,玩家都可以伸手去拿词典中 148,941 个单词里的几乎任何一个——最长可达二十五个字母,恰好是棋盘的宽度——然后寻找放置它的位置。7 Scrabble(拼字游戏)受制于它那七枚随机字母牌,只能用字母架上恰好有的字母来拼词。5 WordChess 则彻底消除了这个瓶颈。

其后果是剧烈的。第一回合就有大约一百万到两百万种合法摆放——一个单词、一个方向,加上宽阔空旷的 25×25 棋盘上的一个位置。双方仅仅各走一步之后,对局就已分支成大约一万亿个局面。而国际象棋在同样一个来回之后,只有四百个。4

规则更简单了。可能性的空间却并非如此。

04 · 一架幂次的梯子

这些数字位于何处

标出的每一级都比下一级高出四十个数量级,即 1040 倍。在这把标尺上,WordChess 的前二十个回合轻松越过宇宙中的原子数,恰好落在一局国际象棋所在的位置。1

Chess WordChess Physical reference
05 · 二十个回合

午饭前下完一整局国际象棋

随着棋盘逐渐填满,国际象棋的分支因子逐渐上升到 35 左右并保持稳定。WordChess 的分支因子则始终保持在数千:每个已经下出的单词都成为一个新的挂靠点,而完整的字母牌组意味着唯一真正的限制,是词典允许哪些交叉。7

把这个推演下去。即便每个回合——包括走法极其丰富的开局在内——都只有刻意保守估计的一千种合法走法,WordChess 也会在前二十个回合内达到 10120——也就是香农数,一局国际象棋的复杂度。若允许每回合一万种走法(这仍然合理),二十个回合就会逼近 10160:比国际象棋的 1060 高出六十到一百个数量级。1

即便把估计压缩到假设玩家每回合只能找到三百种合法走法——只是真实数量的一小部分——二十个回合仍然能产生 1099。依然比国际象棋高出四十个数量级。无论你给出多么悲观的假设,这个结论都站得住。1

关于确定性的说明

国际象棋的数字是数十年穷举计算的成果;它们是已知的。WordChess 的数字则是基于其真实参数——25×25 的棋盘、148,941 词的词典,以及每位玩家手中一整套 100 枚字母牌——做出的审慎估计,误差范围很大。但毫无疑问的是差距的方向和规模。本文中的每一个假设都刻意选得保守,而差距依然巨大。

06 · 为什么文字游戏胜出

复杂度,就是一个选择能分出多少种未来

国际象棋约束着你:马只能走马步,兵一次只挪一格,你的选择虽然丰富,却是有限而熟悉的。WordChess 则把整个语言和整个棋盘交到你手上,让你自己选择。这就是这个设计所做的取舍,也是那张友好的网格背后隐藏着一片组合海洋的原因。

这一切并不能证明 WordChess 更难下好;更大的搜索空间并不等同于更深的策略,而国际象棋的天才之处,正在于它能从狭窄的分支中榨取出如此丰富的意义。但任何把文字游戏想象成轻量级选项的人,都把数学完全弄反了。在前二十个回合里,WordChess 让这项伟大的“王者之戏”看起来几乎显得渺小。

Sources & method

Where the numbers come from

  1. Shannon number (≈10120). Shannon, C. E. (1950). "Programming a Computer for Playing Chess." Philosophical Magazine, Ser. 7, 41(314), 256–275. Estimate: ~30 legal replies per half-move over ~40 moves (80 half-moves), giving 3080 ≈ 10120. Paper (PDF): vision.unipv.it/IA1/ProgrammingaComputerforPlayingChess.pdf. Overview: en.wikipedia.org/wiki/Shannon_number
  2. Chess branching factor (≈35), game length (~70 half-moves), game-tree (10123) and state-space (1044) complexity. "Game complexity," Wikipedia: en.wikipedia.org/wiki/Game_complexity
  3. Legal chess positions ≈ 4.8×1044. Tromp, J. (2021). Chess Position Ranking, estimated (4.82 ± 0.03)×1044 at 95% confidence: github.com/tromp/ChessPositionRanking
  4. Exact opening move counts (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. Also tabulated as "Perft Results," Chess Programming Wiki: chessprogramming.org/Perft_Results
  5. Scrabble’s seven-tile rack. Rack size is a standard rule of play. No published branching-factor figure for Scrabble is relied on here.
  6. Atoms in the observable universe ≈ 1080. Standard cosmological estimate (commonly cited as 1078–1082). "Observable universe, matter content," Wikipedia: en.wikipedia.org/wiki/Observable_universe. See also the Eddington number: en.wikipedia.org/wiki/Eddington_number
  7. WordChess parameters and estimates. Measured directly from the game: a 25×25 board (625 squares, 8 blocker cells), a full 100-tile set (98 letters and 2 blanks) held by every player with no draw, and a 148,941-word English dictionary (average length 8.6 letters; the longest words that fit the board run to 25). The branching-factor and 20-move figures are order-of-magnitude estimates computed from these parameters.
  8. Further reading on Shannon number, Chess -- from Wolfram MathWorld. mathworld.wolfram.com.
  9. Further reading on Shannon number, On the number of positions in chess without promotion. doi.org.
  10. Further reading on Game complexity, [1403.5830] Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard. arxiv.org.
  11. Further reading on Game complexity, Computational Complexity of Games and Puzzles. ics.uci.edu.

Method. "20 moves" means 20 by each player, 40 half-moves, the chess convention. Chess: game count ≈ b40 with b ≈ 30–35 → ~1060. WordChess: opening branching estimated from (playable words that fit through the centre) × (placements per word) ≈ 106 per side; later turns held at a conservative 103–104. The 20-move figures deliberately apply that later-turn b to all 40 half-moves, openings included: b40 ≈ 10120–10160, a floor; counting the two ~106 opening turns adds about six more orders of magnitude (≈10126–10166). The 1099 floor uses b = 300 throughout. These are estimates, not proofs; see "A note on certainty."

Was this worth reading?
Play WordChess
PlayPendium · About · Contact · Privacy · Terms · Cookies · Accessibility · Copyright · Browse all games · Classic arcade games · © 2026