マスログ

2020/10/10

先手必勝!?戦略とゲーム理論(上級編その1)―Grundy数の計算―


 こんにちは。和からの数学講師の岡本です。前回までにお話した「石取りゲーム」。ついに今回は数学的な解説をいたします。初級編、中級編はこちらからご覧いただけます。

初級編

先手必勝!?戦略とゲーム理論(初級編)


中級編

先手必勝!?戦略とゲーム理論(中級編)

1.これまでの考察

 さて、これまでは2山の場合、3山の場合の考察を行ってきました。今回はまず、これらの考察をもう少し詳しく見ていきます。

 2山の場合、「石の数を同じにする」という作戦が必勝法でした。これは言い換えると“同数2山”という状態が、「後手必勝である」ということを意味します。このような状態を後手必勝型と呼ぶことにしましょう。それ以外の状況であれば「うまい一手」により、後手必勝型にすることができます。
 3山の場合も2山と同様に、(1,2,3)や(1,4,5)などの「後手必勝型」があり、それ以外の状況であれば「うまい一手」次第で「後手必勝型」に塗り替えられえます。そのため後手必勝型でない状況を先手必勝型と呼ぶことにしょう。

実はこのゲームの初期配置は先手必勝型と後手必勝型の2通りしかありません。後手必勝型の配置では、どんな手を打っても必ず先手必勝型の配置になってしまい、先手必勝型の配置からは必ず後手必勝型に塗り返す一手が存在することが保証されています。少々わかりづらいネーミングですが、「先手必勝」、「後手必勝」というのは自分主体で考えます。つまり、「この状況であれば自分は先手がいいな」、「この状況であれば後手がいいな」といった具合です。

つまり、このゲームを支配するには「後手必勝型」を知ることがカギになるわけです。

2.戦局の把握

 後手必勝型や先手必勝型の状況を数学的にとらえていきましょう。とらえ方の基本は非常にシンプルで、「ゴール(ゲーム終了の状況)から考える」というものです。
例えば1山の場合、ゲーム終了の状況はもちろん石の数「0」。これを後手必勝型と考えます。「0」になる前の段階の候補は石の数が「1」、「2」、「3」、…と無数に考えられ、どの状況も先手必勝となります。

つまり、1山の場合は「0」という状況以外全て先手必勝型となっています(先攻のプレイヤーが全部の石を取ればゲーム終了となるので当たり前ですね)。では2山の場合はどうでしょうか。初級編で解説した通り、石の数が同数の状況が後手必勝型といえ、それ以外は全て先手必勝型となっています。これも先ほどと同様に「(0,0)」からはじめて、一手前、そのまた一手前という具合に候補を並べていきます。

この図を踏まえて、戦局の状況を表す指標を次節で導入します。

3.戦局の道標―Grundy数―

 ではいよいよ、戦局を特徴付ける指標として「Grundy数」というものを各状況に対して定義します。Grundy数の定義は非常にクセが強いです。

まず、ゲーム終了時点(後手必勝型)のGrundy数を「\(0\)」とします。続いて状況\(A\)のGrundy数を定義しましょう。その状況から移りうる状況たち(\(A_1, A_2, \ldots\))のGrundy数を除く最小の\(0\)以上の整数(非負整数)を、状況\(A\)のGrundy数とします。つまり各Grundy数\(G(A_1),G(A_2),\ldots\)がわかっていないと\(G(A)\)は求められません。

例えば、1山の場合「0」の状況のGrundy数を\(G(0)=0\)と表すことにします。次に状況「1」を考えます。「1」という状況の次にくる状況は「0」のみです。\(G(0)=0\)なので、\(0\)を除く、最小の非負整数として\(G(1)=1\)が得られます。もう少し例を考えましょう。次に石の数が「2」の状況の場合、次の状況の候補は「1」と「0」の2通りあります(もちろん、「0」にすることで勝利ですが、あくまで、取りうる状況全てを考えます)。\(G(0)=0, G(1)=1\)なので、\(0\)と\(1\)を除く最小の非負整数として\(G(2)=2\)が得られます。同様に考えることで一般に

\begin{align*}G(n)=n\end{align*}

という公式が得られます

続いて2山の場合のGrundy数を考えましょう。まずゲーム終了時点の(0,0)のGrundy数を\(G(0,0)=0\)とします。次に状況(1,0)のGrundy数を求めます。まず(1,0)から移りうる状況は(0,0)のみなので、\(G(1,0)\)は\(0\)以外の最小の非負整数である\(1\)となります。同様に\(G(0,1)=1\)も求められます。続いて、\(G(1,1)\)を求めてみましょう。状況(1,1)から移りうる状況は(1,0)または(0,1)の2通りしかありません(これは石取りゲームのルールで、複数の山から石が取れないことから言えます)。\(G(1,0)=G(0,1)=1\)であることから、(1,1)のGrundy数は\(1\)を除く、最小の非負整数として、

\begin{align*}G(1,1)=0\end{align*}

となります。では\(G(2,2)\)はいくらになるでしょうか?状況(2,2)から移りうる状況を全てリストアップすると、(2,1), (2,0), (1,2), (0,2)の4通りとなります。1山の議論からまず\(G(2,0)=G(0,2)=2\)がわかります。また、(2,1)の状況の移りうる状況の候補は

\begin{align*}(2,0), (1,1), (0,1)\end{align*}

の3通りで、それぞれのGrundy数は

\begin{align*}G(2,0)=2, G(1,1)=0, G(0,1)=1\end{align*}

であるので、\(G(2,1)\)のGrundy数は\(2,0,1\)を除く最小の非負整数である\(3\)となります。
このことから

\begin{align*}G(2,1)=3, G(2,0)=2, G(1,2)=3, G(0,2)=2\end{align*}

となり、\(3,2\)を除く最小の非負整数は\(0\)であるので、状況(2,2)のGrundy数は

\begin{align*}G(2,2)=0\end{align*}

と求められます。このGrundy数というのは、戦局の情報を多く持ち合わせており、これを利用することでゲーム全体を支配することが可能となります。つまり、Grundy数は「神の一手の道標」とも言うべき代物です。神の一手については次回の後編にて詰めていこうと思います。

5.さいごに

いかがでしたでしょうか?今回はゲームを支配する指標「Grundy数」の紹介をしました。定義のクセが強く、何をやっているのかわからないかもしれませんがこの数字が神の一手を導いてくれます!次回上級編その2ではいよいよ神の一手の導き方をご紹介いたします!お楽しみに!

和からではご自身のペースで学びたいことを学びたいだけ学ぶことができます。算数や数学の苦手意識克服、お仕事で使う計算から実務に役立つデータ分析まで、幅広く対応いたします。ご興味がある方はぜひ一度無料セミナー、無料個別カウンセリングにご相談ください。

<文/岡本健太郎>

数学教室和(なごみ)」では算数からリーマン予想まで、あなたの数学学習を全力サポートします。お問い合わせはこちらから。お問い合わせページへ

カテゴリー

記事一覧

Instagram

Facebook

Twitter