水平線効果

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

水平線効果(すいへいせんこうか)は探索アルゴリズムの深度を有限とした場合、それ以降の経路をあたかも水平線の向こうのように考慮しないため、長期的に見て問題のある選択をしてしまう問題。

概要[編集]

コンピュータ将棋を例に取り、プログラムがN手先までほぼ全幅探索に近い探索を行うとする。

単純化のためプログラム側にはa,b,cという3つの指し筋があるとし、指し筋aでは自玉がn手先(n<N)で短手数で詰み、指し筋bではm手先(m>N)で長手数で詰み、指し筋cでは当面詰みは発生しないとする。この時の最適解は指し筋cであるが、プログラムはN手先までしか探索しないため、指し筋aは棄却できるが、指し筋bと指し筋cのどちらが優れているか判別できず、詰んでしまう指し筋bを選んでしまう可能性がある。これが水平線効果である。

ここで実力のある人間ならば、たとえN手先までしか読んでいなくとも、指し筋bの方が危ないというヒューリスティックな判断をすることが可能である。このため優秀な将棋プログラムにはたいていヒューリスティックな判断を下せる評価関数が実装されている。しかしヒューリスティックな評価関数があれば必ず水平線効果を回避できるわけではなく、評価値でかなりの勝勢にあるにもかかわらず、直後に読み違いで頓死という例もしばしばある。

たとえば対戦相手がある手Xを指すと、局面が自分にとって逆転不能なほど大きく不利になり、Xを阻止することも非常に困難な場合を考える。この時、実力のある人間ならばXが指されるか効果を発揮するまでに勝負を決めるよう乾坤一擲の筋を見出そうとする。一方、N手先しか読めないプログラムは、無駄な手を指してでもとりあえずXがN手先以内に指されないように努め、いたずらに勝負を先延ばしにしようとする。特に将棋では持ち駒があるため、歩を打って直後に突き捨てるなど無駄に手数を延ばす手が生じやすい。この水平線効果はドワンゴ・日本将棋連盟主催第2回将棋電王戦1戦目における習甦阿部光瑠四段、第3回将棋電王戦3戦目におけるYSS豊島将之七段、電王戦FINAL5戦目における阿久津主税八段 vs.AWAKE(21手目で投了)でも見られた。

解決策[編集]

優れた評価関数の開発以外、現在これといった解決策は提案されていない。

関連項目[編集]