Как вы делаете древовидные структуры данных в C ++? - PullRequest
Новая
       62

Как вы делаете древовидные структуры данных в C ++?

3 голосов
/ 01 августа 2011

Я беру урок по методам ИИ вместе с моим другом, и мы приняли участие в финальном проекте, который кодирует Othello и ИИ для него с использованием C ++ и OpenGL.

ИтакПока у нас есть плата и двигатель Отелло (я использую подход типа MVC).Но единственное, что трудно понять - это ИИ.

Мы должны написать ИИ, который использует альфа-бета-обрезку на дереве, чтобы быстро рассчитать следующий ход, который он должен сделать.

Понятия альфа-бета-обрезки, а также алгоритм определения того, какие квадраты стоят больше, чем другие, что касается игры.

Однако ни моему партнеру, ни мне еще предстоит принятькласс структур данных, и поэтому мы не знаем, как правильно создать дерево в C ++ или даже с чего начать.

Итак, мой вопрос к вам, переполнение стека: с чего быстро начать?(и эффективно) написать и обойти дерево для альфа-бета-отсечения в C ++ без использования STL .(В нашем задании говорится, что нам запрещено использовать STL).

Любая помощь приветствуется, спасибо!

1 Ответ

2 голосов
/ 01 августа 2011

Дерево для обрезки альфа-бета обычно неявно. Это способ не позволить вашему алгоритму поиска ИИ тратить время на плохие решения. Вот псевдокод из Википедии: 

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;

Здесь children - массив узлов с членами childCount. Листовые узлы будут иметь 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;
}
...