一般に二人零和完全情報ゲームの探索では、minimax法と比べαβカット法を用いた方が探索効率が良い(悪くなることはない)。各ノードで最善手から読むことで「探索量が平方根程度になる」と言われているが、ここにはちょっとした落とし穴がある。
そもそも最善手から読めるのだったら探索なんかしない(笑)。それは冗談として、将棋のルールに依存した問題がある。
将棋は敵の駒を取った時、その駒を後で使うことができるため、一気に合法手の幅が増えることになる。従って、敵駒を取る手が最善手の時、その先の自手番ノードでは探索幅が広がるために探索量が増える可能性があるわけだ(これは将棋固有の現象でチェスでは起きない)。このことから、不必要に「敵駒を取る手」を読むと、探索効率は悪くなる可能性があることになる。
余談だが、αβカット法を用いた時の探索量は、あくまで２手以上深く読む場合にminimax法より効率が良くなるのであって、１手先の先読みでは何ら変わらない。
minimax法の探索量をwd（wは幅、dは深さ）とすれば、αβカット法が最も効率よく働いた場合の探索量は、√w(d+1)程度[*1]と考えるのが妥当だと思うのだが、将棋の場合、wの変化が非常に激しいので、この式を鵜呑みにするのも問題になりそうだ。
[*1] コンピュータ将棋の進歩３のp.28に「深さ固定のαβ法によって探索される局面の数はn=2×wd/2」とあるが、これは明らかに変だ。この式だとd=1の時、n=２×√wになってしまう。正しくはn=wだからだ。
そもそも最善手から読めるのだったら探索なんかしない(笑)。それは冗談として、将棋のルールに依存した問題がある。
将棋は敵の駒を取った時、その駒を後で使うことができるため、一気に合法手の幅が増えることになる。従って、敵駒を取る手が最善手の時、その先の自手番ノードでは探索幅が広がるために探索量が増える可能性があるわけだ(これは将棋固有の現象でチェスでは起きない)。このことから、不必要に「敵駒を取る手」を読むと、探索効率は悪くなる可能性があることになる。
余談だが、αβカット法を用いた時の探索量は、あくまで２手以上深く読む場合にminimax法より効率が良くなるのであって、１手先の先読みでは何ら変わらない。
minimax法の探索量をwd（wは幅、dは深さ）とすれば、αβカット法が最も効率よく働いた場合の探索量は、√w(d+1)程度[*1]と考えるのが妥当だと思うのだが、将棋の場合、wの変化が非常に激しいので、この式を鵜呑みにするのも問題になりそうだ。
[*1] コンピュータ将棋の進歩３のp.28に「深さ固定のαβ法によって探索される局面の数はn=2×wd/2」とあるが、これは明らかに変だ。この式だとd=1の時、n=２×√wになってしまう。正しくはn=wだからだ。