ターン制ストラテジーのための状態評価型深さ限定モンテカルロ法における消極的行動の抑制
8
0
0
全文
(2) The 19th Game Programming Workshop 2014. れる行動の数 数は 7 億 20000 万通り( 取れ. 10. 6!)にも. 及ぶ ぶ（同一局面 面に遷移する るものも含む む）．実際には より駒数や 1 駒あたりの合 合法手数が多い場合も珍 珍 しく くない．. 2.3 3 ゲーム木 木の生成方 方針 ターン制ス タ トラテジーは は複数着手性 性を持つとい い 図 1. TUB BSTAP のプレイ画面（先 先手左手側） ）. う特 特性上，木探 探索の実装方 方法には大きく分けて 2 通りが存在する る．1 つは図 2 のように個々の駒の行 行. R1. R 駒. 動を を枝として 1 ターン内 の行動を数段に分けた探 探. R)， 戦闘機(F)， 攻撃機(A)，戦車(T)，対空戦車(R. 索木 木を作る方法 法，もう 1 つ つは図 3 のように 1 ター ー. 歩兵(I)，自走 歩 走砲(U)の 6 種類の駒を用 種 用いる．これ れら. ン内 内に行動可能 能な全ての駒 駒の行動をま まとめて 1 つ. の駒間には相 の 相性が存在す する．相性は は後述する HP. の枝 枝として探索 索木を作成す する方法である．これ ら. に与えるダメ に メージ量に影 影響する．. は根 根からの枝の の数こそ異な なるものの，1 ターンを終 終. R2. R マップ. えた た後に辿りつ つくノードは は同じ数とな なり， 2.2 で 説明 明した特徴か からこれら全 全てのノードを調べき る. は常に同じ盤 盤面サイズ・ ・駒の初期配 配置 将棋等では. ことは難しい．過去に提案 案された AI はどちらかの. を用いる．し を しかし，ター ーン制ストラ ラテジーでは は通. 木の の生成法を選 選択している る．. 常，プレイ毎 常 毎に異なる設 設定の駒配置 置や盤面を用 用い 対戦を行う． 対 マスには複 複数の種類（地 地形）があり り， 被るダメージ 被 ジが増減する る． R3. R 着手順 各手番では は，プレイヤ ヤは全ての自 自駒を 1 回ず ずつ. 図 2. 自由な順番で 自 で行動させる ることが出来 来る．すべて ての. 1 駒の行動を を枝としたゲ ゲーム木. 駒を行動させ 駒 せると相手の の手番となる る．両者それ れぞ れの手番をタ れ ターンと呼ぶ ぶ． R4. R 勝利条件 件 いずれかの のチームの駒 駒が全滅した た場合，駒が が盤. 図 3. 面に存在して 面 ているチーム ムが勝利とな なる．ただし し，. 1 ター ーンの行動全 全てを枝とし したゲーム木 木. 3. 手法概略 略. ターン数に上 タ 上限を設け，その上限以 以内に全滅条 条件. 本稿では，既 本 既存手法，提 提案手法を合 合わせ 6 つの. を満たさない を い場合の判定 定条件はチー ーム毎の総 HP. AI を紹介し，性能評価を行 行う．そのため，それぞ ぞ. 量の差で決定 量 定される．. れに についての立 立ち位置を予 予め述べる． ．性能やそれ れ. R5. R HP. ぞれ れの特徴など どは図 4 に示 示す通りとなっている．. 各駒は 1 か から 10 の HP P を持つ．攻 攻撃を受ける るこ. これ れらの中で 1 駒の行動が が 1 つの枝となるゲーム. とで と HP は減 減少し，0 にな なるとその駒 駒は盤上から ら取. 木に による探索を行うのは は UCT，UC CT+Progressivve. り除かれる． り. Wid dening の 2 つであり， つ そ その他の AI は 1 ターン内. 2.2 2 TUBST TAP の特徴 徴. の全 全ての行動を をまとめて 1 つの枝とし している． 図にある 図 UC CT，UCT+Prrogressive Widening，攻撃 W 撃. 1 ターン内 内における複 複数着手性により，ターン ン制. 行動 動探索，DLM MC は既存手 手法であり，DLMC+攻撃 撃. ストラテジー ス ーではプレ イヤがとれ れる行動の順 順列. 整は今回提案 行動 動探索，DLM MC+局所調整 案する手法で. （合法手）が が非常に多い い．例えば 1 駒あたりの の平. ある る．各手法に について簡単 単に概要を述 述べる．. 均合法手が 均 110，駒数が 6 とすると， ，1 ターン内 内に. - 33 -.
(3) The 19th Game Programming Workshop 2014. 4. 既存手法 法 以下 下に本稿で用 用いる記号を を示す． s : 盤面の状態 態． S : 全ての盤面 面の状態sの集 集合． a : 1 つの駒の行動 A s : 状態sの の合法手とな なる全ての行 行動aの集合． s′ s, s. : 状態ssで行動aを行 行った次状態 態． 行った た場合，行動 動可能な駒が が残っている る．. 図 4. 1,. 手 手法の関係. P. …. :1 ターン内全 全ての駒による行動の順列 列．. : 状態sの の合法手とな なる行動の順 順列pの集合．. s′ s, s. ・UCT ・ 1 駒の行動 動を 1 ノードとして探索 索を行う標準 準的 な手法． な 1 ター ーン内に駒数 数分の探索を を繰り返し行 行う．. 2,. : 状態ssで行動の順 順列pを行った た次状態． 行った場合，相 相手の手番となる． る状態sの評 価関数による 評価値． : 状態評価. 4.1 1 UCT. ・UCT+Prog ・ gressive Wiidening UCT では 1 ターン全て ての行動を満 満足に探索し しき. の指 指標に UCB1 値（式 1）を用いる．囲碁や将棋な. れないため， れ Progressivee Widening を使用する． を. ど様 様々なゲーム ムでしばしば ば用いられる手法であり，. UCT U はモンテカルロ木 探索の一種であり，探索 索. ター ーン制ストラ ラテジーであ あっても有望 望な手法で あ. ・攻撃行動探 ・ 探索. る可 可能性が高い い．しかし， ，ターン制ス ストラテジー ー. 攻撃行動に による順列の のみ探索する る手法．移動 動行. は 1 ターンの候 候補手が膨大 大であるとい いう理由から ら，. 動は別のルー 動 ーチンによっ って処理する る．攻撃行動 動の. 単純 純に UCT による探索を に を行ったとしても，強い い. みを探索する み るため，攻撃 撃的な着手が強い．一方で で，. AI を作ることは難しい．一 一方で，過去 去に UCT の枝 枝. 防御的な着手 防 手は移動ルー ーチンに依存 存する．. 刈りを行う事で で AI の性能 が向上する事が確認され れ. ・DLMC ・ 陣形を重視 視するため，全駒による る行動を 1 つ つの. て い る [3] ． そ こ で 枝 刈 り の 代 わ り と し て. ノードとして ノ て探索を行う う手法．ただ だし，膨大な な探. 尚， 尚 1 ターンの行動全て てを 1 つの枝 枝とするゲー ー. 索空間の中で 索 で，ランダム ムに選んだ一 一部のノード ドの. ム木 木を用いる場 場合，UCT としての利点が生かせな. み評価を行う み う．また，各 各着手の評価 価はシミュレ レー. いた ため，1 駒の の行動を 1 枝 枝として実装 装する．. Pro ogressive Wid dening を用い いて探索空間 間を狭める．. ションによっ シ って行う．こ この際，終局 局までのシミ ミュ. UCB1＝ U ̅. レーションを レ を行わず， 途中で打ち切 途 切る．打ち切 切っ た局面に対し た して状態評価 価関数を用い いることで着 着手. （式 式 1）. ̅ ：あるノー ード j の勝率. の評価とする の る．着手の生 生成方法が原 原因となり， 防. :あるノード j のシミュ ュレーション ン回数. 御的な行動を 御 を取りやすい い性質を持つ つ．また，U UCT. :シミュレー ーション回数 数の合計. と異なり選択 と 択されたノー ードは全駒の の行動を含む むた. 4.1.1 Progressiive Wideninng Progressive P Widening（PW W W と略す）[4]とは，ある 局面 面の訪問回数 数 n に応じ て，有望な着手だけを探 探 索す する手法であ ある．本稿で では，攻撃行 行動を優先 し て探 探索させる為 為 PW を導入 入する． 具体的には， 具 式 2[5]に従 従って探索す する候補手を 増や やしていく．追加する候 候補手は，攻 攻撃行動を重 重 複無 無くランダム ムに選ぶもの のとする．攻 攻撃行動を全 全 て追 追加した場合 合，移動行動 動をランダム ムに追加する る．. め，1 め ターン ンにおける探 探索は 1 回でよい． ・DLMC+攻 ・ 攻撃行動探索 索 攻撃に優 れた攻撃行動探索，防御に優れ た DLMC D の2つ つを用い，そ それぞれの得 得意分野を利 利用 することで総 す 総合的に優れ れた手を選択 択する手法． ・DLMC+局 ・ 局所調整 DLMC の探 探索対象に攻 攻撃行動が含 含まれやすい いよ うに調整する う る手法．. - 34 -.
(4) The 19th Game Programming Workshop 2014. 候補手 候 候補手 候. log. 40 1..4. る． 2. n. 2000 log 45 1.2. 30 000. それぞれのパ そ パラメータは はシミュレー ーション数 600 00 とした．計算時間はほ ほぼ同一となっている． ．. 11 n. 30 000 （式 2）. 結果 果を表 1 に示 示す．尚，勝 勝率は引き分 分けを勝利の の 半分 分として算出 出している．. n:シミュレー ーション数. 表 1 UCT+PW U の UCT に対す する戦績. 4.1.2 シミュレーションの の詳細 TUBSTAP における駒 駒の行動は大 大きく分けて て単 純に移動する 純 るだけの行動 動と攻撃を含 含む行動の 2 通 りがある． り 1つ つの駒が持つ つ行動のうち ち攻撃する行 行動 は移動するだ は だけの行動に に比べると平 平均的には非 非常 に少ない．そ に そのため，完 完全にランダ ダムなシミュ ュレ ーションを行 ー 行うと指定タ ターン内に勝 勝敗が決せず ず， 引き分けで終 引 終わることが が多々発生す する．これは はチ ェス等でも指 ェ 指摘される点 点である．で では攻撃を優 優先 してシミュレ し レーションを を行えば良い いかというと と， 今度はシミュ 今 ュレーション ン中で安易あ あるいは無謀 謀な 攻撃が増加す 攻 するために，探索結果と としてそれら らを 期待する待ち 期 ちの行動が多 多くなってし しまう． そこで本稿 稿では攻撃可 可能な駒が存 存在する状況 況な らば必ず攻撃 ら 撃を行う方策 策と完全にラ ランダムな行 行動 を行う方策の を の 2 つを混合 合して用いて ている（前者が が8 割，後者が 割 2 割）． 尚，これら らのシミュレ レーション手 手法には様々 々な 改善が考えら 改 られるが，探 探索手法の比 比較という観 観点 から本論文の か の実験ではす すべての手法 法で同じシミ ミュ レーション手 レ 手続きを用い いている．. 表 1 から UC CT+PW の勝 率が十分に伸びているこ とが が確認できる る．UCT+PW W の式 1，2 は調整してい い ない いため，性能 能を向上でき きる余地は大 大きく残され れ てい いる．. 4.2 2 攻撃行動 動探索 村山らは攻撃 村 撃する行動に に注目した手 手法を提案 し た[[1]．以下に詳 詳細を示す． ． 【攻 攻撃行動探索 索】 I.. 状態sにお おける長さℓ以 以下の攻撃行 行動のみで構 構 成される順 順列を全て列 列挙する．攻 攻撃行動が存 存 在しない場 場合と長さ ℓ以降の行動 動は特定のル ル ーチンに従 従った行動を を順列に追加 加し 1 ターン 分の順列と とする． P s. ,. , …,. ⊂P s. II. P s に 含 ま れ る 順 列 か ら 遷 移 す る 次 状 態 s′ s,. 状態評価関数 数 により評 評価し，最も評 評 を状. 価の高い順 順列 を選択 択する． ∗. 4.1.3 予備実 験：PW の効果 PW の効果 果を確認するために予備 備実験を行っ た． 実験条件は以 実 以下の通りで である．. argmaxx ∈. s s,. 攻撃行動にのみで構成さ I において長 長さℓ以下の攻 れる る順列しか探 探索を行わな ないのは計算 算量爆発を防 防. ・マップは図 ・ 図 1 と同じも ものを用いる る. ぐ為 為である．た たとえ攻撃行 行動のみに限 限定したと し. ・先手後手 ・ 5500 戦，計 1000 1 戦. ても も全駒が偶然 然攻撃行動を をとれる場合 合，計算量 の. ・AI ・ は UCT，UCT+PW の 2 種. 爆発 発が起こりえ える．そこで で事前に探索 索する順列 の 長さ さを制限して ておくことで で，計算量の爆発を防い い. また，本稿 稿で用いる UCT U は 1 ター ーン内に行え える. でい いる．. シミュレーシ シ ション数を固 固定とし，1 回の行動に使 回 使用. この手法は図 こ 図 5 のよう な駒の行動順が重要とな. するシミュレ す レーション数 数は駒数で割 割った数を用 用い る．例えば， る 操作可能な駒が 6 駒存在し，1 ター ーン. る局 局面で上手く動作する． ．ここで大文 文字小文字 は. 内に行えるシ 内 シミュレーシ ション数が 6000 回である ると. チー ームを表して ており，数字 字は残り HP P，×印は移動 動. すると，1 す ターン内に 6 回の行動が行われる為 ，1. でき きないマスを を表す．駒 U（自走砲）は移動しな. 回の行動に費 回 費やすシミュ ュレーション ンは 1000 回と とな. けれ れば距離 2-3 3 までの位置 置に攻撃する ることができ き，. - 35 -.
(5) The 19th Game Programming Workshop 2014. 駒 P（戦車）は は移動後も攻 攻撃が可能だ だが隣接する る駒. DLMC】 【D. にしか攻撃で に できない．そ そのため，P P を先に動か かし. I.. 順列 をランダムにm m個サンプル ルする．. てしまうと て u を攻撃でき きずターンが が終了してし しま. P s. う．最善とな う なるのは U で先に で p を攻 攻撃し P で u を. II.. 攻撃する場合 攻 合である．攻 攻撃行動探索 索は攻撃行動 動の. ,. ,…,. ⊂P s. P′ s に含 含まれる に よる次局面ss s,. をdタ. ーン先ま までシミュレ レーションし し，状態評価関. み 2 手目以降 降を読み切る るためこうい いった局面で でも. 数. 上手く探索が 上 が行える．た ただし，上手 手く動作する るの. により評価を に を行う．これ れをn回繰り返 返. し，評価 価値の合計を を測定する．. は攻撃が行え は える場合のみ みである．. h . i 回目の のシミュレー ーション.. : →. d ターン ン進める. III. 図 5. 攻 攻撃行動探索 索がうまく働く局面の例. ∑. P′ s の中 中で評価最大 大の行動 ∗を選択する． を . （先手： ：大文字） 図 6 のような状況は攻 攻撃行動探索 索で上手く探 探索. ,. ∗. argm max ∈. DLMC D ではシミュレー ションによる局面の評価 価. できない例で で である．U は隣接する は p に対して攻 攻撃. を 1 ターン内の全ての駒 の行動が終了した局面に. できず， で u に対 対しては攻撃 撃できるが戦 戦果が低く反 反撃. 限定 定している．これによ り，全駒の動 動作が決ま っ. を受けてしま を まう．また，U の位置取 取りが邪魔な なた. た状 状態を評価す するため，駒 駒間の相互位 位置を評価 し. め P も p に対 対して攻撃で できない．こ このような状 状況. やす すい．しかし，全駒を動 動作させた場 場合，遷移す す. であれば，先 で 先に U を退か かした上で，P で p を攻 攻撃. る局 局面は膨大な な数となる． ．そこで，探 探索空間を減 減. するのが最善 す 善となる．. らす すため，ラン ンダムな前向 向き枝刈りを を用いている る． これ れにより高速 速な動作が可 可能となって ていが，良い い 手の の見落としの のリスクが大 大きく存在す する． ランダムな着 ラ 着手を用いる る DLMC は移 移動するだけ. 図 6. の行 行動を取りや やすく，防御 御的な行動を を取りやすい い．. 探索が失敗する局面例 攻撃行動探. これ れは攻撃する る行動より移 移動する行動 動の方が多い い. （先手： ：大文字）. ため めである．こ このような特 特性から図 1 のような初 初. 初期局面でも も上手く動作 作し また，図 1 のような初. 期局 局面において て上手く動作 作するが，図 図 5 のような. ない，このよ な ような初期局 局面は移動ル ルーチンしか か動. 局面 面には弱い．また，図 6 のような状況であれば， ，. 作しない為で 作 である．図 1 のような局 局面を得意と とす. DL LMC は一旦引く手を取 りやすく，その後の相手 手. るのは次に紹 る 紹介する DLM MC となる．. の行 行動次第で打 打開できる状 状況に持ち込 込みやすい．. 4.3 4 DLMC Depth-Limiited Monte-C Carlo[2]は図 7 に示す通 り 2 つの特徴があ つ ある．1 つは膨 膨大なノード（合法手と とな る順列）の中 る 中で極一部し しか探索を行 行わない事． も う 1 つはモン ンテカルロ手 手法をベースとしている が， シミュレーシ シ ションは途中 中で打ち切る ることである る． シミュレーションの打ち切りはボードゲー ム Amazon A にお おいて優れた た結果を示し している手法 法で ある[6][7]．尚 あ 尚，UCT+PW W に打ち切り りを加える事 事も 行ったが，単 行 単純な実装で では性能が落 落ちてしまう う為. 図 7. 本稿では扱わ 本 わない．. - 36 -. DLMC C の概要図.
(6) The 19th Game Programming Workshop 2014. III. P′ s に含ま まれる によ よる次局面s s,. 4.3.1 状態評 価関数 打ち切った た後に使用す する状態評価 価関数 g(s)は は重 要な要素では 要 はあるが，1 回のシミュレ 回 レーション毎 毎に 使用するため 使 め， DLMC ではシンプル で ルな状態評価 価関 数を用いてい 数 いる．. B. s. M 2, 1,. E. ン先までシ シミュレーシ ションし，状 状態評価関数 数 により り評価を行う う．これをn n回繰り返し し， 評価値の合 合計を測定す する． h . i 回目の のシミュレー ーション.. : →. B. d ターン ン進める.. 0 orr E. if M else. ー を d ター. 0. ∑. . ,. で評価最大の の行動 ∗ を選 選択する． IV.. P′ s の中で. M:自チームの M の駒の HP の総和（駒 の I は 0.2 倍）. . E:敵チームの E の駒の HP の総和（駒 I は 0.2 倍）. ∗. argm max ∈. B:ボーナス係 B 係数. ここで B は は勝敗が決し した際に，対 対戦中の場合 合と. この手法は特 こ 特定の局面に における良い い手の見逃 し. 区別し，評価 区 価値を倍にす するための係 係数である． 勝. を防 防ぐ事を目的 的としている る．図 8 にあるように攻 攻. 利であれば自 利 自チームの方 方が敵チーム ムよりも HP P の. 撃行 行動探索にと とって最も評 評価の高い 1 つの順列を. 総和が大きい 総 いためより良 良い評価とな なり，敗北で であ. DL LMC の着手に に加える事で で動作してい いる．. れば敵チーム れ ムの方が自チ チームよりも も HP の総和 和が. 攻撃行動探索 攻 索による最善 善手と DLM MC のランダム. 大きいためよ 大 より悪い評価 価となる．. な合 合法手がそれ れぞれ別個に にシミュレー ーションに よ. また，駒 I の HP を 0.2 倍して使用し 倍 しているのは は，. って て評価される る為，図 1 や や図 5 のような状態どち. I の攻撃力が非常に弱く，活躍があま まり期待でき きな. らの の状況にも対 対応すること とが出来る．. いためである い る．他の駒に に重みはかけ けられていな ない．. 5. 5 提案手法 法 攻撃行動探 探索は攻撃的 的な手を取る ることに優れ れて いる一方で， い 防御的な手 手を取れない い．特に図 1 の ような状況で よ で陣形を取る ることが出来 来ない．DL LMC であればこの で のような状況 況であっても も陣形を取る るこ とが可能であ と ある．しかし し，図 5 のよ ような詰め行 行動. 図 8 DLMC+攻撃 D 撃行動探索の概要図. は非常に弱く は くなる． これら 2 つ つはお互いに に明確な欠点 点を持ってお おり，. 5.2 2 局所調整 整. 補える立場に 補 にある．そこ こで， DLMC C に攻撃行動 動探. 局所調整では 局 は DLMC で サンプルした解のうち有 有. 索を組み合わ 索 わせることで で性能の向上 上を図る．. 望な なものを更に に選別し，そ そのうえで最 最後の数駒の の. 5.1 5 攻撃行動 動探索と DLMC の併用 の. 行動 動に攻撃行動 動探索を用い いて変更する る． 【提 提案手法 2:D DLMC の局 局所調整】. 単純な手法 法ではあるが が DLMC の着 着手に攻撃行 行動. I.. 探索の最善手 探 手を組み込む む事で性能の の改善を図る る．. 順列 をラ ランダムにm m個サンプルする． P s. 【提案手法 11: DLMC+攻 攻撃行動探索 索】 I... P s III.. II.. 順列 を をランダムに に m 個サンプルする． ,. ,…,. 数. をdタ. により評価を に を行う．これ れをn回繰り返 返. し，評価 価値の合計を を測定する． h . に加え える． ,…,. ⊂P s. ーン先ま までシミュレ レーションし し，状態評価関. ⊂P s. の高い い順列 ′を求め める．さらに に行動 ′をP P s ,. ,…,. 含まれる に よる次局面ss s, P′ s に含. 状態sを を攻撃行動探 探索し，その の中で最も評 評価. P s. ,. : →. i 回目の のシミュレー ーション. d ターン ン進める.. , ′ ⊂P s. . - 37 -. ∑. ,.
(7) The 19th Game Programming Workshop 2014. IIII. P′ s で評 評価の高い上 上位 j 個の順 順列を抜き出 出す． P s. ,. ,…,. ⊂ P s. 6. 対戦実験 験 本稿で紹介し 本 した UCT+PW PW，DLMC，DLMC+攻撃 撃. 含まれる順列 列 の行動を を末尾から k 個 s に含. 行動 動探索，提案 案手法 1，提 提案手法 2，提案手法 1+ +2. 削除し，攻撃行動探 探索をよる k 個の行動か から. のそ それぞれを用 用いて対戦実 実験を行う． ．実験条件 は. 成る順列 列 ′を に加え える．ここで で 1 ターンに に行. 4.1.3 と同様とし，計算時 時間を揃える為，パラメー ー. 動可能な な駒数は u とする． と. タは は表 2 の通 通りとした． 1 ターンの の実行時間 は. IV V. P. , ′. , s. ′′ , ′′ , … , ′′. VI. V P′ s , P. 程度 度としている る．尚，表に には存在しな ないが DLM MC. ′の生成. と提 提案手法にお おいて使うシ シミュレーションの深 さ. , ′ , ′ ,…, ′. ,…,. V. V II と同様 様にP. Corre i5 3.3GHzz，メモリ 8G GB の PC を用いて約 3 秒. 行動の削除. ′ , ′ ,…, ′. ′′ P. ,…,. d は 2，提案手法 1 におい て攻撃行動探索が調べる. ⊂P s. 順列 列の長さℓは は 4，提案手 手法 2 の抜き き出す順列数 数 j. s を評価する．. は 10，書き換える行動数 k は 4 とした．また，提 提. 最も評価の高 高い順列 を選 選 s の中で最. 案手 手法 1+2 は提 提案手法 2 のⅠ～Ⅲを実行した後に. 択する． ∗ ∈. argmax ∪. 提案 案手法 1 のⅡ Ⅱ～Ⅳを動作 作させる形で で成り立たせ せ，. サン ンプル数とシ シミュレーシ ション数以外 外のパラメー ー タは はそれぞれと と同じものを を使う．. 提案手法 2 は DLMC の中で評価の の の高い合法手 手を. 対戦結果を表 対 表 3 に示す ．数値はそれぞれ，勝利 利. 攻撃行動探索 攻 索に調整させ せることで動 動作している る．. 数－ －引き分け数 数－敗北数 となっており，括弧内 は. 図 9 に示すよ ように攻撃的 的な調整がされた合法手 手が j. 勝率 率を表す．. 個増えること 個 とになる．提案手法 提 2 において順列 列 に. 結果より，提 結 提案手法がそ それぞれ DL LMC と UC CT. おける末尾行 お 行動を変更す するのは，動 動作可能な駒 駒数. に大 大きく勝ち越 越している事 事がわかる．また DLM MC. が減った状況 が 況であれば提 提案手法 1 に比べれば探 に 探索. ける引き分け数が減っ て に比 比べると自己 己対戦におけ. すべき局面が す が減り，同じ じ長さの順列 列分探索した たと しても計算コ し コストが少な なくなるため めである．ま た， 経験則となる 経 るが 1 ターン ンの全行動の の内，末尾に にお. おり，防御的な な行動を取 りやすかった た問題点を解 解 決で できている．UCT+PW の の方が DLM MC に比べて提 提 案 手 法 に 対す る 勝 率 が 良 い の は ，提 案 手 法 が. いて攻撃をか い かける事が良 良い合法手と となる場合が が多. DL LMC に比べて改善して いる点が攻撃的な部分で. いように思え い える．例えば ば図 6 のよう うな状況で最 最善. ある る為，元々攻 攻撃的な部分 分が強い UCT+PW に対す す. となる合法手 と 手は攻撃行動 動を全行動の の内の末尾に にお. る勝 勝率は DLM MC からあま り伸びなかったものと考 考. いて行う事で い で得られる．. えられる． 表 2 AI のパラ ラメータ. 図 9. DLMC+局 局所調整の概 概要図 表 3 対戦結果 win – draw - loss (winratte). - 38 -.
(8) The 19th Game Programming Workshop 2014. 7. 人間プレイヤとの対戦. 参考文献 [1]. TABSTAP の元となったファミコンウォーズ DS2. 村山，藤木，池田，“学術研究用プラットフ ォームとしての大戦略系ゲームのルール提. を 50 時間以上プレイしたプレイヤ 2 人が手法 1+2. 案”，IPSJ-GPW 2013-11-01，pp.146-153. を用いた AI と対戦した結果，AI の 4 勝 3 分 3 敗. [2]. という結果となった．対戦回数は少ないものの，. 藤木，村山，池田，ターン制ストラテジーの ための状態評価型深さ限定モンテカルロ法，. AI 側が勝ち越している．現状，対戦に用いるマッ. 第 8 回 E&C シンポジウム,2014-3-19. プサイズは小さな物に限定している．小さなマッ [3]. プという前提条件さえあれば AI であっても人間と. 加藤，三輪，鶴岡，“ターン制ストラテジー ゲームにおける戦術決定のための UCT 探索. まともな対戦が出来るという結果となった．. とその効率化”，IPSJ-GPW 2013-11-01，. また，人間プレイヤの感想を聞くと「一度防御. pp.138-145. に周ると的確に攻めてくる」 「面倒な人間プレイヤ [4]. に近い」といった感想が多く聞けた．人間プレイ. Remi Coulom，“Computing Elo Ratings of Move Patterns in the Game of Go” ， ICGA. ヤが楽しむ相手としてはあまり良くない AI かもし. Journal Vol.30 pp.198-208，2007. れないが，AI の強さという面では十分な性能が出 [5]. せている．. 美添，山下， “コンピュータ囲碁 モンテカル ロ法の理論と実践” ，共立出版， （2011）. [6]. 8. まとめと今後の展望. Kloetzer, J., Iida, H., Bouzy, B., “The Monte-Carlo Approach in Amazons”. 本稿では，ターン制ストラテジーにおけるゲー. Computer Games Workshop,2007. ム木の生成方針から，DLMC の詳細，UCT のター. [7]. Kloetzer, J.,“Monte-Carlo. ン制ストラテジーへの適用方法，などを紹介した. Techniques:Applications to the Game of. 上で新たに 2 つの手法を提案した．. the Amazons”, Japan Advanced Institute. 提案した 2 つの手法と過去に提案されている手. of Science and Technology, 2010, 博情第. 法で対戦実験を行う事で提案手法の有用性を示し，. 240 号 Includes bibliographical references. UCT+PW の AI に対し最大で 66.65%の勝率を示し. pp. 87-92. た．また，UCT+PW に勝ち越す DLMC に対しては. [8]. 77.05%の勝率となることを報告した．. ターン制戦略ゲーム 学術用基盤プロジェク ト TUBSTAP，. また，現在の対戦実験で用いているマップは非. http://www.jaist.ac.jp/is/labs/ikeda-lab/tbs. 常に小さいものであり，実際のターン制ストラテ ジーでは駒数やマップサイズはより大きなものと なる．生産などのルールを含めると現在の AI の方 針では対応しきれない．そこで盤面の一部を抽出 して現在の AI に与えるために局面の分割をする機 構や，分割されたそれぞれの局面に整合性を持た せた上で動作させる為の統合 AI などが必要である．. - 39 -.
(9)
関連したドキュメント
私たちの行動には 5W1H
方法 理論的妥当性および先行研究の結果に基づいて，日常生活動作を構成する7動作領域より
担い手に農地を集積するための土地利用調整に関する話し合いや農家の意
本研究所は、いくつかの出版活動を行っている。「Publications of RIMS」
が作成したものである。ＩＣＤが病気や外傷を詳しく分類するものであるのに対し、ＩＣＦはそうした病 気等 の 状 態 に あ る人 の精 神機 能や 運動 機能 、歩 行や 家事 等の
12―1 法第 12 条において準用する定率法第 20 条の 3 及び令第 37 条において 準用する定率法施行令第 61 条の 2 の規定の適用については、定率法基本通達 20 の 3―1、20 の 3―2
船舶の航行に伴う生物の越境移動による海洋環境への影響を抑制するための国際的規則に関して
では、シェイク奏法（手首を細やかに動かす）を音
