情報拡散ゲームについて

この記事は「数学ゲーム Advent Calendar 2018」4日目の記事です

こんにちは、さくBです。

アドベントカレンダーに参加するのは初めてですので、どうかよろしくお願いします。

普段は折り紙を折っていますが、今日は数学ゲームの話をしたいと思います。

ここでお話するのは「情報拡散ゲーム」というものです。

名前に「ゲーム」とついていますが、現実的に対戦して遊ぶというよりは、情報拡散の振る舞いを観察しようという視点でお話します。

（ちなみに僕が院生時代に研究したテーマです）

図のように盤面の中心のマスに青いマーカーが置いてあります。

この青いマーカーは情報源です。

1秒後には隣接するマスに情報が伝達されます。

さらに1秒後には、また隣接するマスに情報が伝達され広がります。

さらに1秒後にはもっと広がります。

これが情報拡散の基本です。

ここまでは大丈夫でしょうか。

では次に別の色の情報も追加してみましょう。

例えば青色のマーカーと赤色のマーカーが図のように置かれているとします。

この場合の情報拡散の振る舞いを見てみましょう。

まず、1秒後です。

そして2秒後。

3秒後。

4秒後。

グレーのマスが出てきましたね。

これは青色の情報と赤色の情報が同時に到達し、どちらの情報もうまく伝わらなかったことを意味します。

青色の情報を伝えたいプレイヤーにとっても、赤色の情報を伝えたいプレイヤーにとっても残念な結果です。

（また、一度色がついたマスは、後から来た別の色の情報によって上書きされることはありません）

さて、今度は少し特殊な盤を用います。

上辺と下辺、右辺と左辺がそれぞれつながっている、「トーラス」と呼ばれる形の盤です。

それから、マスの数を少し増やしてみました。

上辺と下辺、右辺と左辺がそれぞれつながっているというのは、上図のように情報が反対側の辺にも伝わるという意味です。

長くなりましたが、ここまでが前置きで、ここからが本題です。

青のプレイヤーは中心のマスにマーカーを置きました。

あなたは赤のプレイヤーです。

できるだけ多くのマスに赤の情報を伝えるにはどこに置くのがベストでしょうか？

（青と赤、両方のマーカーが置かれてから情報が拡散され始めます。盤がトーラスであること、7x7マスであることに注意してください）

（一度色のついたマスは、後から来た別の色の情報によって上書きされることはありません）

＝＝＝＝＝＝＝＝＝

しばらく間をあけて

＝＝＝＝＝＝＝＝＝＝

答えは「どこに置いても結果は同じ」でした。

例を2つ紹介します。

この例では、7つのマスがグレーになり、残りを赤と青で等しく分け合っています。

この例でもグレーのマスが7つ、残りを赤と青が等しく分け合います。

今度は、8x8マスの盤面ではどうでしょうか。

例によって、青色は中心付近に置いています。

（トーラスなのでどこに置いても一般性は失いません）

以下の盤面において、できるだけ多くのマスを赤色にするにはどこに赤色のマーカーを置けば良いでしょうか。

＝＝＝＝＝＝＝

またまた少し間をあけて

＝＝＝＝＝＝＝＝

正解は下図の赤マーカーが置いてあるところならどこでもオーケーです。

赤丸で示した場所であればどこに置いても、64マスを青と赤で等しく分け合うことになります。

これまで、情報拡散ゲームの振る舞いを見てきましたが、

盤面が正方形である必要はないので、n×mの大きさの盤面で結果を調べてみると面白いと思います。

特にm,nがともに奇数でm≠nの場合には、変わった結果が得られます。

また、2次元である必要もないので、3次元の場合について考えたり、マスを三角形にしてみたりしても面白いと思います。

これで、今回の情報拡散ゲームについてのお話はおしまいです。

長々とお付き合いいただき、ありがとうございました。

0:31 追記

数学ゲームアドベントカレンダーということでしたが、対戦できないものを紹介してしまい申し訳ありません。

でも、この情報拡散ゲームをもとにして新たな対戦ゲームを作ってみるのも面白いかもしれません。

12月4日分の記事が埋まっていないということで、ピンチヒッター的に記事を書かせていただきました。

記事を書き上げるのもかなり時間ギリギリになってしまい、推敲もせず投稿したため、テンポが早く理解しにくい内容になってしまったことをお詫びします。

でも、アドベントカレンダーに穴をあけずに済んで（少なくとも今日までは）良かったです。

あ、トーラスだし、ドーナツだし、穴はあいてるのか