B*

コンピュータサイエンスにおいて、B*（「ビースター」と発音）は、与えられた初期ノードから任意の目標ノード（1つ以上の可能な目標ノードから）への最小コストの経路を見つける、最良優先グラフ探索アルゴリズムです。 1979年にハンス・ベルリナーによって初めて公開され、 A*探索アルゴリズムと関連しています

要約

このアルゴリズムは、単一の点値の推定値ではなく、ツリーのノードの区間を保存します。次に、ツリーのリーフノードを探索し、最上位ノードの1つが明らかに「最良」の区間を持つまで探索します

詳細

推定ではなく区間評価

B*木の葉ノードには、単一の数値ではなく区間の評価が与えられます。区間には、そのノードの真の値が含まれると想定されています。葉ノードに付与されたすべての区間がこの特性を満たす場合、B*は目標状態への最適な経路を特定します

バックアッププロセス

木内の区間をバックアップするために、親の上限は子の上限の最大値に設定されます。親の下限は子の下限の最大値に設定されます。異なる子がこれらの上限を提供する可能性があることに注意してください

B*は、ルートの直接の子の下限が、ルートの他の直接の子の上限と少なくとも同じ大きさになったときに発生する「分離」を作成するために、系統的にノードを拡張します。ルートで分離を作成する木には、最良の子が他のどの子よりも少なくとも優れているという証明が含まれています

実際には、複雑な探索は実用的なリソース制限内で終了しない可能性があります。そのため、アルゴリズムには通常、時間制限やメモリ制限などの人工的な終了基準が付加されます。人工的な制限に達した場合、どの手を選択するかについてヒューリスティックな判断を下す必要があります。通常、木構造はルートノードの間隔など、広範な証拠を提供します。

拡張

B*はベストファーストプロセスです。つまり、ツリーを走査し、繰り返し下降して拡張する葉を見つけるのは非常に効率的です。このセクションでは、拡張するノードの選択方法について説明します。（注：ツリーがメモリ常駐かどうかは、実メモリまたは仮想メモリを介してどのようにマッピングおよび／または管理されるかを含む、全体的な実装効率に依存します。）

木の根において、アルゴリズムは「最良証明」と「残余証明」と呼ばれる2つの戦略のいずれかを適用します。最良証明戦略では、アルゴリズムは最も高い上限値に関連付けられたノードを選択します。そのノードを拡張することで、その下限値が他のどのノードの上限値よりも高くなることを期待します。

反証-残余戦略は、ルートの子ノードのうち、2番目に高い上限を持つノードを選択します。そのノードを展開することで、上限を最も高い子ノードの下限よりも小さくできる可能性があります。

戦略の選択

最も高い上限を持つ子ノードの下限が、すべての下限の中で最高になるまで、反証-残余戦略を適用しても意味がないことに注意してください

元のアルゴリズムの説明では、どの戦略を選択すべきかについて、これ以上の指針は示されていませんでした。より小さな木を持つ選択肢を拡張するなど、いくつかの合理的な代替案があります。

非ルートノードでの戦略選択

ルートの子ノードが選択されると (prove-best または disprove-rest を使用)、アルゴリズムは上限が最も高い子ノードを繰り返し選択してリーフ ノードに進みます。

リーフノードに到達すると、アルゴリズムはすべての後続ノードを生成し、評価関数を用いてそれらに区間を割り当てます。その後、すべてのノードの区間はバックアップ操作によってバックアップされます。

転置が可能な場合、バックアップ操作では選択パス上にないノードの値を変更する必要があるかもしれません。この場合、変更を伝播させるために、アルゴリズムは子ノードからすべての親ノードへのポインタを必要とします。バックアップ操作によってノードに関連付けられた区間が変更されない場合、伝播は停止する可能性があることに注意してください。

堅牢性

区間が正しくない場合（ノードのゲーム理論的価値が区間内に含まれないという意味で）、B*は正しい経路を識別できない可能性があります。しかし、このアルゴリズムは実際にはエラーに対してかなり堅牢です

Maven （Scrabble）プログラムには、評価エラーが発生する可能性がある場合にB*の堅牢性を向上させる革新的な機能が搭載されています。分離により探索が終了した場合、Mavenはすべての評価区間を少しずつ広げてから探索を再開します。このポリシーはツリーを徐々に広げ、最終的にすべてのエラーを消去します。

2人用ゲームへの拡張

B*アルゴリズムは、2人対戦の決定論的ゼロサムゲームに適用されます。実際には、唯一の違いは「最良」をそのノードで動いている側に基づいて解釈することです。つまり、自分の側が動いている場合は最大値を取り、相手が動いている場合は最小値を取ります。同様に、すべての区間を動く側の視点から表現し、バックアップ操作中に値を反転させることもできます。

応用

アンドリュー・パレイはB*をチェスに適用しました。エンドポイント評価はヌルムーブ探索を実行することで割り当てられました。このシステムが、同じハードウェア上で動作する アルファベータプルーニング検索エンジンと比較してどの程度優れたパフォーマンスを示したかについては報告されていません

Maven （スクラブル）プログラムは、エンドゲームにB*探索を適用しました。エンドポイントの評価は、ヒューリスティックプランニングシステムを用いて割り当てられました。

B* 検索アルゴリズムは、組み合わせゲームのセットの合計ゲームにおける最適な戦略を計算するために使用されています。

参照

参考文献

「 https://en.wikipedia.org/w/index.php?title=B*&oldid=1334420717」より取得