問題は水平線効果

探索の一番の問題は水平線効果で、
これを帰りのバスの中で考えたんですが、
たとえば、将棋なら探索してて「飛車をとられる」ような手痛い手があったとすると、
min的には、相手は飛車をとってくるとみなすから、
当然、その上のmaxでは、それを回避する手を捜そうとする。そうすると、「歩をただでとられる」ような端歩突きをやって、
将来のピンチを逃れようとする。
これが水平線効果の実態と理解していますが、
抽象化して考えると、「ただより良い手を探索してる」だけで、なにも間違ってはいないんだよね。
CPUは数字で損得を考えてるだけなんだから。
ということは、何が問題かというと、
「歩をただで取られて損する」ことと「数手の時間」を交換していることになる。
飛車をとられるより、ただで歩をとられるほうがマシだから。
逆に考えると、時間稼ぎをしないようにすればいいんだけど、
それをCPUに判らせるのは難問なのである。

関連書籍やサイトを読んでも、「完全に解決した理論」はまだ発見されてないようで、
もし発見したら大発見になると思う。

実践的には、「ただで歩をとられるような手を選んだ」ら＝水平線とみなして、もっと探索するとかいうテクニックが解説してあった。
激指は、実現確率を持ち込んで、確率が閾値を下回るまで探索することで緩和しているらしい。
そもそも、何手を読むという考え方が間違ってるわけで、プロ棋士や人間は、「何手を読む」なんて決めて読んでる人はいないと思う。良さそうな手を大丈夫そうなとこまで読むだけで。
CPUの苦し紛れの逃げは、人間にはこっけいだけど、CPUに実装するのは難しいようです。
こうやって、学んだことを実際に書いていくと、本当に理解しているか突き詰めることになっていいかも

昨日の日記はいくつか、すでにリンクを張っていただいてましたが、お礼はまた週末にでも。