探索法

このページはOpera6.0　で正常に表示できることを確認しています。

---

木構造について

チェスコンピュータは着手を決定するために次々と手を先読みしていきます。 これは、現在の局面で可能な着手を生成し、 さらにそれぞれの着手を指した後の局面でも可能な着手を生成し… という風にして先読みをしていくのですが、 このとき着手が枝分かれしていく様子をちょうど木をさかさまにしたような形で書くことができます。 そのため、このような構造を木構造といいます。 探索アルゴリズムではこの木構造を仮想的に(もしくは実際に)構築し、 それぞれの指し手を評価していきます。

初期配置

e4

d4

Nf3

e5

c5

e6

d5

f5

Nf6

Nf6

e5

Nc3

c4

木構造で使われる用語を以下に説明しておきます。

根(root)

木構造において分岐の始まる最初の部分。上図における「初期配置」の部分。

枝(branch)

1つ1つの分岐。上図における線で表された部分。

節(node)

枝と枝の接点。

葉(leaf)

根から離れる方向に枝を持たない節。

親、先祖

現在のノードから根の間にあるノードを先祖という。 特に根の方向に1つ戻ったノードを親ノードという。

子、子孫

現在のノードから葉の間にあるノードを子孫という。 特に葉の方向に1つ進んだノードを子ノードという。

枝刈りについて

チェスにおいて白の第1手は20通りあります。また、黒の第1手も20通りあります。 このことから、白黒お互いに1手づつさしたあとの局面は400通り存在します。 これが2手3手と増えていくにつれて局面は爆発的に増加していきます。 当然これらを全て探索することはできないので、 どうにかして探索する局面を減らす必要があります。 この、探索しない枝を決定することを枝刈りといいます。

枝刈りには、理論的に探索不要であることを示す、 理論的に問題ない枝刈りが多く発生するようにもっていく、 経験則に従う(これは現在では良くないとされています)、 などで行うアルゴリズムが提案されています。

コンピュータチェスのトップへ