なんとかちゃんねるに、ちょっと気になる書き込みがあったので引用して説明します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
399 名前：名無し名人[] 投稿日：2015/12/15(火) 10:36:35.30 ID:Z1RRPQRq 昔のソフトに一手一時間なんてざらだったがなw 400 名前：名無し名人[sage] 投稿日：2015/12/15(火) 11:00:58.55 ID:tclOT/5A [2/2] 64の羽生将棋も時間無制限にすると鬼のように考えてる 401 名前：名無し名人[sage] 投稿日：2015/12/15(火) 11:37:42.21 ID:CWvkKb7V あの長時間思考って、何を考えてたんだろう。 閾値を読んだノード数で指定して、閾値に達するまでは指さないとか？ 402 名前：名無し名人[sage] 投稿日：2015/12/15(火) 12:28:10.83 ID:xeinW7aI [1/2] 当時は反復深化のiterationで回る回数がそのまま思考レベルだった。 探索ノード数で打ち切るような技術は当時なかった。 412 名前：名無し名人[sage] 投稿日：2015/12/15(火) 22:25:43.41 ID:H3A+yAiR >>402 評価関数呼ばれるたびにカウンタ増やすだけだし出来ないわけないんじゃない |
このなかでは、意外にも、402が正解に一番近いです。
現代でも探索を途中で打ち切るのはとても難しいのです。
探索では普通、反復深化法で探索深さを徐々に深くして行きます。
これを(反復深化の)iterationと呼びます。
iterationの途中で中断した場合、得られる結果というのはどこまで利用できるのでしょうか。これが、実はうまく利用するのはとても難しいのです。
前回のiterationのベストのスコアの指し手を使っておくということはもちろん出来ます。しかしそれだと、今回のiteration、途中までやった分、まるまる無駄になります。ただでさえ遅いのに、そんなことはしたくありません。それなら、iterationのキリのいいところまでやるべきです。
また、当時のCPUは8bitマイコンとかでCPUクロックは4MHzとかしかなく、また探索ノード数は16bitには収まらないため32bitで持つ必要があり、そのためには32bit整数のインクリメントが必要になるわけですが、16bitレジスタ2回にわけて足すか、何かしないといけなくて7命令ぐらい必要となりました。
Z80のコードで書くとこんな感じだったと思います。(30年ぐらい前のことなのでよく覚えてませんが…)
|
1 2 3 4 5 6 7 |
LD HL,(low16) INC HL LD (low16),HL LD DE,(high16) LD HL,0 ADC HL,DE LD (high16),HL |
ただでさえ遅いCPUなのでこんな足し算すらしたくないのです。まして、一定のノード数に達したら中断するためには、この32bitの値と値との比較をしないといけなくなります。考えただけで気が遠くなりそうです。
また、探索のiterationの最後のやりかけの分が丸々無駄になるのが許せませんでした。なので、当時において探索をノード数で打ち切るソフトなど一つもなかったと思います。(逆アセンブルして確認したわけではありませんが)
ソフトによっては反復深化すらしていませんでした。反復深化は置換表があって初めて威力を発揮するわけですが、当時の貧弱なメモリ環境では置換表自体を十分に確保できなかったからです。
また、反復深化が威力を発揮するのは、depthが深くなってからで、当時はdepth3ぐらいが精一杯のところでしたから、反復深化を用いていないソフトが結構あったのも仕方ない意味もあります。
そんなわけでして、単にUIで指定された思考レベルの残り深さでsearch関数を呼び出すだけというプログラムになっていることもしばしば…。
そしてRootで最高のスコアを返した指し手をそのまま指すという作りになっていました。具体的にソースコードで示すと次のようになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Move best_move; // 最終的にこの指し手を選ぶ int16_t search(Value alpha, Value beta, Depth depth) { MovePicker mp; Move m; while(m = mp.next()) // この局面の指し手をひとつずつ { do_move(m); // mで局面を進める score = (depth < 1) ? eval() : -search(-beta,-alpha,depth-1); undo_move(m); // mで局面を戻す if (alpha < score) { // alpha値更新 alpha = score; if (depth == 思考レベル) // root node best_move = m; if (alpha >= beta) break; // beta cut } } return alpha; } |
なんと思考部本体、C++のコードだと20行ほどしかありません。(当時はアセンブラなので行数はもっともっと長かったですけども) まあ、この探索部に比べると、指し手生成のほうがはるかに大変なわけですね。
笑っちゃうようなコードですね。このコードで探索の途中打ち切りを入れるでしょうか？入れれないですね。反復深化ですらありませんしね。
そんなわけでして当時には一定数のノードで探索を打ち切るというようなソフトは皆無だったと思いますよ。当時にはそういう技術自体がなかったと言っても過言ではないと思います。
さすがにαβは使っていたと思いますが…
疑似コードはMinMaxになってますよ？
おお、ほんまや！修正しときました(｀･ω･´)ゞ
昔森田和郎さんに話を伺ったときは、今のような深さ優先ではなく幅優先(横型探索とおっしゃっていました)でやられていましたね。
ですので評価関数の出来が重要だったようです。
その分メモリを大量に使うため、大変だったようですが…
森田さんは当時、いまのPonanzaのような状態だったので、森田さん基準で語ると当時の平均像からはかけ離れる気もしますが、幅優先でされていたのは、そういえば当時月刊アスキーかベーマガ(マイコンベーシックマガジン)かの記事で拝見した覚えが。
幅優先にしていたのは深さ優先にしても置換表がメモリが足りなくて使えないから、それなら評価関数の精度を少しでも上げて、有望そうな指し手だけを細く深く(と言っても5手ぐらい)読む、みたいな方針なんだろうなと思います。現代の探索でもPVとnonPVとにわけてPVでは結構深くまで読みますが、それと似た発想なんでしょうね。
まあしかし、そんなことをしていたのは、森田さんぐらいで、他の人は置換表も何もなしに本記事のような縦型探索のコード書いてたように思います。
＞森田さんは当時、いまのPonanzaのような状態だったので、、、
一日も早く
Ponanzaは当時、いまのやねうら王のような状態だったので、、、
というような状況が訪れますように、、、。
さて
http://d.hatena.ne.jp/yaneurao/20141122
によれば
＞（森田将棋）100万年と言うと、探索できる局面数は、864T(テラ)局面(864000000000000局面)である。
そして
https://twitter.com/yaneuraou/status/678041866726596610?ref_src=twsrc%5Etfw
によれば
> perft 10 nodes = ３２８５０８７１８２０３３８２ （＝３２８T）
そうすると森田将棋が１００万年探索し続けると１０手先まで読みきってしまう。
でも、それでは将棋になりませんので、自分の手番では８手先（depth 8)まで読んで終了とします。
この時のnodesは
http://qiita.com/ak11/items/8bd5f2bb0f5b014143c8
によれば
> perft ８ nodes = ４１６０６２１３３００９ （＝０．４１６T）
これであれば２０００回ほどの手番探索ができます。
そうして時折９手先まで読む。（depth ９）
https://twitter.com/yaneuraou/status/676283049693216770?ref_src=twsrc%5Etfw
> perft ９ nodes = １１６６１４７２２２２６３２ （＝１１．７T）
ちなみにすべての手番を９手先まで読むと７３手までしか読めず、１４６手時間切れで負けます。
まあそういう訳で、そこそこつおい森田将棋の誕生となる訳でありました。
さすがはやねさん、ちゃんと読んでおられましたね。
前提の一文、提示し忘れました。
＞昔森田さんに話を伺ったときは、・・・（幅優先）横型探索とおっしゃっていました。・・・