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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

スプレイグ・グランディの定理(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. 

外部リンク[編集]