水平線効果

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

水平線効果(すいへいせんこうか)は探索アルゴリズムの深度を有限とした場合、それ以降の経路をあたかも水平線の向こうのように考慮しないため、長期的に見て問題のある選択をしてしまう人工知能における問題である。通常多くのゲームにおいて、可能な状態あるいは配置の数は莫大であり、コンピュータはそのごく一部(大抵ゲーム木の数下)しか探索することができない。

ミニマックス法αβ枝刈りといった技術を使用して大きなゲーム木を評価する時、探索深度は実現可能性の理由のため制限される。しかしながら、ゲーム木の部分的な評価は紛らわしい結果を与える可能性がある。探索深度の「水平線」のすぐ先に大きな変化が存在する時、計算装置は水平線効果の餌食となる。

水平線効果は静止探索によって探索アルゴリズムを拡張することで緩和することができる。これは、駒の捕獲といったゲーム状態において大きな重要性を持つ手の分類について水平線の先を見る能力を探索アルゴリズムに与える。

葉ノードについて評価関数を書き直す、より多くのノードを十分に解析することの両方もしくは一方によって多くの水平線問題が解決される。

解説[編集]

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

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

ここで実力のある人間ならば、たとえN手先までしか読んでいなくとも、指し筋bの方が危ないというヒューリスティックな判断をすることが可能である。このため優秀な将棋プログラムにはたいていヒューリスティックな判断を下せる評価関数が実装されている。しかしヒューリスティックな評価関数があれば必ず水平線効果を回避できるわけではなく、序盤でハメ手にひっかかったり、評価値でかなりの勝勢にあるにもかかわらず、直後に読み違いで劣勢になり、時には頓死という例もしばしばある。この水平線効果はドワンゴ・日本将棋連盟主催第3回将棋電王戦第3局における豊島将之七段対YSS、電王戦FINAL第2局のSelene対永瀬拓矢六段、同第5局における阿久津主税八段対AWAKEで現れた。

別の例として、対戦相手がある手Xを指すと、局面が自分にとって逆転不能なほど大きく不利になり、Xを阻止することも非常に困難な場合を考える。この時、実力のある人間ならばXが指されるか効果を発揮するまでに勝負を決めるよう乾坤一擲の筋を見出そうとする。一方、N手先しか読めないプログラムは、無駄な手を指してでもとりあえずXがN手先以内に指されないように努め、いたずらに勝負を先延ばしにしようとする。特に将棋では持ち駒があるため、歩を打って直後に突き捨てるなど無駄に手数を延ばす手が生じやすい。このパターンは第2回将棋電王戦第一局の阿部光瑠四段対習甦(無駄な歩打ち)、前述のYSS対豊島七段(同じく無意味な歩)、電王戦FINAL第一局の斎藤慎太郎五段対Aprey(終盤の連続王手)で見られた。

脚注[編集]

関連項目[編集]