3

私は友人と一緒に AI メソッドのクラスを受講しており、C++ と OpenGL を使用してオセロとそのための AI をコーディングする最終プロジェクトに協力しています。

これまでのところ、ボードとオセロ エンジンがあります (私は MVC タイプのアプローチを使用しています)。しかし、把握するのが難しいことが 1 つわかっているのは、AI です。

ツリーでアルファベータ枝刈りを使用して、次の動きをすばやく計算する AI を作成する必要があります。

ゲームに関する限り、アルファベータ剪定の概念と、どの正方形が他の正方形よりも価値があるかを検出するアルゴリズム。

ただし、パートナーも私もまだデータ構造クラスを受講していないため、C++ でツリーを適切に作成する方法や、どこから始めればよいかさえわかりません。

だから私の質問は、スタック オーバーフローです: STL を使用せずに C++ で Alpha-Beta Pruning のツリーをすばやく (そして効果的に) 書き始めてトラバースするには、どこから始めればよいでしょうか。(私たちの割り当ては、STL の使用が許可されていないと述べています)。

どんな助けでも大歓迎です、ありがとう！

4

1 に答える 1

2

アルファベータ法のツリーは通常、暗黙的です。これは、AI検索アルゴリズムが悪いソリューションに時間を浪費するのを防ぐ方法です。ウィキペディアの擬似コードは次のとおりです。

function alphabeta(node, depth, α, β, Player)         
    if  depth = 0 or node is a terminal node
        return the heuristic value of node
    if  Player = MaxPlayer
        for each child of node
            α := max(α, alphabeta(child, depth-1, α, β, not(Player) ))     
            if β ≤ α
                break                             (* Beta cut-off *)
        return α
    else
        for each child of node
            β := min(β, alphabeta(child, depth-1, α, β, not(Player) ))     
            if β ≤ α
                break                             (* Alpha cut-off *)
        return β 
(* Initial call *)
alphabeta(origin, depth, -infinity, +infinity, MaxPlayer)

この関数は、ボードの位置を再帰的に評価します。「ノード」は現在の位置であり、「ノードの子ごとに」と表示されている場所は、現在の位置で可能な各移動の結果として新しいボード位置を生成する場所です。深さパラメータは、ツリーを評価する先を制御します。無制限の深さへの移動を分析することは実用的でない場合があります。

それでも、教育目的で剪定する前に一定の深さのツリーを構築する必要がある場合、可変数の子を持つことができるノードを持つツリーの構造は非常に単純で、次のようになります。

struct Node
{
    Node ** children;
    int     childCount;
    double  value;
};

Node * tree;

これは、 childCountchildrenメンバーを持つNode配列です。リーフノードにはchildCount=0。ツリーを構築するには、次のように利用可能なボードの位置を検索します。

Node * CreateTree(Board board, int depth)
{
    Node * node = new Node();
    node.childCount = board.GeAvailableMoveCount();
    node.value      = board.GetValue;
    if (depth > 0 && node.childCount > 0)
    {
        node.children = new Node * [node.childCount];
        for (int i = 0; i != node.childCount; ++i)
            node.children[i] = CreateTree(board.Move(i), depth - 1);
    }
    else
    {
        node.children = NULL;
    }
    return node;
}

void DeleteTree(Node * tree)
{
    for (int i = 0; i != tree.childCount; ++i)
        DeleteTree(tree.children[i]);
    delete [] tree.children; // deleting NULL is OK
    delete tree;
}
于 2011-08-01T07:13:44.220 に答える