シャノン数

シャノン数は、アメリカの数学者クロード・シャノンにちなんで名付けられ、チェスのゲームツリーの複雑さの控えめな下限値10 ¹²⁰であり、白の次に黒の手が続く 2 組の手の可能性が平均で約 10 ³個あり、典型的なゲームはそのような手の組み合わせが約 40 回続くことに基づいています。

シャノンの計算

シャノンは1950年の論文「チェスをプレイするコンピュータのプログラミング」の中で、チェスのゲームツリーの複雑さの下限を計算し、約10 ^120通りのゲームの可能性を示し、チェスを力ずくで解くことの非実用性を実証した。 ^{[1] (この影響力のある論文は、}コンピュータチェスの分野を紹介した。)

シャノンはまた、可能なポジションの数を、一般的にの順序、つまりおよそと推定しました。これには、いくつかの違法なポジション (たとえば、第 1 列にポーンがある、両方のキングがチェックされている) が含まれ、キャプチャーや昇格後の合法的なポジションは除外されます。 ${\frac {63!}{32!{8!}^{2}}}$ $3.7*10^{43}$

各プレイヤーが駒を 5 回ずつ動かした後 (10手)、プレイできるゲームは 69,352,859,712,417 通りあります。

より厳しい境界

アッパー

ビクター・アリスはシャノンの数を考慮して、ポジションの数の上限を5×10 ⁵²と計算し、実際の数は約10 ⁵⁰であると推定した。^[4]その後の研究では、上限は8.7×10 ⁴⁵であると証明され、^[5]昇進がない場合の上限は4×10 ^{37であることが示された。}^[6]^[7]

より低い

アリスはまた、ゲームツリーの複雑さは「平均分岐係数 35 と平均ゲーム長さ 80 に基づいて」少なくとも 10 ^{123であると推定しました。比較として、よく比較される}観測可能な宇宙の原子の数は、おおよそ 10 ⁸⁰と推定されます。

正確な見積もり

ジョン・トロンプとピーター・エステルランドは、整数とチェスの位置の間の効率的に計算可能な一対一関係に基づいて、95%の信頼水準で合法的なチェスの位置の数を推定しました。 ^[5] $(4.822\pm 0.028)\times 10^{44}$

賢明なチェスゲームの数

シャノン数との比較として、チェスを「理にかなった」ゲームの数で分析すると（クイーンをポーンに即座に取られて補償を受けないなど、馬鹿げた、または明らかに負ける動きは数えず）、結果は約 10 ⁴⁰ゲームに近くなります。これは、各プレイ（半手）で約 3 つの理にかなった動きの選択肢があり、ゲームの長さが 80 プレイ（または、同等に 40 手）であることに基づいています。^[8]

参照

注釈と参考文献

^ シャノン、クロード E. (1950 年 3 月)。レヴィ、デイヴィッド (編)。「XXII. チェスをプレイするためのコンピュータのプログラミング」(PDF)。哲学雑誌。7. 41 (314)。ニューヨーク、NY:シュプリンガー: 256–275。doi : 10.1080 /14786445008521796。ISBN 978-1-4757-1970-3. ISSN 1941-5982. 2020年5月23日時点のオリジナル（PDF）からアーカイブ。
^ “A048987”. OEIS .
^ “A079485”. OEIS .
^ Allis, Victor (1994). ゲームと人工知能におけるソリューションの探求( PDF)。マーストリヒト、オランダ:リンブルフ大学博士論文。ISBN 978-90-900748-8-7。
^ ab Tromp, John (2022). 「チェスポジションランキング」. GitHub .
^ Steinerberger, Stefan (2015年8月). 「チェスにおける昇格のないポジションの数について」. International Journal of Game Theory . 44 (3): 761–767. doi :10.1007/s00182-014-0453-7. ISSN 0020-7276. S2CID 31972497.
^ Gourion, Daniel (2022年10月12日). 「昇格のないチェスダイアグラム数の上限」. ICGAジャーナル. 44 (2) (バージョン2版): 44–55. arXiv : 2112.09386 . doi :10.3233/ICG-220210 . 2021年12月18日閲覧。
^ Grime, James (2015年7月24日). チェスのゲームは何種類あるか? (ビデオ). Numberphile – YouTube経由。ジェームズ・グライム博士がシャノン数とその他のチェスについて語っています (ブレイディ・ハランによる動画)。MSRI、数学科学。

外部リンク

数学とチェス

[1] シャノン、クロード E. (1950 年 3 月)。レヴィ、デイヴィッド (編)。「XXII. チェスをプレイするためのコンピュータのプログラミング」(PDF)。哲学雑誌。7. 41 (314)。ニューヨーク、NY:シュプリンガー: 256–275。doi : 10.1080 /14786445008521796。ISBN 978-1-4757-1970-3. ISSN 1941-5982. 2020年5月23日時点のオリジナル（PDF）からアーカイブ。

[2] “A048987”. OEIS .

[3] “A079485”. OEIS .

[4] Allis, Victor (1994). ゲームと人工知能におけるソリューションの探求( PDF)。マーストリヒト、オランダ:リンブルフ大学博士論文。ISBN 978-90-900748-8-7。

[TrompCPR-5] Tromp, John (2022). 「チェスポジションランキング」. GitHub .

[6] Steinerberger, Stefan (2015年8月). 「チェスにおける昇格のないポジションの数について」. International Journal of Game Theory . 44 (3): 761–767. doi :10.1007/s00182-014-0453-7. ISSN 0020-7276. S2CID 31972497.

[7] Gourion, Daniel (2022年10月12日). 「昇格のないチェスダイアグラム数の上限」. ICGAジャーナル. 44 (2) (バージョン2版): 44–55. arXiv : 2112.09386 . doi :10.3233/ICG-220210 . 2021年12月18日閲覧。

[8] Grime, James (2015年7月24日). チェスのゲームは何種類あるか? (ビデオ). Numberphile – YouTube経由。ジェームズ・グライム博士がシャノン数とその他のチェスについて語っています (ブレイディ・ハランによる動画)。MSRI、数学科学。