Мин Макс Макс алгоритм в питоне

Question

В алгоритме minmax, Как определить, когда ваша функция достигает конца дерева и прерывать рекурсивные вызовы.

Я сделал функцию max, в которой я вызываю функцию min. В функции min, что я делаю? Для максимальной функции я просто возвращаю bestscore.

def maxAgent(gameState, depth):
      if (gameState.isWin()):
        return gameState.getScore()
      actions = gameState.getLegalActions(0);
      bestScore = -99999
      bestAction = Directions.STOP

      for action in actions:
        if (action != Directions.STOP):
          score = minAgent(gameState.generateSuccessor(0, action), depth, 1)
          if (score > bestScore):
            bestScore = score
            bestAction = action
      return bestScore

def minvalue(gameState,depth,agentIndex):
       if (gameState.isLose()):
         return gameState.getScore()
       else:
         finalstage = False
         number = gameState.getNumAgents()
         if (agentIndex == number-1):
           finalstage = True
           bestScore = 9999
           for action in gameState.getLegalActions(agentIndex):
             if(action != Directions.STOP

Я не мог понять, как действовать сейчас? Я не позволил установить предел глубины дерева. оно должно быть произвольным.

Answer 1

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

Answer 2

Я полностью согласен с Релет.Но вы можете рассмотреть это также:

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

Как подсказывает Эмбер, попробуйте опубликовать некоторый код, чтобы мы знали, насколько сложным вы хотите, чтобы решение было.Кроме того, если вы объясните, сколько вы знаете / can_do, то мы могли бы предложить более полезные варианты - вещи, которые вы могли бы реально реализовать, а не просто удивительные идеи, о которых вы, возможно, не знаете, как или у вас есть времяреализации

Answer 3

В алгоритме minmax, Как определить, когда ваша функция достигает конца дерева и прервать рекурсивные вызовы.

По сути, вы спрашиваете, когда вы достиглиКонечный узел.

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

Answer 4

Этот сайт имеет минимаксную запись, хотя он основан на IronPython: http://blogs.microsoft.co.il/blogs/dhelper/archive/2009/07/13/getting-started-with-ironpython-part-4-minimax-algorithm.aspx

Там написано:

Алгоритм Minimax по своей природе рекурсивен и поэтому требует условия остановки, в нашем случае либо игра завершена (больше нет ходов), либо достигнута желаемая глубина (строки 3-8).

Вы можете избежать двух разных функций, используя Negamax http://en.wikipedia.org/wiki/Negamax