コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

スプレイグ・グランディの定理

出典: フリー百科事典『ウィキペディア(Wikipedia)』
Sprague-Grundyの定理から転送)

スプレイグ・グランディの定理: Sprague–Grundy theorem)とは、 組合せゲーム理論において、通常のプレイ規約下におけるすべての公平ゲームニム数英語版と等価であることを意味する定理である。このとき、公平ゲームにおけるグランディ値ニム値はゲームと等価なユニークな数として定義される。位置(もしくは位置の加数)に自然数(例えばニムのようなゲームにおいて考えられるヒープのサイズ)によって添字が付けられているゲームの場合、連続したヒープサイズに対するニム数の列はゲームのニム列と呼ばれる。

この理論は R. P. Sprague英語版 (1935) と P. M. Grundy英語版 (1939) により別々に発見された。

参考文献

[編集]
  • Sprague, R. P. (1935–36). “Über mathematische Kampfspiele”. en:Tohoku Mathematical Journal 41: 438-444. NAID 20000416299. https://www.jstage.jst.go.jp/article/tmj1911/41/0/41_0_438/_article/-char/ja/. 
  • Schleicher, Dierk; Stoll, Michael (2004). An introduction to Conway's games and numbers. arXiv:math.CO/0410026. 

関連項目

[編集]

外部リンク

[編集]