Шаблон алгоритма: как уменьшить вложенные для циклов

Question

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

С каждым слоем он будет оценивать, является ли движение хорошим или плохим для игрока и назначает очки, в конце он выбирает ходы с наивысшими точками.

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

counter = 0 
    for x in list: 
     counter += 1 
     list_2 = [x * 2 for x in list] 
     print 'list_2', list_2, counter 
     for x in list_2: 
      counter += 1 
      list_3 = [x * 2 for x in list_2] 
      print 'list_3',list_3, counter 
      for x in list_3: 
       counter += 1 
       list_4 = [x * 2 for x in list_3] 
       print 'list_4', list_4, counter 

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

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

Answer 1

Вот эквивалентная функция, которая использует рекурсию. Он контролирует рекурсию с двумя параметрами, которые отслеживают текущую глубину и максимальную глубину. Если текущая глубина превышает максимальную глубину он будет немедленно вернуться, таким образом останавливая рекурсию:

def evaluate(l, max_depth, cur_depth=0, counter=0): 
    if cur_depth > max_depth: 
     return counter 

    for x in l: 
     counter += 1 
     l2 = [x * 2 for x in l] 
     print cur_depth, l2, counter 
     counter = evaluate(l2, max_depth, cur_depth + 1, counter) 

    return counter 

При вызове с max_depth=2 он будет производить тот же результат, за исключением того, что вместо имени переменной выводится текущая глубина.

Answer 2

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

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

def countup(i=0): 
    print(i) 
    if i==MAX_COUNT: return 
    countup(i+1) 

Для вашего алгоритма вам необходимо значение для оценки платы. Например, в диапазоне [-1,1]. Игрок A можно назвать выигрышным, если оценка -1, а Игрок B выигрывает, если оценка равна 1. Рекурсивный алгоритм может быть следующим.

def evaulate(board, player, depth=0): 
    if depth==MAX_DEPTH: return hueristicEvaluation(board) 
    bestMove = None 
    if player==PLAYER_A: 
    val=999 # some large value 
    for move in get_moves(): 
     newboard = board.makeMove(move) 
     eval, _ = evaluate(newboard, PLAYER_B, depth+1) 
     if eval < val: 
     bestMove = move 
     val = eval 
    elif player==PLAYER_B: 
    val=-999 # some large negative value 
    for move in get_moves(): 
     newboard = board.makeMove(move) 
     eval, _ = evaluate(newboard, PLAYER_A, depth+1) 
     if eval > val: 
     bestMove = move 
     val = eval 
    return val, bestMove 

Это аннотация, но идея есть. Отрегулируйте в зависимости от того, как вы представляете board или player s. Функция hueristicEvaluation может быть чем-то таким же простым, как подсчет частей на доске для каждого игрока и насколько они близки к другой стороне. Помните, что эта функция должна возвращать число между [-1,1]

случаями пограничных рассмотреть, что я не принял во внимание:

• Если все хода победы и/или потерь
• Если есть НЕТ перемещается в позиции, например, если ваши кусочки полностью заблокированы частями вашего оппонента.

Многие улучшения существуют для простого поиска, подобного этому.Читайте, если вам интересно :)

• Для шашек, возможно, Memoization ускорит многое. Я не уверен, но я думаю, что это будет особенно в начале. See python's way of doing this.
• Pruning
• Alpha-beta pruning
• Branch and bound