将棋プログラム「YSS」について

コンピュータ囲碁の仕組み
~ 将棋との違い ~
山下 宏
2014年6月21日
歌舞伎座.tech#4
私について
電王戦で豊島さんとYSSで対戦しました。
将棋だけでなく囲碁も作っています。
コンピュータ囲碁の大会(UEC杯、2014年3月
開催、全16チーム)
1位 Zen
(天頂の囲碁) 日本
2位 CrazyStone (最強の囲碁) フランス
3位 Aya
→ 私のプログラム
世界トップクラスではないが、そこそこ上位。
というわけで囲碁のお話です。
将棋の局面評価
局面を直接数値に変換
+286
囲碁の局面評価
将棋と同じく直接変換
黒の13目勝ち
2006年まではこの手法だった
コンピュータの棋力の推移
2006年に囲碁は何が起こったか?
モンテカルロ法を利用した囲碁ソフトが登場
モンテカルロ法とは?
乱数を使って数値計算を行う手法
何度も繰り返すことで正解に近づく
円周率(π)の計算など
モンテカルロ法を使った囲碁の仕組み
1.乱数で黒石、白石を交互に置く
2.打つ場所がなくなったら終了
3.点数を計算する
4.1. - 3. を何度も繰り返す
(実際のサンプルを表示)
モンテカルロ法での局面評価
乱数で最後まで打ってみる
黒の45目勝ち
1000回繰り返すと675回黒が勝つ
9路でのシミュレーション
初期局面
30手目
終局図
19路でも基本は同じ
初期局面
100手目
終局図
シミュレーションの精度を上げる
囲碁知識を利用
アタリを逃げる、石を取る
直前の相手の手の近くに打つ
石のパターン(3x3など)
プロの棋譜から着手確率を調べる
高確率
低確率
アタリ
黒石の着手確率
数値が大きいほど着手確率が高い
パターンを利用したサンプル
サンプルを再生
単純乱数(上)と囲碁っぽい乱数
単純乱数(上)は途中
図がひどい。最後はど
ちらも同じ感じ
シミュレーションが強さを決める
1手に10000回のシミュレーション
純粋乱数
・・・ 15級
囲碁知識を利用 ・・・ 2段
シミュレーション = 評価関数
将棋 ・・・ 評価関数の正確さ
囲碁 ・・・ シミュレーションの正確さ
将棋の木探索
深さ1、2、3と順番に深く読んでいく
囲碁の木探索
開始局面から最終局面へ、を何度も繰り返す
将棋と囲碁の手の選択(木探索)
将棋
平均可能手数、80手(最大593手)
すべての可能な手を読む
見込みのない手は浅い読みで打ち切り
囲碁
平均可能手数、250手(最大361手)
木探索では上位30手程度しか調べない
読みぬけの危険あり
モンテカルロ法+探索は応用範囲
が広い
ルールだけの実装で評価関数を作れる
囲碁以外でも
アマゾン、Lines of Action、さめがめ
多人数ゲームでも
カタンの開発者たち、ハーツ
リアルタイムゲームでも有効
Ms. Pac-Man
Ms. Pac-Man
一番高得点になる行動
を選ぶ
知識ベースのソフトを破
り最高得点を取得
現在のコンピュータ囲碁の棋力
アマチュアの県代表レベル
98%以上のアマチュアはもう勝てない
プロとは4子でいい勝負
将棋だと飛香落ち程度に相当
将棋に比べて10年遅れている感じ
まとめ
囲碁はモンテカルロ法で壁を超えた。
将棋も囲碁もプロ(人間のエキスパート)の手を
真似することで強くなった。
意味は分からずとも上級者の真似をするのは大事
将棋は全幅探索。囲碁は選択探索。
モンテカルロ法+木探索は応用範囲が広い
ゲームによって向き不向きがある
将棋では初段程度でうまくいってない
ご静聴ありがとうございました