2016-06-19 2 views
1

У меня возникла проблема с реализацией дерева, используемого для алгоритма mini-max для моего модуля AI.Динамическое дерево Java для алгоритма mini-max

Дерево, которое мне нужно написать, будет иметь 4 уровня: корень (0) - перемещение AI (1) - перемещение игрока (2) и перемещение AI (3). Каждый уровень будет содержать n детей и будет иметь такие поля, как (состояние правления, скорость поля и координаты для перемещения). С моими расчетами на третьем уровне дерева возможное число детей составило бы около 25 000. Как мне это реализовать?

На данный момент я реализовал 3 различных ArrayList х объектов, каждый список для определенного уровня:

  • firstDepthList - содержит объекты с возможной доски состояния, скорости поля и координаты для перемещения);
  • secondDepthList содержит Объекты с возможным состоянием плат (для каждого элемента с firstDepthList), скорость и координаты перемещения; и
  • thirdDepthList который содержит Объекты, как указано выше для каждого элемент от secondDepthList. Конечно, я связал списки вместе для платы и перемещает непрерывность.

Возможно, вы бы рекомендовали лучшее решение?

ответ

0

Алгоритм Mini-max требует только одного значения: max (или минимум, зависит от номера уровня). Вам не нужно хранить все дерево.

Он может быть реализован как рекурсивная функция. И не создавая много состояний, можно использовать только одно устройство правления (например, шахматная фигура от А до В)

double getRating(BoardState state, int currentPlayer, int depth){ 
    //current player has to be 1 or -1 
    if (depth <= 0){ 
     return state.positionRating(); 
    } 
    double bestRating = -Double.MAX_VALUE; 
    for(Move m: state.possibleMoves(currentPlayer)){ 
     state.apply(m); // modify state 
     double rating = currentPlayer * getRating(state, -currentPlayer, depth-1); 
     // player 1 wants to have biggest number, player -1: lowest 
     bestRating = Math.max(bestRating, rating); 
     state.revert(m) // restore state 
    } 
return bestState*currentPlayer; 
} 
Смежные вопросы