グランディ関数

グランディ関数について

グランディ関数は、非循環の有向グラフにおいて各頂点に整数を割り当てる関数で、スプレイグ・グランディ関数とも呼ばれます。この関数は、役割の区別がない2人交互型ゲームにおいて、プレイヤーの動きの結果を数学的に解析するために非常に有用です。特に、自分の番に手がない場合に負けとなるゲームの勝敗に関与します。

定義

ゲーム局面の表す有向グラフ

有向グラフは、頂点の集まりとそれをつなぐ有向辺から成り立っています。ある頂点から次の頂点へ向かう有向辺によって、ゲームの各局面を頂点で示します。それぞれの局面の後に続く局面は、現在の局面から可能な手を選んだ結果の頂点で示され、次の局面の集合が関数Nで表されます。

グランディ関数の計算

特定の頂点xに関連づけられるグランディ関数gは、次のように定義されます。

• - 如果N(x)が空集合（次の頂点が存在しない場合）なら、g(x)は0です。
• - N(x)に次の頂点が1つ以上存在する場合、g(x)は次の頂点のグランディ関数の値と一致しない最小の非負整数となります。

必勝法の原理

グランディ関数の値g(x)が正の場合、対応する局面を選んだプレイヤーが勝利する可能性が高いとされています。この理由は、適切な手を選ぶことで次の局面のグランディ値が0になる方へ持っていけるからです。一方で、g(x)が0の場合には、次に移行可能な局面でどの手を選んでもグランディ関数の値が正となるため、その局面のプレイヤーが不利になります。

実例

1山くずしゲーム

このゲームは、2人が交互にコインを取り合い、最終的にコインを取れなくなった方が負けとなる形式です。以下に、毎回1枚から3枚を取る場合と、毎回1枚を取る場合のグランディ関数を考えてみます。

毎回1枚以上3枚以下取る場合

• - コインが5枚ある局面では、次の局面はN(5)={4,3,2}となります。
• - 各局面のグランディ関数値は、g(0)=0, g(1)=1, g(2)=2, g(3)=3, g(4)=0, g(5)=1となり、g(5)が正なので先手が勝つことが予想されます。

毎回1枚取る場合

• - 同じくコインが5枚ある局面の場合、次の局面はN(5)={4}です。
• - この場合のグランディ関数値は、g(0)=0, g(1)=1, g(2)=0, g(3)=1, g(4)=0, g(5)=1となり、やはり先手が勝つことが示唆されます。先手はコインを1枚取り、自らの勝利へとつなげられます。

毎回1枚以上取る場合

• - この場合の次の局面はN(5)={4,3,2,1,0}です。
• - 各局面のグランディ値はg(0)=0, g(1)=1, g(2)=2, g(3)=3, g(4)=4, g(5)=5となり、先手が全枚数を取ると勝利します。

ゲームの和

2つのゲームG1とG2の合成ゲームG1 + G2では、プレイヤーはどちらかのゲームの手を選択し、その局面からゲームを続けます。この合成ゲームのグランディ値は、スプレイグ・グランディの定理を用いて各ゲームのグランディ値のニム和で求めることが可能です。たとえば、同じ1山くずしゲームが2つあるとき、そのニム和を利用して局面のグランディ値を計算し、勝敗を導き出すことができます。

このように、グランディ関数はゲーム理論において欠かせない概念であり、正確に理解し活用することでゲームの戦術に深みを与えることができます。

もう一度検索