スプレイグ・グランディの定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/11/04 07:51 UTC 版)
スプレイグ・グランディの定理（英: 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.
- Grundy, P. M. (1939). “Mathematics and games”. Eureka 2: 6–8. オリジナルの2007年9月27日時点におけるアーカイブ。. Reprinted, 1964, 27: 9–11.
- Schleicher, Dierk; Stoll, Michael (2004). An introduction to Conway's games and numbers. arXiv:math.CO/0410026.
- Milvang-Jensen, Brit C. A. (2000). Combinatorial Games, Theory and Applications.
関連項目
外部リンク
| 定義 | |
|---|---|
| 解概念と精緻化 | |
| 戦略 | |
| ゲームのクラス | |
| ゲーム | |
| 定理 |
|
| 主要人物 |
|
| 関連項目 | |
- スプレイグ・グランディの定理のページへのリンク
