囲碁プログラム 彩の仕組み 山下 宏 2008年9月4日 FIT2008.

Presentation on theme: "囲碁プログラム 彩の仕組み 山下 宏 2008年9月4日 FIT2008."— Presentation transcript:

1 囲碁プログラム 彩の仕組み 山下 宏 2008年9月4日 FIT2008

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

3 モンテカルロ法の仕組み １．乱数で黒石、白石を交互に置く ２．打つ場所がなくなったら終了 ３．点数を計算する
４．１. － ３. を何度も繰り返す （実際のサンプルを表示）

4 シンプルな評価関数 人間の知識が少ない 人間の棋譜から特長を学習 大量の単純な計算を繰り返すことで正確な評価が可能 泥臭い作業は不要！
好形、悪形の認識 相手の直前の手からの距離 大量の単純な計算を繰り返すことで正確な評価が可能 コンピュータらしい方法

5 パターンを利用して乱数を賢くする ３ｘ３のパターンを学習 人間の棋譜から統計を取る 着手確率を求める 高確率 低確率

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

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

8 局面評価の結果 単純な乱数 パターンを利用 黒いほど黒の陣地になりやすい 白いほど白の陣地になりやすい

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

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

11 19路盤での候補手の選択方法 3x3のパターン 盤の端からの距離での確率 直前の相手の手からの距離 2手前の自分の手との距離
連の死活探索の結果 「死んだ」石が動き出す確率を極端に下げる 上位20手程度だけを探索

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

13

14 並列化がしやすい 将棋 αβ法は並列効率が悪い 囲碁 モンテカルロ法は並列効果がよい！

15 将棋よりも囲碁も方が先に？！ モンテカルロ法が本格的になって１年で９路でプロに近いレベルに ２年でプロに１９路で８子で勝利
８コアで。コア数が４倍になれば１子減る？ 将棋は2010年に名人に勝つ？予想 このペースで進むなら将棋よりも先に囲碁の方が名人に勝ってしまうかも