アルファ・ベータ法と探索間の類似点
アルファ・ベータ法と探索は(ユニオンペディアに)共通で4ものを持っています: 反復深化深さ優先探索、ミニマックス法、分枝限定法、ゲーム木。
反復深化深さ優先探索
反復深化深さ優先探索(英: iterative deepening depth-first search、IDDFS)とは、探索アルゴリズムの一種であり、深さ制限探索の制限を徐々に増大させ、最終的に目標状態の深さになるまで反復するものである。各反復では深さ優先探索の順序で探索木のノードを調べるが、全体として見れば(刈り込みがない場合)、各ノードを初めて調べる順序は幅優先探索と同じ順序になる。 IDDFSを知識あり探索にしたものがIDA*である。これは、ダイクストラ法を知識あり探索にしたものがA*であることに対応する。.
アルファ・ベータ法と反復深化深さ優先探索 · 反復深化深さ優先探索と探索 ·
ミニマックス法
ミニマックス法(みにまっくすほう、minimax)またはミニマックス探索とは、想定される最大の損害が最小になるように決断を行う戦略のこと。将棋、チェス、オセロなどといった完全情報ゲームをコンピュータに思考させるためのアルゴリズムとしても用いられるが、元々はフォン・ノイマンが中心となって数学的に理論化されたゲーム理論において、打ち手を決定する際に適用されるルールの一つ。 これに対し、想定される最小の利益が最大になるように決断を行う戦略はマクシミン戦略という。.
アルファ・ベータ法とミニマックス法 · ミニマックス法と探索 ·
分枝限定法
分枝限定法(ぶんしげんていほう、branch and bound, BB)は、各種最適化問題(特に離散最適化と組合せ最適化)の最適解を求める汎用アルゴリズムである。分枝操作(branching operation)と限定操作(bounding operation)から構成される。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。 1960年、A.
ゲーム木
ーム木(ゲームき、game tree)は、組合せゲーム理論において、ゲームの盤面を有向グラフのノードで、手をエッジで表したものである。完全ゲーム木とは、ゲームの最初から指せる全ての手を含んだゲーム木である。なお、組合せゲーム理論ではない通常のゲーム理論の「ゲームの木」については展開型ゲームを参照。 三目並べの最初の2手のゲーム木 右図は、三目並べのゲーム木の最初の2レベル(あるいは2手)までを示したものである。ここでは、盤面を回転させたり反転させて同じになるものは等価としているため、最初の1手は3種類(中心、角、角と角の間)しかない。2手目は、1手目が中心の場合は2種類、そうでない場合は5種類ある。 完全ゲーム木の葉ノードの数をゲーム木複雑性(game-tree complexity)と呼び、そのゲームが最終的にどれだけの異なる盤面で終わるかを示している。三目並べのゲーム木複雑性は 26,830 である。 ゲーム木は人工知能で重要であり、最良の手はゲーム木を探索することで得られ、ミニマックス法などのアルゴリズムを使用する。三目並べのゲーム木は小さいので探索も容易だが、チェスなどの完全ゲーム木は大きすぎて全体を探索することができない。その場合は代わりに部分ゲーム木を使う。部分ゲーム木は、一般に現在の盤面から指せる手を時間内に探索できるぶんだけ含んだものである。 2人で対戦するゲームはAND/OR木で表現することもできる。先手が勝つには、後手がどういう手を指しても先手が勝つ手が存在しなければならない。これをAND/OR木では、先手の指せる手を論理和で表し、後手のさせる手を論理積で表す。.
上記のリストは以下の質問に答えます
- 何アルファ・ベータ法と探索ことは共通しています
- 何がアルファ・ベータ法と探索間の類似点があります
アルファ・ベータ法と探索の間の比較
探索が77を有しているアルファ・ベータ法は、8の関係を有しています。 彼らは一般的な4で持っているように、ジャカード指数は4.71%です = 4 / (8 + 77)。
参考文献
この記事では、アルファ・ベータ法と探索との関係を示しています。情報が抽出された各記事にアクセスするには、次のURLをご覧ください: