ゲームと戦略

トップページ研究分野と周辺

ゲーム理論(theory of games)は、「ある特定の条件下において、利害が異なる複数の主体の間で生じる戦略的な相互関係」を研究する数学及び経済学の一分野、というように定義されている。
国家間の外交や企業間競争等のシミュレーションも視野に入れ、先読みに基づく最適な行動の選択を可能にするための理論でもあり、人工知能でも重要な研究分野とされている。
或る状況から派生する状況が複数あり、その連鎖によって在り得る状態が枝分かれ的に増えていく状況は、何もゲームに限らず、様々な分野に共通する構造である。その効率的な探索方法を開発する事は、人工知能全般に影響を与える。
また、ゲームの制作は、楽しくプログラミングを勉強するための格好の課題でもある。

Min-Max法

Min-Max法は、オセロや将棋のような二人で交互に指し合う対戦型ゲームの戦略決定法として、最も基本的なアルゴリズム(計算手順)であり、コンピュータオセロやコンピュータ将棋等の実装で幅広く用いられている。
図の最も上のノード(円)が盤の初期状態を表す。先手が仮に3つの手を指し得る場合を示している。
上から2段目の3つのノードが先手が指し終わった後の其々の盤の状態だ(3つの手其々について枝分かれしている)。
ここでは、全ての盤の状態に於いて、先手後手とも3つずつの指し手があるものと仮定している(実際のオセロや将棋ではもっと多い)。
水色のノードは先手の手番の時の盤の状態、赤いノードは後手の手番の時の盤の状態を示す。
数字は全て先手、後手、どちらかのプレーヤにとっての、盤の局面の有利さを表す(ここでは先手にとっての数字とする。色が変わっても先手にとっての有利さである事に変わりはない)。
或る盤の状態から先手(又は後手)にとっての有利さを求めるには、評価関数を用いる(盤の状態を入力、有利さを出力とする関数)。
評価関数は、例えばオセロであれば隅の確定石(もう絶対にひっくり返らない石)の数等で作成する。
Min-Max法では、まず最も先読みした状態から、其々の局面の有利さの数字を評価関数によって埋めていく(ここでは、斜めになっている4段目の数字を埋める)。
次に、一つ上がって3段目の各数字を埋める。しかし、ここからは評価関数によるのではなく、一つ下の段の数字を使って以下の法則で埋めていく。
埋めたい段が、数字が有利さを表しているプレイヤー(ここでは先手)の手番であれば、一つ下の段のうち最も大きい数字で埋める。
埋めたい段が、数字が有利さを表しているのと反対のプレイヤー(ここでは後手)の手番であれば、一つ下の段のうち最も小さい数字で埋める。
この単純な法則だけで、下から遡って全ての段を埋める。
初期状態から、先手は最も大きい数字7の付いた真ん中の指し手を選ぶ。次に相手は、先手が最も不利(点数が低い)になる右側の7の付いた指し手を選ぶ。また、先手は最も大きい左の指し手を選ぶ。
このように、相手はこちらの得点が最小(Min)になる手、こちらは自分の得点が最大(Max)になる手を繰り返すため、Min-Max法という。
この方法によれば、先読み出来た範囲の中から、最も良い手を確実に選ぶ事が出来る。どちらかは、相手がどんな手を打っても確実に勝てる必勝戦略が得られる。
しかし、実際には8×8オセロ、将棋等の著名なゲームでは、後に述べるようにゲーム状態数が大き過ぎて、現在のコンピュータでも実際的な時間内では計算不能な数となるので、必勝手順はまだ知られていない(将棋や囲碁の状態数は宇宙に存在する原子の推定数より多いとすら言われ、必勝手順解明は将来に渡って不可能とすら言われている)。

Min-Max法の図解

α-β法(枝刈り)

Min-Max法は、一手先読みするたびに、評価値を調べる局面数が爆発的に増えていくので、計算に非常に時間がかかる。
しかし、出来るだけ先を読んだ方が正しい手を選択出来る。そのため、Min-Max法の様々な計算手順削減法が考えられ、その代表がα-β法だ。
図で斜めの4段目(ここでは、読みの最先端)の各盤(局面)の評価値を評価関数を用いて作成するところは、Min-Max法と同じとなる。
しかし、そこから上を一つ下の段の数字を使って埋めていくところで、工夫が行なわれる。図の例で説明する。
3段目の左から2番目の局面では、下の4段目の一番左の評価が8なので、とりあえず8点が付いた。3段目は自分(数字が有利さを表しているプレイヤー)の手番なので、一つ下の段から一番大きい数字を選ぶ。
従って、この局面は8点以上になるはずだ。しかし、一つ上の2段目は相手の手番なので、3段目から一番小さい数字の局面を選ぶ。
既に3段目の一番左の局面に7があるので、8以上になる局面が2段目から選ばれるはずはない。
従って、3段目でとりあえず8が付いた局面については、残りの下の段(緑の破線部分)を調べる必要はない。
次に、2段目の一番右の局面を見ると、3段目の一番左が1なので、とりあえず1点が付いた。2段目は相手の手番なので、一つ下の段から一番小さい数字を選ぶ。
従って、この局面は1点以下になるはずだ。しかし、一つ上の1段目は自分の手番なので、2段目から一番大きい数字の局面を選ぶ。
既に2段目に5、7と、1より大きい評価点のついた局面があるので、1以下になる局面が1段目から選ばれるはずはない。
従って、2段目でとりあえず1が付いた局面については、残りの下の段(青の破線部分)を調べる必要はない。
このように、手番がどちらにあるかによって異なる2種類の枝刈り方法を交互に実施できる。

α-β法の図解

(原始)モンテカルロ・シミュレーション

或る局面が或るプレイヤーにとってどれだけの有利さがあるかは、評価関数で判定する必要がある。
しかし、完全な評価関数を作るのは容易ではない(もし完全な評価関数があれば、次の手のうち最善の手を選べばいいだけになり、先読みする必要もなくなる)。
オセロであれば、序盤は定石、中盤は確定石の数や開放度等を評価関数に用いるが、完全ではない(オセロ終盤は完全読み切り出来るので、評価関数は不要となる)。
最初から評価関数が不要な最善手探索法として、モンテカルロ法がある。
最も単純な方法は、図のように選択出来る手が仮に2つ(いくつでもよい)の場合、そこから先を勝敗が付く(プレイアウトする)までコンピュータでランダムに打ち合う事を繰り返す。
双方の手は、ルールによりその状況で選択可能な手から完全に出鱈目に選ぶ。
単純に、最も勝率の良い手を選ぶのが、原始モンテカルロ・シミュレーションと呼ばれる方法だ。
ランダムな試行が多い程、精度は上がるが、ゲームの枝分かれの数は膨大なので、ごく一部で全体を判断する事になる。
従って、あまり強い方法ではない。オセロに実装すると、最初はそこそこ戦うが、戦略を備えた相手に対しては、中盤以降必ず劣勢になり、負けてしまう。

原始モンテカルロ・シミュレーションの図解

ゲームの状態数(探索空間の広さ)

例えばオセロならば、最初に盤中央部に白黒二つずつ置かれた状態で始まる。
ゲームによって決まったスタートの状態から、ルール上可能な手(合法手)は複数あり、どれを選択するかによってゲームの状態は異なるものになる。
二人で交互に打ち合うゲームの場合、まず先攻が手を選んでゲームの状態が変わり、後攻が選択出来る合法手の数も決まって来る。Min-Max法の図の枝の先端の数がゲームの状態数だ。(但し、先攻と後攻の手の組合せが違っても、結果的に同じ状態になる事は考えられる)。
単純に、選択手の順列が違えばゲームの状態は全て異なるものと仮定し、どんな局面でも先攻と後攻が選択出来る合法手は10手、必ず10回ずつ打ち合えば終わる二人対戦型ゲームがあったとする。
このゲームの全てのあり得る状態(ゲームの状態数)は10の20乗となる。
著名なゲームの状態数は、チェッカー約10の30乗、オセロ約10の60乗、チェス約10の120乗、将棋約10の220乗、囲碁約10の360乗と推定されている。最初にランダムにカードを切って始めるトランプ・ゲーム等の状態数も相当大きいものと予想される。
しかし、実際のゲームでは、局面によって合法手の数が変わったり、終了までの手数が様々なのが普通で、正確な状態数を算出するのは容易ではない。
そこで、シミュレーションによりランダムな(或いは何らかの定石等を組み込んだ)戦略に基づく試合を多数行い、平均終了手数、各局面に於ける平均合法手数から算出する。
平均合法手数がn、平均終了手数がmのとき、ゲームの推定状態数はnのm乗である。
これを以下のように、対数の公式等を用いて10の何乗かを算出すると、上記のゲーム等と比較出来る。