である．抵抗の抵抗値はいずれも等しいとする．これを Bridg-It 盤面の電気回路表現と呼ぶ．先手が線分を引く時は，連結ゲームの電気回路表現による解析対応する抵抗を銅線で置き換え，抵抗値を 0 にする（短絡）．後手が線分を引く時は，引いた線分と交わる回路上の抵抗を切断し，抵抗値を無限大にする（除去）. 図 2（右）は後手の Analysis on a connection game 引きうる線分を模したもので，後手が線分を引くときに短絡， in electrical circuit representation 先手が線分を引くときに除去を行う [1]. 制度設計理論（経済学）プログラム 11_14830 滝田潤 Jun Takita 指導教員松井知己 Adviser Tomomi Matsui 本研究では，ボードゲーム，とりわけ連結ゲームと呼ばれるクラスのゲームに対する数理的解析を試みる． D. Gale によって発明された Bridg-It という連結ゲームには，C. Shannon による電気回路を用いたプレイマシンが製作され，先手プレイヤーとして優れた実力を見せた．本研究では，この電気回路の抵抗値を変えることによりプレイヤーの強さを調整し，Bridg-It を図 2. プレイヤーが引きうる線分に基づく電気回路遊戯として再構成することを試みる. Shannon のプレイマシンが取る戦略は，電気回路上で最も 1. Bridg-It 電圧が大きい抵抗部分を見つけて短絡するというものである． Bridg-It はボード上の点をつないでどちらが先に勝利条件を二つ以上の抵抗部分が同じ電圧を示したならば，ランダムに満たすか競いあう，二人用のボードゲームである．Bridg-It 盤一つを選択する．ゲームの進行した状態を図 3 に示す. 先手面を図 1 に示す．二人のプレイヤーは先手と後手に分かれ，先が一様抵抗の抵抗回路モデルであるとき，任意の初手に対し手は隣り合った黒い点をつなぐ線分を，縦方向または横方向にて後手の必勝手順が存在することが知られている [2]．引く．先手の勝利条件は，盤の左右を連結する経路を得ることである．後手は隣り合った白い点をつなぐ線分を，縦方向または横方向に引く．後手の勝利条件は，盤の上下を連結する経路を得ることである．線分を引く際，対戦相手が引いた線分に重なり合う線分を引いてはならない．引ける線分は，交互に 1 本ずつである．棋譜では先手の手は大文字と数字の組，後手の手は小文字と数字の組で表す．終了状態に 2 本線で示した手は F4，1 本線の手は b6 と呼ぶ. 図 3. 電気回路表現でのゲームの進行 Shannon のモデルでは抵抗値が一様であるため，最大電圧が生じる抵抗部分と最大電流値を示す抵抗は一致する．しかし本研究のモデルでは抵抗値を個別に変動させるため，電圧図 1. Bridg-It 盤面と，終了状態の例(黒の勝利) と電流値のどちらを採用するかで，プレイマシンの挙動が変化する．本研究では電流値を採用した. Bridg-It のプレイマシンとして初めて登場したのが，1951 年に C. Shannon により製作された抵抗回路モデルである． Shannon はこのゲームを鳥かご (Bird cage) の名で呼んでいた． 2. 抵抗回路モデルの実装抵抗回路モデルの実装は C++で行った．目的は抵抗回路モこのプレイマシンが搭載するヒューリスティックは先手プレデル同士の対戦を行った場合の棋譜を全通り生成し，勝率計イヤーとして，最善ではないものの優れた実力を見せたとい算を行うことである．う. 概念図を図 4 に示す．Bridg-It 盤面を模した電気回路を先手，以下抵抗回路モデルを記述する．図 2（左）は Bridg-It の盤後手の抵抗配置に基づいてそれぞれ生成し，これを初期状態面上で先手が引きうる線分を模して，電気回路を作ったものとする．先手番ならば，先手の抵抗回路をもとに，オームの法則及びキルヒホッフの法則より連立 1 次方程式を立式し，表 5. 先手（行）に対する後手（列）の勝率各頂点の電位及び各抵抗の電流値を求める．これより最大電流値を持つ抵抗を見つけ候補集合とする．候補集合から枝を一つ選び，対応する先手の抵抗回路の抵抗を短絡，後手の抵抗回路の抵抗を除去する．後手についても同様である. 表 6. 先手の初手を E5 に固定したときの後手の勝率図 4. プログラムの概念図候補が複数存在する場合は分枝が生じるが，この処理は再帰的に行う．各盤面の候補集合からまだ選ばれていない抵抗を選ぶという方法で，深さ優先探索を行う．図 4 の各ノードに後手の勝率を示した．各ノードの勝率は，終了状態（葉ノード）では 0（先手勝利）または 1（後手勝利）とし，それ以外のノードでは子ノードの勝率の平均を取ることで計算でき 4. る. まとめ VH 比モデルの勝率は初手によって大きく変動し，初手を 3. 計算実験ランダムとする条件下ではどのモデルが強いかについて明確 Bridge-It において，連結すれば勝ちとなる盤面の方向を連な構造を明らかにすることが出来なかった．人間のプレイヤ結方向と呼ぶとき，連結方向の線分は残りの線分よりも短絡ーが後手の立場で VH 比モデルに挑戦する場合，強さを調整する優先度が高いと言える．実際，Shannon の一様抵抗モデするには以下の手続きが望ましい. ルでは，初手は連結方向の枝からランダムに一つを選び短絡初手，先手は連結方向の枝からランダムに取る．その初する．そこで，枝を連結方向の枝集合𝐸! と残りの枝集合𝐸! に手からの勝率を参照し，強いプレイヤーが好まれれば後手二分し，e ∈ 𝐸! に抵抗値𝑟! を，e ∈ 𝐸! に抵抗値𝑟! を配置するモの勝率が低いところ，弱いプレイヤーが好まれれば後手のデルを考案した．これを VH 比モデルと呼ぶ．枝集合𝐸! に配勝率が高いところの抵抗配置を採用する. 置する抵抗値を𝑟! ， 𝐸! に配置する抵抗値を𝑟! とし，VH 比を今後の課題としては，プレイマシン同士で算出できる勝率 p = 𝑟! /𝑟! で定義する．VH 比を変動させた時のプレイマシンが，どの程度人間と戦ったときの強さを反映しているか分析の性質の変化は以下の通りである. するということが挙げられる．また，VH 比以外のモデル構・ p < 1 連結方向の優先度が低いモデル築も課題の一つである. ・ p = 1 一様抵抗モデル・ p > 1 連結方向の優先度が高いモデル表 5 は，先手・後手ともに 0.5～1.9 の範囲で VH 比を変化させたときのシミュレーション結果である．一様抵抗モデル同士 5. 参考文献 [1] M. Gardner, The 2nd Scientific American Book of Mathematical Puzzles and Diversions, Simon & Schuster, Manhattan, NY, 1961. の対戦では後手が必ず負けてしまう．しかし，VH 比を 1.5 以 [2] T. Fischer, ``Bridg-It Beating Shannon's Analog Heuristic,'' 上に上げた場合，変化が見られる. Technical report, Friedrich Schiller University Jena: Faculty of 後手が勝つことの出来るのは先手が初手 E5 を取る場合のみである．その場合の後手の勝率を表 6 に示す. Mathematics and Computer Science, 2009.