Sprouts

HISTORY †

最近では、スーパーに行くと、ブロッコリー、マスタード、キャベツ、そばなど、いろいろなスプラウトが販売されているので、Sprouts=もやしのことだなと気づく人も多いかと思います。

Sproutsは、紙と鉛筆だけで遊ぶゲームです。紙の上に図形ができあがっていく様子が、植物の芽が伸びていくようなので、こうした命名をされたのでしょう。

Sproutsは、John Horton Conway と Michael S. Paterson という二人の数学者が、1967にケンブリッジ大学(UK)で発明したゲームです。同学の学生達の間でトポロジーのゲームとして流行しました。

↑

DESCRIPTION †

↑

SETUP †

紙の上に点をいくつか打って置きます。点の数は、通常7個ですが、二つだけでも十分に複雑なゲームになります。

↑

MOVE †

各プレーヤーは、自分の手番で、

点から線を引きます。線は、別の線と交わることがなければ、次のうちのどちらかの書き方ができます。
1. 書き出した点から同じ点に戻る
2. 別の一点に結びつけます。
引いた線の上に、一つ点を書きます。

ただし、一つの点から生える線は3本までという制限があります。

パスはできません。

↑

GOAL †

ルールは二通りあります。

↑

正型 †

手番になっても、線を引けなくなったプレーヤーが負けになります。右の図では、先手が勝ちになります。

↑

逆型 †

手番を終わって、次のプレーヤーが線を引けない状態になったら負けです。右の図では、後手が勝ちになります。

↑

STRATEGY †

ここでは、このゲームについての、考え方を紹介します。

n個の点から始めたとすると

まず、初期状態で、点から引ける線の残りの総数を考えると、裸の点から出せる線の数は3本ですので、3×n です。
次に、一本線を引くと、それぞれの点から一つづつ出せる線の数が減り、一つ点を線上に足します(出せる線=1本)ので、3×n - 2 + 1 = 3×n - 1

点からまだ線が3本出ていない点を、生きている点と呼び、3本出ている点を死んだ点と呼ぶことにします。

点の位置によっては、生きている点でも線を引けない状態になることがあることに注意してください。

先のシーケンスから、一度の手番で出せる線の素は少なくとも一つ減ることは明かです。また、最後の手番に加えられた、最後の点は生きた点の状態でゲームが終わります。つまり、手番が高々(3×n-1)回で決着がつくことがわかります。

ということで、無駄なく生きた点を消費し続けると、最初の点の数によって、偶数回の手番でゲームが終了するか奇数回で終了するかが予測できます。勝つためには、生きた点を殺すかどうかを制御することが必要です。

さて、どのようにゲームの長さを制御すればいいのでしょうか。

n点でスタートしたゲームが、m回の手番で決着するとして、

最終的に紙の上に書かれた点の数 = m + n
生きた点に残った、まだ引ける線の数の合計 l = 3n - m (ゲーム開始時 3nであったものが、一回の手番で一本ずつ減った結果)
ゲームの終了時に、生きた点に隣接する二つの死んだ点があります (右図)
生きた点に隣接した死んだ点以外の死んだ点をパリサイ点*1と呼ぶことにします
ここで、二つの異なる生きた点に隣接する死んだ点は存在しないことを確認しておきます。二つの隣の点が生きているなら、その生きた点は線で接続できるはずです。
パリイ点の数 = 最終的に紙の上に書かれた点の数 - (まだ引ける線の数 + 隣接した死んだ点の数)
... パリサイ点の数 φ = (n + m) - (l + 2l) = (n + m) - 3(3n - m) = 4m - 8n
よって、 m = 2n + 1/4 φ

最後の式から、演繹的に次のことが分かります。

手番は少なくとも2n回必要
パリサイ点は4の整数倍
手番の終了時にパリサイ点が少なくとも P個あれば、ゲームは少なくとも、 2n + 1/4 P 回は続く
上記から、逆に
手番の終わりに、まだ線の引ける線の本数の合計がl本あれば、ゲームは高々 3n - l 回で終わる

これから、ゲームを長引かせたいなら、パリサイ点を作ることが必要です。一方、相手は生きた点を残すように線を引くことで、手番数を短くできるはずです。線で囲まれた領域の中に、どのようにこれらの点が残っていくかを考慮すれば、うまく手番の数を制御できるようになります。

↑