コンピュータ将棋協会blog

少し前にFPGAで将棋プログラムを作ってみるブログにて、たらいまわし関数が採り上げられていました。最近ときどき話題にのぼるたらいまわし関数ですが、激指のY山さんのような並列処理のテストよりも、関数型言語による遅延評価やラムダ式の説明などで見かけることが多そうです。ブログ記事でもLispの話は出てきますけれど。

たらいまわし関数に遅延評価(lazy evaluation)を適用すると、

if ( x <= y ) return y;
return tarai(tarai(x-1,y,z), tarai(y-1,z,x), tarai(z-1,x,y));

x <= yのときは、zの値にかかわらず関数の値が決まるので、実はzの計算は省略することができます。このような展開がありうることを見越して、真にその値が必要になるまでzの計算を遅らせることで、できるだけ省いてしまおう、というのが遅延評価の考え方です。遅延評価型のたらいまわし関数の場合、tarai(10,0,0)は31回、tarai(10,5,0)は76回の呼び出しで済みます（たぶん）。だからこそLispは早いわけです。

実はこのテクニック、ゲームプログラミングの世界では大昔から愛用されています。ゲームプログラミングの経験がない方のためにおおざっぱに説明すると、アルファベータ枝刈りとは、早いうちにできるだけ良さそうな手を読んでおくことで、後から読んだ手の読みを「前に読んだ手より良くならない」ことがわかった時点で早々に見切り、探索の無駄を省くアルゴリズムです。つまり、あまり良さそうでない手の評価を遅延させることで速くなっているわけです。

そしてマルチコア時代の今、効率化のために演算順序を大きく変えてしまっていることによる課題の克服が、ゲームプログラムを並列化する際の最大の壁となっています。 複数のCPUコアのそれぞれに指し手の探索を割り当てたとき、あるコアの読みの結果によって他のコアに割り当てた手が枝刈りの対象になってしまうと、その手を読んだのは無駄だった、ということになり、その分コア数比例よりも大きく劣る性能になってしまいます。このような状況を防ぐのは意外に難しく、かのディープ・ブルーも実はかなり非効率な探索を行っていたのだそうです。

これは遅延評価一般に通ずる課題のはずで、ゲームプログラマが時代を先取りして取り組んでいるといえます。今後、関数型言語などの理論的な枠組による解決をはかるか、逆にゲームプログラミングから計算機理論へのフィードバックができるのか、コンピュータ将棋開発者の皆さんにはブログをはじめ各方面で大いに語っていただきたいのですが、いかがでしょう？