i am struggling to see how my minimax algorithm is not working. It cycles through all the best moves but it dosen't pick the best one and i can't figure out why. For example i can input 1 5 9 and win. sorry in advance if the solution is something simple Here is the code.
board = {1: ' ', 2: ' ', 3: ' ',
4: ' ', 5: ' ', 6: ' ',
7: ' ', 8: ' ', 9: ' '}
win = False
turn = 1
depth = 1
nodeindex = 0
possibles= []
moves = []
depth = 0
targetdepth = 3
movesdone = []
#def minimax(moves, targetdepth, depth, turn, scores):
def checkForWin(mark):
if board[1] == board[2] and board[1] == board[3] and board[1] == mark:
return True
elif (board[4] == board[5] and board[4] == board[6] and board[4] == mark):
return True
elif (board[7] == board[8] and board[7] == board[9] and board[7] == mark):
return True
elif (board[1] == board[4] and board[1] == board[7] and board[1] == mark):
return True
elif (board[2] == board[5] and board[2] == board[8] and board[2] == mark):
return True
elif (board[3] == board[6] and board[3] == board[9] and board[3] == mark):
return True
elif (board[1] == board[5] and board[1] == board[9] and board[1] == mark):
return True
elif (board[7] == board[5] and board[7] == board[3] and board[7] == mark):
return True
else:
return False
def checkForWin2():
if (board[1] == board[2] and board[1] == board[3] and board[1] != ' '):
return True
elif (board[4] == board[5] and board[4] == board[6] and board[4] != ' '):
return True
elif (board[7] == board[8] and board[7] == board[9] and board[7] != ' '):
return True
elif (board[1] == board[4] and board[1] == board[7] and board[1] != ' '):
return True
elif (board[2] == board[5] and board[2] == board[8] and board[2] != ' '):
return True
elif (board[3] == board[6] and board[3] == board[9] and board[3] != ' '):
return True
elif (board[1] == board[5] and board[1] == board[9] and board[1] != ' '):
return True
elif (board[7] == board[5] and board[7] == board[3] and board[7] != ' '):
return True
else:
return False
def possiblemoves(board):
y=0
possibles.clear()
for i in board:
if board[i] == " ":
possibles.append(i)
return possibles
def botgo(possibles, mark):
bestscore = -800
bestmove = 0
for key in board.keys():
if (board[key] == ' '):
board[key] = mark
score = minimax(board,0,False)
board[key] = ' '
if(score > bestscore):
bestscore = score
bestmove = key
insert(bestmove,mark='O')
return
def printboard():
print(board[1] + '|' + board[2] + '|' + board[3])
print('-----')
print(board[4] + '|' + board[5] + '|' + board[6])
print('-----')
print(board[7] + '|' + board[8] + '|' + board[9])
def start():
turn = 1
count = 0
while count != 9:
humango()
printboard()
possiblemoves(board)
botgo(possibles, mark='O')
printboard()
count = count + 1
#minimax(depth, possibles)
def spacefree(space):
if board[space] == ' ':
return True
else:
return False
def insert(space, mark):
if spacefree(space):
board[space]=mark
if checkForWin(mark):
if mark == 'X':
printboard()
print("human win")
exit()
else:
printboard()
print("BOT WIN")
exit()
else:
print("cannot insert there!!!")
space = int(input("Enter position"))
insert(space, mark)
def checkdraw(board):
if checkForWin2():
return True
def humango():
global turn
space = int(input("Enter position"))
insert(space, mark='X')
turn = turn + 1
printboard()
def minimax(board, depth, ismax):
if checkForWin(mark='O'):
return 1
elif checkForWin(mark='X'):
return -1
elif checkdraw(board):
return 0
if ismax == True:
bestscore = -800
for key in board.keys():
if (board[key] == ' '):
board[key] = 'O'
score = minimax(board, depth + 1, False)
board[key] = ' '
if (score > bestscore):
bestscore = score
printboard()
return bestscore
else:
bestscore = 800
for key in board.keys():
if (board[key] == ' '):
board[key] = 'X'
score = minimax(board, depth + 1, True)
board[key] = ' '
if (score < bestscore):
bestscore = score
return bestscore
start()
sorry for the messy code, thank you in advance
It seems you are complicating things, it will be much easier for you to debug with less code to look at. I would first suggest that you use a list instead of a dict to simplify your code in this game: board = [' ']*9. All my suggestions/simplifications below are based on this representation.
1.. Checking for win on a 1D board is super easy. First you create a variable with all the possible winning lines:
winning_lines = ([0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6])
Then you can loop through them with a loop:
def is_win(board, player):
for pos in winning_lines:
if board[pos[0]] == board[pos[1]] == board[pos[2]] == player:
return 1
2.. Checking for draw is even simpler since you only need to check if there are empty spaces or not:
def is_draw(board):
return 0 if ' ' in board else 1
3.. You don't need the depth variable in this game since you always go to maximum depth, ending in win, draw or loss. The depth can be used to always chose the shortest path to winning if there are more than 1 path, or the longest path to loss. Then you need to add and subtract depth from your check_win return statements in the minimax loop.
4.. You can get all the possible moves with list comprehension:
possible_moves = [i for i in range(len(board)) if board[i] == ' ']
Debugging
There are a few other clean ups to do, but to figure out why it gives the wrong answer you need to do some debugging. Does your win/draw/loss function work as you think it does, i.e. does it return the correct result for a known input board? Does it loop through all the possible moves? Print things in your minimax loop and see if it behaves as you would expect.