強豪囲碁ソフト「彩」について 山下 宏 2009 年 9 月 11 日 機械振興会館 ※彩（あや）と読みま す.

Presentation on theme: "強豪囲碁ソフト「彩」について 山下 宏 2009 年 9 月 11 日 機械振興会館 ※彩（あや）と読みま す."— Presentation transcript:

1 強豪囲碁ソフト「彩」について 山下 宏 2009 年 9 月 11 日 機械振興会館 ※彩（あや）と読みま す

2 モンテカルロ法って？ z 乱数を使って数値計算を（適当に）行う 手法 y 円周率（ π ）の計算など z ギャンブルで有名なモナコの地名 z フォン・ノイマンが命名 z… なぜかラスベガス法ではない

3 モンテカルロ法の衝撃 z1996 年 囲碁プログラム「彩」を作りはじ める z2007 年 GnuGo が KGS で 6 級、彩は 8 級 z2007 年 10 月にモンテカルロ法に移行 z2008 年 2 月、モンテカルロ法の彩が 3 級 に y12 年かけて GnuGo にすら届かなかったのが 4 ヶ月で GnuGo を遥かに追い越した！ z 従来の人間の思考の真似をしていたプロ グラマには大ショック

4 モンテカルロ法のおかげで製品 化 z2009 年 7 月に彩が「囲碁世界 V 」として発 売 y ただ最強ではありません。 KGS で 2 級。

5 最強の囲碁ソフトと対戦するに は z2009 年 9 月 18 日に発売予定の「天頂の囲 碁」 y 思考エンジンは Zen （作者は尾島陽児さん） yKGS で初段 ( 日本だと 3 段程度に相当 )

6 彩の仕組み z 評価関数はモンテカルロ法 y 囲碁知識やパターンを利用 z 木探索は UCT y 従来の局面認識を利用した読む手の絞込み

7 従来のプログラムの評価 右上の黒石は死んでいそうだな … 左下は黒の陣地かな？ 黒が 9 目勝っている 局面が与えられたらそれを分析

8 モンテカルロ法による評価 どうやって判断したらいいか分か らないな･･･ とりあえず、でたらめに最後まで 打ってみよう！ 白が１５目勝ち

9 モンテカルロ法を使った囲碁の仕組 み １．乱数で黒石、白石を交互に置く ２．打つ場所がなくなったら終了 ３．点数を計算する ４．１. － ３. を何度も繰り返す ※本当に乱数で打っていくと終わらないため 「眼」には打たない、というルールを付け加え る。 （実際のサンプルを表示）

10 9 路でのシミュレーション （ playout ） 初期局面 30 手目 終局図

11 19 路でも基本は同じ 初期局面 100 手目 終局図

12 目数差ではなく、勝率、を使う １ y1 回目は 15 目勝った (+15) y2 回目は 20 目負けた (-20) y3 回目は 81 目勝った (+81) 大きく勝ちす ぎ！ y4 回目は 10 目負けた (-10) y ーーーーーーーーーーーーーーーーーーーー ー y 目数差 合計 +66 y 平均 +66/4 =+16.5 目勝ち

13 目数差ではなく、勝率、を使う ２ y1 回目は 15 目勝った 勝ち +1 y2 回目は 20 目負けた 負け +0 y3 回目は 81 目勝った 勝ち +1 y4 回目は 10 目負けた 負け +0 y ーーーーーーーーーーーーーーーーーーーー ー y 合計 +2 y 平均 +2/4 =0.50 勝率 50%

14 目数差ではなく、勝率、を使う ３ z 目数差のほうが情報量が多い気がするが、 実際に対戦させると勝率の方が強い。 z 「勝率」の利用が 33 勝 5 敗、勝率 0.86 z 「勝率」の方が安定した評価ができる！ y100 目勝っても半目勝っても勝ちは勝ち？ y 勝率と目数差を組み合わせる？ x15 目勝ちは +1 + 0.15 、など

15 従来の彩の局面評価（人間の真 似） z 石の死活 y 探索で調べる z 陣地の大きさ y 影響力関数を使う z 石の強さ y 石の連絡 y 陣地の大きさ y 周囲の敵、味方の状況 y 逃げ出せる可能性

16 影響力関数（陣地の判定） z 石の近くほど点数が高 い z 黒石は＋、白石はー z 死石は相手の石として 計算 z すべてを合計して＋な ら黒地、－なら白地

17 陣地の判定の比較 従来の地の評価モンテカルロによる地の評 価 モンテカルロの方が右辺の黒地に評価が滑らかに出ている

18 石の強さ（生存確率）の評価 従来の評価モンテカルロによる評価 従来は 100% 、 68% と大雑把。モンテカルロは滑らか。

19 シミュレーションの精度を上げる z 囲碁知識を利用 y アタリを逃げやすく、石を取り やすく z ３ｘ３の範囲のパターンを学 習 y 人間の棋譜から統計を取る y 着手確率を求める 高確率 低確率 アタ リ

20 黒石の着手確率 数値が大きいほど着手確率が高い

21 パターンを利用したサンプル サンプルを再生

22 単純乱数（上）と囲碁っぽい乱 数 単純乱数（上）は途 中図がひどい。最後 はどちらも同じ感じ

23 石の強さ（生存確率）での比較 単純乱数囲碁っぽい乱数 単純乱数は本来生きている石が不安定になっている

24 局面評価の結果（極端な例） 単純な乱数パターンを利用 単純な乱数は上下の黒石が接続しているのが分かってな い パターンを利用した方がより正しく局面を理解でき る

25 単純乱数と囲碁っぽい乱数の棋 力 z9 路盤では 100 回対戦させて 99 回囲碁っぽ い乱数が勝つ z19 路盤では 100 回全部勝つ z 囲碁の知識をシミュレーションに組み込 むことは非常に効果がある！

26 9 路盤と 19 路盤での違い z 探索速度 y 9 路盤 6300 playout/ 秒 Core Duo 1.83GHz y19 路番 1600 playout/ 秒 1 core のみで y それほど速いわけではない z9 路盤では枝刈しなくてもそこそこ強いも のが作れる z19 路盤では可能な手の数が多いため「手 をしぼる」作業を行わないとあまり強く できない。

27 19 路盤での候補手の選択方法 z 全ての手に確率を与える y3x3 のパターン y 盤の端からの距離での確率（ 3 線、 4 線が高確 率） y 直前の相手の手からの距離（近いほど高確 率） y 連の死活探索の結果 x 「死んだ」石が動き出す確率を極端に下げる y 眼形の急所（中手や欠け眼） yAMAF で評価が高い手 z 上位 20 手程度だけを探索

28 得意と苦手 z モンテカルロ法とはいえ万能ではない！ z 手順が形によらず強制されるケースに弱 い y 隅の死活 y 攻め合い z ぼんやりした判断は強い y 石の連絡 y 石の強さ y 厚みの評価（中で生きられない、中央の地）

29 以前からの局面評価も無駄ではない z モンテカルロ法に以前からの局面評価を 組み合わせると効果的 y 部分的な死活探索 y 眼形認識 x 中手 x 欠け眼の判断 y セキの認識 z 重要な手を素早く抽出できる

30 シミュレーション（ｐｌａｙｏｕ ｔ）の手順 １．全ての可能手から乱数で手選ぶ ２．自爆する手？ ( アタリに突っ込む手 ) 中手は OK セキ？ 確率を下げて別の手を選びなおす ３．着手 ４．可能な手の確率表を更新 ５．１．に戻る

31 可能な手の確率表更新（パター ン） 3x3 のパターンの更新 今打った手の周囲 確率を上げる 1 手前の相手の手の周囲 確率を下げる

32 可能な手の確率表更新（囲碁知 識） 今打った石が 1 手で取れるか？ 今打った石の修正の敵石がダメ 2 で取れるか？ 局面を動かさすに取れるか調べる 自分の石がダメ 1( アタリ ) にされた 逃げる手 ( 確実に逃げれる手のみ ) 自分の石がダメ 2 にされた 周囲のダメ 2 の敵石を取りにいく 自分の石がダメ 3 にされた 周囲のダメ 2 、ダメ 3 の敵石を取りにいく 1 手前がコウなら埋める 2 手前がコウならコウを取り返す 三目中手の形が出来たら中手を打つ などなど

33 可能な手の確率表更新（その他） UCT で黒 A と打ったときの最善手が白 B 、の場 合、 playout の中で 黒 A と打った場合、白 B と打つ確 率を上げる。 元々死んでいる石が次に生きよう、とした場 合に殺す手の確率を上げる。（Ａと打たれた らＢと打て、という規則を事前に調べておく ） 黒にここに打たれた ら 白はここに（黒は死んでい る）

34 Ｐｌａｙｏｕｔに行く前の処理 今打った手で死んだ石は動かないように ( 死石のダメに打つ確率を下げる ) 今打った手が死石が動く手なら、ちゃんと殺 す手の確率を 1000 倍に（地平線効果対策） セキの場合は自爆しないように確率を 0 に セキ。黒も白も生きてい る 水色には黒も白も打たないよ うに

35 ＡＭＡＦ（Ａｌｌ Ｍｏｖｅｓ Ａｓ Ｆｉｒｓｔ） １ 手の評価速度を速くする工夫 (All Moves As First 、 AMAF ） 仮に黒 D5 白 E7 黒 E6 ・・・と playout で打った場合に、最初 の黒 D5 と黒 E6 の順番が仮に変わっても結果は一緒だろう。 だから黒 D5 と打って勝ったのなら、黒 E6 と打っても勝った 、として 計算してしまおう、という手法です。これを拡張してもし 黒が 勝った場合、黒が打ったすべての手を「最初に打たれた」 と仮定して全部更新してしまおう、という非常に乱暴な手 法です。 9 路なら半分の 50 手ぐらいが 1 回の playout が更新できるので 50 倍くらい手の評価速度が上がります。

36 ＡＭＡＦ（Ａｌｌ Ｍｏｖｅｓ Ａｓ Ｆｉｒｓｔ） ２ 実際は各手ごとに、「通常の UCB の値」と「 AMAF での値 」の 2 つを持ち、下の用にミックスさせて一番値が大きい 手を選びます。 ucb_value = child->GetUcbValue(); // 通常の評価 amaf_value = child->GetAmafValue(); // AMAF での評価 beta = sqrt(K / (3 * node->visits + K)); // K=100, ミックス定数 ucb_amaf = beta * amaf_value + (1 - beta) * ucb_value; 探索回数が少ないうちは AMAF の評価を重視するように。 Rave （ Rapid Action Value Estimate ）も同じ意味で使われて います

37 メモリの節約１ z 基本はまだ一度も探索したことのない局 面で 1 回 playout を行う。 z 既に 1 回でも playout を行った局面ではそ こで可能な手をどれか選び、その手に対 して playout を行う z この方法だとメモリを非常に食う

38 メモリの節約２ zCrazyStone ではある手に対して 81 回 playout を行った後に、初めて次の局面に 移り、そこで手を選ぶ。 z9 路では 81 回、 19 路では 361 回。 y メモリは少なくて済む zMoGo は 1 回でも playout を行ったら、次の 局面に移り手を選ぶ。 z どちらが良いかは不明。

39 playout を増やしたときの勝率 GnuGo 相手に 9 路盤で

40 時間をかけると強くなる？ z レーティング（強さを点数化） y100 点で 1 段差 y100 点上がると勝率は 0.64 上昇 z2 倍の思考時間を使うとレーティングは y 将棋 63 点上昇（将棋プログラム YSS の場合 ) y 囲碁 65 点上昇（囲碁プログラム彩の場合 ) z 囲碁も将棋も同じ程度強くなる y しかし並列化した場合は … ？

41

42 並列化がしやすい z 将棋 yαβ 法は並列効率が悪い z 囲碁 y モンテカルロ法は並列効果がよい！ y マルチコア化が進む現在のＣＰＵ事情を考え ると未来は明るい！

43 並列化の方法 zplayout のみを並列化 z 探索木の情報を一つのハッシュ表に保存 z 読み書きするたびにロック zA-B-C-D-E と読む場合は、局面 A をロック、 アンロック、局面 B をロック・・・と進む z Ｅまで来たらアンロックして playout を行 う

44 Ｖｉｒｔｕａｌ Ｌｏｓｓ １ z 並列の効率を上げるテクニック y 最善応手手順が A-B-C-D-E の時、すべてのス レッドが同時に A-B-C-D-E と読もうとすると ロックが頻発して効率が下がってしまう。 y そこで最初のスレッドは A の手を選んだとき、 この手を「 1 回負けた」として点数を下げる ( 後で戻す ) y 同様に B,C,D,E でも下げる。 yD の手と F の手が同じくらいだった場合は、 2 番目のスレッドは A-B-C-F-G と F の手を選ぶ。

45 Ｖｉｒｔｕａｌ Ｌｏｓｓ ２ y こうして別の手を探索しやすくなることによ りロックの回数が減って効率が上がる。 y シングルスレッドと比べて本質は変わってし まうが影響は小さい。