石取りゲームの数学
ゲームと代数の不思議な関係
佐藤文広 著
A5判・上製・256頁・3200円＋税
石取りゲーム等, 必勝法を数学的に研究できる2人遊びゲームを題材に, ゲームの世界に潜む数学的構造の美しさ・深さを伝える.
まえがき
まえがき
この本では,石取りゲームなど,必勝法を数学的に研究できる 2人遊びゲーム
について,お話していきます.ゲームの世界に潜む数学的構造の美しさ・深さ
をお伝えしたいと思っています.
石とりゲームの見本ともいうべきゲームは,「ニム」とか「三山くずし」とか
言われるゲームです.石を(といっても本当に小石でもいいですが,ピーナッツ
でもコインでもかまいません)何個かずつ 3つの山にまとめておいて,2人で交
互にどれか 1つの山から好きな個数だけ石を取っていきます.最後の石を取っ
た方が勝ちというゲームです(最後に取ってしまった方が負けという遊び方も
あり,勝ちの方を正規形,負けの方を逆形のゲームといって区別します).ご存
知の方も少なくないと思いますが,このゲームは,はじめに並べた石の個数に
よって先手必勝か後手必勝かが決まっていて,代数的な必勝法があります.
この「三山くずし」やその変形など,数学的な必勝法を持つゲームの研究が
この本のテーマです.
もう少し詳しく言うと,この本で取り扱う 2人遊びゲームは,
(1) サイコロやルーレットのような偶然性に依存しない
(2) 相手の持ち手が隠されたりせず情報が完全にオープンである
という特徴を持つものです.このようなゲームは組合せゲームと言われています.
そして,
(3) 2人のプレーヤーには同一の指し手が許されている
(4) 有限回の指し手で必ずゲームが終了する
という条件も要請します.
このようなゲームは,じつはゲームの開始局面ですでに先手必勝か,後手必勝
かが決まってしまい,その意味ではゲームの中では単純な部類に属すといえる
かもしれません.しかし,神ならぬ人間の身には十分複雑なゲームがいくらで
もあり,その上,調べれば調べるほどゲームと代数の間の不思議な関係が浮かび
上がってきて,深い数学が展開できる対象なのです.その面白さをお伝えする
ことがこの本の目的です.読むにあたっては,説明を見る前に,ぜひ,実際に
ゲームをやってみて下さい.その上で,数学的説明を読むとぐんと理解しやす
くなるでしょう.
読み進んでいくと,ゲームの分析を通じて,多くの基本的な数学的,特に代数的
な概念に出会います.例えば,半順序集合(ポセット),半群,群,標数 2の体など
ですが,それらが登場する章の章末に補足として,簡単な説明を加えました.
しかし,特に代数的色彩の強い節(第7.4節,第12.2節)以外では,集合論のごく
基礎的な用語の他にはさほど予備知識を仮定していません.むしろ,
普通の教科書だと抽象的に説明されてしまうこれらの概念に,ゲームを通して
なじんでもらえるのではないかと期待しています.
本書で取り上げるゲームを少し変形してみると,いくらでも新しいゲームが
作り出せます.それを自分で調べていけば,数学を手作りしていく感覚が得ら
れるでしょう.これも,読者にぜひお勧めしたいことです.そのために必要な
基礎知識は,本書で十分に得られるはずです.
では,各章の内容について簡単に説明しておきます.
第 1章では,三山くずしを調べます.三山くずしの数学的構造は自然数の 2進整
数表示と関係がある「ニム和」という演算で解明されます.これは天下り的に
やれば短い説明を与えることもできますが,この章では,答えを手探りしていく
発見的方法で解答に接近していくことにします.
第 2章では,上に説明した(1)〜(4)の特徴を持つゲームに対し,集合の言葉を
用いて数学的モデルを与えます.第 3章では,その数学的モデルに基づいて,
ゲームの必勝法を解明するための強力な基準となるグランディ数と,ゲームの
和について調べます.ここで,ゲームの理論におけるニム和の深い意味が明らか
になるでしょう.この第 2章,第 3章は,後の章での考察すべての基礎となります.
第 4章では,三山くずしを n個の石の山に一般化した n山くずし(ニム)という
1つのゲームが,様々な異なるゲームに形を変えていく様子を調べます.
数学がみかけに惑わされずに本質をつかみだす力を持っていることがよく分かる
と思います.
第 5章は取れる石の個数に制限を加えたニムが,第 6章はさらに山を複数の
小山に分割することも許したニムが主題です.
J.H.Conwayは,ニム和に対して「ニム積」という積も考え,非負整数の集合に
特殊な四則(加減乗除)を導入し,そのゲームへの応用も与えました.第 7章は,
Conwayの理論の紹介です.後に Lenstraは,半順序集合上のコイン裏返しゲーム
とゲームの積の概念を考案し,ニム積がゲームの積とうまく対応していることを
示しました.この理論を第 8章で紹介します.代数の教科書で体の理論を学ぶと,
有限体や標数 2の体に出会います.この 2つの章で,標数 2の体という一見抽象的
な存在が,ゲームの中に具体的存在として生きていることが見えてくるでしょう.
第 9章では,チャヌシッチとかワイトホフの二山くずしとよばれるゲームを調べ
ます.このゲームは,後手必勝形の決定が黄金比と関係するために興味をひかれ
よく紹介されていますが,グランディ数もまだ決定されておらず,完全に解明され
切ったとは言えない,なかなかに難しいゲームです.まだまだ,研究が続いている
ことを知っていただくために,グランディ数の加法的周期性という比較的最近の
結果も紹介してみました.
第 10章では,佐藤幹夫氏によるマヤゲームの理論を詳しく紹介しました.マヤゲーム
の理論は有名で,その概要はよく紹介されます(例えば,山田裕史『組合せ論
プロムナード』第 8講).しかし,完全な紹介は容易に入手できる形にはなっていま
せん.他を参照せずに読めるようにまとめてあります.
第 11章では,ハッケンブッシュという図形を素材にしたゲームを紹介しました.
数学はこんなものも取り扱えるのかと,驚きすら感じられるのではないかと思い
ます.証明の細かいところでは,一部,第 10章の結果を使うところがありますが,
大体は独立して読めるでしょう.
冒頭で述べましたが,同じルールのゲームでも,最後に手詰まりになって手が指せ
なくなったプレイヤーを負けとする正規形の遊び方と,最後に手を指してしまった
プレイヤーを負けとする逆形の遊び方があります.じつは,逆形の遊び方をすると,
第 3章に説明した基礎理論が破たんし,ゲームの必勝法の解明は極めて難しくなる
ことが知られています.そのため,この本でも,第 4.2節を除いて,ここまで正規形の
遊び方のみを考えてきました.締めくくりとして,第 12章では,逆形のゲームを
取り上げます.ここでは,第 4,5,6,9,10章で扱ったゲームの逆形版について適用
できる山zｱ洋平氏の結果に加え,ゲームの理論において最近ホットな話題となった
「逆形商」について紹介します.この分野では,先端の研究も意外に近いところに
あるのです.
以上の説明でもわかると思いますが,第 4章から先は,かなり独立に読むことができ
ます.次に各章の間の論理的なつながりを図示しておきますから,これを参考に
しながら,興味を持った章から読んでいけばよいでしょう.ただし,点線は,前の章で
扱ったゲームが例として出てくる,または,前の章の結果が一部の議論で利用される
といった,弱いつながりを意味しています.
参考文献表は,巻末にあります.その文献表にある本への参照は[2],[21]のように
番号で行ないます.上で引いた山田裕史氏の本でしたら[18]となります.
それでは,ゲームの数理の世界を堪能してください.
佐藤 文広