[Ploy]

このコーナーでは、アブストラクトゲームと数学の関係や、ゲームの設計に潜む数理科学用語などを紹介します。

数学コラムのコーナー

  1. ゲーム理論と室内ゲーム
  2. The Ring Worldのボードについて

Fano Plane

Fano Plane

FIRE and ICEは、Fano Planeをデザインの基本にしたゲームです。

Fano Planeとは位数2のFinite Plane(有限平面)もしくは射影平面(Projective Plane)のことです。(日本語では射影平面という呼び方の方が一般的かもしれません。)

位数 q の射影平面とは、次の条件を満たす図形です。

q2 + q + 1 個の点からなり、

  1. どの直線も q + 1 点を通る
  2. どの2点も、ただ1つの直線に乗る

Fano Planeは、q=2の時の図形で、図のような形になります。 いずれの点や線も、上記の条件を満たしていることが確認できます。 (この平面上では、頂点{1,2,4}の内接円も直線とみなすことをご理解ください。)

別の言い方をすれば、頂点の集合{1,2,3,4,5,6,7}における、Fano Planeの端は、 {1,2,4}, {2,3,5}, {3,4,6}, {4,5,7}, {5,6,1}, {6,7,2}, {7,1,3} と言えます。 これらの端は、三要素{1,2,4}にそれぞれ、7を法として1ずつ加えることで生成できます。 生成規則によって作られた三要素は、他のいずれの二つの要素とも異なり、いずれの順序においても、すべての対応する要素が7を法として異なる要素を持っています。

  • Fano330-R-Morrisは、まさにこの図形をゲームボードとしたアブストラクトゲームです。
  • FIRE and ICEでは、この7種類の端の組み合わせが、島の征服条件であり、 どうようのパターンで島をつなげた場合に勝利条件になっています。

ゲームの解決

論理的には、アブストラクトゲームとコンピューター2で言及したように、Mini-Max法によって、(主に二人で対戦する)アブストラクトゲームは、どちらのプレーヤーが勝つか、引き分けるかといった解を得ることができます。しかし、当館に掲載してあるようなほとんどの単純でないゲームは、ゲームの探索空間が広く、現実時間内に、すべての場合を計算し尽すことが困難です。しかし、ゲームの顛末はどうなるのかについて、数学的な考察によって探索空間を狭める工夫に加えて、膨大なコンピューター時間を費やすなどによって、いくつかのゲームが解決されています。

ゲームの研究において、解決のレベルをしめすために使われる用語がありますので簡単に解説しておきます。Solved Gameについて、英語版WikiPediaでは充実した情報が掲載されていますが、日本語の情報が見当たりませんので、ここでは、英語版WikiPediaに書かれている内容を中心に紹介します。

Ultra-weak
極弱く(解決)
完全な手をお互いが指した場合、「先手必勝か、後手必勝か、または引き分けになるか、ゲームの開始時点からわかっている」ことが証明できている。完全な手を決定しえないような、構造的でない証明によるものでも構わない。
例えば、Hexは、NashによってUrtra-weakに解決されたゲームです。
Weak
弱く(解決)
普通「解決されている」状態というと、この「Weakに解決されている」状態を指す。ゲーム開始時から、起こりうるすべての合法手に対して、勝利、引き分け、負けになるアルゴリズムが提示されている。
Connect 4, 立体四目並べ / Qubic他、多くの解決されたとされているゲームは、Weakに解決されたゲームです。
Strong
強く(解決)
(どちらか、または両方のプレイヤーがさし間違いのミスを犯した後も含む)すべての局面において、完全な指手を生成できるアルゴリズムを提示することができる。
探索空間の狭いTic-tac-toeや、論理的な必勝手順が示されているnimは、Strongに解決されたゲームです。

Perfect play / 完全な手 ... 最善手

完全な手とは、相手の手に関わらず、プレイヤーを最善の結果をもたらす戦略/選択のことです。2Playerのアブストラクトゲームは、ゲームの終了*1時点では、必ず、どちらかのプレーヤーが勝っているか、引き分けになっていますので、その状態から帰納的に完全な手=意図的に自分に不利な手を選択しないような手を選択して、途中局面までさかのぼり、途中の局面についても評価を与えることができます。同じ結果になるような複数の選択肢がある場合には、自分に有利な結果なら最短でそこにたどり着く、自分に不利な結果になるなら最長の手数を費やす、手を完全な手と限定することがあります。

フラクタル

The Ring Worldのボードのフラクタルアニメーション
図をクリックすると次のレベルへ早送りします
 
フラクタル図形とは、自己相似性な性質を持つ図形のことを言います。 自己相似な図形とは、図を拡大してみると、 内部に同じ形の図が無限に繰り返される構造を持つ図形です。

代表的なフラクタル図形には、 コッホ曲線、カントール集合、マンデルブロー集合、ペアノ曲線、シェルピンスキーのギャスケットなどがあります。それぞれ、考案者に由来する名前がつけられています。

フラクタル次元

複雑な、フラクタル図形を定量的にあつかうために、従来の幾何次元を見直した、フラクタル次元があります。フラクタル次元は、従来の幾何図形次元(点=0次元, 線=1次元, 面=2次元, 立体=3次元)とコンパチブルな上位の概念です。

対象となる図形をn等分すると、分割された図形がm個含まれているとき、 フラクタル次元を、次のように定義します。
logn(m)
この考えに基づいて、
線分は2等分すると2個の同じ形の図形になるので、log2(2)=1
正方形は各辺を2等分すれば4個の正方形になるので、log2(4)=2
というように、計算できます。

ただし、フラクタル図形と呼ばれる図形は、フラクタル次元が整数にはならない性質があります。

右図The Ring Worldのボードも、このフラクタル次元が非整数になる性質を満たしています。この図形については、The Ring Worldのボードについてにて詳しく考察します。

オートマトン

The Life Game
図をクリックすると新しい配置からはじまります
 
オートマトン(Automaton)は、自動人形を表す言葉です。 アブストラクトゲームとオートマトンの関係は、History of Chess?で紹介する、 18世紀にいくつか登場したChessをプレーする人形があります。

近年、情報科学の発展に伴い、オートマトンは、プログラム(形式)言語を解釈するシステムなどのシステムの内部状態を保持して自動で動作する複雑(に見える)なシステムの特徴を表すために用いられています。

英国の数学者Conwayによって考案されたライフゲームは、二次元平面をグリッドに分割し、それぞれのグリッドの周囲の状態で遷移するセル・オートマトンの代表です。

グリッドの状態は、onとoffの二種類で、以下のルールに従って、次世代の状態に遷移します。 グリッドがonの場合、周囲にonのグリッドの数が

  • 1個以下 過疎により死滅します
  • 2,3個 次の世代に生き残ります
  • 4以上 過密により死滅します

グリッドがoffの場合、3個のonグリッドに囲まれた場所は、次の世代でonになります。

方眼用紙一枚に、一世代ずつの状態を描いて、複雑に状態が移り変わる様子を確認することができます。コンピューターを使えば、より手軽にライフゲームを体験できるので、FortranやBasicなどの言語で、ライフゲームをプログラミングした方も多いのではないでしょうか。館長と富永先生の共著awkでプログラミングにも、awkで記述したライフゲームが掲載してあります。

ライフゲームのアイディアは、あまりに多くの人を魅了し、ライフゲイムの宇宙をはじめとする書籍や記事が発表され、後にたくさんの派生オートマトンが生まれました。

ライフゲームは、対戦を目的としたゲームではありませんが、このアイディアを対戦型のゲームに発展させるアイディアも複数見つけることができます。

当館のオリジナルゲーム、The Ring Worldにも、単純なオートマトンの仕組みが組み込まれています。

オイラー数

オイラー数は、整数列を示す数と区別するため、オイラー標数ともよばれる、図形の特徴を表す数です。高校生ぐらいまでの数学では
多面体の 頂点数 V, 辺の数 E, 面の数 F とすると、オイラー数Χは、

Χ = V - E + F

と勉強されたのではないでしょうか。凸多面体ならばこれは常に2になります。

Nimber / グランディー数

SEE ALSO

Feedback

選択肢 投票
おもしろい 4  
役に立つ 0  
興味ない 0  
理解できない 2  
やってみたい 0  
食べてみたい 0  

*1 ルールで終了することが確かであるなら

TOP   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS   [Privacy Policy]  
Last-modified: 2015-10-21 (水) 17:42:51 (556d)