Я пытаюсь реализовать компьютерного игрока в игре типа Connect Four. Альфа-бета-обрезка казалась лучшим способом добиться этого, но я не могу понять, что я делаю неправильно.
Ниже приведен код, который я придумал. Он начинается с начального корневого состояния. Алгоритм для каждого возможного допустимого хода (и если не происходит обрезки): делает глубокую копию состояния, обновляет состояние (увеличивает глубину, переключает ходы, добавляет фигуру, устанавливает эвристическое значение) и добавляет это новое состояние в список преемников корня.
Если новое состояние не является листом (т.е. на максимальной глубине), оно рекурсивно продолжается. Если это лист, алгоритм проверяет корневое значение и соответствующее локальное значение альфа/бета и соответственно обновляет. После проверки всех возможных допустимых параметров алгоритм возвращает соответствующее локальное значение альфа/бета.
По крайней мере, это то, что я намеревался. Каждый запуск возвращает значение 0. В соответствии с запросом вот код инициализации:
class GameState:
def __init__(self, parentState = None):
# copy constructor
if not(parentState == None):
self.matrix = copy.deepcopy(parentState.matrix)
self.successor = copy.deepcopy(parentState.successor)
self.depth = parentState.depth
self.turn = parentState.turn
self.alpha = parentState.alpha
self.beta = parentState.beta
self.connects = copy.deepcopy(parentState.connects)
self.value = parentState.value
self.algo_value = parentState.value
self.solution = parentState.solution
# new instance
else:
# empty board
self.matrix = [[0 for y in xrange(6)] for x in xrange(7)]
## USED WHEN GROWING TREE
self.successor = [] # empty list
self.depth = 0 # start at root
self.turn = 1 # game starts on user's turn
## USED WHEN SEARCHING FOR SOLUTION
self.alpha = float("-inf")
self.beta = float("+inf")
self.connects = [0, 0, 0] # connects in state
self.algo_value = float("-inf")
self.value = 0 # alpha-beta value of connects
self.solution = False # connect four
def alphabeta(root):
if root.depth < MAX_EXPANSION_DEPTH:
# pass down alpha/beta
alpha = root.alpha
beta = root.beta
# for each possible move
for x in range(7):
# ALPHA-BETA PRUNING
# if root is MAXIMIZER
if (root.turn == 2) and (root.algo_value > beta): print "beta prune"
# if root is MINIMIZER
elif (root.turn == 1) and (root.algo_value < alpha): print "alpha prune"
# CANNOT prune
else:
# if move legal
if (checkMove(root, x)):
# CREATE NEW STATE
root.successor.append(GameState(root))
working_state = root.successor[-1]
# update state
working_state.successor = []
working_state.depth += 1
working_state.turn = (working_state.turn % 2) + 1
cons = dropPiece(working_state, x, working_state.turn)
# update state values
# MAXIMIZER
if working_state.turn == 2:
working_state.value = ((cons[0]*TWO_VAL)+(cons[1]*THREE_VAL)+(cons[2]*FOUR_VAL)) + root.value
working_state.algo_value = float("-inf")
# MINIMIZER
else:
working_state.value = ((-1)*((cons[0]*TWO_VAL)+(cons[1]*THREE_VAL)+(cons[2]*FOUR_VAL))) + root.value
working_state.algo_value = float("inf")
# if NOT a leaf node
if (working_state.depth < MAX_EXPANSION_DEPTH):
# update alpha/beta values
working_state.alpha = alpha
working_state.beta = beta
ret = alphabeta(working_state)
# if MAXIMIZER
if (root.turn == 2):
if (ret > root.algo_value): root.algo_value = ret
if (ret > alpha): alpha = ret
# if MINIMIZER
else:
if (ret < root.algo_value): root.algo_value = ret
if (ret < beta): beta = ret
# if leaf, return value
else:
if root.turn == 2:
if (working_state.value > root.algo_value): root.algo_value = working_state.value
if working_state.value > alpha: alpha = working_state.value
else:
if (working_state.value < root.algo_value): root.algo_value = working_state.value
if working_state.value < beta: beta = working_state.value
if root.turn == 2: return alpha
else: return beta
working_state
конечным узлом, иногда вы возвращаете значение, изменяяroot.algo_value
, но позже вы такжеreturn
либоalpha
, либоbeta
. Это очень трудно понять. (PS: Эта функция огромна и имеет глубокие отступы. Это дает много места для вашей ошибки, чтобы скрыть ее, и затрудняет точное определение того, где именно заканчиваются отступы. Подумайте о том, чтобы разбить эту функцию на более мелкие функции, которые легче тестировать по отдельности.) - person Kevin J. Chase   schedule 20.11.2014