minimax algorith for reversi

[thabo.tman.545]

my code tries to generate a tree for reversi/othello but it runs into an infinite while loop and i am unable to debug it.The purpose of this code is to make minmax algorithm for the aiplayer.please help.

import numpy
board=numpy.array([[0,0,0,0,0,0,0,0],
                   [0,0,0,0,0,0,0,0],
                   [0,0,0,0,0,0,0,0],                  
                   [0,0,0,1,2,0,0,0],                 
                   [0,0,0,2,1,0,0,0],                  
                   [0,0,0,0,0,0,0,0],                  
                   [0,0,0,0,0,0,0,0],                   
                   [0,0,0,0,0,0,0,0]])
matrix_list=[numpy.copy(board)]
points=[]
decoy_list=[]
valid_moves=[[3,5],[5,3],[4,2],[2,4]]
valid_move=[[[3,5],[5,3],[4,2],[2,4]]]
depth=0
#the above assignments is to be provided by riversi game 
while len(valid_move)!=0:
       for t in range(len(matrix_list)):
          value=[0]*len(valid_move[t])
          for z in range(len(valid_move[t])):
              c=matrix_list[t]
              valid_moves=valid_move[t]
              #player one
              if depth%2==0:
                 board=numpy.copy(c)
                 if (valid_moves[z][0])-1!=-1 and (valid_moves[z][1])-1!=-1:
                     if board[valid_moves[z][0]-1][valid_moves[z][1]-1]==2:
                        k=1
                        board[valid_moves[z][0]][valid_moves[z][1]]=1
                        while (valid_moves[z][0]-k)!=-1 and (valid_moves[z][1]-k)!=-1:
                              if board[valid_moves[z][0]-k][valid_moves[z][1]]==2 and board[valid_moves[z][0]][valid_moves[z][1]-k]==2:
                                 board[valid_moves[z][0]-k][valid_moves[z][1]]=1
                                 board[valid_moves[z][0]][valid_moves[z][1]-k]=1
                                 value[z]+=1
                                 decoy_list.append(board)
                              k+=1 
                 if (valid_moves[z][0])-1!=-1 and (valid_moves[z][1])+1!=8:
                     if board[valid_moves[z][0]-1][valid_moves[z][1]+1]==2:
                        k=1
                        board[valid_moves[z][0]][valid_moves[z][1]]=1
                        while (valid_moves[z][0]-k)!=-1 and (valid_moves[z][1]+k)!=8:
                               if board[valid_moves[z][0]-k][valid_moves[z][1]]==2 and board[valid_moves[z][0]][valid_moves[z][1]+k]==2:
                                  board[valid_moves[z][0]-k][valid_moves[z][1]]=1
                                  board[valid_moves[z][0]][valid_moves[z][1]+k]=1
                                  value[z]+=1
                                  decoy_list.append(board)
                               k+=1 
                 if (valid_moves[z][0])+1!=8 and (valid_moves[z][1])+1!=8:
                     if board[valid_moves[z][0]+1][valid_moves[z][1]+1]==2:
                        k=1
                        board[valid_moves[z][0]][valid_moves[z][1]]=1
                        while (valid_moves[z][0]+k)!=8 and (valid_moves[z][1]+k)!=8:
                               if board[valid_moves[z][0]+k][valid_moves[z][1]]==2 and board[valid_moves[z][0]][valid_moves[z][1]+k]==2:
                                  board[valid_moves[z][0]+k][valid_moves[z][1]]=1
                                  board[valid_moves[z][0]][valid_moves[z][1]+k]=1
                                  value[z]+=1
                                  decoy_list.append(board)
                               k+=1 
                 if (valid_moves[z][0])+1!=8 and (valid_moves[z][1])-1!=-1:
                     if board[valid_moves[z][0]+1][valid_moves[z][1]-1]==2:
                        k=1
                        board[valid_moves[z][0]][valid_moves[z][1]]=1
                        while (valid_moves[z][0]+k)!=8 and (valid_moves[z][1]-k)!=-1:
                               if board[valid_moves[z][0]+1][valid_moves[z][1]]==2 and board[valid_moves[z][0]][valid_moves[z][1]-k]==2:
                                  board[valid_moves[z][0]+1][valid_moves[z][1]]=1
                                  board[valid_moves[z][0]][valid_moves[z][1]-k]=1
                                  value[z]+=1
                                  decoy_list.append(board)
                               k+=1    
                 if (valid_moves[z][0])-1!=-1:
                    if board[valid_moves[z][0]-1][valid_moves[z][1]]==2:
                       board[valid_moves[z][0]][valid_moves[z][1]]=1
                       k=1
                       while (valid_moves[z][0]-k)!=-1 and board[valid_moves[z][0]-k][valid_moves[z][1]]==2:
                              board[valid_moves[z][0]-k][valid_moves[z][1]]=1
                              value[z]+=1    
                              k+=1 
                              decoy_list.append(board)
                 if (valid_moves[z][0])+1!=8:
                    if board[valid_moves[z][0]+1][valid_moves[z][1]]==2:
                       k=1
                       board[valid_moves[z][0]][valid_moves[z][1]]=1
                       while (valid_moves[z][0]+k)!=8 and board[valid_moves[z][0]+k][valid_moves[z][1]]==2:
                              board[valid_moves[z][0]+k][valid_moves[z][1]]=1
                              value[z]+=1    
                              k+=1 
                              decoy_list.append(board)
                 if (valid_moves[z][1])-1!=-1:
                     if board[valid_moves[z][0]][valid_moves[z][1]-1]==2:
                        k=1
                        board[valid_moves[z][0]][valid_moves[z][1]]=1
                        while (valid_moves[z][1]-k)!=-1 and board[valid_moves[z][0]][valid_moves[z][1]-k]==2:
                               board[valid_moves[z][0]][valid_moves[z][1]-k]=1
                               value[z]+=1    
                               k+=1
                               decoy_list.append(board)
                 if (valid_moves[z][1])+1!=8:
                     if board[valid_moves[z][0]][valid_moves[z][1]+1]==2:
                        k=1
                        board[valid_moves[z][0]][valid_moves[z][1]]=1
                        while (valid_moves[z][1]+k)!=8 and board[valid_moves[z][0]][valid_moves[z][1]+k]==2:
                               board[valid_moves[z][0]][valid_moves[z][1]+k]=1
                               value[z]+=1    
                               k+=1 
                               decoy_list.append(board)
                 if z==len(valid_move)-1:
                    points.append(value)
#player2
              if depth%2==1:
                 board=numpy.copy(c)
                 if (valid_moves[z][0])-1!=-1 and (valid_moves[z][1])-1!=-1:
                     if board[valid_moves[z][0]-1][valid_moves[z][1]-1]==1:
                        k=1
                        board[valid_moves[z][0]][valid_moves[z][1]]=2
                        while (valid_moves[z][0]-k)!=-1 and (valid_moves[z][1]-k)!=-1:
                              if board[valid_moves[z][0]-k][valid_moves[z][1]]==1 and board[valid_moves[z][0]][valid_moves[z][1]-k]==1:
                                 board[valid_moves[z][0]-k][valid_moves[z][1]]=2
                                 board[valid_moves[z][0]][valid_moves[z][1]-k]=2
                                 value[z]+=1  
                                 decoy_list.append(board)
                              k+=1 
                 if (valid_moves[z][0])-1!=-1 and (valid_moves[z][1])+1!=8:
                     if board[valid_moves[z][0]-1][valid_moves[z][1]+1]==1:
                        k=1
                        board[valid_moves[z][0]][valid_moves[z][1]]=2
                        while (valid_moves[z][0]-k)!=-1 and (valid_moves[z][1]+k)!=8:
                               if board[valid_moves[z][0]-k][valid_moves[z][1]]==1 and board[valid_moves[z][0]][valid_moves[z][1]+k]==1:
                                  board[valid_moves[z][0]-k][valid_moves[z][1]]=2
                                  board[valid_moves[z][0]][valid_moves[z][1]+k]=2
                                  value[z]+=1  
                                  decoy_list.append(board)
                               k+=1 
                 if (valid_moves[z][0])+1!=8 and (valid_moves[z][1])+1!=8:
                     if board[valid_moves[z][0]+1][valid_moves[z][1]+1]==1:
                        k=1
                        board[valid_moves[z][0]][valid_moves[z][1]]=2
                        while (valid_moves[z][0]+k)!=8 and (valid_moves[z][1]+k)!=8:
                               if board[valid_moves[z][0]+k][valid_moves[z][1]]==1 and board[valid_moves[z][0]][valid_moves[z][1]+k]==1:
                                  board[valid_moves[z][0]+k][valid_moves[z][1]]=2
                                  board[valid_moves[z][0]][valid_moves[z][1]+k]=2
                                  value[z]+=1 
                                  decoy_list.append(board)
                               k+=1 
                 if (valid_moves[z][0])+1!=8 and (valid_moves[z][1])-1!=-1:
                     if board[valid_moves[z][0]+1][valid_moves[z][1]-1]==1:
                        k=1
                        board[valid_moves[z][0]][valid_moves[z][1]]=2
                        while (valid_moves[z][0]+k)!=8 and (valid_moves[z][1]-k)!=-1:
                               if board[valid_moves[z][0]+1][valid_moves[z][1]]==1 and board[valid_moves[z][0]][valid_moves[z][1]-k]==1:
                                  board[valid_moves[z][0]+1][valid_moves[z][1]]=2
                                  board[valid_moves[z][0]][valid_moves[z][1]-k]=2
                                  value[z]+=1
                                  decoy_list.append(board)
                               k+=1  
                 if (valid_moves[z][0])-1!=-1:
                     if board[valid_moves[z][0]-1][valid_moves[z][1]]==1:
                        k=1
                        board[valid_moves[z][0]][valid_moves[z][1]]=2
                        while (valid_moves[z][0]-k)!=-1 and board[valid_moves[z][0]-k][valid_moves[z][1]]==1:
                               board[valid_moves[z][0]-k][valid_moves[z][1]]=2
                               value[z]+=1    
                               k+=1 
                               decoy_list.append(board)
                 if (valid_moves[z][0])+1!=8:
                    if board[valid_moves[z][0]+1][valid_moves[z][1]]==1:
                       k=1
                       board[valid_moves[z][0]][valid_moves[z][1]]=2
                       while (valid_moves[z][0]+k)!=8 and board[valid_moves[z][0]+k][valid_moves[z][1]]==1:
                              board[valid_moves[z][0]+k][valid_moves[z][1]]=2
                              value[z]+=1    
                              k+=1 
                              decoy_list.append(board)
                 if (valid_moves[z][1])-1!=-1:
                     if board[valid_moves[z][0]][valid_moves[z][1]-1]==1:
                        k=1
                        board[valid_moves[z][0]][valid_moves[z][1]]=2
                        while (valid_moves[z][1]-k)!=-1 and board[valid_moves[z][0]][valid_moves[z][1]-k]==1:
                               board[valid_moves[z][0]][valid_moves[z][1]-k]=2
                               value[z]+=1    
                               k+=1
                               decoy_list.append(board)
                 if (valid_moves[z][1])+1!=8:
                     if board[valid_moves[z][0]][valid_moves[z][1]+1]==1:
                        k=1
                        board[valid_moves[z][0]][valid_moves[z][1]]=2
                        while (valid_moves[z][1]+k)!=8 and board[valid_moves[z][0]][valid_moves[z][1]+k]==1:
                               board[valid_moves[z][0]][valid_moves[z][1]+k]=2
                               value[z]+=1    
                               k+=1 
                               decoy_list.append(board)
                 if z==len(matrix_list)-1:
                    points.append(value)
      matrix_list=decoy_list[:]
      decoy_list=[]
      valid_move=[]
      for x in range(len(matrix_list)):
         valid_moves=[]
         for i in range(8):
              for j in range(8):
                  #valid_moves-valid_move for player 1
                  if depth%2==1:
                     if board[i][j]==2:
                        if i-1!=-1 and j-1!=-1:
                           if i+1!=8 and j+1!=8:
                              if board[i-1][j]==1 and board[i+1][j]==0:
                                 valid_moves.append([i+1,j])
                              if board[i][j+1]==1 and board[i][j-1]==0:
                                 valid_moves.append([i,j-1])
                              if board[i+1][j]==1 and board[i-1][j]==0:
                                 valid_moves.append([i-1,j])
                              if board[i][j-1]==1 and board[i][j+1]==0:
                                 valid_moves.append([i,j+1])
                              if board[i-1][j+1]==1 and board[i+1][j-1]==0:
                                 valid_moves.append([i+1,j-1])
                              if board[i+1][j-1]==1 and board[i-1][j+1]==0:
                                 valid_moves.append([i-1,j+1])
                              if board[i-1][j-1]==1 and board[i+1][j+1]==0:
                                 valid_moves.append([i+1,j+1])
                              if board[i+1][j+1]==1 and board[i-1][j-1]==0:
                                 valid_moves.append([i-1,j-1])

#valid_moves-valid_move for player 2
                  if depth%2==0:
                     if board[i][j]==1:
                         if i-1!=-1 and j-1!=-1:
                            if i+1!=8 and j+1!=8:
                               if board[i-1][j]==2 and board[i+1][j]==0:
                                  valid_moves.append([i+1,j])
                               if board[i][j+1]==2 and board[i][j-1]==0:
                                  valid_moves.append([i,j-1])
                               if board[i+1][j]==2 and board[i-1][j]==0:
                                  valid_moves.append([i-1,j])
                               if board[i][j-1]==2 and board[i][j+1]==0:
                                  valid_moves.append([i,j+1])
                               if board[i-1][j+1]==2 and board[i+1][j-1]==0:
                                  valid_moves.append([i+1,j-1])
                               if board[i+1][j-1]==2 and board[i-1][j+1]==0:
                                  valid_moves.append([i-1,j+1])
                               if board[i-1][j-1]==2 and board[i+1][j+1]==0:
                                  valid_moves.append([i+1,j+1])
                               if board[i+1][j+1]==2 and board[i-1][j-1]==0:
                                  valid_moves.append([i-1,j-1])
         valid_move.append(valid_moves)
      print len(valid_move)
      print len(matrix_list)
      depth+=1

[Hiroshe]

It would be nice to see the output so we can see the size of valid_mode.

It's kind of hard to tell whats going on with that spacing, but my guess it that your always appending one thing onto valid_move with each iteration. This is flagged by the line valid_move.append(valid_moves), which guarentees that valid_move is always of length 1.

Also, is valid_move always the exact same as valid_moves except for the fact that your incapsolating your list inside a list of length 1? You can probably drop valid_move all togeather.

[woooee]

it runs into an infinite while loop and i am unable to debug it.

Add print statements so you know where it is and what the variables contain.

Instead of testing for i-1!= -1 (which is the first pass of the for loop) and i/j+1 != 8 (which happen on the final loop pass) just set the for loop to range(1, 7) for "i", "j" or both.

         for i in range(8):
              for j in range(8):
                  #valid_moves-valid_move for player 1
                  if depth%2==1:
                     if board[i][j]==2:
                        if i-1!=-1 and j-1!=-1:
                           if i+1!=8 and j+1!=8:

Also, what happens when i-1 is -1 and j is not

if board[i-1][j]==1 and board[i+1][j]==0:

you access the [-1][j] element which may or may not be allowed depending on how the -1 is used, but is probably not what you want. Start with a simplier program and test it as you go along.