Хорошая эвристика для Connect-K AI

Question

Я пишу простой AI Connect-K (без обрезки, только 4 слоя). Мне было интересно, что такое эффективная эвристика , что быстро вычислить.

Что-то лучше, чем то, что у меня есть:

def eval(board, player) 
    connections = 0 
    magnitude = 0 
    for x in range(0, self.boardW(board)): 
     for y in range(0, self.boardH(board)): 
      if(self.get_player(board, x, y) == player): #assuming x and y are in bounds 
       temp = 1 
       # keep checking in this direction to find the max temp can be 
       if (magnitude < temp): 
        magnitude = temp 
      if(self.get_player(board, x, y) == player): 
       connection += 1 
     ........ 
    return connection**2 + magnitude**2 

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

Мои к будет больше, чем 4; таким образом, я не могу выполнить исчерпывающий поиск дерева.

Answer 1

A min-max Поиск может быть полезен в этом сценарии, возможно, в сочетании с упрощенным MCTS. В основном, более глубокая рекурсия позволит вам достичь большего количества конечных состояний игры. Анализируя, какой игрок выигрывает в каждом из этих случаев, вы лучше понимаете ценность определенного хода.

Метод min-max весьма полезен для игр между двумя игроками и широко используется для настольных игр, таких как это. MCTS может быть немного избыточным, но общая идея заключается в том, чтобы торговать обширным поиском случайного и более глубокого поиска. Например, вместо того, чтобы иметь коэффициент ветвления 20 и только 5 уровней рекурсии (20^5 = 3,2 миллиона), вы можете случайно выбрать 10 ветвей и иметь 6-7 шагов рекурсии с одинаковым количеством вычислений.

Что-то, что дало хорошие результаты в аналогичном проекте (AI для шашек), должно было уменьшить коэффициент ветвления дальше в рекурсии. Определив максимальное ветвление (максимальное количество ветвей, которые нужно исследовать на этапе рекурсии), пусть это число будет больше, чем типичное ветвление для верхнего уровня, и уменьшится дальше рекурсии до гораздо меньшего числа (5-10 вполне скоро и 1-3 внизу). Таким образом, вы получаете лучшее из обоих миров. Вы изучаете все предстоящие действия, но также получаете много информации о том, как они влияют на более поздние части игры.

Краткое описание: Используя MCTS и min-max, вы можете найти множество конечных состояний. Если противник выиграл, дайте ему большой отрицательный результат. Если вы выиграли, дайте ему большой положительный результат. Если ни один, вы не можете дать ему 0 или использовать функцию, указанную в вашем вопросе. Пусть оценка состояния родительской игры зависит от количества их детей, используя алгоритм min-max.