Qhapaqの技術文書

Size: px

Start display at page:

Download "Qhapaqの技術文書"

あいとはまもり
9 years ago
Views:

1 Qhapaqの技術文書猿猿真似からはじめる素敵なコンピュータ将棋ライフ Sawada Ryoto (May, 2016) Who is Qhapaq かぱっくと読みます aperyチルドレンの一人です Qhapaq とは偉大なものを指すケチュア語で本作が多くの巨人の肩の上に立った作品であることを示しています大樹の枝への勝率は55 程度 WCSC 2016の順位は13位なぜかGPSと激指に大金星をあげました今回はQhapaqの改造の中でも特に効果があったものを紹介します失敗した実験にも意味はあるのですがあまりに雑多になったので今回は断念写真は例のあれです

本作が多くの巨人の肩の上に立った作品であることを示しています大樹の枝への勝率は55 程度 WCSC 2016の順位は13位

2 前書コンピュータ将棋の能力値解説１評価関数探索手生成並列化定跡大樹の枝はこんな感じかな評価関数最も大事な項目駒の並びから局面の有利/不利を判断します Ponanzaが絶対王者なのは評価関数の質が極めて高いからと言われています長らく玉を含む三つの駒の並び KPP が使われていましたがそろそろ革命の予感探索幾らコンピュータでも全ての合法手を検討していては計算資源が足りません飛車をタダ捨てする手のような駄目な手は早く見限る枝刈ように色々な工夫がされています

高いからと言われています長らく玉を含む三つの駒の並び KPP が使われていましたがそろそろ革命の予感探索

3 前書コンピュータ将棋の能力値解説２評価関数探索並列化手生成高速化全般合法手や効きの生成静的評価関数の呼び出しなどが早いと NPSが高いAIが作れます定跡序盤の変化を予め覚えておくことで持ち時間を節約するとともに相手を研究手に誘おうとします人間と同じですね手生成定跡大樹の枝はこんな感じかな並列化複数のコンピュータを使って検討を分業することでAIを強くします人間と同様チームワークが悪いと強くなりません

時間を節約するとともに相手を研究手に誘おうとします人間と同じですね手生成定跡大樹の枝はこんな感じ

4 前書どうやって能力値を上げるか１評価関数探索手生成並列化定跡大樹の枝はこんな感じかな評価関数プロ棋士やコンピュータの棋譜を教師とし KPPなどを調節します計算量がとんでもなく多いためドケチには辛い問題です探索枝刈のパラメータを探索したり新しい枝刈のルールを考えたりします新参者は普通 Stockfishという聖書を読むことから始めますやねうらお氏の記事を活用すると良いと思います 5%85%A8%E8%A7%A3%E6%9E%90/

枝刈のパラメータを探索したり新しい枝刈のルールを考えたりします新参者は普通 Stockfishという聖書を読むことから始めます

5 前書どうやって能力値を上げるか２評価関数探索並列化手生成詳細はやねうらお氏のブログ参照二度目 NPSの上昇は確実な強化に繋がりますが高い技術レベルがないと改良は難しいです定跡自己対戦の棋譜などから良さそうな変化をピックします WCSC2016では読み太が定跡を上手く活用していた印象です手生成定跡大樹の枝はこんな感じかな並列化チェスから輸入することが多いようです lazy SMPは実装できればレートが100前後上がるようで報われやすい分野ですが十分な並列数が必要なのでドケチには辛い

ピックします WCSC2016では読み太が定跡を上手く活用していた印象です手生成定跡大樹の枝はこんな感じかな並列化

6 Qhapaqの挑戦１探索パラメータの調整評価関数局面の検討を打ち切る理由は沢山あります今の最適手より悪い変化は読まない αβ枝刈パスより悪い手は読まない Nullmove pruning 飛車をタダで渡すようでは駄目だろう深く読むほど悪くなる局面は駄目そうだ浅く読んで駄目そうな局面は駄目そうだ今回は数あるパラメータの中でも勝率に響きやすいと噂のFutility marginを調整ある局面から数手先の局面の評価値の予測値が既に見つけている変化より悪い場合探索を打ち切る探索手生成並列化定跡

深く読むほど悪くなる局面は駄目そうだ浅く読んで駄目そうな局面は駄目そうだ今回は数あるパラメータの中でも勝率に響きやすいと

7 如何にして枝刈を最適化するか Blunderの方法幾つかの局面に対して枝刈できたのにしなかった数と枝刈できないのにした数を測定し両者を減らすように調整していきます長所過学習特定の相手に特化した結果総合的に弱くなるが起こりにくい短所実装が辛い計算時間がかかる多分 Qhapaqの方法改造前大樹の枝との勝率を比べ一番勝率が高いのが一番いいパラメータと考えます長所実装が楽計算時間も減らせる短所ノイズが出る改造前の相手に特化した過学習パラメータを生み出しかねない

pdf 幾つかの局面に対して枝刈できたのにしなかった数と枝刈できないのにした数を測定し両者を減らすように調整していきます長所過学習

8 早速勝率の最適化を試みるが想定される対局回数がとんでもないことに Futility marginのデフォルトの値傾きと高さを指定するとしたら二つのパラメータの最適化各パラメータ10通り試すとしても100通りの組み合わせが必要各組合せ1000試合やるとして100000試合必要とてもつらい

9 もう少し楽をしたい探索パラメータに対して勝率は緩やかに変わると仮定パラメータ２探索パラメータに対する勝率の等高線グラフ予想図最適解に近づくほど緩やかに勝率は上昇していくはず 55% 50% 45% 勝率が低かった点の近くは探さなくていいのではなかろうかパラメータ１

10 進化戦略による最適化口コミで美味しいお店を探すのと大体同じパラメータ２パラメータ２パラメータ１ ① 適当に観測者(20-30個)をばらまくガウス分布少ない対局数(10-20局)で勝率を測定パラメータ１ ② 勝率の高い観測者を残し他を消す

11 進化戦略による最適化口コミで美味しいお店を探すのと大体同じパラメータ２パラメータ２パラメータ１パラメータ１ ③ 生き残った点の近くに次の観測者を置く平均分散を取り再びガウス分布 ④ 最終的に最適解近辺に観測者が集まる

12 カーネルを用いた関数補完食ログの星の平均値でランキングするのと大体同じパラメータ２ W K ( x, y ) f ( x, y ), K ( x, y ) i i i i i K i ( x, y ) exp( ( x xi ) 2 ( y yi ) 2 ) パラメータ１進化戦略を何度も行いデータ数を増やす f(x,y) : 勝率 i : 各観測者 Ki カーネル関数 Wi 各観測者の勝率 f(x,y)の最大値近辺に最適値があるはず二次元程度なら大体一日弱で最適値のあたりがつく

13 Qhapaqの挑戦１終盤の枝刈調整勝てそうなとき負けそうなときFutility marginをどう変調すれば逆転を防げる/狙えるか if (abs(score) < ScoreMateInMaxPly){ int ts=score * 100 / PawnScore; int tempdf1; if(abs(ts)>1000){return;} //1000以上のscore差についてはfutを変えない if(ts<0){ tempdf1=ts*futd1m; }else{ tempdf1=ts*futd1p; } for (int d = 1; d < 16; ++d) { for (int mc = 0; mc < 64; ++mc){ FutilityMargins[d][mc] = static_cast<score>((futc+tempdf1) * static_cast<int>(log(static_cast<double>(d*d)/2) / log(2.0) ) - 6* mc + 45); } } } 評価値に応じたmarginの変化自分が有利な場合も不利な場合も枝刈を減らした方が強くなるようです将棋指しの皆さま的にはどうです 3次元系で最適化したところ 1000試合で53%程度勝ち越すようになりました

$++d) { for (int mc = 0; mc < 64; ++mc){ FutilityMargins[d][mc] = static_cast<score>((futc+tempdf1) *$

14 Qhapaqの挑戦２評価関数の変調評価関数コンピュータに受けの棋風攻めの棋風を加えられないか零から作るのは無理でも評価関数の中で受け攻めに深く関係する値を書き換えることで棋風を変調できないだろうか探索手生成並列化定跡

15 進化戦略を用いた最適化２評価関数同じ特徴を持つ評価関数を抽出纏めて変調することでウン万次元の最適化を数次元にまで落とし込む今回纏めて調整したパラメータ KPPのうち PPが自分の駒のもの玉の安全さに相当 KPPのうち PPが相手の駒のもの玉の危険さに相当玉の安全さの価値をx倍危険さの価値をy倍と一括で変換+最適化勝率が約55% 1300試合

16 まとめゲームノートPCによる低予算な開発を目指しました Aperyとの主な違い局面に応じた枝刈パラメータの調整特徴量を抽出することによる超低次元な評価関数の調整使った手法自己対戦による勝率の最適化進化戦略による高速な最適化 Qhapaqの戦績大樹の枝に55 ぐらいの確率で勝てる 0.1秒将棋で1300試合一次予選突破 5位たこっとさんに256手目に詰められました二次予選敗退 13位激指さんとGPSさんに勝つという謎の大金星

自己対戦による勝率の最適化進化戦略による高速な最適化 Qhapaqの戦績大樹の枝に55

17 たぬきのもりと比較しないって約束したじゃないですかたぬきのもりの最適化手法との違いは発想は同じたぬきのもりの手法がQhapaqの上位互換ですorz パラメータ２一番の違いは点の生成アルゴリズムですガウス分布だと左図のように複数峰がある関数の最適化が難しいですが Tree-structured Parzen Estimatorはこういった形に強いようです詳細は勉強中パラメータ１敗戦の弁単峰の低次元系なら違いはないだろうし三次元系以上を計算しきるリソースはそもそもなかったので一度は自分でコードを作ってみるという勉学的な効用を優先したのですきっと

pref=2&pli=1 一番の違いは点の生成アルゴリズムですガウス分布だと左図のように複数峰がある関数の最適化が難しいですが Tree-structured Parzen

18 Qhapaqの今後 Hyperopt + 抽出した評価関数の最適化上手く行けば貧乏開発者が評価関数を弄れる時代到来か dynamicなfutility marginの導入各種ツールの展開自己対戦ツールの公開時間があったら進化戦略自己対戦勝率最適化ツールの公開根性が足りたら各種お勉強 apery やねうら王技巧本当に出るんをメタった定跡作成手法を探してみたりやねうら王のコード読んだり Qhapaqちゃんのデザイナーを探したり電王トーナメント出るの出られたらぜひ

自己対戦勝率最適化ツールの公開根性が足りたら各種お勉強 apery やねうら王技巧本当に出るんをメタった定跡作成

19 主に開発者向けの余談評価関数でも枝刈でも強くなったのになんで勝率55%なの評価関数と枝刈パラメータは相関がある様子 Dynamic marginは枝刈を最適化しているとは限りませんがまずまずの品質で枝を刈ってくれるようなので今後はdynamic marginを使った方が良いと思います進化戦略でばら撒いた観測者の数と対戦数ってどうやって決めたの 1ステップが2時間以内に終わるように決めました夜朝で数世代進むように収束に近づくほど点や試合の数を増やした方がよさそうですがどれぐらいがベストかは謎です今後はhyperoptに寝返るつもりなので確かめる予定もないです自己対戦の持ち時間は 1手0.1秒でやっています 1秒や1分も試したかったのですが十分なサンプル勝率55%程度なら1000試合はやるべきですが集まらないと思ったのでやめました apery相手に過学習してる可能性は十二分にあります aperyチルドレンが大会に沢山出るだろうから aperyローカルな対策でいいと考えてましたが次はどうしましょう

収束に近づくほど点や試合の数を増やした方がよさそうですがどれぐらいがベストかは謎です今後はhyperoptに寝返るつもりなので確かめる予定もないです自己対戦の持ち時間は 1手0.

20 旧アピール文書 Qhapaqのアピール文 1. Qhapaqの概要 "Qhapaq"は偉大なを意味するケチュア語です本プロジェクトが偉大な知の巨人の肩に立っていることに由来しています Qhapaqは所謂aperyファミリーのひとつです 2016年1月から開発をはじめ 3月末時点でのapery github上の最新版に対する勝率は55%ぐらいです開発者がドケチであるため今回のプロジェクトの目的はゲームノートPC一つでできる軽量低予算な機械学習の実現となっています現在探索パラメタの高速な最適化手法既存の評価関数を再利用したオンライン学習手法を新規開発中です 2. Qhapaqの手法進化戦略による探索パラメータの高速最適化 stockfishベースの探索には枝刈の閾値を初めとした多くのパラメータが存在します探索パラメータの最適化とは勝率を最大化するパラメータの組み合わせを探すことを意味しておりこれはノイズ付き多次元関数の最適化問題に帰着します本研究では進化戦略を用いることで従来手法に比べ数倍程度に高速な最適化を実現しました探索パラメータを最適化することで一晩程度の探索でレートを35程度上昇させることに成功しました既存の評価関数を再利用したオンライン学習 aperyの評価関数では70000局程度の棋譜を学習していますしかしゲームノートPCで70000局の棋譜を対象に bonanzaメソッドを用いようとすると棋譜の読み込みに30時間強掛かります開発者のPCで800局の読み込みに20分程度掛かっていることから予想そこで評価関数を零から作ることを諦め強豪ソフト/プレイヤーの棋譜を既存の評価関数に追加で学習させるオンライン学習法を開発しています既存の評価関数を初期値に少数の棋譜でbonanzaメソッドを用いると過学習によりレートが著しく落ちるので評価関数の各パラメータが元の値から離れた場合その距離に応じて復元力を働かせるようにしています結果指し手に有意な差教師データに対する一致率で5%程度実際の指し手はさらに異なると思われるを出しながら過学習をによるレート低下を起こさない元のaperyに対して勝率51% ことに成功しました 3. Qhapaqの今後オンライン学習で勝率が殆ど上昇していない原因としては復元力が強すぎるor弱すぎる教師データにした棋譜 ponanza 技巧の2015年の棋譜約800局との相性が悪いそもそも教師データ数が足りていないが考えられますパラメータの調整で強くなるなら良いですが棋譜が沢山必要になるようだと本プロジェクトの目的から外れたものになってしまうのではないかと考えています強いAIを作るのも魅力的ですが振り飛車に特化したAIなど AIに棋風の概念を持たせるような研究も興味深いと考えています最新情報についてはtwitter にてご報告いたします開発者のPC = Intel Corei7-4710MQ 2.50 Ghz メモリ16GB

低予算な機械学習の実現となっています現在探索パラメタの高速な最適化手法既存の評価関数を再利用したオンライン学習手法を新規開発中です 2.

dlshogiアピール文章

dlshogiアピール文章第 28 回世界コンピュータ将棋選手権 dlshogi アピール文章山岡忠夫 2018 年 5 月 1 日更新下線部分は第 5 回将棋電王トーナメントからの差分を示す 1 特徴ディープラーニングを使用指し手を予測する Policy Network 局面の勝率を予測する Value Network 入力特徴にドメイン知識を活用モンテカルロ木探索並列化自己対局による強化学習既存将棋プログラムの自己対局データを使った事前学習