数学ってったってもちろん色々あって、たとえば物理量の数学、精度の数学、情報と確度の数学、会計勘定の数学や金貸しの数学などなど、功もあれば罪もある。
そして今回紹介する一冊は、数学の純然たる論理性について新たなセンスを触発させてくれるもの。
『組合せゲーム理論の世界 安福智明・坂井公・末續鴻輝 共立出版』
とりあえず本書の導入箇所に目を通してみれば ─
本書でいう「ゲーム」は、例えば石取り合戦のように、お互いに’着手’を成しつつ一定量の整数個のモノを奪い合い(消し去り合い)、双方攻防の過程で'局面'を転々と変えてゆきつつ、どちらかのプレーヤーが’着手’不能となるまで続ける競技。
この「ゲーム」にて起こりうる膨大な'局面'変化と勝敗確定、それらの数学命題化と証明、そして端的な実証例…これらが(おそらくは)本書の主題であり、さまざまな論題のヴァリエーションと複合化を通じた基本構成でもあろう。
じっさい、サブタイトルには「数学で解き明かす必勝法」と冠されている。
さらに、数学素人の僕なりにちらっと想像膨らませてみれば、このゲーム必勝数学の応用ルールセットは石取りやオセロなどに留まることなく、もっと複雑な局面コンビネーションのコンュータゲームなども大いに含むのではないかと察する。
ともあれ、本書導入箇所のほんの一端のみを僕なりに了察した上で、此度の読書メモとして以下に略記する。
本書導入箇所からおこる「組み合わせゲーム」とは、以下の前提を最低要件とするルールセット(競技)の中核的モデルである;
・サイコロなどの偶然の要素を含まず、確定性に則って競い合うルールセット
・各プレーヤーの’着手’がお互いに開示され、完全情報性が保証されているルールセット
この「ゲーム」の導入的なとっかかり定義づけとして;
(G1) とりあえずプレーヤーを2人として、交互に'着手’するか、あるいは放棄(パス)する
(G2) '着手'の機会を永遠に失ったプレーヤーが負けの、正規形ゲームである
(G3) ’着手’による’手数’の総計は有限回数である
(G4) 各'局面ごとの'着手'は有限個である
なお、'手数’は有限回数とはいえ、各’局面’ごとの’着手’も有限個に留まるとは限らない(超限ゲームたりうる)。
或る’局面’から有限の’手数'を辿って到達可能な新’局面’を、もとの局面の’後続局面’とみなす。
トータルの’手数’をそれらの集合とみなし、その集合の要嘘数は終了局面で1とし、そこに至らぬ局面での要素数は1より小さいとする。
これで、必ず勝敗が片付くショートゲームたりうる。
しかし、延々とループする千日手ゲームもありうるとする。
以上の基本定理が成り立つならば、任意の局面にて「一方のプレーヤーのみが必勝戦略」を有しうる。
しかしながら、どちらのプレーヤーが「必勝戦略」に在るのかをひとつひとつの’着手ごとに検証してゆくことはおそろしく困難。
’着手’が少ない(あっという間に片付く)単純ゲームならばまだしも、じっさいのルールセットにおける「ゲーム」はおのおのプレーヤーの’着手’の数がどんどん増えてゆきうるので、それら組み合わせによる’局面’の数も爆発的に増えてゆくことになる。
そこで発揮されうる超協力な数学が、『組合せゲーム理論』である。
さまざまなゲーム’局面’のうちに統一的つまり数学的な構造を見出し、代数の数学に則って「必勝戦略」とそのプレーヤ―を特定可能。
=================================
「必勝戦略」検証の上での単純で端的なゲームとして、「不偏ゲーム」がある。
そもそも不偏ゲームの基本前提として;
或る局面の直前まで’手番’を有していた’後手’プレーヤー’が「必勝戦略」を有する局面をP局面とする。
一方で、これから’手番’を為す’先手’プレーヤーが「必勝戦略」を有する局面をN局面とする。
だから、不偏ゲームにては終了局面は必ずP局面となる(後手が勝ったことになる)。
しかし、或る局面がたった1手でP局面に遷移するならば、この局面はN局面である(だから先手が勝ったことになる。
さらに ─
この不偏ゲームにてありうる全’局面’の全体集合をLとする。
うち、ありうる終了’局面’の集合をTとする。
(上の定義に則った)さまざまなP局面の集合を集合Pとしし、またさまざまなN局面の集合を集合Nとする。
全体集合Lを 集合Nと 集合P に分割、L=N∪P とする。
以上から成り立つ、不偏ゲームの命題:
① 集合T ⊂ 集合P である。
或る局面Gがあり、そこから1手で遷移しうる局面をG´として ─、
② G∈NならばG´∈PとなるG´は存在する
③ G∈PならばG´∈PとなるG´は存在しない。
この命題の証明。
まず、与えられた或る局面が終了局面のとき、この局面は①から集合Pに属しており、かつ正規形ゲームなので、この局面は必ずP局面となる。
一方、与えられた或る局面が集合Nに属しているとき、この局面は②から1手でP局面に移動できるので、数学的帰納法からこの局面は必ずN局面である。
また、与えられた或る局面が集合Pに属しつつも、終了局面ではないとき、③から1手先の局面はすべてN局面となり、だからこの局面は必ずP局面となる。
===================================
かかる不偏ゲームのうち最も分かりやすいもののひとつが、ニム(NIM)である。
端的な例が「石取りゲーム」など。
原型は以下。
幾つかの有限個の石を集めて’、幾つかの山’を作る。
とりあえずプレーヤーを2人とし、交互に1つの’山’から好きなだけ石を取る(’着手’する)。
石が1つも無くなった局面を終了局面とし、(上で記したように)これはP局面である。
’山’が1つだけになった局面は、ここに残った石をすべて先手が取り去ってゲーム終了局面と出来、だから(上で記したように)これはN局面。
これを数学命題にすると ─
'山'が1つのニムの局面 (m1) では m1=0 のときP局面、そうでなければN局面。
'山'が2つのニムの局面 (m1, m2) では、m1=m2 のときP局面、そうでなければN局面。
これらの命題を証明(前者命題は後者命題に含まれるので、後者のみ証明)。
2つの’山'における石の’偶数和’について数学的帰納法で証明する。
まず m1+m2=0 のとき(すなわち m1=m2-0 のとき)明らかに終了局面、よってP局面である。
さらに、
m1+m2 = k >0 のときにこれら命題の主張が成立すると仮定。
ここで m1+m2 = k+1 の場合。
局面(m1, m2) は着手によって (m´1, m2) あるいは (m1, m´2) に変わり、ここでは(m´1, m2)に変わるとする。
(なお m´1<m1 また m´2<m2 )
m1=m2 の場合。
m´1< m2 でありまた m´1+ m2 ≦ k であるので、数学的帰納法によって一手先の局面はすべてN局面といえる。
したがい、(m1, m2) はP局面である。
m1≠m2 かつ m1<m2 の場合。
(m1, m2) からは着手によって (m1, m1) に変わる。
m1+m1 < m1+m2 = k+1 であるから (m1, m1) はP局面であり、一手先がP局面となるのだから数学的帰納法から (m1, m2)はN局面である。
ここまでが’山’2つの場合に限ったニムの命題と証明。
だが、’山’が3つ以上あると石の数もまた着手もヴァリエーションがぐっと増え、だから局面変化の数も増えてしまう。
そこで今度は、石のあらゆる数を2進数に置き換えた上で排他的論理和として表現する「ニム和」を導入し、さまざまなニム和が0となれば必要かつ十分にP局面であることを示し…
====================================
以上、あくまでもほんの導入箇所のみをざっと掻い摘んでみた。
プレーヤーの’着手’ごとにもたらされる’局面’変化と勝敗判定について、ほんの導入編の一端に過ぎぬが、それでもこれだけの数学技法がある。
本書のコンテンツはさらに整数集合論の活用なども併せ含め、ヴァリエーション図案も数式も高次に複雑になり、さまざまパズルやコラムも交えつつ200頁以上にわたって展開してゆく。
数学に(数学思考に)自信のある社会人さらに大学生や高校生に是非チャレンジ薦めたい’新しさ’がここにある ─ とはいえ僕にはすべての捕捉は出来そうにもないので、また気が向いたらちょっとずつ読み進めてゆくつもりだ。
おわりだ