Реализация tictactoe tree

Question

Я использую игровое дерево в C++ для моего tictactoe.

Идея такова: минимаксное дерево может иметь любое количество детей, в зависимости от ситуации с игрой. Уровни дерева обычно называются слоями. На каждом слое возможность играть («поворот») переключается на другого игрока.

Теперь важно: дерево начинается с текущего положения на плате, так как оно s root node. So each tree node consists of a list. The possible moves (from the computer с точки зрения) являются членами этого списка.

Мой вопрос: как я могу построить это дерево? Очевидно, что текущее состояние платы должно быть каким-то образом определено, так что функция оценки знает, с чего начать поиск.

Struct node 
{ 
    Node* successors 

    // get available movecount 
    int count() 
    {    
     for (int count=0; count< free cells) 
      ++count 
    } 

    Node* curr_board_state= root; 
} 

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

Есть некоторые идеи. Надеюсь, кто-то может мне помочь.

Answer 1

Для tic-tac-toe каждый узел в дереве игры может иметь не более 9 детей, так как существует не более 9 возможных ходов. Насколько я понимаю, было бы необычным подходом к явному представлению всего игрового дерева для его оценки. Более простой подход состоял бы в том, чтобы представить игровое поле. При поиске в дереве игр узлы оцениваются путем фактического изменения состояния платы, выполнения оценки и последующего устранения гипотетического перемещения. То, что вы описываете как ваш подход, - это базовая версия Minimax algorithm, которая точно соответствует гипотетическому выполнению движения, которое будет оцениваться, продолжая рекурсивным образом, где на каждом уровне дерева просматривается перспектива игроков.

Answer 2

«Узлы оцениваются путем фактического изменения состояния платы, выполнения оценки и последующего устранения гипотетического хода».

С учетом вышесказанного, я не представлял сделать что-то вроде

int availableMoves(vector<pair<unsigned int, unsigned int> >& v) const { 
//clear result vector. 
v.clear(); 
//check if the game is in progress. 
int state = evaluateState(); 
if(state != IN_PROGRESS) 
return state; 

//if the game is in progress, check for empty cells. 
for(unsigned int x = 0; x < 3; i++) 
for(unsigned int y = 0; y < 3; j++) 
if(board(x,y) = free;) 
v.push_back(pair<unsigned int, unsigned int>(x, y)); 
return IN_PROGRESS; 
} 

Struct node 

{ 
    node * availalableMoves; 
} 

node * CreateTree(Board b, int depth) 
{ 

vector<pair<unsigned int, unsigned int> > availableMoves; 

// Allocate new space for nodes to be evaluated 

unsigned int numAvailableMoves = (unsigned int)availableMoves.size(); 
for(unsigned int i = 0; i < numAvailableMoves; i++) { 

Stack<occupiedMoves.size();>my_free_store; 

void* pv1= my_free_store.get(); 
int* buffer = static_cast<int*>(pv1); 
void* pv2= my_free_store.get(sizeof(availableMoves)); 
availableMoves* pconn= new(pv2) availableMoves(incoming,outcoming,buffer); 

алгоритм Мой negamax выглядит следующим образом:

int Search(int depth) 
{ 
int score; 
int x,y; 
int bestScore = -2; 
bool bestMove = false; 
if(depth == 0) return Evaluate(); 
for (int turns = 0; turns < 9; ++turns) { // loop over turns 
while (occupied(x,y)); 
make_move(x, y); 
score = -Search(depth-1); // recursion 
unMake(); 
if(score > bestScore) { 
bestScore = score; 
bestMove = (x,y); 
} 
} 
return bestScore; 
return bestMove; 
} 

Вопрос заключается в том, что оценка() должна содержать