組合せゲーム理論への応用

ウィキペディア小見出し辞書

組合せゲーム理論への応用

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/05/15 10:26 UTC 版)

「超現実数」の記事における「組合せゲーム理論への応用」の解説

超現実数はそもそも囲碁の研究に動機づけられたものであり、定番ゲームと超現実数の間には様々な関連性がある。この節では便宜のために、数学的対象 {L | R} のことはゲーム (Game)、チェスや囲碁のような遊興のことは遊技 (game) と呼び分けることにする。 ここで考えたい遊技は以下のような性質を持つものである: プレイヤー（試技者）は二人（便宜上 Left と Right とする） 決定論的（ゲームの各手番はランダム要素なしにプレイヤーのメイクする選択で完全に決まる） （プレイヤーの隠し札や隠しマスのような）秘匿された情報はない プレイヤーには交互に手番 (turn) が回ってくる（遊技によって、一回の手番に複数手 (move) を許すものも許さないものもある） 遊技の各取組（一番）は有限回の手数で終了しなければならない プレイヤーに正規の指し手が何も残されていない状態になったら即座に取組は終了しそのプレイヤーの負けとなる 大抵の遊技にとって、初期盤面配置はどちらかのプレイヤーに大きな有利となることはないが、試技の進行の過程で一方のプレイヤーが勝利に近づくにつれて、盤面はそのプレイヤーに明らかに有利となっていく。遊技の分析のためには、ゲームを任意の盤面に結び付けるのが有効である。与えられた盤面の値がゲーム {L | R} であるとは、L は Left の単一手で達成可能な盤面の値全体の成す集合、R は Right の単一手で達成可能な盤面の値全体のなす集合となるように与えるものとする。 零ゲーム 0) は L, R がともに空集合となるゲームであるから、次の手を打つプレイヤーが即座に負けである。二つのゲーム G := {L1 | R1}, H := {L2 | R2} の和は、G + H := {L1 + H, G + L2 | R1 + H, G + R2} というゲームとして定義され、これは各プレイヤーが手番ごとに試技 (play) を行うゲームを選べることに対応するが、正規の手が打てなくなったプレイヤーが負けとなることは変わらない。例えば、二人のプレイヤーがチェス盤を二面使って指す場面を想像しよう、プレイヤーは交互に手を指すけれども、各手番においてどちらの盤面で指すかは完全にプレイヤーの自由にゆだねられる（どちらを選んでも選んだ方に一手を打てるだけで、選ばなかった盤面には何も干渉できない）というのがゲームの和の解釈である。ゲーム G = {L | R} に対して、−G とは {−R | −L} なるゲームのことで、これは二人のプレイヤーがその役割を入れ替えたものになっている。任意のゲーム G に対して G − G = 0 となることは容易にわかる（ここで、ゲームの差 G − H は G + (−H) で定義する）。 このようにゲームを実際の遊技に結び付ける単純な方法でも、非常に興味深い結果が得られる。二人の完璧なプレイヤーがひとつの遊技を与えられた盤面から始めるとき、その初期盤面に付随するゲームが x であるとすると、任意のゲームを以下の四種に分類できる: x > 0 ならば Left が勝つ（どちらが先手・後手かに関わらず） x < 0 ならば Right が勝つ（どちらが先手・後手かに関わらず） x = 0 ならば後手が勝つ x ‖ 0 ならば先手が勝つ より一般に、G > H とは G - H > 0 となることと定義する、<, =, ‖ についても同様。ここに、記法 G ‖ H とは G と H が比較不能という意味で、G > H, G < H, G = H の何れも不成立ということと等価である。比較不能な遊技は、加えられた手によってどちらのプレイヤーが優勢となるかが変わるため、互いに混迷している (confused) ということもある。零ゲームと混迷しているゲームはファジー（わからない）（英語版）と言い、正・負・零とは対立する。ファジーゲームの例には、∗（英語版） が挙げられる。 遊技の終盤近くはときどき、相互に干渉しない複数の小さな遊技に分解する（その中の一つにしかプレイヤーの打てる手がないという場合を除いて）。例えば、囲碁において、盤面は徐々に碁石で埋まっていき、プレイヤーが手を指せる空所はいくつかの小さな島に分けられていくだろう。各島は、それ自体が区分けされた小さな盤面上の一つの囲碁のように見える。これらの小さな遊技のそれぞれを分析することができたなら、そのような分解は有効であって、そしてそれらの分析結果を繋ぎ合わせて遊技全体に対する分析を得る。しかし、そうやって分析することができると安易には言えないようにも思われる。例えば、先手必勝の二つの小さな遊技があったとして、しかしそれらを組み合わせて一つの大きな遊技としたとき、それが先手必勝の遊技であるかはもはや分からない。幸運にも、これを分析する方法がある。それには次の注目すべき定理を用いる: 定理 一つの大きな遊技をふたつのより小さな遊技に分解するとき、その小さな遊技に付随するゲームを x および y とすれば、もとの大きな遊技に付随するゲームは x + y である。 小さな遊技の組み合わせとなる遊技は、それら小さい遊技の選言和（英語版）と呼ばれ、定理はここで定義したゲームの加法が、それら遊技の選言和をとることに等価であることを述べている。 歴史的なことを言えば、コンウェイは本項とは逆順に超現実数の理論を発展させたのであった。コンウェイは、囲碁の寄せを分析し、相互干渉しない小遊技の分析を繋ぎ合わせてそれらの選言和の分析とする何らかの方法があれば有用であるという実感を得ていた。そうしたことからコンウェイはゲームの概念とそれらに対する加法演算を発明した。そこからさらに符号反転および大小比較の定義へと開発は動いて行き、ゲームからなるある種のクラスが興味深い性質を持つことをコンウェイは指摘している。それが超現実数全体の成すクラスである。最終的に乗法演算を開発するに至って、超現実数の全体が実際にひとつの体を成すことおよびそれが実数の全体と順序数の全体をともに含む体系となることが証明された。