局面の局所的な類似性を利用したモンテカルロ木探索の効率化
7
0
0
全文
(2) Vol.2013-GI-29 No.1 2013/3/4. 情報処理学会研究報告 IPSJ SIG Technical Report. 有力な着手であっても UCB1 値が大きくなるのは遅い可能 性があるという問題点がある. そこで, 類似局面の勝敗を利 用することで有力な着手を早くみつける RAVE[3] という 手法が提案された. 本研究でも用いた囲碁プログラムであ る”Fuego”では UCB1 に RAVE を組み合わせてモンテカ. 図 1 (1) 探索するゲーム木 図 2 (2) 探索. 図 3 (3) 拡張. ルロ木探索を行っている.”Fuego”はトップレベルのプログ ラムの一つであり, KGS [1] という囲碁サーバーで”3d”と いう強さである.”d”はおおよそ「段」に相当する. また, 9 路盤ではかなりの強さを発揮するが, トッププロにはまだ 及ばない棋力である. 本研究では, 囲碁プログラムの棋力の更なる向上を目的 として, 局面の類似性に基づく RAVE の拡張を提案する. 本研究の着目点は, ある局面の勝率を似た局面の勝率で見 積もる際によく似ている局面なら見積りは正確になるが, あまり似ていない局面では荒い見積りしかできないという 点である.RAVE と局面の類似性の関係については, これま であまり検討されてこなかった. そこで, 本研究では着手近 辺の局所的な類似性に着目し, RAVE における見積りの精 度を向上させることを試みた. 局所的な類似のもっとも簡 単な指標として, 着手の周囲 8 ヶ所の状態の一致の有無を 採用した. この指標は, RAVE 以外のパラメータ調整では 既に囲碁で用いられているため, RAVE でも効果的である と期待できる. 提案手法を実装し, 様々な条件での対局通じ て提案手法の効果を検証した.. 2. 関連研究. 図 4 (4) プレイアウト図 5 (5) 結果の伝達 ( 1 ) 情報を得るリーフを一つ選ぶ. リーフの選択はルートから有力な ノードを選び続けることで行う (図 2) ( 2 ) 訪問回数が閾値に達したノードがあれば展開する. (図 3) ( 3 ) プレイアウトを行う (図 4) ( 4 ) プレイアウトの結果をノードに返す (図 5). ドの選択をいかに行うかに探索の特徴が表れる. プレイア ウトの結果としては, 終局時の相手との地の差を用いるこ ともできるが, 地を無視して勝敗を用いる方が効果的とさ れている [参照]. 本研究で用いた Fuego でも, 勝敗を勝ち 1, 負けを 0 としてプレイアウトの結果として用いている. プ レイアウトの回数が増えれば増えるほど, リーフでの評価 値の信頼性がます.. 2.1.1 UCT UCT は, モンテカルロ木探索の代表的なアルゴリズム. 囲碁におけるゲーム木探索と囲碁における局所的なパ ターンについて述べる.. である. これはゲーム情報学でも広く扱われていて, 様々な ゲームの探索に有効であることが分かっている. この UCT は図 1 でのノードの選択で UCB1 値を用いてノードを選択. 2.1 モンテカルロ木探索. する.UCB1 値は以下のように定義される.. ゲーム木の探索にも様々な手法があるが, コンピュータ 囲碁ではモンテカルロ木探索が有力とされ, 実際に広く使 われている.. r UCB1(s,a) = Xs + c. 2 log n ns. モンテカルロ木探索では局面の優劣を, お互いにランダ. s:ノード, a:s で可能な着手, Xs : ノード s を通ったプレイ. ムな着手 (プレイアウト）を行った場合の勝率を元に判断. アウトの平均報酬, c:定数, n:ノード s の親ノードを通った. する. 背景として, もしある局面がどちらかに有利であれ. 回数, ns :ノード s を通った回数. ば, プレイアウトで勝利する可能性も高いだろうという考. Xs は 平 均 報 酬 Xs は 囲 碁 で は 勝 率 を 用 い る.ns =. えがある. 囲碁では終局時においては結果を計算する事が. 0 の時 UCB1(s,a) = ∞ であるので, ノードに着手の数. 可能であり, 自分の眼に打たないという制約があれば手数. と同じ回数プレイアウトを行えば, 全ての着手に 1 度ずつ. を重ねれば終局する. この点で. プレイアウトを用いた評価. プレイアウトが行われることになる 右辺の第一項は勝率. は囲碁に適している. また従来のゲーム木探索手法と比べ. の高いノードほど選ばれやすい傾向を, 右辺の第二項は訪. ると, 評価関数が必要でないことも強みである. このモンテ. 問回数の少ないノードほど選ばれやすい傾向を生み出して. カルロ木探索の採用により飛躍的にコンピュータ囲碁プロ. いる. 定数 c はこれらの傾向のバランスを調整している. つ. グラムは強くなった.. まり, 第二項の影響によって訪問回数の少ないノードに対. モンテカルロ木探索では図 1-5 のようにしてこのプレイ アウトを行っている.. しては優先的にプレイアウトが割り当てられる. 親ノード を多く通るとルートの中の分子が大きくなり, そのノード. この一連の流れの中でモンテカルロ木探索の性能に関わ. 自体が選ばれると分母が大きくなる. そのために, そのノー. るのが図 2 で示されているノードの選択である. このノー. ドを通ることができるのに選ばれないと第二項は大きく. ⓒ 2013 Information Processing Society of Japan. 2.
(3) Vol.2013-GI-29 No.1 2013/3/4. 情報処理学会研究報告 IPSJ SIG Technical Report. なっていく. この第二項の影響によってすべてのノードに. プレイアウト数が少ない時は RAVE 値の利用している勝敗. 程よくプレイアウトが割り当てられる. プレイアウト回数. 数が多いので, RAVE 値が優先的に使われる また, プレイ. が多くなると第二項の影響が小さくなるので, 第一項の影. アウト数が多い時は UCB1 値の信頼性が増すので, UCB1. 響が強くなる. そのために, 評価値の高いノードが選ばれる. 値が優先的に使われる. ようになる. また, プレイアウト回数を増やすと平均報酬 がミニマックス値 (各プレイヤが最善手を選んだ場合の報 酬) に収束することが知られている [4], [9].. 2.2 囲碁における局所的なパターンの利用 囲碁では局所的なパターンを利用することが, 一般的 である. これは, 「ツケにはハネよ」「ハネには伸びよ」等. 2.1.2 RAVE UCT では探索の間に通ったノードの情報しか考慮され. の格言や局所的な石の並びに「一間飛び」 「桂馬」 「タケフ」. ない そのため, プレイアウト回数が少ない間の UCB1 値. 等の名前がある. これらを元に人間は候補手を考えている. と十分にプレイアウトを行った平均報酬の差が大きいとい. と考えられる. このことから局所的なパターンの利用はコ. う問題がある 結果として, 有力なノードに割くプレイア. ンピュータ囲碁に限った話ではないことが分かる.. ウトの数も少なくなってしまう. プレイアウト回数が少な. コンピュータ囲碁においても以下のように局所的なパ. い間にも有力なノードを選択するように考えられた手法 ˙ が, RAVE[3] であるRAVE は局面の類似性を利用して情報. ターンが利用されている. 中西ら (2011)[13] の研究では局. を補う手法と解釈することが出来る. つまり，似た局面で. いていると考えられる. このようにコンピュータ囲碁では. のプレイアウトの結果であれば, 本来調べたい局面からの. パターンマッチングを行うことは様々な指標に用いられて. プレイアウトの結果と近いと期待できるというアイデア. いる [2], [12], [13].. 所的なパターンを着手の思いつきやすさ手の指標として用. である.citegelly07.RAVE を用いた探索では, 以下のように. 本研究では局所的なパターンを局面の類似性の指標とし. UCB1 値とこの RAVE 値を組み合わせた値 value (s,a) の. て用いることで, RAVE の精度を向上させることを目的と. 大きいノードを選択することで探索の効率化を図っている.. している.. value(s, a) = β(s, a)RAVE(s, a)+(1−β(s, a))UCB1(s, a). 3. RAVE での着手近辺の局所的な類似性の 利用. β(s, a) =. k (3ns + k). 本研究の目的は類似性をより詳細に検討し, RAVE の効. s:ノード, a:s で可能な着手, RAVE(s, a):ノード s の着手 a. 果を高めることである. そのために着手の周囲の状況を考. の RAVE 値, ns :ノード s を通った回数, k:定数, UCB1(s, a):. 慮に入れる. 周囲としては着手点の周囲 8 ヶ所 (図 7 参照). ノード s の着手 a の UCB1 値, β(s, a):変数. を考える．つまり, 同じ場所への着手であっても，この周 囲 8 ヶ所の状況が同じ着手は, そうでないものよりもより. また, RAVE 値は以下のようにして計算される.. 類似していると扱う.. s RAVE(s, a) = X(s, a) + c m(s) =. X. log m(s) m(s, a). m(s, a). 3.1 Fuego でのノード選択 Fuego では UCT と RAVE を以下のように組み合わせて, value の高いノード s を選択している.. a. s:ノード, a:s で可能な着手, X(s, a):子孫のノードで着手 a を選んだプレイアウトの勝率, c:定数, m(s, a):子孫のノー ドで着手 a を選んだ回数, m(s):着手 a を合法手に持つノー. value(s, a) = β(s, a)RAVE(s, a) + (1 − β(s, a))UCB1(s, a) β(s, a) =. ドを通った回数. m(s, a) ns · (1.0/0.9 + 1.0/20000 · m(s, a) + m(s, a)) X m(s, a) = αj. RAVE の式は UCB1 値の式と似ているが, RAVE の場合 第一項はノード s 以降の探索で着手 a を選んだプレイアウ. j. 目新しさを表す 1 回のプレイアウトで着手を行った盤上. first − i len − i s:ノード, a:着手, m(s, a):ノード s もしくはその子孫の. の点の数だけ RAVE 値は更新されるので, UCT では 1 回. ノードで着手 a を選んだ回数, ns :ノード s を通った回数, ,. のプレイアウトで 1 つのノードの勝敗しか情報が得られな. first:RAVE 値を更新する着手がプレイアウトの中で初めて. かったが, RAVE では 1 回のプレイアウトで複数のノード. 打たれたノードのルートからの深さ, len:プレイアウトの長. の情報を得られることになる. そのために, 少ないプレイア. さ. トの勝率を, 第二項はノード s 以降の探索中での着手 a の. αj = 2 −. ウト数でも結果が収束しやすい. そのために, value(s,a) は ⓒ 2013 Information Processing Society of Japan. 3.
(4) Vol.2013-GI-29 No.1 2013/3/4. 情報処理学会研究報告 IPSJ SIG Technical Report. Fuego では各プレイアウトの結果に重みをつけて, RAVE での勝率を重み付き平均として計算している.αj = t の時 そのプレイアウトの勝敗を t 回分のプレイアウトとして扱 う. したがって, αj = 1.4 でプレイアウトで勝利したとす ると, そのプレイアウトの結果は 1.4 回試合をして 1.4 回 1. 勝ったものとして扱われる.αj = 1 であれば, 重みをつけ. : 黒番. b. ていないと同じである. そのため, この αj を大きくするこ. 2. 3. 5. 6. : 白番. 4. とによって, 各プレイアウトごとの重要さに差をつけるこ とができる. この効果については図 6 で確認できる. 1. 9. 0.9. c. b. 10. 11. a. a 15. 0.8. 16. c. 8. 13. 14. c. 12. a. 17. 7. a. 18. 19. 26. 27. b 21. 20 c. 0.7 23. 22. 0.6. β 0.5. 25. 24. 29. 28. c. a. 30. 0.4 0.3. ns = 1α a=1 ns = 1α a=2 ns = 100α a=1 ns = 100α a=2. 0.2 0.1 0 0.1. 1. 10. 100. m(s,a) ˛–. 1000. 32. 31. 33. 34. 35. 36. 37. 39. 38. 図 8 ゲーム木. 10000. 図 6 重みを増やす効果. 図 6 は全てのプレイアウトの重みを一律に変化させた場 合の, RAVE の試行回数 m(s,a) と UCB1 と RAVE の重視 具合を表すベータの対応を描いたグラフである alpha=1 と alpha=2 を比較すると, 2 の方が上にある つまり, ベー タが大きく rave が重視されることが分かる,. 1. : 黒番. b. 3.2 着手周辺の類似性に基づく重み付け. 2. 3. 5. 6. : 白番. 4. 従来の RAVE との差を図 8 のゲーム木を例に説明する 図 8 のノードのうち 2 番のノードにおける RAVE 値の計. c. 算方法について, 特に図 7 の着手点 a への着手の RAVE 値 9. について説明する. エッジにラベルがあるものはラベルの. 10. 11. a. 点に着手していることを表し, ラベルが無いものは a の周. a 15. c. b. 16. 17. 8. 13. 14. c. 12. a. 7. a. 18. 19. 26. 27. b 21. 20. 囲以外への着手であるとする.. c. RAVE の発想はある点への着手の効果は着手の順序に. 23. 22. 24. 25. 29. 28. c 30. a 31. 32. 33. 34. 37. 35. 36. 39. 38. 図 9 従来の RAVE. 図 7 着手 a の周囲. ⓒ 2013 Information Processing Society of Japan. 4.
(5) Vol.2013-GI-29 No.1 2013/3/4. 情報処理学会研究報告 IPSJ SIG Technical Report. あまり影響を受けないために, 順序の違うプレイアウトに. ソースプログラムである Fuego に実装した そして, 提案. も用いることができると言うものである. そのため, 従来. 手法を導入した Fuego とオリジナルの Fuego の対局や, 別. の RAVE では, ルートから 2 番のノードを通って行われる. の囲碁プログラムである Pachi との対局を行ない, 勝率を. プレイアウトを 2 番のノードの RAVE 値の更新に用いる.. 測定した 9 路盤, 13 路盤, 19 路盤の三種類で行なった 実. つまり, 2 番のノードの RAVE 値の更新には図 9 の 16, 23,. 装の概要は, 着手の周囲 8 箇所を判定するため, 8 箇所の変. 25, 31, 32, 33, 37 番のノードからのプレイアウトを用いる.. 更状況を整数で表現し, RAVE の重みの計算で参照したこ. そのうち, ルートからのパスに a の着手を含むものは, 23,. とである ソースコードの変更部分は約 X 行程度であった. 25, 31, 32, 33, 37 番のノードである. これらのノードでの. 実装の簡略化のため, ある一度でも変化した格子点は異な. プレイアウトが 2 番のノードの着手 a の RAVE 値の更新. るとして扱った つまり着手の後に石が打ち上げられて, 偶. に用いる. 一方提案手法の場合では. 然元の状況に戻った場合には判定を誤ることがある しか しそのような可能性は少ないと考えられる 実験には以下. 1. : 黒番. b 2. 3. 5. 6. 9. c. b. 10. 11. a. a 15. 16. 7 c. k 倍したプログラム. 8. パターン優先 ( k, l). 13. 時の αj を k 倍, 一致しなかった時の αj を l 倍した. b 21. 20. プログラム. c 23. 22. 24. 25. 26. これらを以下のような条件でオリジナルの fuego と対戦 29. 28. 27. c. させた. a. 30. 31. 32. 33. 34. 37. 提案手法のようにある着手の周囲. 8 ヶ所の状態と一致した状態の時にある着手を行った. 14. a 19. 18. Fuego オリジナルの Fuego (リビジョン 1603) 倍率変更 k オリジナルの fuego の更新の際に一律 αj を. c. 12. a. 17. : 白番. 4. のようなプログラムを用いた.. 35. 36. 38. 実験条件 碁盤 9 路盤. 39. ルール 中国ルール コミ 6 目半. 図 10 提案手法. 試合数 10000 プレイアウト数 10000. 図 10 では周囲 8 ヶ所の状態が 2 番のノードの着手点 a. 時間 無制限. の周囲 8 ヶ所の状態と一致する時に a へ着手したパスに含. 表 1 の結果は左肩に*のついたものは基準となる勝率,. まれるリーフは 23, 31, 37, 38, 39 番のノードである. これ. #のついたものは有意水準 5%で有意に強くなった勝率,. らのノードのうち従来の RAVE で 2 番のノードの RAVE. $のついたものは有意水準 1%で有意に強くなった勝率であ. 値の更新に用いられていたものは, 23, 31, 37 番のノードで. る. 倍率変更 k の変数 k の値を変えて実験を行ったところ. ある. これら 3 つのノードの局面では着手点 a の周囲に関. 倍率変更 1.5 がオリジナルの Fuego に対して黒番・白番と. しては 2 番のノードの局面での着手点 a に着手された後の. もに有意水準 5%で有意に強くなった. このことから 9 路盤. 局面と類似していると考えた. よって, これらのリーフでの. ではオリジナルの Fuego に比べて αj は 1.5 倍にすること. プレイアウトは 2 番のノードでの着手点 a への着手の効果. が望ましいと考えられる. また, 提案手法を導入したパター. を従来のものより類似した局面で測定していると期待され. ン優先 (1.5, 1), パターン優先 (2, 1) の結果から, 提案手法. る. そのために, 本手法では従来の手法で用いていたリー. はある着手の周囲 8 ヶ所の状態と一致した状態の時にある. フの中で着手点 a への着手の効果と同等と考えられるプレ. 着手を行った時の αj を 1.5 倍, 2 倍することで効果を発揮. イアウト, つまり, 23, 31, 37 番のリーフでのプレイアウト. することがわかった. オリジナルの Fuego に対して αj は. の更新の際の αj を大きくする. もしくは, それ以外のリー. 1.5 倍にするのが適正であると考えたので, これを基準に提. フでのプレイアウトの αj を小さくする. このことによっ. 案手法を適応したものがパターン優先 (3, 1.5), パターン優. て 23, 31, 37 のリーフでのプレイアウトの結果を重視する.. 先 (2.25, 1.5) である. パターン優先 (2.25, 1.5) は今回の実. 本研究ではこの手法を用いている.. 験の中で黒番・白番ともにもっとも高い勝率をあげた.. 4. 対戦実験 4.1 対 Fuego 提案手法の効果を測定するために, 提案手法をオープン ⓒ 2013 Information Processing Society of Japan. また, 13 路でも同様の実験を行った. 黒番のみで実験を 行った. その他の設定は 9 路の時と同じである. 13 路では オリジナルの Fuego に対して有意に強くなったものはな かったが, 高い勝率をあげているものもあった.. 5.
(6) Vol.2013-GI-29 No.1 2013/3/4. 情報処理学会研究報告 IPSJ SIG Technical Report. (9 路). 勝率. 19 路. 勝率. 白番. プログラム名. 黒番. 2.9%. 1.2%. 倍率変更 0.75. 49.8%. 38.4%. プログラム名. 黒番. 倍率変更 0 倍率変更 0.5. Fuego (倍率変更 1). Fuego (倍率変更 1). 49.7% *50.6%. *56.0%. *44.0%. 倍率変更 1.25. #57.6%. #45.6%. 倍率変更 1.5. 50.4%. 倍率変更 2. 56.4%. 44.9%. 倍率変更 1.75. 51.9%. 倍率変更 2.5. 56.0%. #45.7%. 倍率変更 2. 47.4%. 倍率変更 3. 56.5%. 45.2%. 倍率変更 2.5. 45.0%. 倍率変更 3.5. 56.1%. 44.0%. パターン優先 (1, 0.75). 倍率変更 4. 55.1%. 43.6%. Fuego (パターン優先 ( 1, 1)). パターン優先 (1, 0). 33.2%. 24.4%. パターン優先 (1.25, 1). パターン優先 (1, 0.25). 49.9%. 36.0%. パターン優先 (1.5, 1). #55.7%. パターン優先 (1, 0.5). 54.2%. 42.4%. パターン優先 (1.75, 1). #55.6%. Fuego (パターン優先 ( 1, 1)). *56.0%. *44.0%. パターン優先 (2, 1). パターン優先 (1.5 1). $58.6%. $47.1%. パターン優先 (4, 1). パターン優先 (2, 1). #57.5%. $46.6%. Fuego (パターン優先 ( 1, 1)). *50.6%. 倍率変更 1.5. パターン優先 (4, 1). #55.1%. 50.4% *50.6% 54.6%. 49.1% 52.5%. 52.5%. 42.1%. パターン優先 (1.5625, 1.25). #54.0%. Fuego (パターン優先 (1, 1)). *56.0%. *44.0%. パターン優先 (2.1875, 1.25). 52.3%. パターン優先 (3, 1.5). $58.4%. $47.0%. パターン優先 (2.5, 1.25). 49.7%. パターン優先 (2.25, 1.5). $59.4%. $48.2%. パターン優先 (4, 2) $58.0% 表 1 対戦実験結果 (9 路). $46.6%. パターン優先 (4, 2) 43.6% 表 3 対戦実験結果 (19 路). のが適正であると考えたので, これを基準に提案手法を適 応したものがパターン優先 (2.1875, 1.25) である. 有意水. 13 路. 勝率. プログラム名. 黒番. 準 5%で有意ではないが, パターン優先 (1.25, 1) も勝率を. *51.4%. あげているので, 提案手法はある着手の周囲 8 ヶ所の状態. Fuego (倍率変更 1) 倍率変更 1.25. 50.8%. 倍率変更 1.5. 49.7%. 倍率変更 1.75. 48.6%. 倍率変更 2. 48.5%. ン優先 (1.5625, 1.25) でこの設定を採用している. パターン. 倍率変更 2.5. 46.6%. 優先 (1.5625, 1.25) も有意水準 5%で有意に強くなった.. Fuego (パターン優先 ( 1, 1)). *51.4%. パターン優先 (1.25, 1). 52.0%. パターン優先 (1.5, 1). 52.7%. パターン優先 (1.75, 1). 51.3%. パターン優先 (2, 1) 50.5% 表 2 対戦実験結果 (13 路). と一致した状態の時にある着手を行った時の αj を 1.25 倍 することで効果を発揮するのではないかと考えた. パター. 以上の結果から提案手法は 9 路, 19 路に対して有効で あることがわかった.13 路についてはパラメータの調整が 必要である. また, 9 路での Fuego の 1 局当りの計算時間 は平均 18.3s, 最短 8.5s, 最長 41.9s であり, パターン優先. (3, 1.5) の 1 局当りの計算時間は平均 21s, 最短 11.4s, 最長 42.7s であった. また, 13 路での Fuego の 1 局当りの計算時. また, 19 路でも同様の実験を行った.19 路の試合には時. 間は平均 76.3s, 最短 42.1s, 最長 281.8s であり, パターン優. 間がかかるので, 試合数は 1000, 黒番のみで実験を行った.. 先 (1.5, 1) の 1 局当りの計算時間は平均 89.3s, 最短 45.5s,. その他の設定は 9 路の時と同じである. ただし, Fuego, パ. 最長 216.6s であった.19 路での Fuego の 1 局当りの計算時. ターン優先 (1.25, 1.5625), パターン優先 (1.75, 2.1875) は. 間は平均 208.2s, 最短 140.2s, 最長 276.5s であり, パター. 3000 試合行った結果である.. ン優先 (1.75, 1) の 1 局当りの計算時間は平均 235.6s, 最短. 結果は表 3 のようになり, 左肩に*のついたものは基準と. 144.9s, 最長 332.9s であった.. なる勝率, #のついたものは有意差 5%で有意に強くなった 勝率である.19 路では倍率変更 1.25, パターン優先 (1.75,. 4.2 対 Pachi. 1), パターン優先 (1.5625, 1.25) がオリジナルの Fuego に. Fuego 同士の対戦で有意に勝率が向上したプログラムを. 対して黒番で有意に強くなった. また, 提案手法を導入し. Pachi(version 10.00 (Satsugen)) と対戦させた. 実験条件は. たパターン優先 (1.75, 1) の結果から, 提案手法はある着手. 以下の通りである. の周囲 8 ヶ所の状態と一致した状態の時にある着手を行っ. 実験条件. た時の αj を 1.75 倍することで効果を発揮することがわ. 碁盤 9 路盤. かった. オリジナルの Fuego に対して αj は 1.75 倍にする. ルール 中国ルール. ⓒ 2013 Information Processing Society of Japan. 6.
(7) Vol.2013-GI-29 No.1 2013/3/4. 情報処理学会研究報告 IPSJ SIG Technical Report. コミ. 似性を利用して効率的に情報を収集する RAVE のような. 6 目半. 試合数 10000. 考え方は有効である対象は多いと考えられ, 提案手法も応. 時間. 用可能であると期待される. それらの具体化は, 今後の研究. 無制限. Fuego はプレイアウト数 10000 回, Pachi はプレイアウ. 課題である.. ト数 30000 回とした. 試合数は 10000 試合行った. 参考文献 9路. 勝率. プログラム名. 黒番. Fuego (倍率変更 1). [1] [2]. *66.6%. 倍率変更 1.5. 66.6%. パターン優先 (1.5, 1). 67.7%. パターン優先 (2.25, 1.5) 67.3% 表 4 対 Pachi 実験結果 (9 路). 提案手法は有意ではないが, 勝率を向上させることがで. [3]. [4]. [5]. きた. 対戦相手によってパラメータの調整を行う必要があ ると予想される. [6]. 5. おわりに 本研究では, 探索問題を解くためのアルゴリズムである. [7]. UCT に着目し, UCT と組み合わせて用いられる RAVE と いう手法の効率改善に取り組んだ.RAVE とは, 局面の情報 が少ない場合には類似する局面を補うことで, モンテカル. [8]. ロ木探索の性能を高める手法である. 類似性の具体的な指 標としては, 囲碁を題材とした研究では標準的な, 着手の 周囲 8 ヶ所の状態を用いた. この類似性の指標を, 着手の周. [9] [10]. 囲 8 ヶ所の石の状況が一致した状況での試行 (プレイアウ ト) で得られた結果を, 一致しなかった状況での試行より重 視する様に, RAVE の枠組みを拡張した. RAVE において,. [11]. 着手の周囲 8 ヶ所の石の状況が一致した状況での試行 (プ レイアウト) で得られた結果を, 一致しなかった状況での試 行 (プレイアウト) で得られた結果より重視するように, こ. [12]. の類似性の指標を活用した. 着手の周囲の 8 ヶ所が一致した状況をどの程度重視す. [13]. ると良いかについては, 盤面の大きさ (9 路盤, 13 路盤, 19 路盤) によって異なることが, 実験結果から分かっている.. [14]. 従って, このパラメータは, 適用対象の問題ごとに決める必 要があると思われる. なお, 実験の過程で, RAVE 自体をど. [15]. のように重視するかを決めるパラメータについても, Fuego には調整の余地があることが分かった. 今回の実験の結果. [16]. から提案手法の効果はあったと考えられる. 今後は, 機械学 習を用いてこのパラメータを調整していくことも視野に入 れている [6], [7], [10], [16], [17]. RAVE の重視具合の調整 だけでなく, 周囲 8 ヶ所を利用して類似性を判定する提案. [17]. Kgs. http://www.gokgs.com/index.jsp?locale=ja JP. Cheng-Wei Chou, Shi-Jim Yen, and Jung-Kuei Yang. Using global corresponding move bias on mcts. In The 17th Game Programing Workshop 2012, pp. 63–67, 2012. Sylvain Gelly and David Silver. Combining online and offline knowledge in uct. In the 24th international conference on Machine learning, 2007. L Kocsis and Cs Szepesvari. Bandit based monte-carlo planning. In Machine Learning: ECML 2006, Vol. 4212, pp. 282–293. Springer, 2006. 関栄二, 三輪誠, 鶴岡慶雅, 近山隆. 将棋におけるモンテカ ルロ木探索の特性の解明. In The 17th Game Programing Workshop 2012, pp. 68–75, 2012. 佐藤佳州, 高橋大介. 大規模な対局に基づいた教師データの 重要度の学習. In The 17th Game Programing Workshop 2012, pp. 22–29, 2012. 藤田康博, 浦晃, 三輪誠, 近山隆. General game playing に おけるモンテカルロ木探索のシミュレーション方策の学 習. In The 17th Game Programing Workshop 2012, pp. 38–45, 2012. 池田心. モンテカルロ碁における多様な戦略の演出と形勢の 制御 接待碁 ai に向けて. In The 17th Game Programing Workshop 2012, pp. 47–54, 2012. 村松正和. コンピュータ囲碁の現状. 情報処理学会誌, Vol. 53, No. 2, pp. 133–138, 2 2012. 竹内聖悟, 金子知適. 探索パラメータの調整に適した目的関数の調査-モンテカ ルロ木探索将棋の探索パラメータの調整-. In The 17th Game Programing Workshop 2012, pp. 84–91, 2012. 横山大作. モンテカルロ木探索アルゴリズムの将棋への適 用. In The 17th Game Programing Workshop 2012, pp. 76–83, 2012. 本田拓郎, Simon Viennot, 池田心. 囲碁における大局観 を実現する広域パターンマッチング. In The 17th Game Programing Workshop 2012, pp. 17–21, 2012. 中西惇, 中村貞吾. 局面変化とパターンによる着手予測を 用いた囲碁の好手の判別. In The 16th Game Programing Workshop 2011, pp. 108–111, 2011. 万代悠作, 橋本剛. Ucb+を用いた big two ai の研究. In The 17th Game Programing Workshop 2012, pp. 205– 210, 2012. 大町洋, 池田心. 同時進行ゲームのためのモンテカルロ木 探索. In The 17th Game Programing Workshop 2012, pp. 197–204, 2012. 鈴木洋平, 金田康正. 多様性に注目した将棋プレイヤの 集団学習に関する調査. In The 17th Game Programing Workshop 2012, pp. 30–37, 2012. 野中翔平, 中村貞吾. 合議制囲碁プログラムのための多 様な知識の集団学習. In The 17th Game Programing Workshop 2012, pp. 55–62, 2012.. 手法に価値があると考えられる. また, 実験条件を変えるこ とで， 今回の結果の多方面から分析していく. モンテカルロ木探索は, 囲碁のような二人零和完全情 報 ゲ ー ム 以 外 に も, 多 数 応 用 さ れ て い る [5], [11], [14],. [15].UCT が使われる問題であれば, プレイアウトの類 ⓒ 2013 Information Processing Society of Japan. 7.
(8)
関連したドキュメント
処分の違法を主張したとしても、処分の効力あるいは法効果を争うことに
算処理の効率化のliM点において従来よりも優れたモデリング手法について提案した．lMil9f
ü modeling strategies and solution methods for optimization problems that are defined by uncertain inputs.. ü proposed by Ben-Tal & Nemirovski
個別の事情等もあり提出を断念したケースがある。また、提案書を提出はしたものの、ニ
業務繁忙時にも対 応できるよう、施 設に必要な従事者 を適正に配置する とともに、利用者 サービス向上、効 率的・効果的な管 理運営の観点を踏
著者らはケーソン浮上り防止技術の開発にあたり、ケーソ ン外周面の FS によるせん断抵抗力の効果を把握するため、実 大 1/40 に縮小した模型引抜き試験を行い、 FS
また，この領域では透水性の高い地 質構造に対して効果的にグラウト孔 を配置するために，カバーロックと
平成 27 年 2 月 17 日に開催した第 4 回では，図-3 の基 本計画案を提案し了承を得た上で，敷地 1 の整備計画に
