1

I am trying to write the code for minimax algorithm for tic tac toe in python all by myself, I have wrote the code but whenever the function is getting called it is showing a "maximum recursion depth in comparison" error. I am stuck in this part. When I am trying to debug it it is also not helping out.

import sys

marked=['','','','','','','','','']
markingSignal=[False,False,False,False,False,False,False,False,False]


def printTable():
    print("\t%s|\t%s|\t%s\n------------------------\n\t%s|\t%s|\t%s\n------------------------\n\t%s|\t%s|\t%s\n"%(marked[0],marked[1],marked[2],marked[3],marked[4],marked[5],marked[6],marked[7],marked[8]))

def winning(m,player):
    i=0
    x=0
    while x<3:
        if m[i]==player and m[i+1]==player and m[i+2]==player:
            return True
        x=x+1
        i=i+3    
    x=0
    i=0
    while x<3:
        if m[2]==player and m[4]==player and m[6]==player:
            return True
        x=x+1
        i=i+3  
    x=0
    i=0
    if m[0]==player and m[4]==player and m[8]==player:
        return True
    if m[2]==player and m[4]==player and m[6]==player:
        return True
    return False         


def minimax(table,marktab,points,pos=0):
    copyTab=table
    copymark=marktab
    remaining=0
    for x in table:
        if x==False:
            remaining=remaining+1
    if remaining==0:
        return points,pos
    scores=[None]*remaining
    positions=[None]*remaining
    z=0
    maximum=0
    bestpos=0
    previous=88
    x=0
    while x<9:
        if table[x]==False:
            if points%2==0:
                copyTab[x]==True
                copymark[x]=='O'
                result=winning(copymark,'O')
                previous=x
                if result:
                    return points ,x
            else:
                copyTab[x]==True
                copymark[x]=='X'    
            scores[z],positions[z]=minimax(copyTab,copymark,points+1,previous)
            z=z+1
            copyTab[x]==False
            copymark[x]==''
        x=x+1
    for x in range(0,len(scores)):
        if x==0:
            maximum=scores[x]
            bestpos=positions[x]
        if scores[x]<maximum:
            maximum=scores[x]
            bestpos=positions[x]
    return maximum, bestpos        



def takeInput(player):
    filled=False
    while filled==False:
        print("Enter Your Choice 1-9")
        x=int(input())
        if x>9:
            print("Invalid Choice")
            continue
        if markingSignal[x-1]:
            print("This slot is already filled")
            continue
        filled=True    
    marked[x-1]=player
    markingSignal[x-1]=True


def main():

    sys.setrecursionlimit(5000)
    print(sys.getrecursionlimit())
    printTable()
    count=0
    player='X'
    while count<9:

        if count%2==0:
            player='X'
            takeInput(player)
        else:
            player='O'  
            p,choice=minimax(markingSignal,marked,0)  
            marked[choice]=player
            markingSignal[choice]=True         
        printTable()
        result=winning(marked,player)
        if result:
            print("\n%s WON !!!\n"%(player))
            break
        count=count+1


main()

In this code the user input part is working fine but the computer input or the minimax algorithm part is not working, and showing the recursion error

halfer
  • 19,824
  • 17
  • 99
  • 186
Golden Clips
  • 23
  • 4
  • What is the purpose of `minimax`? – Iain Shelvington Dec 29 '19 at 19:16
  • 3
    At a glance I would guess `copyTab=table` and `copymark=marktab` might be the problem - these pass the same lists by reference rather than making copies. To make copies do `copyTab = table[:]` instead. – Stuart Dec 29 '19 at 19:21
  • 1
    https://stackoverflow.com/a/9697367/567595 and the links there and other answers might help on assigning variables in Python. – Stuart Dec 29 '19 at 19:27
  • I have been looking at your code for a while, and there are just too many errors to sum up. Take to heart Stuart's comment, but the copying, the double table, ... it makes no sense. Why don't you go over to Wikipedia and look how a minimax is implemented? It will be better than debugging the many misconceptions in your code. – trincot Dec 29 '19 at 19:50
  • I have just two months ago started learning python. I have spend hours writing this, it would be heartbreaking for me to copy the algorithm from the internet now – Golden Clips Dec 29 '19 at 19:59
  • As a programmer you'll also need to learn the asset to throw away code when necessary and start from scratch. I have answered several questions about minimax implementations before, even concerning tic-tac-toe, but here I am going to pass. – trincot Dec 29 '19 at 20:04
  • And BTW, also this is the internet, so if someone is going to post a fixed version, it will be more or less the same. – trincot Dec 29 '19 at 20:06

2 Answers2

1

So, in your code 

scores[z],positions[z]=minimax(copyTab,copymark,points+1,previous)

this is entering a never end cicle. It is breaking over and over... The previous value is always between 88 and 0. That recursive function must return at a certain point (you only have a return before calling the recursive function where is a winning position. After the first move you can't have a winning position, therefore the recursive never ends).

Taking this into consideration in minimax function you are not copying the values, only passing by reference:

copyTab=table.copy()
copymark=marktab.copy()

Also, you are not increasing the X value because in the recursive function the board is not updated and not tested.

So you need to assign the values: copyTab[x]=True copymark[x]='O' And not using double equals == that will just return a boolean value.

So the function is now working as intended:

def minimax(table,marktab,points,pos=0):
    copyTab=table.copy()
    copymark=marktab.copy()
    remaining=0
    for x in table:
        if x==False:
            remaining=remaining+1
    if remaining==0:
        return points,pos
    scores=[None]*remaining
    positions=[None]*remaining
    z=0
    maximum=0
    bestpos=0
    previous=88
    x=0
    while x<9:
        if table[x]==False:
            if points%2==0:
                copyTab[x]=True
                copymark[x]='O'
                result=winning(copymark,'O')
                previous=x
                if result:
                    return points ,x
            else:
                copyTab[x]=True
                copymark[x]='X' 
            scores[z],positions[z]=minimax(copyTab,copymark,points+1,previous)
            z=z+1
            copyTab[x]=False
            copymark[x]=''
        x=x+1
    for x in range(0,len(scores)):
        if x==0:
            maximum=scores[x]
            bestpos=positions[x]
        if scores[x]<maximum:
            maximum=scores[x]
            bestpos=positions[x]
    return maximum, bestpos
Azevinho
  • 23
  • 1
  • 4
  • *"That recursive function must return at a certain point."*: I see at least two places in the code where it has a `return` without recursing deeper. *"you are not increasing the X value"*: the code has a line that says `x = x + 1`. – trincot Dec 29 '19 at 19:38
  • @trincot, I changed my answer with those points, explaining them. He is only returning if there is a winning move. And the X value is increasing only after calling the recursive function. Therefore the function that started the recursive will never go to the next task. For this porpuses it could be added a new parameter to return after a certain recursive deepeness – Azevinho Dec 29 '19 at 19:42
  • That doesn't explain it. After the first move, it *must* recurse deeper, so that is normal, and also there is a test for a draw where it also returns. Also the second point is not clear. The `x` must not increase before the recursive call, since the recursive call has its own `x` local variable. – trincot Dec 29 '19 at 19:45
  • And it's own local variable is always inited as 0. And yes, it needs to go deeper in the beginning. Although it's needed to change to know that he is testing that place on board. – Azevinho Dec 29 '19 at 19:51
  • OH, oh, he is not assigning!!! `copyTab[x] == True` not `copyTab[x] = True` – Azevinho Dec 29 '19 at 19:52
  • Ah now you get it :D Stuart already informed about this 25 minutes ago, lol. All the rest you were saying was really not on the issue... – trincot Dec 29 '19 at 19:52
  • It's now working the code as intended. Main answer edited – Azevinho Dec 29 '19 at 19:59
  • I predict that there are more problems. But I'll let you discuss with the OP. – trincot Dec 29 '19 at 20:00
  • Thanks man, the recursive error is gone now but i am getting other error now :P . I will try to solve those one. – Golden Clips Dec 29 '19 at 20:13
0

The other answer wants to help, but actually you do not need those copies. What you are applying is a do-undo pattern, so you make a step, check the result and undo the step. This can be done without duplicating the tables, but it has to be done prior to returning from inside the loop too. Also, the == = bugs need to be addressed of course

def minimax(table,marktab,points,pos=0):
    #copyTab=table                             # copyTab eliminated
    #copymark=marktab                          # copymark eliminated
    remaining=0
    for x in table:                            # note that this...
        if x==False:
            remaining=remaining+1
    if remaining==0:
        return points,pos
    scores=[None]*remaining
    positions=[None]*remaining
    z=0
    maximum=0
    bestpos=0
    previous=88
    x=0
    while x<9:
        if table[x]==False:                    # ... and this line were referring to table anyway
            if points%2==0:
                table[x]=True                  # now it is table and =
                marktab[x]='O'                 # marktab and =
                result=winning(marktab,'O')
                previous=x
                if result:
                    table[x]=False             # this ...
                    marktab[x]=''              # ... and this undo steps were missing
                    return points ,x
            else:
                table[x]=True                  # table and =
                marktab[x]='X'                 # marktab and =
            scores[z],positions[z]=minimax(table,marktab,points+1,previous) # table and marktab
            z=z+1
            table[x]=False                     # table and =
            marktab[x]=''                      # marktab and =
        x=x+1
    for x in range(0,len(scores)):
        if x==0:
            maximum=scores[x]
            bestpos=positions[x]
        if scores[x]<maximum:
            maximum=scores[x]
            bestpos=positions[x]
    return maximum, bestpos

Then the opponent happily loses, just like with the other fix.

Side remarks

  • marked and markingSignal could use replication, so marked = ['']*9 and markingSignal = [False]*9
  • the %-format expects a tuple on the right side, so instead of the long % (marked[0],...) thing you can simply write % tuple(marked)
  • after getting rid of copyTab and copymark, table and marktab are not really needed to be passed as arguments
  • markingSignal is not really needed anyway, checking table[x]=='' can tell if a field is free or occupied

This solves the recursion problem, however it does not help on the algorithm. See how the pseudo-code looks like on Wikipedia:

function minimax(node, depth, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
        return value
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min(value, minimax(child, depth − 1, TRUE))
        return value

In your code there is a maximum-finding only, let's call it max(scores). You would also need a min(scores) somewhere, depending on which player is considered at the moment, or you can apply the often used "trick" that min(scores) can be done as finding max(-scores), but such "flip" is not present in the code either.

As you say you want to fix it yourself, I just provide the shortened version which contains the suggested simplifications, but otherwise intact (so it loses without hesitation):

import sys

marked=[''] * 9

def printTable():
    print("\t%s|\t%s|\t%s\n------------------------\n\t%s|\t%s|\t%s\n------------------------\n\t%s|\t%s|\t%s\n"%tuple(marked))

def winning(player):
    i=0
    x=0
    while x<3:
        if marked[i]==player and marked[i+1]==player and marked[i+2]==player:
            return True
        x=x+1
        i=i+3    
    x=0
    i=0
    while x<3:
        if marked[2]==player and marked[4]==player and marked[6]==player:
            return True
        x=x+1
        i=i+3  
    x=0
    i=0
    if marked[0]==player and marked[4]==player and marked[8]==player:
        return True
    if marked[2]==player and marked[4]==player and marked[6]==player:
        return True
    return False         

def minimax(points,pos=0):
    remaining=0
    for x in marked:
        if x=='':
            remaining=remaining+1
    if remaining==0:
        return points,pos
    scores=[None]*remaining
    positions=[None]*remaining
    z=0
    maximum=0
    bestpos=0
    previous=88
    x=0
    while x<9:
        if marked[x]=='':
            if points%2==0:
                marked[x]='O'
                result=winning('O')
                previous=x
                if result:
                    marked[x]=''
                    return points ,x
            else:
                marked[x]='X'    
            scores[z],positions[z]=minimax(points+1,previous)
            z=z+1
            marked[x]=''
        x=x+1
    for x in range(0,len(scores)):
        if x==0:
            maximum=scores[x]
            bestpos=positions[x]
        if scores[x]<maximum:
            maximum=scores[x]
            bestpos=positions[x]
    return maximum, bestpos        

def takeInput(player):
    filled=False
    while filled==False:
        print("Enter Your Choice 1-9")
        x=int(input())
        if x>9:
            print("Invalid Choice")
            continue
        if marked[x-1]!='':
            print("This slot is already filled")
            continue
        filled=True    
    marked[x-1]=player

def main():
    printTable()
    count=0
    player='X'
    while count<9:
        if count%2==0:
            player='X'
            takeInput(player)
        else:
            player='O'  
            p,choice=minimax(0)  
            marked[choice]=player
        printTable()
        result=winning(player)
        if result:
            print("\n%s WON !!!\n"%(player))
            break
        count=count+1

main()
tevemadar
  • 12,389
  • 3
  • 21
  • 49