Actually i’m implementing a minimax algorithm with alphabeta pruning for a chess AI but i’m getting a maximum recursive depth reached error in some positions.
I guess my recursive function minimax isn’t correct but i can’t find the problem.
Maybe you will ;p
def minimaxRoot(depth, board,isMaximizing, tour):
possibleMoves = getPossibleMoves(board, tour)
if len(possibleMoves) == 0:
return None
bestMove = float('-inf')
bestMoveFinal = None
for m in possibleMoves:
prev = board[m[3]][m[2]]
board = move_test(m, board)
value = max(bestMove, minimax(depth - 1, board,float('-inf'), float('inf'), not isMaximizing, 1-tour))
#affiche(board)
board = undo(m, board, prev)
if( value > bestMove):
bestMove = value
bestMoveFinal = m
return bestMoveFinal
def minimax(depth, board, a, b, is_maximizing, tour):
global nb
nb+=1
print(depth)
if(depth <1):
return -evaluate(board, tour)
possibleMoves = getPossibleMoves(board, tour)
if len(possibleMoves) == 0:
if isInCheck(tour,board):
if is_maximizing:
return float('-100000')
else:
return float('100000')
else:
if is_maximizing:
return float('20000')
else:
return float('-20000')
#Meilleur coup pour l'ia
if(is_maximizing):
bestMove = float('-inf')
for m in possibleMoves:
prev = board[m[3]][m[2]]
board = move_test(m, board)
bestMove = max(bestMove, minimax(depth - 1, board, a, b, not is_maximizing, 1-tour))
board = undo(m, board, prev)
a = max(a, bestMove)
if b <= a:
return bestMove
return bestMove
#Meilleur coup de l'adversaire (= pire coup pour l'ia)
else:
bestMove = float('inf')
for m in possibleMoves:
prev = board[m[3]][m[2]]
board = move_test(m, board)
bestMove = min(bestMove, minimax(depth - 1, board, a, b, not is_maximizing, 1-tour))
board = undo(m, board, prev)
b = min(b, bestMove)
if b <= a:
return bestMove
return bestMove