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手までの候補が求まった直後にdepthn 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くらいが目標か。(そんなことより選手権・・・)

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がたくさんあるってくらいなので貧乏クラスタでもしないと勝負にならんですよね。(週末にコーヒーブレイクなどしつつ)

温故知新(4)

意外に続いているシリーズになってる。

今回は割と具体的に手を動かす作業。

  

Java将棋のアルゴリズム―アルゴリズムの強化手法を探る (I・O BOOKS)
 

 

実は買い置いていたのだが全く手に取っていなかった。コンピュータ将棋界のレジェンドのひとりである池さんの著書で一番新しいものを選んだ感じである。

とりあえず,ソースが出版社のサイトにあるので落としてきた。

実は随分久しぶりにJavaを触る。一番遊んだのがBD-JBD-REに書き込んでPS3で動かしていたころで,一番最近は青い本でGroovyをちょっと試したころか。

ということでJDKのインストールからである。

せっかくなので11.0.2ってのが最新らしいので入れてみる。思えば遠くに来たもんだ。

 

ソースを落としてコンパイルをしてみる。クラスパスってなんだっけ?古い記憶が適当すぎるのが分かって愉快なレベルである。

エンコードもShift-JISなのでvscodeが化ける化ける。

で,最近のJavaは色々厳密になってきてるらしくてVectorの型アノテーションJava用語で間違ってたらゴメン)が無いと叱られる。ってことで,TeやらKyokumenやらと型を明記してコンパイルを通す。

CPU対戦がやっとできたのだが,HandHashSeedの配列があふれているらしい。適当に大きくして戦ってみた。コマンドライン入力の対戦とは久しぶりである。

なぜか飛車先の歩をそのまま成らせてくれて勝てた。

CPU対CPUをやったときに非合法手で反則負けをしてたので,もしかしたらどこかに不具合があるのかもしれない。遅いマシンでは発生しなかったのだとしたらHash衝突の可能性もある。

 

本題はここから。

まず見どころは二章,合法手生成。駒の移動先・駒の種類に対して移動可否の配列を定義している。booleanである。Javaだとこういうの速いのかな?

これを筋・段・移動先の三重forループで回して生成している。うちで年末年始で作ったものはmerom686さんのコードを参考にしており似たような雰囲気である。理由は行数が少ないからだ。当然bitboardとかの方が速いだろうが長いのは嫌い。

 

他にもTeやKyokumenなどベタなネーミングのオブジェクトが満載でこれは池さんが初心者を意識して書かれたものと思われる。初期配列などもソース量が増えるにも関わらず初心者向けにベタな記述になっている。

 

六章,高速化のところではいくつかの高速化手法が理由を明記しながら説明されている。具体的な計測例などがあればうれしいが初心者向けではないか。高度な高速化に関しては読者への課題と記載されているがうさぴょん2などには実装されているのであろう。

 

七章,定跡データがバイナリファイルなのがちょっと惜しい。対戦で気になった手順などは手早く編集して対戦に戻りたいのでテキストファイルの方が扱いが良いと思う。まぁ,私がやねうら王ライブラリ勢なんだが

 

八章九章は序盤中盤の評価法。古典的なのでまぁ,そういうのもあるのかと。

十章は枝狩りの話が少し。もう少し高度な話が合っても良いかと思ってしまうが,初心者向け初心者向けと心を落ち着かせる。

十一章TTの話。30bitはやはりぶつかってそうな気がする。

十二章,CSAプロトコルの実装。今はUSIプロトコルを実装して将棋所で管理するのが主流なのでおすすめできない。当時は将棋所がまだ無かったのだろうか。

 

最終章,ここが個人的には一番面白かった。非常に残念だが引用されているサイトなどが現在閲覧不可能なものがあって惜しい。

 

最後にjava.util.Randomなどを駆使してlong(つまり64ビット)にして256Mエントリー与えてみたんだがハッシュ衝突をうまく回避できなかった。残念である。

ディープラーニング用のPCスペックについて

 

pytorchで学習させているんだが,GPUの学習よりモデルに食わせるデータを扱うpythonのコードが時間かかってCPUもGPUもあんまり負荷がかかってない。

敢えて言うと下のケースと同じ。GPUの差が出ないでCPUのシングルスレッド性能だけで学習時間が決まってしまうようなことをしてる。

  

bleu48.hatenablog.com

 

pythonディープラーニングするとき,専用機作るならCPUクロック重視で間違いないだろうね。コア数はまず関係ないね。もちろんGPU用意しない人は多コアで。

もちろん,そうでないケースも多いけどウチではCPUはクロック重視,GPUは搭載メモリ重視って感じかな。

GPUのメモリは足りないと本当に哀しいことになります。

1足す1が2にならない世界

近頃カーネマンにハマっているので認知バイアス関係なんだけど,

非線形なものに対する直感ってのは慣れていないと難しい。

 

ロケットブースターを2倍にしてもロケットの加速度は2倍にならないし,エンジン馬力を2倍にしても車の最高速度は2倍にならない。力学に詳しい人なら前者が少し増えるだけ,後者は√2倍が精々ってのがすぐ思いつくが素人さんはそうはいかない。通常の3倍の移動速度ってものを類似の推進系で作り出すのは非常に困難なものと理解できる。

 

計算機の世界でも20年以上前からクラスタリングは実用化されているし,普及PCでも十数年前からマルチコアが一般的である。アムダールの法則を持ち出すまでもなく,2倍のリソースで2倍の計算速度が得られないことは自明である。

 

また,俗な考え方だが5万円のPCは10万円のPCの半分のパフォーマンスってことは稀だし,20万円のPCは10万円のさらに倍のパフォーマンスを期待できるわけではない。ただ,特例的なソフトウェアの実行においては有効に働く場合が結構ある。要するにそういう設計がなされているということだ。この価格レンジを外れた場合はあまり起こりえない事象なので,所謂PCのコストパフォーマンス層と言える。知識のない人が購入するならこの層にしておけってやつだ。

とはいえ,2倍の計算速度が出る計算機は2倍以上の効果があることが多い。結果が早く得られることにより次の決断を早めることは何よりも有効な場合が多い。たとえばコンピュータ将棋である。

 

”質の悪い評価関数の場合、探索量が2倍になったところでR50~80ぐらいしかあがらないだろうと言われています。逆に質の良い評価関数の場合、R100~150ぐらい上がるのではないかと言われています。”

並列化による棋力の向上について - ひよこ将棋、はじめました。

 

GPS将棋は700台構成ですが、Puella αが700台使えたらどうなるか?GPS将棋は、700台構成で確実に棋力が上がることを示しました。Puella αだと、おそらく200?300程度上がるでしょう。”

現状認識@2013年4月: A級リーグ指し手1号

 

他にも激指の横山先生は32コアの並列で6~7倍の高速化が見込めると発表されていたり,GPS将棋では疎結合クラスタは密結合のクラスタの2倍の台数で同程度の効果が得られると書かれている。

 

1足す1が2にならない世界。密結合32倍のコアで6~7倍と言うのは直感的に少し少ないように思われるが,同時期のGPS将棋では密結合4ノードと疎結合8ノードが同適度で2倍強という発表もあり妥当な数字かと思われる。

 

”NスレッドでやってもN倍の効率アップにはならず、√N倍程度の効率アップにしかならない。実際は、√Nよりは少し効率が良いようだが、ともかく、そういう状況だ。”

将棋ソフトの並列探索は何故難しいのですか? | やねうら王 公式サイト

 

密結合4コアだと1コアの2倍くらいの速度は期待していいくらいのイメージだ。疎結合で立方根だろうか。電気代を考えると1コアで2倍の時間使うのが経済性が良いだろうが対戦では時間は固定リソースである。しかも,これは実装がうまくいった例である。

並列計算には個々の計算同士がうまく通信し合ってこそ有効に働く。上記に書かれたコンピュータ将棋の世界だと共有メモリに置換表という情報を共有することで重複した局面の再探索をしないことで高効率化が図られている。

上記疎結合の700台では立方根の約9倍程度のパフォーマンスは恐らく出ないだろうとの見込みが示されている。これは根本的な情報共有の問題である。

 

ところで,考えてみて欲しい。私も直感的に思った。700台のPCを使って10倍の速度が出ないのはちょっと勿体無いのではないかと。

4コアで2倍ってのももう少し位いや,3倍超えて欲しい気がする。

なんとかならんもんだろうかと考えている。難問である。

 

(要約すると)新しい並行計算の手法を思いついて実装したのだが,あまりうまくいっていない。そんなことより評価関数(