Tic-Tac-Toe AI: как сделать дерево?
У меня есть огромный блок, пытающийся понять "деревья" при создании бота Tic-Tac-Toe. Я понимаю понятие, но я не могу выяснить для реализации их.
Кто-то может показать мне пример того, как дерево должно быть сгенерировано для такого случая? Или хорошее учебное руководство при генерации деревьев? Я предполагаю, что твердая часть генерирует частичные деревья. Я знаю, как реализовать генерацию целого дерева, но не частей его.
4 ответа
Представьте себе, что в любой точке доски крестик-нолик каждое возможное движение является ветвью. Текущее состояние платы — это корень. Один ход – это ветка. Теперь представьте (по одному), что каждая ветвь становится текущим состоянием. Каждый возможный ход становится новой ветвью. Лист дерева - это когда сделан последний ход и доска заполнена.
Причина, по которой вам нужно иметь дерево, заключается в том, что после того, как оно построено, вам нужно выяснить, какая ветвь имеет больше листьев, которые являются сценариями «WIN». Вы строите ветвь всех возможных результатов, складываете общее количество 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 )
Очень псевдокод.
Я не думаю, что вам нужно держать дерево в памяти. Вам просто нужно реализовать рекурсивную функцию, которая работает примерно так:
Move getBestMove(Board state, boolean myTurn)
Затем вы просто выполняете рекурсию, пока не достигнете состояния выигрыша, проигрыша или ничьей.
Стек вызовов со временем стал бы выглядеть как дерево, если бы вы нарисовали его на бумаге. Вы должны вернуть ход, ведущий к узлу, в котором противник (определенно / наиболее вероятно) проигрывает (даже если он также играет с использованием getBestMove)
Однако для пространства состояний всего лишь крестики-нолики вы могли бы просто сделайте полную справочную таблицу с лучшими ходами! : -)
Возможно, вам будет интересна эта статья на codeproject :
Решите Tic Tac Toe с помощью алгоритма MiniMax
Она на C#, но адаптировать ее на C++ не составит труда.
Эта статья также была хорошим чтением для меня, когда я пытался реализовать свою первую игру Tic-Tac-Toe на C++ :
Если вы хотите генерировать дерево в памяти (что не обязательно), возможно, можно использовать алгоритм, подобный следующему (псевдокод):
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