[Nine Mens Morris]


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

//----
//''Table of Contents''
//#contents()

* 数学コラムのコーナー [#p63320e1]
+ [[ゲーム理論と室内ゲーム]]
+ [[The Ring Worldのボードについて]]

* Fano Plane [#t078b6cf]
#ref(./FanoPlane.jpg,right,around,nolink,Fano Plane)
[[FIRE and ICE]]は、Fano Planeをデザインの基本にしたゲームです。

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

位数 q の射影平面とは、次の条件を満たす図形です。
>
q&super{2}; + q + 1 個の点からなり、
+ どの直線も q + 1 点を通る
+ どの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を法として異なる要素を持っています。

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

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

ゲームの研究において、解決のレベルをしめすために使われる用語がありますので簡単に解説しておきます。Solved Gameについて、英語版WikiPediaでは充実した情報が掲載されていますが、日本語の情報が見当たりませんので、ここでは、英語版WikiPediaに書かれている内容を中心に紹介します。
:Ultra-weak|極弱く(解決)&br;
//In the weakest sense, solving a game means proving whether the first player will win, lose, or draw from the initial position, given perfect play on both sides. This can be a non-constructive proof (possibly involving a strategy stealing argument) that may not actually help determine this perfect play.
//ゲームの開始から、どちらかのプレーヤーが勝つか、引き分けになるか、完全な手をお互いが指した場合において、断定できることが分かっている。完全な手を決定しえないような、構造的でない証明によるものでも構わない。
''完全な手''をお互いが指した場合、「先手必勝か、後手必勝か、または引き分けになるか、ゲームの開始時点からわかっている」ことが証明できている。''完全な手''を決定しえないような、構造的でない証明によるものでも構わない。&br;
例えば、[[Hex]]は、[[NashによってUrtra-weakに解決>Hex#y0d81a20]]されたゲームです。

:Weak|弱く(解決)&br;
//More typically, solving a game means providing an algorithm that secures a win for one player, or a draw for either, against any possible moves by the opponent, from the beginning of the game.
//一方のプレーヤーが勝つか、引き分けになるような、ゲーム開始からの、すべての合法手に対して有効である、確固たるアルゴリズムが示されているゲーム。&br;
普通「解決されている」状態というと、この「Weakに解決されている」状態を指す。ゲーム開始時から、起こりうるすべての合法手に対して、勝利、引き分け、負けになるアルゴリズムが提示されている。&br;
[[Connect 4]], [[立体四目並べ / Qubic]]他、多くの解決されたとされているゲームは、Weakに解決されたゲームです。

:Strong|強く(解決)&br;
//The strongest sense of solution requires an algorithm which can produce perfect play from any position, i.e. even if mistakes have already been made on one or both sides.
//すべての局面においても、完全な指手を生成できるアルゴリズムを示すことができるゲーム。
(どちらか、または両方のプレイヤーがさし間違いのミスを犯した後も含む)すべての局面において、完全な指手を生成できるアルゴリズムを提示することができる。&br;
探索空間の狭い[[Tic-tac-toe]]や、論理的な必勝手順が示されている[[nim]]は、Strongに解決されたゲームです。

//The strongest sense of solution requires an algorithm which can produce perfect play from any position, i.e. even if mistakes have already been made on one or both sides.
//完全ゲームを作り出すアルゴリズム

// As an example, the game of tic-tac-toe is solvable as a draw for both players with perfect play (a result even manually determinable by schoolchildren). Games like nim also admit of a rigorous analysis using combinatorial game theory.

// Whether a game is solved is not necessarily the same as whether it remains interesting for humans to play. Even a strongly solved game can still be interesting if the solution is too complex to be memorized; conversely, a weakly solved game may lose its attraction if the winning strategy is simple enough to remember (e.g. Maharajah and the Sepoys). An ultra-weak solution (e.g. Chomp or Hex on a sufficiently large board) generally does not affect playability.

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

//ゲーム理論では、'perfect play'は、敵がその後の手がどんなものであるかに関わらず、プレイヤーに最善の結果をもたらす振る舞い または 戦略のことを言います。
//すべての合法最終局(勝ち、負け、引き分け)が評価されます。

//By backwards reasoning, one can recursively evaluate a non-final position as identical to that of the position that is one move away and best valued for the player whose move it is. 
//帰納的に、最善手で最終局面のひとつ前の局面も唯一無二に決まるはずです。

//Thus a transition between positions can never result in a better evaluation for the moving player and a perfect move in a position would be a transition between positions that are equally evaluated. 
//ですから、ある局面からある局面への遷移のほうがよりよい評価になることはなく、ある局面でのperfect moveは、同じく評価される局面間の遷移になります。

//As an example, a perfect player in a drawn position would always get a draw or win, never a loss. If there are multiple options with the same outcome, perfect play is sometimes considered the fastest method leading to a good result, or the slowest method leading to a bad result.
//たとえば、引き分けのポジションにあるperfect playerは、(最終的に)引き分け、または勝ちという結果になりますが、負けることはないはずです。もしも同じ結果を迎えるための選択肢が複数あるとすると、perfect playは、良い結果がでるまでの最短の道筋、または悪い結果がでるまでにもっとも多くの手数を要する道筋のことをさします。

//ゲームの最適な戦略が(まだ)わかっていなくても、ゲームをプレイするコンピューターなら、ゲームの終局 解決から 

//ある時点から後にperfect playをplayできることができて、

//ベネフィットを享受することができるかもしれない。


//コンピューター・チェスのプログラムは、これをやるということで有名です。
//Although the optimal strategy of a game may not (yet) be known, a game-playing computer might still benefit 

//from solutions of the game from certain endgame positions (in the form of endgame tablebases), which will allow it to play perfectly after some point in the game. 

//Computer chess programs are well-known for doing this.

* フラクタル [#r695ca8a]
&flash(/plugin/htmlinsert/RingWorld/RingFractal.swf,240x240,bgcolor="#ffffff",align=left,float="right", description="<b>The Ring Worldのボードのフラクタルアニメーション</b><br /><u>図をクリックすると次のレベルへ早送りします</u><br />&nbsp;"){};
フラクタル図形とは、%%%自己相似性%%%な性質を持つ図形のことを言います。
自己相似な図形とは、図を拡大してみると、
内部に同じ形の図が無限に繰り返される構造を持つ図形です。

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

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

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

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

右図[[The Ring World]]のボードも、このフラクタル次元が非整数になる性質を満たしています。この図形については、[[The Ring Worldのボードについて]]にて詳しく考察します。
#clear
* オートマトン [#na24c287]
&flash(/plugin/htmlinsert/RingWorld/Life.swf,256x256,bgcolor="#ffffff",align=left,float="right", description="<b>The Life Game</b><br /><u>図をクリックすると新しい配置からはじまります</u><br />&nbsp;"){};
オートマトン(Automaton)は、自動人形を表す言葉です。
アブストラクトゲームとオートマトンの関係は、[[History of Chess]]で紹介する、
18世紀にいくつか登場した[[Chess>Chess(欧米他)]]をプレーする人形があります。

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

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

グリッドの状態は、onとoffの二種類で、以下のルールに従って、次世代の状態に遷移します。
グリッドがonの場合、周囲にonのグリッドの数が
- 1個以下 過疎により死滅します
- 2,3個    次の世代に生き残ります
- 4以上    過密により死滅します

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

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

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

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

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

* オイラー数 [#n853ec40]
オイラー数は、整数列を示す数と区別するため、[[オイラー標数>http://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E6%A8%99%E6%95%B0]]ともよばれる、図形の特徴を表す数です。高校生ぐらいまでの数学では&br;
多面体の 頂点数 V, 辺の数 E, 面の数 F とすると、オイラー数Χは、
 Χ = V - E + F
と勉強されたのではないでしょうか。凸多面体ならばこれは常に2になります。

* Nimber / グランディー数 [#l1c17344]
// http://en.wikipedia.org/wiki/Nimber

// http://en.wikipedia.org/wiki/Nimber
//In mathematics, the proper class of nimbers (occasionally called Grundy numbers) is introduced in combinatorial game theory, where they are defined as the values of nim heaps, but arise in a much larger class of games because of the Sprague–Grundy theorem. It is the proper class of ordinals endowed with a new nimber addition and nimber multiplication, which are distinct from ordinal addition and ordinal multiplication.

//The Sprague–Grundy theorem states that every impartial game is equivalent to a nim heap of a certain size. Nimber addition (also known as nim-addition) can be used to calculate the size of a single heap equivalent to a collection of heaps. It is defined recursively by

// α + β = mex({α' + β:α' < α} U {α + β':β' < β}),

// where for a set S of ordinals, mex(S) is defined to be the "minimum excluded ordinal", i.e. mex(S) is the smallest ordinal which is not an element of S. For finite ordinals, the nim sum is easily evaluated on computer by taking the exclusive-or of the corresponding numbers (whereby the numbers are given their binary expansions, and the binary expansion of x xor y is evaluated bit-wise).

// Nimber multiplication (nim-multiplication) is defined recursively by

// α β = mex{α ′ β + α β ′ − α ′ β ′ : α ′ < α, β ′ < β} = mex{α ′ β + α β ′ + α ′ β ′ : α ′ < α, β ′ < β}.

// Except for the fact that nimbers form a proper class and not a set, the class of nimbers determines an algebraically closed field of characteristic 2. The nimber additive identity is the ordinal 0, and the nimber multiplicative identity is the ordinal 1. In keeping with the characteristic being 2, the nimber additive inverse of the ordinal α is α itself. The nimber multiplicative inverse of the nonzero ordinal α is given by 1/α = mex(S), where S is the smallest set of ordinals (nimbers) such that

//1. 0 is an element of S;
//2. if 0 < α ′ < α and β ′ is an element of S, then [1 + (α ′ − α) β ′ ]/α ′ is also an element of S.

//For all natural numbers n, the set of nimbers less than 2^{2^n} form the Galois field GF(2^{2^n}) of order 2^{2^n}.

//In particular, this implies that the set of finite nimbers is isomorphic to the direct limit of the fields GF(2^{2^n}) , for each positive n. This subfield is not algebraically closed, however.

//Just as in the case of nimber addition, there is a means of computing the nimber product of finite ordinals. This is determined by the rules that

// 1. The nimber product of distinct Fermat 2-powers (numbers of the form 2^{2^n}) is equal to their ordinary product;
// 2. The nimber square of a Fermat 2-power x is equal to 3x/2 as evaluated under the ordinary multiplication of natural numbers.

//The smallest algebraically closed field of nimbers is the set of nimbers less than the ordinal \omega^{\omega^\omega}, where ω is the smallest infinite ordinal. It follows that as a nimber, \omega^{\omega^\omega} is transcendental over the field.

#clear
* SEE ALSO [#sb0f146a]
#related
- [[WikiPediaのSolved Gamesの項目>http://en.wikipedia.org/wiki/Solved_game]]

* Feedback [#u1caae51]
&facebooklike(400x180,action="like",scrolling="yes",show_face="true",layout="standard",colorscheme="light",align="right",float="right",rlmargin="10");
#vote(おもしろい[4],役に立つ[0],興味ない[0],理解できない[2],やってみたい[0],食べてみたい[0])
//#pcomment_nospam(noname)

TOP   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS   [Privacy Policy]