コンピュータ囲碁の仕組み ～ 将棋との違い ～

Presentation on theme: "コンピュータ囲碁の仕組み ～ 将棋との違い ～"— Presentation transcript:

1 コンピュータ囲碁の仕組み ～ 将棋との違い ～
コンピュータ囲碁の仕組み ～ 将棋との違い ～ 山下 宏 2014年6月21日 歌舞伎座.tech#4

2 私について 電王戦で豊島さんとYSSで対戦しました。 将棋だけでなく囲碁も作っています。
コンピュータ囲碁の大会(UEC杯、2014年3月開催、全16チーム) 1位 Zen (天頂の囲碁) 日本 2位 CrazyStone (最強の囲碁) フランス 3位 Aya → 私のプログラム 世界トップクラスではないが、そこそこ上位。 というわけで囲碁のお話です。

3 将棋の局面評価 局面を直接数値に変換 ＋２８６

4 囲碁の局面評価 将棋と同じく直接変換 黒の１３目勝ち ２００６年まではこの手法だった

5 コンピュータの棋力の推移

6 ２００６年に囲碁は何が起こったか？ モンテカルロ法を利用した囲碁ソフトが登場

7 モンテカルロ法とは？ 乱数を使って数値計算を行う手法 何度も繰り返すことで正解に近づく 円周率（π）の計算など

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

9 モンテカルロ法での局面評価 乱数で最後まで打ってみる 黒の４５目勝ち 1000回繰り返すと675回黒が勝つ

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

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

12 シミュレーションの精度を上げる 囲碁知識を利用 アタリを逃げる、石を取る 直前の相手の手の近くに打つ 石のパターン（３ｘ３など）
プロの棋譜から着手確率を調べる アタリ 高確率 低確率

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

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

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

16 シミュレーションが強さを決める １手に１００００回のシミュレーション シミュレーション ＝ 評価関数 純粋乱数 ・・・ １５級
純粋乱数 ・・・ １５級 囲碁知識を利用 ・・・ ２段 シミュレーション ＝ 評価関数 将棋 ・・・ 評価関数の正確さ 囲碁 ・・・ シミュレーションの正確さ

17 将棋の木探索 深さ１、２、３と順番に深く読んでいく

18 囲碁の木探索 開始局面から最終局面へ、を何度も繰り返す

19 将棋と囲碁の手の選択（木探索） 将棋 囲碁 平均可能手数、80手（最大593手） すべての可能な手を読む 見込みのない手は浅い読みで打ち切り
平均可能手数、250手（最大361手） 木探索では上位30手程度しか調べない 読みぬけの危険あり

20 モンテカルロ法＋探索は応用範囲が広い ルールだけの実装で評価関数を作れる 囲碁以外でも 多人数ゲームでも リアルタイムゲームでも有効
アマゾン、Lines of Action、さめがめ 多人数ゲームでも カタンの開発者たち、ハーツ リアルタイムゲームでも有効 Ms. Pac-Man

21 Ms. Pac-Man 一番高得点になる行動を選ぶ 知識ベースのソフトを破り最高得点を取得

22 現在のコンピュータ囲碁の棋力 アマチュアの県代表レベル プロとは４子でいい勝負 将棋に比べて１０年遅れている感じ
９８％以上のアマチュアはもう勝てない プロとは４子でいい勝負 将棋だと飛香落ち程度に相当 将棋に比べて１０年遅れている感じ

23 まとめ 囲碁はモンテカルロ法で壁を超えた。 将棋も囲碁もプロ(人間のエキスパート)の手を真似することで強くなった。
意味は分からずとも上級者の真似をするのは大事 将棋は全幅探索。囲碁は選択探索。 モンテカルロ法＋木探索は応用範囲が広い ゲームによって向き不向きがある 将棋では初段程度でうまくいってない

24 ご静聴ありがとうございました