昔の将棋ソフトは何故あんなに遅かったのですか?

なんとかちゃんねるに、ちょっと気になる書き込みがあったので引用して説明します。

このなかでは、意外にも、402が正解に一番近いです。
現代でも探索を途中で打ち切るのはとても難しいのです。

探索では普通、反復深化法で探索深さを徐々に深くして行きます。
これを(反復深化の)iterationと呼びます。

iterationの途中で中断した場合、得られる結果というのはどこまで利用できるのでしょうか。これが、実はうまく利用するのはとても難しいのです。

前回のiterationのベストのスコアの指し手を使っておくということはもちろん出来ます。しかしそれだと、今回のiteration、途中までやった分、まるまる無駄になります。ただでさえ遅いのに、そんなことはしたくありません。それなら、iterationのキリのいいところまでやるべきです。

また、当時のCPUは8bitマイコンとかでCPUクロックは4MHzとかしかなく、また探索ノード数は16bitには収まらないため32bitで持つ必要があり、そのためには32bit整数のインクリメントが必要になるわけですが、16bitレジスタ2回にわけて足すか、何かしないといけなくて7命令ぐらい必要となりました。

Z80のコードで書くとこんな感じだったと思います。(30年ぐらい前のことなのでよく覚えてませんが…)

ただでさえ遅いCPUなのでこんな足し算すらしたくないのです。まして、一定のノード数に達したら中断するためには、この32bitの値と値との比較をしないといけなくなります。考えただけで気が遠くなりそうです。

また、探索のiterationの最後のやりかけの分が丸々無駄になるのが許せませんでした。なので、当時において探索をノード数で打ち切るソフトなど一つもなかったと思います。(逆アセンブルして確認したわけではありませんが)

ソフトによっては反復深化すらしていませんでした。反復深化は置換表があって初めて威力を発揮するわけですが、当時の貧弱なメモリ環境では置換表自体を十分に確保できなかったからです。

また、反復深化が威力を発揮するのは、depthが深くなってからで、当時はdepth3ぐらいが精一杯のところでしたから、反復深化を用いていないソフトが結構あったのも仕方ない意味もあります。

そんなわけでして、単にUIで指定された思考レベルの残り深さでsearch関数を呼び出すだけというプログラムになっていることもしばしば…。

そしてRootで最高のスコアを返した指し手をそのまま指すという作りになっていました。具体的にソースコードで示すと次のようになります。

なんと思考部本体、C++のコードだと20行ほどしかありません。(当時はアセンブラなので行数はもっともっと長かったですけども) まあ、この探索部に比べると、指し手生成のほうがはるかに大変なわけですね。

笑っちゃうようなコードですね。このコードで探索の途中打ち切りを入れるでしょうか?入れれないですね。反復深化ですらありませんしね。

そんなわけでして当時には一定数のノードで探索を打ち切るというようなソフトは皆無だったと思いますよ。当時にはそういう技術自体がなかったと言っても過言ではないと思います。

昔の将棋ソフトは何故あんなに遅かったのですか?」への7件のフィードバック

  1. さすがにαβは使っていたと思いますが…
    疑似コードはMinMaxになってますよ?

  2. 昔森田和郎さんに話を伺ったときは、今のような深さ優先ではなく幅優先(横型探索とおっしゃっていました)でやられていましたね。
    ですので評価関数の出来が重要だったようです。
    その分メモリを大量に使うため、大変だったようですが…

    • 森田さんは当時、いまのPonanzaのような状態だったので、森田さん基準で語ると当時の平均像からはかけ離れる気もしますが、幅優先でされていたのは、そういえば当時月刊アスキーかベーマガ(マイコンベーシックマガジン)かの記事で拝見した覚えが。

      幅優先にしていたのは深さ優先にしても置換表がメモリが足りなくて使えないから、それなら評価関数の精度を少しでも上げて、有望そうな指し手だけを細く深く(と言っても5手ぐらい)読む、みたいな方針なんだろうなと思います。現代の探索でもPVとnonPVとにわけてPVでは結構深くまで読みますが、それと似た発想なんでしょうね。

      まあしかし、そんなことをしていたのは、森田さんぐらいで、他の人は置換表も何もなしに本記事のような縦型探索のコード書いてたように思います。

    • >森田さんは当時、いまのPonanzaのような状態だったので、、、

      一日も早く
      Ponanzaは当時、いまのやねうら王のような状態だったので、、、
      というような状況が訪れますように、、、。

  3. さて
    http://d.hatena.ne.jp/yaneurao/20141122
    によれば
    >(森田将棋)100万年と言うと、探索できる局面数は、864T(テラ)局面(864000000000000局面)である。

    そして
    https://twitter.com/yaneuraou/status/678041866726596610?ref_src=twsrc%5Etfw
    によれば
    > perft 10 nodes = 328508718203382 (=328T)

    そうすると森田将棋が100万年探索し続けると10手先まで読みきってしまう。
    でも、それでは将棋になりませんので、自分の手番では8手先(depth 8)まで読んで終了とします。
    この時のnodesは
    http://qiita.com/ak11/items/8bd5f2bb0f5b014143c8
    によれば
    > perft 8 nodes = 416062133009 (=0.416T)
    これであれば2000回ほどの手番探索ができます。

    そうして時折9手先まで読む。(depth 9)
    https://twitter.com/yaneuraou/status/676283049693216770?ref_src=twsrc%5Etfw
    > perft 9 nodes = 11661472222632 (=11.7T)
    ちなみにすべての手番を9手先まで読むと73手までしか読めず、146手時間切れで負けます。

    まあそういう訳で、そこそこつおい森田将棋の誕生となる訳でありました。
    さすがはやねさん、ちゃんと読んでおられましたね。

  4. 前提の一文、提示し忘れました。

    >昔森田さんに話を伺ったときは、・・・(幅優先)横型探索とおっしゃっていました。・・・

samurai へ返信する コメントをキャンセル

メールアドレスが公開されることはありません。 が付いている欄は必須項目です