先手、後手が交互に手を指し、勝敗を競う有名なゲームにNim game(石取りゲーム、3山崩し)がある。Nim gameの必勝法は、既に数学的に完全に解明されている。これまでNim gameを修正あるいは拡張したゲームが様々に考案され、研究されてきた。本論文の考案するゲームNim on graphs(グラフ上のNim)も、Nim gameの拡張であるが、ゲームがグラフ上で行われることに特徴があり、ゲームの展開(先手と後手どちらが有利か)がグラフの構造に深く関わる。事実、ある構造をもつグラフ上のNimの結果を導くのに、Mengerの定理が重要な役割を果たし、別の構造をもつグラフ上のNimの結果が、グラフのMatchingの性質と関わることが分かった。前者を本論文のChapter 1で、後者をChapter 2で論議する。

1　Nim on graphsのルール

Gをグラフとし、今後、主にG上で行われるNim on graphsを考える。グラフGの辺の集合、頂点の集合を、それぞれ記号E(G), V(G)で表すことにする。Nim on graphsのルールを説明する。グラフG上の重み付きグラフと駒を1つ用意し、駒をGの頂点に置く。これを記号Gw,vで表し、Nim on graphsの局面という。ここで、w:E(G)→N=NU{0}はGの辺に重みを与える写像、vは駒を置く頂点である。最初に適当な局面が与えられ、先手、後手が交互に次の手(一連の選択)を行うことによりゲームが進行する。

(i)駒の位置する頂点に接続する辺で正の重みをもつものを1つ選ぶ。

(ii)選んだ辺の重みをより小さな重み(非負整数)に置きかえる。

(iii)駒を、選んだ辺に沿ってもう一方の端点へ移動する。

ただし、自分の手番で、駒の位置する頂点に接続するどの辺の重みも0であるために、指し手を失った競技者を敗者とする。

　注意　図1右のように何個かの小石を積んだいくつかの山を、通常のNim gameの局面という。通常のNim gameとは、与えられた適当な初期局面から始め、先手、後手が交互に次の手を打ち合い、小石が全て取り上げられた結果、指し手を失った競技者を敗者とするゲームである。

　手:山を1つ選び、その山から少なくとも1つ以上の任意個数の小石を取り去る。

通常のNim gameの局面で、それぞれの山の小石の個数がk, l, m,…n個であるもの(図1右)は、図1左のようなグラフ上のNimゲームと同じである。

　先手(後手)が後手(先手)の任意の手に応じて適切な手を指せば、ゲームに必ず勝てるとき、先手必勝(後手必勝)という。また、このときのゲームの初期局面を先手必勝局面(後手必勝局面)という。

　本論文では、ゲームNim on graphsについて、次の2つの問題を考える。

　Problem A:与えられた初期局面から始めたゲームが先手必勝か後手必勝かを決めよ。

　Problem B:与えられた局面のGrundy数を求めよ。

　ここで、局面AのGrundy数g(A)は、次の式で帰納的に定義される非負整数である。

　g(A)=min(N＼{g(A')|A'はAの後続元})　(1.1)

ただし、局面Aを局面A'にするような手が、ルール上許されているとき、A'をAの後続元という。

　これより、次の事実が示せる。

　局面AのGrundy数=0⇔局面Aから始めるゲームが後手必勝である。　(1.2)

よって、Grundy数が求まればProblem Aは解決したことになる。ところが、Grundy数を定義から直接求める計算は膨大であり困難である。ここでいうProblem Bとは、定義よりも簡略に局面のGrundy数を求めるアルゴリズムを見つけることである。

　通常のNim gameに関するProblem Bは既に解決されており、図1右の局面、すなわち、k, l, m,...,n個の小石が積まれた山から成る局面のGrundy数は次の公式で与えられることが知られている。

ここで、演算子〓はNim和であり、次のように定義される。すなわち、2進法表示された非負整数

〓

とする。Nim和は結合則、〓を満たす。

　上述の通り、Problem BはProblem Aを含み、より困難な問題である。しかし、ゲームの勝敗にだけ興味があるなら、Problem Aが解ければ十分である。Problem Bを解くこと、すなわち局面のGrundy数を求めることは、ある種の複合ゲーム(複数のゲームから定義される大きなゲーム)を考える場合に意味を持ってくることが知られている。

2　Chapter 1の主な結果

Nim on graphsの局面を表すグラフGが2部グラフで、ある固定点から奇数距離、偶数距離の点をそれぞれ奇数位置の頂点、偶数位置の頂点ということにし、全ての奇数位置の頂点の次数が2であると仮定する。(図2を参照せよ。)

　Chapter 1の主な目的は、この仮定の下でProblem Aを解くことであり、実際、定理1.2.5がその解を与える。Chapter 1のもう一つの目的は、多重辺をもつグラフ上のNimに関するProblem Bを、多重辺を持たないグラフ上のNimに関するProblem Bに帰着できることを示すことである。以後、定義、定理等の番号は本文に従う。

　定義.G上の重み付きグラフGwがあるとし、u,vをGの相異なる2頂点とする。辺の集合Eについて、u,vを結ぶ任意の道がEのある辺を通るとき、Eをu,vに関する切断集合といい、Eに含まれる辺の重みの合計を、切断集合Eの値という。また、u,vに関する切断集合のうち値を最小とするものを、u,vに関する最小切断集合という。

　定義1.2.1.　重み付きグラフGwのある奇数位置の頂点uに接続する2辺の値が異なるとする。Gwを奇数位置の頂点uで切り離すとは、Gの頂点の集合V(G)に新たな頂点uを加え、uに接続する2辺のうち値の大きい方の辺の端点uをuに置き換え、新しいグラフGuwを作ることとする。このとき、u,uをGuwの切り口と呼び、特にuをGuwの太い切り口と呼ぶことにする。

　定理1.2.5.　Gw,vを、駒が偶数位置vにある任意の局面とする。Gw,vが先手必勝局面であることの必要十分条件は、次の3条件を満たす奇数位置の頂点uが存在することである。

(i)uに接続する2辺の重みが異なる。小さい方の値をmとする。

(ii)uで切り離したグラフGuwの2つの切り口に関する最小切断集合の値がmに等しい。

(iii)Guwの2つの切り口に関する任意の最小切断集合を除いても、vと太い切り口は連結されている。

定理の証明には、Mengerの定理を用いる。

　例1.2.2.　図2の2つの局面それぞれについて、Problem Aを解こう。左の局面については、定理1.2.5の3条件を満たす奇数位置の頂点uが見つかる。一方、右の局面については、条件(i)(ii)を満たす奇数位置の頂点が1つ見つかるが、これは条件(iii)を満たさないことが分かる。よって、定理1.2.5より、左の局面は先手必勝局面、右の局面は後手必勝局面であると結論づけられる。

3 Chapter 2の主な結果

Chapter 2では、局面を表すグラフGが多重辺及び輪(同じ点を結ぶ辺)をもたないとする。Section 2.2と2.3では、さらに、交互閉路を持たない最大マッチングをもつと仮定し、これをMで表し、固定する。Chapter 2の主な目的は、この仮定の下で、Nim on graphsに関するProblem AとProblem Bを調べることである。Section 2.2がProblem Aを、Section 2.3がProblem Bを扱う。これらの結果を利用することにより、Nim on treesに関するProblem Bが完全に解決する。これをSection 2.4で例を用いて説明する。Section 2.5では、Nim on cyclesに関するProblem Bを完全に解決する。

3.1　Problem Aに関する結果(本文のSection 2.2)

定義2.2.1.　仮定で与えられた最大マッチングMについて、次の記号を導入する。

　B=Mの不飽和点を始点とするM−交互道に含まれる全ての辺から生成される辺部分グラフ

　O=Mの不飽和点から偶数長のM−交互道で結ばれ得る頂点の集合

　O1={u∈O|Mの不飽和点u0が存在し、u0とuを結ぶM−交互道が唯1つ存在する。}

u∈O1に対し、不飽和点u0とuを結ぶ唯1つのM−交互道をLu、MをLu上で交換して得られる最大マッチング、すなわち(M−E(Lu))∪(E(Lu)−M)を、記号Muで表す。なお任意の不飽和点uは、その不飽和点自身から長さ0の唯一のM−交互道で結ばれると考え、O1に属するものとする。またこのとき、Mu=Mであることが分かる。

　次の定理は、最大マッチングMをもつグラフ上のNimに関するProblem Aをある程度解決する。

　定理2.2.6.　(i)v∈O1のとき、〓Mv,vこ属する局面は後手必勝局面である。特に、vがMの不飽和点のとき、〓M,vに属する局面は後手必勝局面である。

　(ii)v〓Oのとき、〓M,vに属する局面は先手必勝局面である。

但し、E⊂E(G)、v∈V(G)に対し、〓E,v={Gw,v|任意のe∈Eに対して、w(e)>0}とする。

　例2.2.1.　図3(a)のグラフGについて、太線で示された辺の集合を最大マッチングMとすれば、Mは交互閉路を含まない。このとき、図の破線部分にグラフBが見つかる。また集合O1、O＼O1に属する頂点、Oに属さない頂点を、それぞれ記号○、□、・で示している。図の全ての辺の重みを任意の正の整数とすると、定理2.2.6より、図(a)において駒を○の頂点においた局面は後手必勝局面、駒を・の頂点においた局面は先手必勝局面であることが分かる。

　実際、駒を・に置いた図(a)の局面からゲームを始めれば、先手は次の作戦で必ず勝てる。

　先手の作戦:駒の位置する頂点に接続しMに属する辺を選び、その辺の重みを0とする。

　一方、uをO1の頂点(○の頂点)、例えば図3(a)の中央の頂点とすれば、Mをuとu0を結ぶ唯1つのM−交互道Lu上で交換して得られる最大マッチングMuは図(b)の太線のようになる。駒をuに置いた図(b)の局面からゲームを始めれば、後手は次の作戦で必ず勝てる。

　後手の作戦:駒の位置する頂点に接続しMuに属する辺を選び、その辺の重みを0とする。

3.2　Problem Bに関する結果(本文のSection 2.3)

GからBに属する全ての辺を取り除いて得られる連結成分の1つをC、Cの境界Γ(C)を次で定義する。

次の定理は、最大マッチングMをもつグラフ上のNimに関するProblem Bの解決に重要な役割を果たす。

　定理2.3.5.　v〓Oとし、GからBに含まれる全ての辺を取り除いて得られる連結成分のうちvを含むものをCとする。Γ(C)⊂O1のとき、EL=Uu∈Γ(C)E(Lu)とすれば、∀Gw,v∈〓M∪EL,vに対し、

である。ここで、

とする。特にMがGの完全マッチングなら、B=〓、C=GよりΓ(C)=〓であるから、EL=〓として、式(3.2)が成立する。

　例2.3.1.　図3(a)のグラフGを考える。グラフGからグラフBに含まれる全ての辺(すなわち図3(a)の破線内の辺)を除くと、孤立点でない連結成分が、図の左下と右上に見つかる。これをそれぞれC1, C2とおくと、Γ(C1)は図の"○"の頂点から成り、Γ(C1)⊂O1が分かる。よって、駒がC1内(図4(a)の破線内)にあれば、C=C1として定理2.3.5が適用できる。図4(a)の太線は、このときの辺の集合M∪ELに含まれる辺を表す。すなわち、図4において、図4(a)の太線の辺の重みを正の整数とする任意の局面(a)について、g(局面(a))=g(局面(b))+1が分かる。但し、図4(b)では重み0の辺を省略している。一方、図3(b)より、Γ(C2)は□の頂点を含み、Γ(C2)〓O1であるから、駒がC2内にある場合、定理2.3.5を適用することができない。

3.3　Nim on treesに関するProblem Bの解決(本文のSection 2.4)

Nim on treesの任意の局面のGrundy数は、定理2.3.5の繰り返しの適用、及び、定理2.2.6(i)の適用により、必ず計算することができる。すなわち、Nim on treesに関するProblem Bは完全に解決された。

　例2.4.1.　図5の局面(a)のGrundy数を求めよう。局面(a)のグラフに対し図の太線の最大マッチングをMとすれば、破線部分にグラフBが見つかる。局面(a)をGw,vとし、これに定理2.3.5を適用すれば、Gσ(w),vとして、図(b)の局面が得られ、g(局面(a))=g(局面(b))+1を得る。局面(b)のグラフから、ゲームに影響しない重み0の辺を除き、局面(c)に再び定理2.3.5を適用すれば、g(局面(b))=g(局面(c))=g(局面(d))+1を得る。重み0の辺を除けば局面(d)は局面(e)に他ならない。局面(e)に対し図のような最大マッチングをMとすれば、駒△は不飽和点にあるから、定理2.2.6(i)よりg(局面(e))=0である。これらより、局面(a)のGrundy数は2であることが分かる。

3.4　Nim on cyclesに関するProblem Bの解決(本文のSection 2.5)

次の命題により、Nim on odd cyclesに関するProblem BがNim on treesに関するProblem Bに帰着される。

　命題2.5.1.　Gw,vを奇数長の閉路上のNimの局面とする。任意の辺eの重みw(e)が正なら、

　g(Gw,v)=g(Gw−1,v)+1　(3.4)

である。ここで、w−1:E(G)→NはGの各辺に重みを与える写像で、次のように定義する。

　任意の辺e∈E(G)に対し、(w−1)(e)〓w(e)−1

　次の命題を述べるため、非負整数m, n, kの関数gk(m, n)を次のように帰納的に定義し、導入する。

ここで、〓は(1.4)で定義されたNim和である。

　次の命題により、Nim on even cyclesに関するProblem BがNim on treesに関するProblem Bに帰着される。

　命題2.5.2.　Gを偶数長の閉路、Gの2通りの完全マッチングをE0, E1とすると、局面Gw,vのGrundy数は次の公式で与えられる。

ここで、m=min{w(e)|e∈E0}、n=min{w(e)|e∈E1}、k=g(Gw−m1E0−n1E1,v)であり、w−m1E0−n1E1:E(G)→NはGの各辺に重みを与える写像で、次のように定義する。

Nim on treesに関するProblem Bは完全に解決されたのだから、これらの命題より、Nim on cyclesに関するProblem Bも完全に解決された。

図1.通常のNimゲームに同値なNim on graphs、△は駒を表す。

図2.　定理1.2.5を適用できる局面の例

図3　交互閉路を持たない最大マッチングをもつグラフ上のNim

図4　例2.2.1の局面(a)(図3)に定理2.3.5を適用する。

図5　Nim on treesの例

　ニムゲーム(石取りゲームあるいは3山崩し)とは、碁石をいくつかの山に分けて積んでおき、2人のプレーヤーが交互に1つの山を選んでそこから好きなだけ石を取り除いていくとき、最後に取る石が無くなった方を負けとするゲームである。このゲームについて、最初の状態が与えられたときに先手必勝であるか後手必勝であるか、すなわち相手がどのような手を指してきてもうまく対処すれば必ず勝てるという方法がどちらのプレーヤーにあるのかということが問題になるが、それは既に20世紀初頭に解決されていた。知られている結果によれば、ある山の石の個数を1つ変えただけでもどちらのプレーヤーが必勝であるかは変化し、その意味で解答はデリケートであり単調性のない世界である。もちろん起こり得る場合すべてについてそれぞれ調べていけばよいのだが、それは膨大な作業になり現実的な解決を与えるとはとうてい言えない。そこで数学的にはGrundy数とよばれる量を帰納的に定義し、それを解析することによって解答を得ることが行われている。さらに、ニムゲームのルールを修正・拡張したゲームが色々考案され研究対象になっている。

　論文提出者福山は、グラフ上のニムゲームという新しいゲームを導入しその先手必勝・後手必勝を調べ、さらにある場合にGrundy数自身を求める研究を行った。これは組み合わせゲーム理論とグラフ理論を結びつける全く新しい分野の開拓である。福山の考案したゲームとは次のようなものである。まず有限グラフGを考える。Gは頂点の集合と、頂点を結ぶ辺の集合からなる。各辺の上には石が積まれている。すなわち各辺に非負整数が対応づけられている。また、ある頂点に駒が置かれている。これが初期状態である。ゲームは、まず先手が駒のある頂点につながるいくつかの辺のうち1つの辺を選びその辺の上の石を任意個数取り去り同時にこの辺に沿って他方の頂点に駒を動かすという操作によって開始される。後手は同様に、先手が移動した駒のある頂点につながる1つの辺を選びその上にある石をいくつか取り去り辺に沿って駒を移動する。以下、先手・後手が交互にこの操作を繰り返していき、石を取り去ることができなくなった方が負けである。

　提出された論文の第一章では、Gは2部グラフであって奇数位置の頂点からは常に辺が2本出ていると仮定して、駒が偶数位置の頂点にあるときに先手必勝あるいは後手必勝を判定するための必要十分条件を与えた。この定理を用いれば駒が奇数位置にある場合にも結果が得られるので、上記のGについては問題は完全に解決されたと言ってよい。証明には、グラフ理論の基礎定理であるMengerの定理、すなわちG上の2つの頂点を分離するために必要な辺の最小個数を頂点を結ぶ道の個数で表示する定理を基本的に用いている。Mengerの定理のこのような応用は初めてであり、その意味でグラフ理論とゲーム理論をうまく結びつけた結果であると言える。

　論文の第二章では、Grundy数自身の解析を行っている。Grundy数が0になることは後手必勝であることと同値であるので、単に先手必勝か後手必勝かを調べるよりも深い解析を進める必要がある。福山は、グラフGは交互閉路をもたない最大マッチングをもつと仮定して、グラフの簡略化によるアルゴリズムを与えることにより問題の解決を図った。得られた定理は樹木(tree)あるいはサイクル(cycle)に応用されている。これらはグラフGの形にのみ依存して決まる結果であり、各辺の上に積まれた石の個数にはよらない。

　ニム型のゲームの必勝法理論は2進法展開に依拠して本質的に単調でないふるまいを見せるが、福山はグラフ上でMengerの定理を用いて流量という物差しに立脚してそれを表現する手法を開発した。このような点に本質的に新しいアイデアを見出すことができる。

　よって、論文提出者福山真彦は博士(数理科学)の学位を受けるにふさわしい充分な資格があると認める。