小清水さんとコンピューター数学

コンピューター・数学 に関することを書きます (特に丸め誤差の話が多いです。)

素数大富豪だけじゃなく HEX もやろう! ― 紹介編―

小清水 です。 (@curekoshimizu)

twitter 上で 素数大富豪 が大変流行ってるのを目撃しております!

素数大富豪アドベントカレンダー

もつくられており楽しそうです!

HEX の提案!

そんな数学コミュニティに流行って欲しいゲームがあります。

それが HEX です。

この HEX は 数学的背景が大変おもしろいゲーム です。

そしてこれを考えたのは

ゲーム理論で有名な数学者 ジョン・ナッシュ であり、

ビューティフルマインド という映画でも有名な方です。

その ナッシュ学生時代 にこのゲームを考え、

そして 数学的面白さ(証明) を提起しました。

どうですか?ワクワクしてきませんでしょうか。

Abstract

1. HEX とはどんなゲームか?

2. HEX がもつ数学的面白さ

1. HEX とはどんなゲームか?

 n\times n マスで2人でやるゲームになります。

ここでは  5\times 5 マス版HEX で実践例を紹介します。

下のような六角形で敷き詰めた図を考えましょう。

f:id:curekoshimizu:20161222011212p:plain

 5\times 5 マスなので  5\times 5 HEX です。

図が対象的ですので、

先攻・後攻はどちらがどちらでも構いませんが

先攻を紫後攻をピンク

とします。

代わりばんこに塗っていき、

紫は左下から右上につなげると勝ち!

ピンクは右下から左上につなげると勝ち!

というゲームになります。

f:id:curekoshimizu:20161222010516p:plain

つながる?というイメージがわからないかと思うので、

ここで模擬プレイをしてみたいと思います。

HEX 模擬プレイ

先攻真ん中 がおすすめです!

○×ゲームでは真ん中を取ると思いますが、それくらいにオススメです!

奇数  \times 奇数 HEX に真ん中はありませんが、

その場合でも真ん中あたりが有力です。

f:id:curekoshimizu:20161222010541p:plain

この手がすごく強く、後手からすると鬱陶しいです。

続いての後手は適当にうってみましょう。

例えばこうです。

f:id:curekoshimizu:20161222010607p:plain

それを受けて先手はこう打つことにしてみましょう。

f:id:curekoshimizu:20161222010707p:plain

この手は激辛です。

なぜかというと

f:id:curekoshimizu:20161222010727p:plain

「A」・「B」のどちらかに ピンクが打ち込んできても

その反対側を塗ってしまえば

紫は右上までつながることが保証されるからです。

そのため、紫は 真ん中〜右上 までつながったようなものです。

これを実感してもらうと「A」にピンクが打ってきたらその反対側を塗る。

f:id:curekoshimizu:20161222100320p:plain

これを実感してもらうと「B」にピンクが打ってきたらその反対側を塗る。

f:id:curekoshimizu:20161222100327p:plain

真ん中から右上までつながりました!

ピンクの手として次にこの手を考えてみましょう。

f:id:curekoshimizu:20161222100333p:plain

これにはこの手が激痛です。「C」に対して先程と同じことが成立します。

f:id:curekoshimizu:20161222100339p:plain

紫勝利図

紫がつながりました!

f:id:curekoshimizu:20161222100349p:plain

途中経過は飛ばしますが、

例えばこういうつながり方でもOKです。

f:id:curekoshimizu:20161222013746p:plain

2. HEX がもつ数学的面白さ

1. (きちんとやれば)先手必勝ゲームである ことが証明できる

2. 引き分けがなく、盤面を埋めれば絶対に勝敗がきまる ことが証明できる

先手必勝手順の存在性

実は、先手必勝手順の 存在性 を証明できます。

だからといって面白くないと言っているわけではりません。

将棋もチェスも プロの勝率を考えると明らかに 先手優勢です。

具体的な手順が示せるわけではなく、

先手必勝手順があるらしい

という内容になります。

実数係数多項式複素数上で必ず存在する (代数学の基本定理) が、

その厳密解の求め方はわからないと似てますね。

とはいえ、 5\times 5 で見たように

 n\times n HEX で マス が小さいと

実感として 先手有利なことがわかります。

 11 \times 11 HEX までは 先手が 実感としてかなり有利 です。

個人的におすすめの大きさは

 15 \times 15 HEX になります。

f:id:curekoshimizu:20161222100312p:plain

印刷してプレイしてみてください!盛り上がりますよ。

先程のような先手一方戦にはならず、

後手からの反撃が始まります!

引き分けがない

引き分けがないというのがHEXの特徴です!

将棋もチェスも引き分けがあるゲームです。

一方で HEX は 数学的性質から 引き分けがないことが証明できます。

すなわち、

どうあがいても 最後まで塗ると必ずつながっていることになる ということになります。

このことをよくよく考えると、

HEX の逆 ができるということです。

すなわち、

つなげたら負け!というルールでも HEX は成立する

ということになります。

引き分けがないことの証明方法は?

  • Jordanの曲線定理
  • Schauderの不動点定理

を使うと証明ができます。

f:id:curekoshimizu:20161222095832p:plain:w400

準備が大変ですが、いつかこのブログで証明できればいいなと思っております。

今回は 紹介編 ということで証明はでてきません。

ブログ更新を楽しみにしてください!

Summary

数学の証明と紐付いたゲーム (Jordanの曲線定理・Schauderの不動点定理) である、

絶対に引き分けることができないゲーム、

HEX を紹介しました!

Android アプリ でも HEX はできます。

皆さん是非プレイしてみてください!