Chess engine recursive problems

Processing.py
1

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]]
2

Missing else part here?

I don’t know

1 Like
3

I don’t understand why the entire function hasn’t be copied :sweat_smile::man_facepalming:
I’ll upload the rest once i come back home

1 Like
4

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,  not isMaximizing, 1-tour))
    board = undo(m, board, prev)
    
    if( value > bestMove):
        bestMove = value
        bestMoveFinal = m
return bestMoveFinal

def minimax(depth, board, is_maximizing, tour):

global nb
nb+=1
if(depth == 0):
    return -evaluate(board, tour)

possibleMoves = getPossibleMoves(board, tour)
if len(possibleMoves) == 0:
    if gameIsOver(board) and isInCheck(tour,board):
        if is_maximizing:
            return float('-inf')
        else:
            return float('inf')
    
#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, not is_maximizing, 1-tour))
        board = undo(m, board, prev)
    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, not is_maximizing, 1-tour))
        board = undo(m, board, prev)
    return bestMove
5

I don’t know py but from what I read you should have a counter for how many times minmax is called.

Explanation:

You have a depth and you check the depth, and that’s certainly the most important, but when there are a lot of possible moves maybe that’s killing him.

So you could try and follow only the first 10 possible moves. Just to test my hypothesis. Later you can find a better way.

1 Like
6

Thank you for your answer !

But actually i am already counting it with the global variable « nb » at the beginning of minimax.

My biggest problem is that : it works most of the time, and the number of recursive calls can be 50 000 even 150 000 when i increase the depth. But in certain positions the nb variable goes to exactly 154 and the the program crashes.

But why would 154 be over the maximum recursion limit when 150 000 doesn’t ?

1 Like
7

nb doesn‘t count what’s going on in the for loop

It might be a difference when one recursion is 30 deep OR if a recursion has 40 children with their recursions

1 Like
8

Did you work further on this?

Can you please post your resulting code

1 Like
9

Hi @Grusat,

It is unlikely that the minimax algorithm with alpha beta pruning (which latter I can’t find in your code snippets) and a common used depth value, running into max recursion error. Maybe if you provide your full code, we could analysing the issues.

Here you can read more details about and an example implementation:

Cheers
— mnse