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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
Jump to navigation Jump to search

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

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

参考文献[編集]

  • Schleicher, Dierk; Stoll, Michael (2004). An introduction to Conway's games and numbers. arXiv:math.CO/0410026. 

外部リンク[編集]