I am trying to make a tic tac toe minimax algorithm. In some scenarios, my algorithm is outputting blatantly wrong moves.
For example, in the following board state, X is to move:
X . .
. O .
. . .
and the optimal move should be the bottom corner, but for some reason the algorithm outputs the top middle.
I have not been able to recognize a pattern on when it is wrong and right. I suspect I either have a simple syntax error or my entire approach is incorrect.
Disclaimer: I am extremely new to programming.
Here is my full script.
My approach is to find all possible moves and return the one with the highest value (topLevelSearch()
). topLevelSearch()
calls moveSearch()
to evaluate each move from the opponents perspective and returns the negative of the opponent's value, recursively calling itself when needed.
def moveSearch(board, player) :
#printBoard(board)
if abs(checkWin(board)) == 1 :
return checkWin(board) * player * -1
elif checkWin(board) == 0:
return 0
elif checkWin(board) == 2 :
moveList = array('i', [])
i = 0
while i < 9 :
if board[i] == 0 :
moveList.append(i)
i += 1
j = 0
valueList = array('f', [0] * len(moveList))
while j < len(moveList) :
board[moveList[j]] = player
valueList[j] = moveSearch(board, -1 * player)
board[moveList[j]] = 0
j += 1
return max(valueList) * -1
def topLevelSearch(board, player) :
printBoard(board)
if abs(checkWin(board)) == 1 :
return
elif checkWin(board) == 0:
return
elif checkWin(board) == 2 :
moveList = array('i', [])
i = 0
while i < 9 :
if board[i] == 0 :
moveList.append(i)
i += 1
j = 0
valueList = array('f', [0] * len(moveList))
while j < len(moveList) :
board[moveList[j]] = player
valueList[j] = moveSearch(board, -1 * player)
board[moveList[j]] = 0
j += 1
bestMove = moveList[valueList.index(max(valueList))]
return bestMove
I have walked through my code so many times in my head, and can't find the error in the logic. I can't find a pattern in when it is right and wrong.
You already solved the problem mentioned in comments (the order of checking a draw with respect to checking for a win).
You mention about this state, where X is to move:
X . .
. O .
. . .
...that the optimal move for X is to move in the bottom corner. But fact is that in this state all moves for X lead to a draw when the game continues with best play, and so they are equally "good". Also the mid-upper move (that the algorithm produces) is fine:
X X .
. O .
. . .
This game will continue with four forced moves:
X X O X X O X X O X X O
. O . => . O . => O O . => O O X
. . . X . . X . . X . .
and will end in a draw.
The corner move might look interesting (because O should not make the mistake to play in a corner):
X . .
. O .
. . X
...but best play is for O to play at a side, and then the rest is a forced game towards a draw:
X O . X O . X O . X O X X O X X O X
. O . => . O . => . O . => . O . => . O O => X O O
. . X . X X O X X O X X O X X O X X
So either way, it is a draw. There is no "more" optimal move.