Многоразовый игровой AI дерево


Проблема

Мне нужен минимаксного дерева игры, так что он может повторно использовать уже созданный правильные шаги, после обрезки ходы уже сделаны. В отличие от двоичного дерева, игра дерево может иметь несколько дочерних узлов, соответствующих возможных ходов. Я хочу, чтобы генерировать новые вершины в уровне-мудрый фон, так что время задержки в лучших переводов сокращается. В рекурсивном Минимакс рутину, каждое дерево тщательно сформированный для каждого шага ; однако контроль конечных ходов или повторные движения будут тоже трудны.

Мое Решение

Эта игра дерево, кроме повторного использования, также позволяют интегрировать открытия движения и конец движения легко . Смарт-указатели используются для автоматический сбор мусора, хотя они могут быть немного дороже, они помогут избежать утечек памяти в долгосрочной перспективе, поскольку количество узлов будет работать в 10-100 тысяч. Снимок диагноз ( см. ниже) было принято, чтобы гарантировать, что все ненужные ветви были правильно подрезаны и количество ссылок по сравнению.

Поскольку это программа прототипа, все ингредиенты реализуется в один файл cpp . Я хочу улучшить ( особенно обрезки части), поэтому входы приветствуются.

Некоторые базовые структуры:

struct board_t
{
    std::vector<uint8_t> pos;
    board_t()
    {
        pos = std::vector<uint8_t>(25, 0);
    }
};

struct node_t
{
    std::unique_ptr<board_t> board_;
    std::weak_ptr<node_t> parent_;
    std::vector<std::shared_ptr<node_t>> children_;

    node_t()
    {
        board_ = std::make_unique<board_t>();
        parent_.reset();
    }
};

struct tree_t
{
    std::shared_ptr<node_t> root_;

    tree_t()
    {
        root_ = std::make_shared<node_t>();
        root_->board_ = std::make_unique<board_t>();
        root_->parent_.reset();
    }

    tree_t(std::shared_ptr<node_t>& node) :root_(node)
    {
    }

    void reset(std::shared_ptr<node_t>& node)
    {
        DeleteTree(root_, node);

        //delete extra children of root node only
        for (auto& next_node : root_->children_)
            if (next_node != node)
            {
                next_node->board_.reset();
                next_node->parent_.reset();
                std::cout << "1 destroyed\n";
            }

        root_ = node;
        root_->parent_.reset();
    }

private:

    void DeleteTree(std::shared_ptr<node_t>& node, std::shared_ptr<node_t>& new_root)
    {
        if (node->children_.empty())
        {
            while (!node->parent_.expired())
            {
                auto strong = node->parent_.lock();
                node = strong;
                if (strong)
                {
                    strong->board_.reset();
                    strong->parent_.reset();
                    if (!strong->children_.empty())
                    {
                        std::cout << strong->children_.size() << " destroyed\n";
                        strong->children_.clear();
                    }
                }
            }

            return;
        }

        for (auto& next_node : node->children_)
            if (next_node != new_root)
            {
                DeleteTree(next_node, new_root);
            }

    }

};

Некоторые вспомогательные функции:

std::unique_ptr<tree_t>& GetTree()
{
    static std::unique_ptr<tree_t> tree = std::make_unique<tree_t>();
    return tree;
}

std::shared_ptr<node_t>& GetTreeRoot()
{
    return GetTree()->root_;
}

void AddChild(std::shared_ptr<node_t>& node, std::shared_ptr<node_t> parent)
{
    node->parent_ = parent;
    parent->children_.emplace_back(node);
}

void PrintTree(std::shared_ptr<node_t>& node)
{
    for (int i = 0; i < node->children_.size(); i++)
        std::cout << "Node " << node->children_[i].use_count()<<"/"<< node->children_[i]->children_.size() <<"   ";
    std::cout << "\n";

    for (auto& next_node : node->children_)
    {
        PrintTree(next_node);
    }
}

int GetDepth(std::shared_ptr<node_t>& node)
{
    int depth = 1;
    std::weak_ptr<node_t> weak = node->parent_;

    while (!weak.expired())
    {
        weak = weak.lock()->parent_;
        depth++;
    }
    return depth;
}

int MaxDepth(std::shared_ptr<node_t>& node)
{
    static int max_depth = 0;

    if (node->children_.empty())
    {
        max_depth = std::max(max_depth, GetDepth(node->parent_.lock()));
        return  max_depth;
    }

    for (auto& next_node : node->children_)
        MaxDepth(next_node);

    return max_depth;
}

Минимак и функции оценки теста:

int Evaluate(std::unique_ptr<board_t>& board, bool maximizing)
{
    static int ptr = 0;  //TEST 
    int arr[] = { 2,1,3,1,-1 ,2,1,3,1,-1 ,1,3,1,-1 ,2,1,3,1,-1 ,1,3,1,-1 ,2,1,3,1,-1 };
    return arr[ptr++];
}

int Minimax(std::shared_ptr<node_t>& node, bool white2max = true)
{
    bool maximizing = (GetDepth(node) % 2 == 1);
    int score = maximizing ? -999 : 999;

    if (node->children_.empty())
    {
        return  Evaluate(node->board_, !maximizing);
    }

    for (auto& next_node : node->children_)
    {
        int val = Minimax(next_node, white2max);
        maximizing ? score = std::max(score, val) : score = std::min(score, val);
    }
    return score;
}

Новая функция генерации листе:

void GenerateNewLeafNodes(std::shared_ptr<node_t>& node)
{
    auto GenerateNewNodes = [](std::shared_ptr<node_t> parent_node)->void
    {
        std::queue<std::unique_ptr<board_t>> positions;
        //TODO void GenerateMoves(parent_node,positions)
        positions.push(std::make_unique<board_t>()); //TEST 
        positions.push(std::make_unique<board_t>()); //TEST 

        while (!positions.empty())
        {
            std::shared_ptr<node_t> node = std::make_shared<node_t>();
            node->board_ = std::move(positions.front());
            node->parent_ = parent_node;
            AddChild(node, parent_node);
            positions.pop();
        }
    };

    if (node->children_.empty())
    {
        return GenerateNewNodes(node);
    }

    for (auto& next_node : node->children_)
        GenerateNewLeafNodes(next_node);
}

Тестовые функции:

void test_build()
{
    AddChild(std::make_shared<node_t>(), GetTreeRoot());
    AddChild(std::make_shared<node_t>(), GetTreeRoot());
    AddChild(std::make_shared<node_t>(), GetTreeRoot());

    auto& root_next1 = GetTreeRoot()->children_[0];


    AddChild(std::make_shared<node_t>(), root_next1);
    AddChild(std::make_shared<node_t>(), root_next1);

    std::cout << "Depth = " << GetDepth(root_next1) << " \n";
    std::cout << "Max_Depth = " << MaxDepth(GetTreeRoot()) << " \n";

    GenerateNewLeafNodes(GetTreeRoot());
    GenerateNewLeafNodes(GetTreeRoot());

    std::cout << "Minmax score = " << Minimax(GetTreeRoot(), true) << " \n";    

    std::cout << "\nTree \n";
    PrintTree(GetTreeRoot());

    //std::cout << " Root " << GetTreeRoot().use_count() << "/ " << GetTreeRoot()->children_.size() << "\n";
    GetTree()->reset(root_next1);  // PRUNING HERE

    std::cout << "\nTree \n";
    PrintTree(GetTreeRoot());
    //std::cout << " Root " << GetTreeRoot().use_count() << "/ " << GetTreeRoot()->children_.size() << "\n";
}

int main()
{
    test_build();
    return 0;
}

Диагностика памяти моментальный снимок, показывающий падение Реф отсчитывает после обрезки:

enter image description here

enter image description here



433
5
задан 31 марта 2018 в 03:03 Источник Поделиться
Комментарии
1 ответ

Конструкторы

Вы должны использовать список инициализации конструктора в ваши конструкторы. В настоящее время, ваши конструкторы по умолчанию будет построить все члены класса, то некоторые из этих вновь построенных участники получают свои значения заменен (по уступке) в теле конструктора. Они могут быть объединены с помощью списка инициализаторов конструктора. Например:

board_t(): pos(25, 0)
{
}

Вы тоже повторяетесь. В node_t конструктор дает board_ член уникальная board_t член. Затем в tree_t конструктор можно переназначать, что значение указателя на новый. Это тоже ненужно reset недавно построенный weak_ptr.

Стиль кодирования

Основная проблема у меня со стилем кода является отсутствие фигурных скобок на некоторые из ваших многочисленных блока инструкции. Например, for петли в tree_t::reset. Язык не требует их, так как есть только один оператор в теле for петли, но делает код более легким для понимания и снижает вероятность ошибок странным позже, когда код добавляется или редактируется.

Вы обычно проходят общие указатели на ссылки, но в некоторых случаях вы делаете копии. Вы будете хотеть проверить, чтобы увидеть, если копия верна, или если вы можете использовать ссылку, или, если в следующие задания вы можете извлечь выгоду из использования std::move вместо копии задания.

Код

В MiniMaxвы злоупотребляете условный оператор, используя его в качестве if заявление. Код будет понятнее, если бы вы использовали, если вместо ?: оператор со встроенными заданий, или (Поскольку вы присваиваете одной переменной) присвоить результат условного (score = maximizing ? std::max(score, val) : std::min(score, val)). Мое личное предпочтение было бы использовать вложенные, если вот так как вы обычно назначается score для себя.

В Evaluate функция вопросов (локальный массив может быть static constпотенциальные доступ за границы массива, если он вызывается слишком часто), но это, кажется, тест функция, которая крайне нуждается в обновлении.

3
ответ дан 31 марта 2018 в 04:03 Источник Поделиться