Problem with Minimax algorythm in Panda 3d

Scripting Issues
1

Hi, I’m implementing the minimax algorythm to my Panda3d Tic-Tac-Toe game, and have a problem.
I have exacly the same method for a game in system console and it works great.

The problem is that my win checking functions are not returning True when filling the board with marks for computer playing with himself. I don’t know what is causing it, maybe the loop is working differently in MyApp class??? i don’t really know.

I’m new to programming so don’t know really what can cause it.
“BoardSize” is the variable defining the size of the board (3 or 4). So when is set to 3, It doesn’t check
the entire 4x4 board.
BoardList is the board made of four lists. It is outside the MyApp class but It doesn’t really matter.

Board0=['','','',''] 
Board1=['','','','']
Board2=['','','','']
Board3=['','','','']

BoardList=[Board0,Board1,Board2,Board3]

Here is the computer move and minimax function code:
(I’m sorry for naming functions with a big letter, I’ll fix that later :slight_smile:

    def computer(self, max_depth):
        
        self.max_score=-1000
        self.best_moveR = 0
        self.best_moveC = 0
        self.random_moveR = random.randint(0, self.BoardSize-1) 
        self.random_moveC = self.random_moveR 
        
        for n in range(0,self.BoardSize):
            for i in range(0,self.BoardSize):
                if BoardList[n][i]=='':
                    BoardList[n].pop(i)
                    BoardList[n].insert(i,'o')
                    self.score = self.minimax(0,False,max_depth)
                    BoardList[n].pop(i)
                    BoardList[n].insert(i,'')
                    if (self.score > self.max_score):
                        self.max_score = self.score
                        self.best_moveR = n
                        self.best_moveC= i
                        print(self.best_moveR)
                        print(self.best_moveC)

            
        self.insertLetter('o', self.best_moveR,self.best_moveC)
        
                               
             
        return self.best_moveR,self.best_moveC
  
    
    def minimax(self, depth, isMaximizing,max_depth):
        

   
        if (self.HorizontalWinC('o') or self.PlayerWinsVC('o') or self.PlayerWinsD1C('o') or self.PlayerWinsD2C('o')):
            return 1
             
        if (self.HorizontalWinC('x') or self.PlayerWinsVC('x') or self.PlayerWinsD1C('x') or self.PlayerWinsD2C('x')): 
            return -1
        
        if (self.DrawC('o') or self.DrawC('x') or depth==max_depth):
            return 0
            
        if isMaximizing:
            self.max_score = -1000
            
            for n in range(0,self.BoardSize):
                for i in range(0,self.BoardSize):
                    if BoardList[n][i]=='':
                        BoardList[n].pop(i)
                        BoardList[n].insert(i,'o')
                        self.score = self.minimax(depth+1,False,max_depth)
                        BoardList[n].pop(i)
                        BoardList[n].insert(i,'')
                        if (self.score > self.max_score):
                            self.max_score = self.score
            return self.max_score
            
        else:
            self.max_score = 800
            for n in range(0,self.BoardSize):
                for i in range(0,self.BoardSize):
                    if BoardList[n][i]=='':
                        BoardList[n].pop(i)
                        BoardList[n].insert(i,'x')
                        self.score = self.minimax(depth+1,True,max_depth)
                        BoardList[n].pop(i)
                        BoardList[n].insert(i,'')
                        if (self.score < self.max_score):
                            self.max_score = self.score
            return self.max_score

Here are the win check functions:

    def HorizontalWinC(self,mark):
        for i in range(0,self.BoardSize):
            print(BoardList[i].count(mark))
            #checking horizontal win
            if BoardList[i].count(mark)==self.BoardSize:
                return True
    #vertical win    
    def PlayerWinsVC(self,mark):
        for i in range(0,self.BoardSize):
            self.VC[mark][i]=0
            
        for i in range(0,self.BoardSize):
            #counting marks x or o in vertical lines
            for n in range(0,self.BoardSize):
                
                if BoardList[n][i]==mark:
                    self.VC[mark][i]+=1
                    print('VC'+str(self.VC))
        
        for i in range(0,self.BoardSize):
            if self.VC[mark][i]==self.BoardSize:
                return True
    #diagonal win 1        
    def PlayerWinsD1C(self,mark):
        self.D1C[mark]=0
        
        for i in range(0,self.BoardSize):
            if BoardList[i][i]==mark:
                self.D1C[mark]+=1 
                print('D1C'+str(self.D1C))
        if self.D1C[mark]==self.BoardSize:
            return True
    #diagonal win 2    
    def PlayerWinsD2C(self,mark):    
        self.D2C[mark]=0   
        
        for i in range(0,self.BoardSize):
            if BoardList[self.BoardSize-1-i][i]==mark:
                self.D2C[mark]+=1 
                print('D2C'+str(self.D2C)) 
        if self.D2C[mark]==self.BoardSize:
            return True 
    
    def DrawC(self,mark):
        self.D1DrawC[mark]=False
        self.D2DrawC[mark]=False
        for i in range(0,self.BoardSize):
            self.VC[mark][i]=0
        #diagonal draw 1
        for i in range(0,self.BoardSize):
            if BoardList[i][i]==mark:
                self.D1DrawC[mark]=True  
                print('D1DrawC',self.D1DrawC)
        
        
        #diagonal draw 2
        for i in range(0,self.BoardSize):
            if BoardList[self.BoardSize-1-i][i]==mark:
                self.D2DrawC[mark]=True 
                print('D2DrawC',self.D2DrawC)
        
        
        self.VDrawCountC=0
        self.HDrawCountC=0
        #vertical draw
        for i in range(0,self.BoardSize):
            if self.VC['x'][i]>=1 and self.VC['o'][i]>=1:
                self.VDrawCountC+=1
                print('VDrawCountC',self.VDrawCountC)
        #horizonal draw

        for i in range(0,self.BoardSize):
            if BoardList[i].count('x')>=1 and BoardList[i].count('o')>=1:
                self.HDrawCountC+=1
                print('HDrawCountC',self.HDrawCountC)
        
        #draw conditions
        if (self.D1DrawC['x']==True and self.D1DrawC['o']==True
            and self.D2DrawC['x']==True and self.D2DrawC['o']==True
            and self.VDrawCountC==self.BoardSize
            and self.HDrawCountC==self.BoardSize):      
            return True
2

Hmm… Well, it’s hard to be confident that this is a problem without a more-thorough check, but I do notice something:

In both your “computer” and “minimax” functions, you alter the instance-variable “self.score”. (In case you’re unfamiliar with the term, “instance variable” refers to a variable that belongs to a given instance of a class, and that is available from anywhere within that instance.)

That is, while the “minimax” function is running, it’s altering the variable that the “computer” function makes use of, potentially producing unexpected results.

If your console-based version of the game was not object-oriented, then it’s possible that you weren’t using the “self.” syntax. As a result, the “score” variables in the two functions would have been two individual variables, rather than a single shared variable, thus perhaps producing different behaviour.

You’re also doing something similar with “self.maxScore”.

Looking at the win-checking functions themselves, and specifically at one of the simplest of them (the horizontal check), I don’t see an obvious problem. Have you tested them specifically by calling them from outside of your minimax algorithm, providing a board that you know contains a win?

By the way, I see that you’re popping values from your lists and immediately inserting new values in their places. If I’m understanding the behaviour of that correctly, then you should be able to do the same thing with just an assignment, like so:

# Instead of...
myList.pop(i) #-the Sailor Man ;P
myList.insert(i, newVal)

# you should be able to do this:
myList[i] = newVal
3

Thank you! I changed the “score” variables names, and It works much better.
In 4x4 board the bot is unbeatable, however on 3x3 it acts a bit strange. In some cases it let’s me win.
I need to dive into the code again, maybe there is an repeated value as well.

1 Like
4

I’m glad that you got it working! :slight_smile:

Let me clarify, if I may:

For variables that only need to exist within a given function, you can use “local variables” instead of “instance variables”. Simply put, a “local variable” is only valid within the function within which it is declared, and will not collide with variables in other functions that have the same name.

This can be done simply by omitting the “self.”. Like so:

class MyClass():
    def __init__(self):
        # This is an instance variable--note the "self."
        self.cat = "kitty"

    def someFunction(self):
        # Because "cat" is an instance variable, we can access it here
        print (self.cat)

        # This, on the other hand, is a local variable
        mew = "meow"

        # We can access it here, since we're still within the
        # same function...
        print (mew)

    def someOtherFunction(self):
        # ... But we can't access it here, because we're
        # no longer within the same function
        print (mew) # Should produce an error!

        # Conversely, we can create a new local variable 
        # here with the same name, since the previous
        # local variable isn't valid here.
        # One should not affect the other!
        mew = "purr"
        print (mew) # Should now work--but prints "purr", not "mew"!