Я разработал шахматный движок в python с использованием минимаксного алгоритма, а также использовал Alpha-Beta Pruning для его дальнейшей оптимизации. В настоящее время я ищу на глубине 4 , что немного, но все еще требуется 10-60 секунд, чтобы подумать о движении.
Главное, что замедляет программу, - это повторение снова и опять. Сначала я генерирую все возможные ходы в deque.collection(), а затем повторяю их один раз, чтобы проверить . Теперь я повторяю его еще раз, чтобы оценить ходы, а затем сравниваю их, чтобы получить наилучший ход. Я использую циклы for на протяжении всего этого, и формат всех возможных ходов представляет собой набор (mainmoves) коллекций (ходов)
Что я могу сделать, чтобы оптимизировать это и сократить время, необходимое для создания хода.
def minimaxRoot(depth,isMaximizing):
global board
possibleMoves = gen(False)
bestMove = -math.inf
bestMoveFinal = None
for move in possibleMoves:
orig = normperform(move)
value = max(bestMove, minimax(depth - 1,not isMaximizing,-math.inf,math.inf))
undo(move,orig)
if value > bestMove:
bestMove = value
bestMoveFinal = move
return bestMoveFinal
def minimax(depth,ismax,alpha,beta):
global board
if depth == 0:
return calcpoints()
maxeval = -math.inf
mineval = math.inf
if ismax == True:
mainmoves = gen(False)
if mainmoves == 'mate':
return 8000
for move in mainmoves:
orig = normperform(move)
eval = minimax(depth-1,False,alpha,beta)
undo(move,orig)
maxeval=max(eval,maxeval)
alpha = max(alpha,eval)
if beta <= alpha:
break
return maxeval
elif ismax == False:
mainmoves2 = gen(True)
if mainmoves2 == 'mate':
return 8000
for move2 in mainmoves2:
orig2 = normperform(move2)
eval2 = minimax(depth-1,True,alpha,beta)
undo(move2,orig2)
mineval = min(mineval,eval2)
if eval2 < beta:
beta = eval2
if beta <= alpha:
break
return mineval