ロゴ
ユニオンペディア
コミュニケーション
Google Play で手に入れよう
新しい! あなたのAndroid™デバイスでユニオンペディアをダウンロードしてください!
無料
ブラウザよりも高速アクセス!
 

アルファ・ベータ法

索引 アルファ・ベータ法

アルファ・ベータ法(— ほう、alpha-beta pruning)は完全情報ゲームにおける探索アルゴリズムの1つである。基本的にミニマックス法と同じであり、同じ計算結果が得られるが、ゲーム木において、計算しなくても同じ計算結果になる部分を枝刈りしている。.

8 関係: 反復深化深さ優先探索二人零和有限確定完全情報ゲームミニマックス法分枝限定法アーサー・サミュエルゲーム木探索擬似コード

反復深化深さ優先探索

反復深化深さ優先探索(英: iterative deepening depth-first search、IDDFS)とは、探索アルゴリズムの一種であり、深さ制限探索の制限を徐々に増大させ、最終的に目標状態の深さになるまで反復するものである。各反復では深さ優先探索の順序で探索木のノードを調べるが、全体として見れば(刈り込みがない場合)、各ノードを初めて調べる順序は幅優先探索と同じ順序になる。 IDDFSを知識あり探索にしたものがIDA*である。これは、ダイクストラ法を知識あり探索にしたものがA*であることに対応する。.

新しい!!: アルファ・ベータ法と反復深化深さ優先探索 · 続きを見る »

二人零和有限確定完全情報ゲーム

二人零和有限確定完全情報ゲーム(ににん ぜろわ ゆうげん かくてい かんぜんじょうほう ゲーム)は、ゲーム理論によるゲームの分類のひとつである。チェス・将棋・チェッカー・オセロ・石取りゲーム(ニム)・囲碁・連珠・五目並べ・三目並べ(○×ゲーム)・マンカラ・ツイクストなど、偶然(運)に左右されないゲームが相当する。.

新しい!!: アルファ・ベータ法と二人零和有限確定完全情報ゲーム · 続きを見る »

ミニマックス法

ミニマックス法(みにまっくすほう、minimax)またはミニマックス探索とは、想定される最大の損害が最小になるように決断を行う戦略のこと。将棋、チェス、オセロなどといった完全情報ゲームをコンピュータに思考させるためのアルゴリズムとしても用いられるが、元々はフォン・ノイマンが中心となって数学的に理論化されたゲーム理論において、打ち手を決定する際に適用されるルールの一つ。 これに対し、想定される最小の利益が最大になるように決断を行う戦略はマクシミン戦略という。.

新しい!!: アルファ・ベータ法とミニマックス法 · 続きを見る »

分枝限定法

分枝限定法(ぶんしげんていほう、branch and bound, BB)は、各種最適化問題(特に離散最適化と組合せ最適化)の最適解を求める汎用アルゴリズムである。分枝操作(branching operation)と限定操作(bounding operation)から構成される。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。 1960年、A.

新しい!!: アルファ・ベータ法と分枝限定法 · 続きを見る »

アーサー・サミュエル

アーサー・リー・サミュエル(Arthur Lee Samuel、1901年 - 1990年7月29日)はアメリカの計算機科学者で、コンピュータゲームと人工知能の分野で主に知られている。Samuel Checkers-playing Program は世界初の学習型プログラムであり、人工知能 (AI) の基本的概念をいち早く世界に示したものである。.

新しい!!: アルファ・ベータ法とアーサー・サミュエル · 続きを見る »

ゲーム木

ーム木(ゲームき、game tree)は、組合せゲーム理論において、ゲームの盤面を有向グラフのノードで、手をエッジで表したものである。完全ゲーム木とは、ゲームの最初から指せる全ての手を含んだゲーム木である。なお、組合せゲーム理論ではない通常のゲーム理論の「ゲームの木」については展開型ゲームを参照。 三目並べの最初の2手のゲーム木 右図は、三目並べのゲーム木の最初の2レベル(あるいは2手)までを示したものである。ここでは、盤面を回転させたり反転させて同じになるものは等価としているため、最初の1手は3種類(中心、角、角と角の間)しかない。2手目は、1手目が中心の場合は2種類、そうでない場合は5種類ある。 完全ゲーム木の葉ノードの数をゲーム木複雑性(game-tree complexity)と呼び、そのゲームが最終的にどれだけの異なる盤面で終わるかを示している。三目並べのゲーム木複雑性は 26,830 である。 ゲーム木は人工知能で重要であり、最良の手はゲーム木を探索することで得られ、ミニマックス法などのアルゴリズムを使用する。三目並べのゲーム木は小さいので探索も容易だが、チェスなどの完全ゲーム木は大きすぎて全体を探索することができない。その場合は代わりに部分ゲーム木を使う。部分ゲーム木は、一般に現在の盤面から指せる手を時間内に探索できるぶんだけ含んだものである。 2人で対戦するゲームはAND/OR木で表現することもできる。先手が勝つには、後手がどういう手を指しても先手が勝つ手が存在しなければならない。これをAND/OR木では、先手の指せる手を論理和で表し、後手のさせる手を論理積で表す。.

新しい!!: アルファ・ベータ法とゲーム木 · 続きを見る »

探索

探索(たんさく、search)とは、特定の制約条件を満たす物を見つけ出す行動のこと。何か問題を解くに当たって、有効な解析的な解法を用いることのできない場合は、試行錯誤によって解を得る場合もある。一部のアルゴリズムは、元々、機械学習と並んで人工知能の分野のアルゴリズムであるが、現在はその他の分野にも応用されている。類義語として検索(search)も参照。.

新しい!!: アルファ・ベータ法と探索 · 続きを見る »

擬似コード

擬似コード (ぎじコード、pseudocode)とは、アルゴリズムなどを、架空の非常に高水準なプログラミング言語(擬似言語)で記述したものである。Pascal、Fortran、C言語などの既存のプログラミング言語の構文と、自然言語に近い表現を組み合わせて記述することが多い。.

新しい!!: アルファ・ベータ法と擬似コード · 続きを見る »

ここにリダイレクトされます:

Α-β法ネガアルファネガアルファ法アルファベータ法

出ていきます入ってきます
ヘイ!私たちは今、Facebook上です! »