Chess ang aming benchmark para sa lalim. Isang tahimik na pagpili sa disenyo ang nagpapalalim pa ng WordChess.
Noong 1950, Claude Shannon, ang ama ng teorya ng impormasyon, , ay tinitingnan kung ilang magkakaibang laro ng chess ang posibleng mangyari. Ang kanyang sagot, halos 10120, ay naging Shannon number, at ito ang nagpatibay ng aming intuition mula noon hanggang ngayon.1 Ito ay isang numero na kasing-handa ng sari-sarap sa pisikal na uniberso, na naglalaman lamang ng mga 1080 atom.6 Maaari mong bigyan ang bawat atom ng sariling chessboard at hindi pa rin sapat ang mga tablero upang laruin ang bawat laro.
Tunay na tinatanggap ng chess ang ganitong katotohanan. Simula sa pagbubukas, may 20 na galaw ang White; sumagot ang Black ng 20, at mayroon nang 400 posisyon pagkatapos ng isang palitan. Anim na kalahating galaw na, lumalampas ang bilang sa 119 milyong; sa ikasampung galaw, umabot ito sa 69 trilyong.4 Tinatawag ng mga manlalaro nito ang branching factor, ang bilang ng mga legal na pagpipilian bawat turno. Sa chess, nangunguna ito sa 35.2 Ang katulad na numero na iyon, na nagdudoble galaw-galaw, ang makina ng misteryo ng laro. Sa loob ng unang labindalawang galaw, naglilipat ito ng mga 1060 laro. Ang pinagmumulan ng lalim ng chess ay hindi ang mga piraso. Ito ay ang pag-branch.
Tuklas ang mga bilang ng mga galaw sa unang bahagi ng Chess. Sa WordChess, mga pagtatantya lamang, ngunit mabilis na nagkakaiba ang dalawang laro na ang pagkakaiba ay malinaw na sa loob ng isang turn.4
| Pagkatapos ng galaw | Chess, eksakto 4 | WordChess, pagtatantya 7 |
|---|---|---|
| 1 | 400 | ~1012 |
| 2 | 197,281 | ~1018 |
| 3 | 119,060,324 | ~1024 |
| 4 | 84,998,978,956 | ~1030 |
| 5 | 69,352,859,712,417 | ~1036 |
Ang mga numero ng Chess ay eksaktong bilang ng paggawa ng mga galaw (perft).4 Ang mga numero ng WordChess ay nag-aasum ng humigit-kumulang isang milyong legal na pagkakalagay sa simula bawat panig at isang konservatibong libo pagkatapos nito, tingnan ang tala ng paraan.
Ang WordChess ay tila mas mahinahong kaibigan, isang laro ng mga salita sa grid, mas malapit sa crossword kaysa sa laban ng kutsilyo. Ang impresyon na iyon ay ganap na maling, at isang linya sa mga alituntunin nito ang dahilan: bawat manlalaro ay may hawak ang buong pool ng isang daang tile.7
Walang rack ng pitong tile, walang suwerte sa paghila, walang paghihintay ng isang patinig. Sa anumang turn, maaaring umabot ang isang manlalaro sa halos anumang 148,941 salita sa diksyunaryo, mga salitang hanggang labing-limang letra ang haba, at hanapin ang kung saan ito ilalagay.7 Scrabble, na pinapabagal ng kanyang pitong random na tile, ay nag-aalok ng branching factor na humigit-kumulang 35, halos katulad ng chess.5 Iniiwas ng WordChess ang bottleneck na ito nang buong-buo.
Ang bunga nito ay malalakas. Ang unang gilid ay nagbubukas sa ilang isang hanggang dalawang milyong legal na paglalagay, isang salita, isang direksyon, at isang lugar sa malawak at bukas na 25×25 na tablero. Kapag gumalaw na lamang ng isang besesang dalawang manlalaro, ang laro ay nahahati na sa mga trilyong posisyon. Ang Chess, pagkatapos ng parehong palitan, ay may apat na daan.3
Mas simple ang mga tuntunin. Ang espasyo ng posibilidad ay hindi.
Bawat hagdan ay sampung beses mas mataas kaysa sa nasa ilalim nito. Sa sukat na ito, ang unang labing-apat na galaw ng WordChess ay tumataas nang malinis sa lumampas sa bilang ng mga atomo sa uniberso, at tumatapos sa eksaktong lugar kung saan nakaupo ang buong laro ng chess.1
Habang puno ang tablero, ang branching factor ng chess ay lumilipat pataas patungo sa 35 at nananatili. Ang ng WordChess ay nananatili sa libu-libo; bawat salitang naipaglaro ay nagsisilbing bagong anchor na maaaring gamitin, at ang buong pool ng mga tile ay nangangahulugang ang tanging tunay na limitasyon ay aling mga pagtugma ang pinapayagan ng diksyunaryo.7
Ipagpatuloy ito pabalik. Sa isang delibadong mapag-ingat na libong legal na galaw bawat turno, ang WordChess ay umabot sa 10120, ang numero ni Shannon, ang kumplikasyon ng isang buong laro ng chess, sa loob ng unang labing-anim na galaw. Paggamitan ang sampung libong galaw bawat turno, na pa rin ay rasonable, at ang labing-anim na galaw ay tumataas patungo sa 10160: isang margin na apatnapu hanggang daang orders of magnitude higit sa ng chess 1060.1
Pababain ang pagtataya hanggang sa ikaw ay nag-aasumang ang isang manlalaro ay nakakahanap lamang ng tatlong daan legal na galaw bawat turno, isang bahagi ng tunay na bilang, at kahit dalawampu na galaw pa rin 1099. Patuloy na apatnapung order of magnitude pa rin ito kaysa sa chess. Natatag ang konklusyon sa bawat pessimistic na assumption na maaari mong ibigay dito.1
Ang mga numero ng chess ay produkto ng dekada ng exhaustively na komputasyon; sila ay kilala. Ang mga WordChess ay mga maingat na estimate, hango sa kanyang tunay na mga parameter, isang 25×25 na board, isang 148,941-word na dictionary, at ang full-pool na rack, at may malawak na error bars. Ang hindi sa duda ay ang direksyon at sukat ng pagkakaiba. Bawat assumption sa artikulong ito ay pinili upang maging conservative, at ang pagkakaiba ay patuloy na napakalaki.
Pinipigilan ka ng chess: ang knight ay gumagalaw bilang isang knight, ang pawn ay lumakad ng isang square, at ang iyong mga opsyon, bagama't mayaman, ay finite at kilala. Ipinapasa ng WordChess ang buong wika at buong board at humihingi sa iyo na pumili. Ito ang trade na ginagawa ng disenyo, at ito ang dahilan kung bakit ang friendly na grid ay nagtatago ng isang combinatorial na karagatan.
Hindi ginagawa nito ang WordChess na mas mahirap gawin, ang mas malaking search space ay hindi pareho sa mas malalim na estratehiya, at ang henerosidad ng chess ay kung gaano karaming kahulugan na iniiwas nito mula sa kanyang makitid na paghihiwalay. Ngunit sinumang nag-iisip na ang laro ng mga salita ang lightweight na opsyon ay talagang nakabaliktad ang matematika. Para sa kanyang unang dalawampu na galaw, ginagawa ng WordChess na parang halos maliit ang malaking laro ng mga hari.
Paraan. Ang "20 moves" ay nangangahulugang 20 para sa bawat manlalaro, 40 half-moves, ang konbensyon sa chess. Chess: bilang ng laro ≈ b40 na may b ≈ 30–35 → ~1060. WordChess: ang pagtantiya ng opening branching ay mula sa (mga laruang salitang tumatawid sa gitna) × (mga pagkakalagay bawat salita) ≈ 106 bawat panig; ang mga huling turno ay pinanatili sa mapag-ingat na 103–104 → b40 ≈ 10120–10160. Ang 1099 floor ay gumagamit ng b = 300. Ito ay mga pagtantiya, hindi mga patunay; tingnan ang "A note on certainty."