Tic-Tac-Toe AI: Как сделать дерево?

Question

У меня огромный блок, пытающийся понять "деревья" при создании бота Tic-Tac-Toe. Я понимаю концепцию, но не могу понять, как их реализовать.

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

Answer 1

Представьте, что в любой точке доски крестики-нолики каждый возможный ход - это ветвь. Текущее состояние платы - корень. Один ход - это ветка. Теперь представьте (по одному), что каждая ветвь становится текущим состоянием. Каждый возможный ход становится новой веткой. Лист дерева - это когда последний ход сделан и доска заполнена.

Причина, по которой вам нужно дерево, заключается в том, что после его построения вам нужно выяснить, какая ветвь имеет наибольшее количество листьев, которые являются сценариями 'WIN'. Вы строите ветвь из всех возможных результатов, складываете общее количество выигрышей, а затем делаете ход, который может закончиться с наибольшим количеством побед.

Сделайте дерево примерно таким:

class Node {
public:
   std::list< Node > m_branches;
   BoardState m_board;
   int m_winCount;
}

std::list< Node > tree;

Теперь вы перебираете список ветвей в дереве, и для каждой ветви перебираете его ветви. Это можно сделать с помощью рекурсивной функции:

int recursiveTreeWalk( std::list< Node >& partialTree)
{

   for each branch in tree
       if node has no branches
           calculate win 1/0;
       else
           recursiveTreeWalk( branch );

   partialTree.m_winCount = sum of branch wins;
}

// initial call
recursiveTreeWalk( tree )

Очень псевдокод.

Answer 2

Не думаю, что вам нужно хранить дерево в памяти. Вам просто нужно реализовать рекурсивную функцию, которая работает примерно так:

Move getBestMove(Board state, boolean myTurn)

Затем вы просто выполняете рекурсию, пока не достигнете состояния выигрыша, проигрыша или ничьей.

Стек вызовов со временем выглядел бы как дерево, если бы вы нарисовали его на бумаге. Вы должны вернуть ход, который приводит к узлу, в котором противник (определенно / наиболее вероятно) проигрывает (даже если он также играет, используя getBestMove)

Однако для такого пространства состояний, как крестики-нолики, вы можете просто сделать полный справочный стол с лучшими ходами! : -)

Answer 3

Вы можете найти эту статью проекта кода интересной:

Решите крестики-нолики с помощью алгоритма MiniMax

Это на C #, но его адаптация на C ++ не составит труда.

Эта статья также была для меня хорошим чтением, когда я пытался реализовать свою первую игру Tic-Tac-Toe на C ++:

объяснение минимакса

Answer 4

Реализация игры Tic Tac Toe, вероятно, является самой простой проблемой, которую нужно решить с точки зрения ИИ и пространство поиска.

Ключ к решению проблемы с Минимакс , Итеративное углубление Поиск в глубину и Обработка альфа-бета алгоритмов.

Вот моя реализация игры на Python, которая содержит всего ~ 200 строк кода и имеет возможность играть в игру как Human vs. Human, Human vs. Computer и Computer vs. Computer. Он также хранит статистику по глубинам и количеству достигнутых / сокращенных узлов, ведущих к лучшему ходу.

Я настоятельно рекомендую edX.org Искусственный интеллект курс , который дает фундаментальные знания по актуальным темам и решениям по искусственному интеллекту.

Answer 5

Если вы хотите сгенерировать дерево в памяти (что не обязательно), возможно, можно использовать алгоритм, подобный следующему (псевдокод):

GenTree(State s):
  T <- empty tree  // T is a tree of States
  SetRoot(T, s)

  ForEach (s' in Successors(s)):
    AddChild(T, GenTree(s'))

  return T

// Call it
GenTree(currentMove)

, где

Successors(s)  // returns a list of successor states of s
AddChild(p, n)  // adds n to the list of p's children