Well that was a question that I asked myself.
I was inspired by this blogpost: http://neverstopbuilding.com/minimax
Without much further ado, Here's the algorithm. (I have strived to explain, what's going at every step in the form of comments)
First of all, we need to establish a function, such that when given a board, we determine if either 'X' or 'O' won.
In my case, I assume any n * n board and all unfilled spots in the board are shown as '-'
So an empty 3 * 3 board would look like this:
[['-', '-', '-'], ['-', '-', '-'], ['-', '-', '-']]
def win(board):
# look for horizontal, vertical and diagonal matches
size = len(board)
count = 0
criss = []
cross = []
for i in board:
curr_row = []
curr_col = []
for j in range(0, len(i)):
if board[count][j] != '-':
# horizontal
curr_row.append(board[count][j])
if board[j][count] != '-':
# vertical
curr_col.append(board[j][count])
if (count == j):
# top-left to bottom-right diagonal
if board[count][j] != '-':
criss.append(board[count][j])
if ((count + j + 1)) == size:
# top-right to bottom-left diagonal
if board[count][j] != '-':
cross.append(board[count][j])
count = count + 1
if len(curr_row) == size:
if set(curr_row) == {'X'}:
return 'X'
elif set(curr_row) == {'O'}:
return 'O'
if len(curr_col) == size:
if set(curr_col) == {'X'}:
return 'X'
elif set(curr_col) == {'O'}:
return 'O'
if len(criss) == size:
if set(criss) == {'X'}:
return 'X'
elif set(criss) == {'O'}:
return 'O'
if len(cross) == size:
if set(cross) == {'X'}:
return 'X'
elif set(cross) == {'O'}:
return 'O'
Now, that was more or less straight forward. Coming to the interesting part, the recursive move function.
def move(board, player):
'''
:param board - a list of lists, such that its a square matrix
:param player - The current player 'X' or 'O'
returns a tuple
if the player is 'X', and is in winning position,
then we return (1, next_position_to_play)
eg: (1, (2, 2))
if the player is 'X', and is in a position to draw at best,
then we return (0, next_position_to_play)
eg: (0, (1, 1))
if the player is 'O', and is in winning position,
then we return (-1, next_position_to_play)
eg: (-1, (2, 1))
if the player is 'O', and is in a position to draw at best,
then we return (0, next_position_to_play)
eg: (0, (1, 0))
if the board is full, we return the game as drawn.
eg: (0, -1)
'''
size = len(board) * len(board)
# size is total number of spots on the board
count = 0
i_count = 0
for i in board:
for j in range(0, len(i)):
if board[i_count][j] == '-':
count = count + 1
i_count = i_count + 1
if count == size:
# The board is empty, and there are tons of choices to make
# but its probably a safe bet, to get the center spot.
return 0, (len(board)/2, len(board)/2)
if count == 0:
# Full Board
return 0, -1
nextplayer = 'O' if player == 'X' else 'X'
winner = win(board)
if winner == 'X':
# if the winner is X, then current player is 'O'
# But does it lead to a winning situation for 'X'? Yes
# return +1, -1
# we are maximizing for X (+1), and -1 since game is over
return 1, -1
elif winner == 'O':
# if the winner is O, then current player is 'X'
# But does it lead to a winning situation for 'O'? Yes
# return -1, -1
# we are minimizing for O (-1), and -1 since game is over
return -1, -1
list_indexes = []
res_list = []
i_count = 0
for i in board:
for j in range(0, len(i)):
if board[i_count][j] == '-':
list_indexes.append((i_count,j))
i_count = i_count + 1
# list_indexes contains all the indexes where element is '-'
for position in list_indexes:
i, j = position
# Go through every empty position on the board, and
# assign the current player to it.
board[i][j] = player
# recursively call move on the current board,
# after we filled one more spot.
# with the player parameter of move being the nextplayer
ret, _ = move(board, nextplayer)
# Remember, ret could be -1, 0 or 1.
res_list.append(ret)
# important to go back and mark postion tried as '-' again.
board[i][j] = '-'
if player == 'X':
# We are maximizing for X (remember note from earlier).
# we return 1 if X is in a winning position. if there is a
# winning position, we find the (first occurence) index of
# the 1, and use that as index on list_indexes.
# if not, most likely all of res_list is just zeros,
# so will just pick list_indexes[0] to be our next move.
max_elem = max(res_list)
return max_elem, list_indexes[res_list.index(max_elem)]
else:
# We are minimizing for O (remember note from earlier).
# We look for -1 in res_list, find its index, and use that
# index on list_indexes.
# if not, most likely all of res_list is just zeros,
# so will just pick list_indexes[0] to be our next move.
min_elem = min(res_list)
return min_elem, list_indexes[res_list.index(min_elem)]
Phew, that took some time to figure out.
Now lets test it out.
In [3]: move([['-','-','-'],['-','-','-'],['-','-','-']],'X')
Out[3]: (0, (1, 1))
In [4]: move([['-','-','-'],['-','X','-'],['-','-','-']],'O')
Out[4]: (0, (0, 0))
In [5]: move([['O','-','-'],['-','X','-'],['-','-','-']],'X')
Out[5]: (0, (0, 1))
In [6]: move([['O','X','-'],['-','X','-'],['-','-','-']],'O')
Out[6]: (0, (2, 1))
In [7]: move([['O','X','-'],['-','X','-'],['-','O','-']],'X')
Out[7]: (0, (1, 0))
In [8]: move([['O','X','-'],['X','X','-'],['-','O','-']],'O')
Out[8]: (0, (1, 2))
In [9]: move([['O','X','-'],['X','X','O'],['-','O','-']],'X')
Out[9]: (0, (0, 2))
In [10]: move([['O','X','X'],['X','X','O'],['-','O','-']],'O')
Out[10]: (0, (2, 0))
In [11]: move([['O','X','X'],['X','X','O'],['O','O','-']],'X')
Out[11]: (0, (2, 2))
In [12]: move([['O','X','X'],['X','X','O'],['O','O','X']],'O')
Out[12]: (0, -1)
And it ends in a draw!
Hopefully, That was interesting.
I'm documenting the algorithms I work on here: https://github.com/sriram-mv/108