Блог

Я пишу простой ИИ 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 направлений (вверх, вниз, влево, вправо, сверху-слева, снизу-слева, …)

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

В этом сценарии может быть полезен поиск 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.