# Problem with Minimax algorythm in Panda 3d

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

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

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

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

I’m glad that you got it working!

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