水平線効果
水平線効果（すいへいせんこうか）は探索アルゴリズムの深度を有限とした場合、それ以降の経路をあたかも水平線の向こうのように考慮しないため、長期的に見て問題のある選択をしてしまう人工知能における問題である。通常多くのゲームにおいて、可能な状態あるいは配置の数は莫大であり、コンピュータはそのごく一部（大抵ゲーム木の数層下）しか探索することができない。
ミニマックス法やαβ枝刈りといった技術を使用して大きなゲーム木を評価する時、探索深度は実現可能性の理由のため制限される。しかしながら、ゲーム木の部分的な評価は紛らわしい結果を与える可能性がある。探索深度の「水平線」のすぐ先に大きな変化が存在する時、計算装置は水平線効果の餌食となる。
水平線効果は静止探索によって探索アルゴリズムを拡張することで緩和することができる。これは、駒の捕獲といったゲーム状態において大きな重要性を持つ手の分類について水平線の先を見る能力を探索アルゴリズムに与える。
葉ノードについて評価関数を書き直す、より多くのノードを十分に解析することの両方もしくは一方によって多くの水平線問題が解決される。
例
編集たとえば将棋において、10手先までしか読めないコンピュータがあったとし、ちょうど10手目でコンピュータ側の飛車が取られる状況にあったとする。ここで、持ち駒に歩があり、歩で王手をかけ、王が逃げたら歩を成り捨てるを繰り返して、飛車を取られるのを11手目以降に先延ばしする手があったとしよう。この手はもちろん、飛車だけでなく歩をも相手に取られることになるので、単に飛車を取られるより悪い手である。ところが10手先までしか読めないコンピュータにとっては、11手目以降で結局飛車を取られることが探索の水平線の向こう側に消えて見えなくなるため、歩で王手をする「一瞬気持ちのいい」手が飛車を取られずに済む好手であるかのように評価され、コンピュータはその場しのぎでより状況を悪化させる手を選んでしまう。
参考文献
編集- Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, pp. 174, ISBN 0-13-790395-2