# Chess engine recursive problems

**URL:** <https://discourse.processing.org/t/chess-engine-recursive-problems/24613>\
**Category:** Processing.py\
**Created:** [October 15, 2020, 5:18am UTC](https://discourse.processing.org/t/chess-engine-recursive-problems/24613 "2020-10-15T05:18:50Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Grusat](https://avatars.discourse-cdn.com/v4/letter/g/48db29/32.png) [@Grusat](https://discourse.processing.org/u/Grusat)\
**Post date:** [October 15, 2020, 5:18am UTC](https://discourse.processing.org/t/chess-engine-recursive-problems/24613/1 "2020-10-15T05:18:50Z")

</div>

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):

```auto
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):

```auto
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]]
```

---

<div class="post-metadata">

**Author:** ![Chrisir](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/chrisir/32/45_2.png) [@Chrisir](https://discourse.processing.org/u/Chrisir)\
**Post date:** [October 15, 2020, 9:58pm UTC](https://discourse.processing.org/t/chess-engine-recursive-problems/24613/2 "2020-10-15T21:58:11Z")

</div>

> [@Grusat](#):
>
> ```auto
> #Meilleur coup pour l'ia
> if(is_maximizing):
> 
> ```

Missing else part here?

I don’t know

---

<div class="post-metadata">

**Author:** ![Grusat](https://avatars.discourse-cdn.com/v4/letter/g/48db29/32.png) [@Grusat](https://discourse.processing.org/u/Grusat)\
**Post date:** [October 16, 2020, 5:47am UTC](https://discourse.processing.org/t/chess-engine-recursive-problems/24613/3 "2020-10-16T05:47:24Z")

</div>

I don’t understand why the entire function hasn’t be copied 😅🤦‍♂️  
I’ll upload the rest once i come back home

---

<div class="post-metadata">

**Author:** ![Grusat](https://avatars.discourse-cdn.com/v4/letter/g/48db29/32.png) [@Grusat](https://discourse.processing.org/u/Grusat)\
**Post date:** [October 17, 2020, 5:50pm UTC](https://discourse.processing.org/t/chess-engine-recursive-problems/24613/4 "2020-10-17T17:50:07Z")

</div>

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
```

---

<div class="post-metadata">

**Author:** ![Chrisir](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/chrisir/32/45_2.png) [@Chrisir](https://discourse.processing.org/u/Chrisir)\
**Post date:** [October 19, 2020, 8:32pm UTC](https://discourse.processing.org/t/chess-engine-recursive-problems/24613/5 "2020-10-19T20:32:11Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Grusat](https://avatars.discourse-cdn.com/v4/letter/g/48db29/32.png) [@Grusat](https://discourse.processing.org/u/Grusat)\
**Post date:** [October 20, 2020, 5:27am UTC](https://discourse.processing.org/t/chess-engine-recursive-problems/24613/6 "2020-10-20T05:27:20Z")

</div>

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 ?

---

<div class="post-metadata">

**Author:** ![Chrisir](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/chrisir/32/45_2.png) [@Chrisir](https://discourse.processing.org/u/Chrisir)\
**Post date:** [October 20, 2020, 8:08am UTC](https://discourse.processing.org/t/chess-engine-recursive-problems/24613/7 "2020-10-20T08:08:12Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Chrisir](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/chrisir/32/45_2.png) [@Chrisir](https://discourse.processing.org/u/Chrisir)\
**Post date:** [December 6, 2024, 2:39pm UTC](https://discourse.processing.org/t/chess-engine-recursive-problems/24613/8 "2024-12-06T14:39:13Z")

</div>

Did you work further on this?

Can you please post your resulting code

---

<div class="post-metadata">

**Author:** ![mnse](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/mnse/32/16520_2.png) [@mnse](https://discourse.processing.org/u/mnse)\
**Post date:** [December 8, 2024, 6:16pm UTC](https://discourse.processing.org/t/chess-engine-recursive-problems/24613/9 "2024-12-08T18:16:16Z")

</div>

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:

> **[Minimax with Alpha-Beta Pruning in Python](https://stackabuse.com/minimax-and-alpha-beta-pruning-in-python/)**
>
> Way back in the late 1920s John Von Neumann established the main problem in game theory that has remained relevant still today: Players s1, s2, ..., sn are pl...

Cheers  
— mnse