Go言語将棋の進捗

bleu48.hatenablog.com

 

python-shogiをベースにpythonで作った簡単な探索部を作って簡単な実験をしていたのが2年ほど前。見やすい簡単なプログラムなので改造等は簡単だが,相当遅いので色々と処理速度に不満があった。(もちろん今でも色んな評価関数の試作および学習実験には用いている。)

昨年末にGo言語で自作したのをちょっとずつ改良してきているが,blogの温故知新シリーズと合わせて良い実験材料になってきている。

前回差し手生成を3倍程度高速化したが,探索部全体的にはあまり速くなっていない。

その後,探索分岐で盤情報をディープコピーせずに指し手UnDoする改良を施し(池さんの本にも書かれている高速化),部分的に3割程度更に高速化した。

 

指し手生成の展開時に,あーこれだったら指し手属性ごとに別々に作れるなぁと思ってしまったので取り急ぎ打ち手だけ駒ごとに分解した。

で,またそのついでに王手時の合い駒だけ別に作成するのも簡単に拡張できるなぁと・・・

 

と色々やってると160~180knpsくらいまで出るようになってきた。特に王手時は王手回避ができているかどうかは一手進めて判定していたので合い駒が正確に打てると探索は相当高速化できる。(モロ温故知新ですな。npsじゃなくdepthが伸びる)

ついでに王手時の探索延長を加えた。これは諸刃の剣っぽい。詰み探索速度は抜群に速くなるが,王手の連続で駒を捨てる筋を優先して読むので詰みがありそうでない場合はそちらばかり探索して全然メインの探索が進まないことになる。酷いときには10秒以上かかっても2手先しか読めてないことも。延長し過ぎなのかも。別ルーチン化する前例が多いのはそういうととかとひとり納得してる。

 

また,floodgate対戦中にバグが見つかったので修正したはずだが,まだ微妙なので再確認する案件。Ponder探索中に相手側が先に投了した場合,探索データに前回分のゴミが残って次の新規対局時に非合法手がでることがあった。現在は解決したはずだがmax_movesの次の対戦が開始できてなかったので何か類似の不具合が残っている様子。こういったのはなかなか発覚しないので難しい。

また,現バージョンにしてレーティングが向上する期待をしていたのだが全く向上する気配がないので差し手生成部とかに致命的バグを増やしたのかもしれないなぁと悩み事を増やしている。(特にYSSに全敗である)

 

そんなことより選手権はどうかというとこれがベースでクラスタリングのコアになるのだが実はあんまり速度は要らない。対戦中継用のノートPCでGo言語のクラスタ管理プログラムが動いて,ネット越にそれぞれの探索エンジンに指示を送ることになる。Go言語だと複数のエンジンとのやり取りをリアルタイム化しやすいってのが主目的である。簡単に言うとログ管理に近い案件であるが,最終出力を担当する以上バグがあっては困る。高速応答が要求されるリアルタイムサーバの技術ではあるのだが,保守的に運用したいので上記アップデートは選手権コードには加えない予定だ。

 

まぁ,調子に乗って改造してしまったが,本来の方向ではなくなってしまった。Bitboard実装は128ビットレジスタが扱えてナンボの技術なのでGo言語ではやる気がしない。あ,でもLazy SMPなら簡単に組めそう。そしたらクラスタ間のやつも・・・。

そろそろ暴走を止めなければ死んでしまう(王手回避だけで週末徹夜しといて何を言うw)

選手権でAperyやきふわらべの活躍如何で次はRust弄ってる可能性があるかも。

ーーー

4月14日追記

gbdaitokai.connpass.com

座駆動で本件をネタにしたので記載しとく。

Aoba Zero,Crazy Shogiに勝ったと言ったけど,その後Crazy Shogiの方が相当強くなってるのでたぶんもう勝てない。

で,現地未発表の残りスライドは

・Go言語のよかったところ

  1. goroutineで簡単に多スレッドのプログラムが記述できる
  2. VS Codeプラグインが充実してて楽
  3. C言語の経験が生きる

・Go言語のつらいところ

  1. int int32 int64ですら明示的型変換を要求する
  2. abs min maxのような組み込み関数すら入ってない
  3. 三項演算子が使えない
  4. for分が遅い(C++比)
  5. インラインアセンブラが使えない(C++比)

後者は本件に向いてないので仕方ないって感じかな。

続・指し手生成祭

bleu48.hatenablog.com

 

あまり手を入れる気がなかったのだが,ふと思いついた高速化手法を試してみた。

開発機をCoffee Lakeに移行したのもあって前回200k/s程度であったものが一気に600k/sを超えてきた。たぶん半分くらいはPCの性能のお陰である。

ただ,駒種毎にループを展開したのでソースはずいぶん増えた。指し手部分だけなら5倍くらいかもしれない。

 

探索速度はというと140knps程度にしかなってないのでボトルネックは指し手生成じゃないなと言う感じ。評価関数を差分化してないのはやはり酷いかな。

 

ーーー

追記:

ベンチマーク計測で最近のモバイルCPUは省電力やらターボブーストやらで動作クロックすら安定しないので適していない感じ。世間ではどうしてんのかねぇ?

Leela Zeroな話

以前,Leela Zeroプロジェクトみたいなのを手伝いが居たら立ち上げたいとかヌルいことを言っていた気がする。チェス盤のLCZeroのソースとかをゆるゆる眺めていた程度だ。改変箇所をリストアップした程度で表に出せるようなものは特にない。

 

まぁ,他の人は知らないが私の場合はアイデアが試せれば満足する性質なので以下の件は大吉報である。全面的に協力したいと思う。

 

https://www.apply.computer-shogi.org/wcsc29/appeal/Aoba_Zero/aobazero2019appeal.txt

 

最初にやるべきはOpenCLからCUDAネイティブへの転換かな。

まぁ,私より得意な方がやるべきかもしれない。

 

そういえば先日のCSA例会でも話題にしたが,複数チームへの技術供与はマズいよね。

ライブラリへプルリク送る感じならいいのかもしれない。

YSS戦

wdoor.c.u-tokyo.ac.jp

 

二連勝で喜んでいたら,四連敗である。(うち3局は同じ将棋w)

その後,勝てそうな将棋を千日手

 

そういえば前のバージョンも打ち歩詰めで負けてから打ち歩詰め回避ルーチンを盛り込んだな。実装しないつもりだったけど,そろそろ千日手打開ルーチンが必要か。

 

負け越しだけどいい勝負させて頂いている。

Go言語実装のままどこまで行くだろうか。

検討用のMultiPV実装について

近頃うちの子(スクラッチで作ってるGo言語プログラム)がそこそこまともに動くようになってきたので調子に乗って検討に使えるように改造してみた。

go infinite対応とMultiPV対応である。

shotgunやHefeweizenでも両方非対応である。(一説にはそれでニコ生で使われないという話もあるらしい)

 

go infinite対応は適当でいい。とりあえず,infiniteをbyoyomi 3600000と同値としといた。stopコマンド対応も難しくはない。探索停止ステータスに移行させればいい。

 

で,MultiPVであるが,単純な実装としてはdepth1で最善手定めたあと,それを候補手から外して次善手を求めればいい。あとは欲しい数だけ繰り返してってルーチンを探索深さを進めながら繰り返せば問題ない。やねうら王もこの手順だ。

しかし考えてみるとMultiPVの手数が増えると単純にほぼ比例した探索時間が必要になる。そもそもシングルスレッド探索なのに惜しい気がしたので次のような実装を試みた。

 

メインスレッドは非MultiPVと同じ。最善手探索の反復深化を進める。

次善手以降はメインスレッドが探索した最善手に呼応して探索する。つまりdepth n mutipv 1が終了することにより深さnの最善手が求まった直後にdepth n multipv 2の探索を『別スレッド』でスタートする。

同様にdepth n mutipv mが終了することによりm手までの候補が求まった直後にdepth n multipv m+1の探索をスタートする。

これにより多スレッドの並列化効率を度外視すれば,メインスレッドは非MultiPVと同じ時間で探索深さが進められるし,次善手以降はそれまでの候補手が決定直後から探索がスタートしているため事実上最速で求まる気がする。

シングルスレッド探索を別々に走らせているだけなので,やねうら王などのLazy SMPのサポートスレッドはどうしたらいいかちょっと分からない。

 

一応以上の実装を全探索スレッドをシングルでGo言語実装してみた。初期局面は6秒強でdepth7まで探索可能であるし,その頃にはdepth6 multipv 5くらいまで他候補手も求まっている。

 

問題は出力であるが,depth1のmultipv 1~mその次にdepth2のmultipv 1~mと来るのが従来型であるが,この順が相当狂うことになる。

具体的には将棋所はこの順を期待しているところがあって非常に見づらい。ShogiGUIはこの辺を柔軟にクリアしてくれているようで問題なかった。同じ探索深さにならないが他のエンジンでもアリなんじゃないかと思う。多分並列化効率は上回るんじゃないかな。

    for depth := 1; depth < 15 && !stop; depth++ {
        loop(po, depth, 0)
        go func(depth int) {
            for PVIdx := 1; PVIdx < multipv; PVIdx++ {
                loop(po, depth, PVIdx)
            }
        }(depth)
    }

 出力はmutexでスレッドセーフを保証してる。

  

結構改良したけど,そもそも探索速度が遅いので強くなったのはちょっとだけのようだ。余裕の頓死である。 

 

floodgateでのレーティングでgo_test01が2000くらいでgo_test02が2600くらいなので強くなってた気がしただけのようである。このレート帯は相手がいないだけなのね。 

特に意味はない。それなのになぜか休日の昼間に更にPonderを組み込んでいる。

次はGPSfishくらいが目標か。(そんなことより選手権・・・)

---

3月30日追記

忙しいはずなのについうっかりやねうら王に実験実装してみた。

メインスレッドの探索速度をあまり落とさずMultiPVになるのだが,multipv 2側のスレッドが速い場合と遅い場合があることが分かった。早い場合は同じdepthで追従してレスポンスがあるが,遅い場合はdepth3つ以上取り残される。

遅い場合ってのはLazy SMPの恩恵が薄いんだろうと推察される。(Lazy SMPのスレッド群はメインスレッドに追従しているので)

結果が出ると確かに納得する部分があるのだがあまり美味しい改造と言えない感じがしている。multipv 2側にスレッドを何割か分けてやると良いんだろうが,本末転倒な気がする。

multipv 2以降を他のマシンで探索する疎結合クラスタとか考えだしてどんどん選手権から離れていってたりする年度末。

2六歩の妙

温故知新シリーズに入れていいネタかもしれない。

5月の選手権に向けて無作為な試行錯誤をする最終段階近い。

評価関数の数式をオリジナルのものを数パターン試行しているが,そこそこ使えそうな雰囲気のものが出来てきている。昨年のHefeweizenに勝てないと実戦投入はないだろうけど。

で,やねうら王に組み込んで戦う実験と自作のルーチンで戦う実験を行う。前者は実戦に近く後者は不具合チェックに近い意味がある。探索深さも前者は10を下回ることはないが後者は精々5,6程度である。(pythonで作ってた時は3くらいw)

 

で,ちょっと気づいたことがあった。やねうら王で戦うとそこそこ普通に戦えて技巧に若干負け越す程度の結構良い感じの評価関数モデルが出来たので,自作ルーチンにも同じモデルを組み込んでみた。やねうら王エンジンなら初手のほぼ2六歩なのに,何戦やっても初手7六歩でいつまで経っても2六歩を指さないのである。飛車先を突かず結局中盤に横へ使うレベルであった。

妙だなぁということで持ち時間を増やしてみたら,depth7で初手2六歩を指すようになった。

もしかしたら,初手から10手くらいの部分は教師データを作っていないからかもしれない。いや,depth7と言えば飛車先歩交換で相手の歩が浮くタイミングでこれを評価してやっと2六歩を選択したんだとも考えられる。確認をしたところ実際評価値的にはそういうことだった。

 

このdepth7ってのが結構微妙な数字で以下のような記事もある。

これは後手が角頭を守る3二金を確実に指すのに要するdepthに関する考察である。

merom686.hatenablog.com

 

将棋の世界に三手の読みと言う言葉があるが,七手読まないとこんな初歩的なことが判別できないのである。双方に類似の手筋があればその手順優劣を正確に把握するには14手必要と言うことになる。例えば歩交換保留形との比較には+αの探索が不可欠となる。もちろん評価関数でこういった形が良いと与えておけばその通りに指すのであるがそれは棋理ではないように思う。

 

複数の駒がぶつかるような局面でもdepth20越えてくると結構高精度だなぁと漠然と考えていたが,複数の手順前後などが結構明確に効いてくるケースがあるようだ。実戦での出現率については詳細は未確認であるが,調べると面白いのかもしれない。

 

大雑把に分類すると類似の案件になるのが香落ち問題である。

奨励会では格下の相手と戦うときに香落ちを強いられる。香車の無い側に玉を囲うことは端攻めに不利ということで,長年の歴史で上手は自然と飛車を振るのが常識化しており,奨励会を出てプロになった人間は少なからず振り飛車の経験を積むことになる。

そう,今の将棋ソフトも飛車を振らないと言われながら香落ち局面では振るのである。何手目とかどの手順でってのはソフト依存ではあるが,多くの強豪ソフトは振ることを確認した。香車一枚程度では対人勝率にも影響は微少だろうから,対振りの練習をしたい人はソフト上手の香落ちを試してみると良いかもしれない。

---

追記:

最初に書いた自作ソフト年末年始で作成したGo言語によるものだが,ちょっと高速化を施して初手10秒未満でdepth7に達するようになった。強くなった気がしたのでfloodgateに放流したところ,YSSなる相手に勝利を収めたようである。あのYSSなら祝杯を挙げていいのではないだろうか。

wdoor.c.u-tokyo.ac.jp

コンピュータ将棋のブルーオーシャンについて

コンピュータ将棋界のレジェンドのひとり伊藤英紀さんの記事が出てた。

FPGA実装などされてる文字通り鬼才である。

個人的に面白そうに思っているがハードルが高いイメージのせいか実装を確認することはまだできていない。

リンク先には難しい話はないのでpdfは熟読されると良い。

 

  

ここで,クラスタリングブルーオーシャン戦略であると書かれており,つい先日のミーティングを思い出した。

今年は但馬先生を助っ人にコンピュータ将棋チームを編成したのだが,主な理由に相談相手というのがある。実のところ私は一昨年始めたばかりで周辺の知識・情報に疎い部分が否めない。但馬先生は偶然にも開発者に近いところに長く居られたのでその辺の情報通であり専門性も近い。

具体的に相談に行くと「○○のグループが何年前にやってたような・・・」「似たアイデアはあって結構やりつくされてるんじゃないかな」「それ出来たらジャーナルペーパーだね」など実のところ否定的なコメントが多いのだが,これが丁度ありがたい。経験が浅い私などは甘く見てる部分が多く,様々なアイデアを夢見がちである。まぁ,古いアイデアの組み合わせなども効果があったりする可能性もあるので否定的意見を真に受けるとも限らないが,情報通のコメントは信頼性が高い。

そこで,「私にはコンピュータ将棋はブルーオーシャンに見えたんですけどねぇ。」ってのがあったのだが結構意見が食い違って面白い。

 

そうなのですよ。私もクラスタリングに注力して伊藤さんと同じようなブルーオーシャン戦略だったのですよ。(このネタあちこちでつかってるけど,このブログは初出かな)

ただ,使い方がPonder特化でシンプルな設計だったのでコードを出すほどでもないかと言う感じ。そもそもさほど勝つ気で行ってないのでねぇ。

まぁ,伊藤さんの言葉を借りると「趣味で好き勝手なことをやる個人」です。スポンサーとか欲しいけど変な縛りがあるなら断る感じですねぇ。分からん人には伝わらんでしょうけど。

 

まぁ,策として仕方ないのは手持ちに古いPCがたくさんあるってくらいなので貧乏クラスタでもしないと勝負にならんですよね。(週末にコーヒーブレイクなどしつつ)