I'm given a state of a Tic-Tac-Toe game. It is a n*n game and the winner is the person who can have "a" number of consecutive X or Os (which a is also given). I should predict weather X or O can win in next state of the game. for example if the state is like this:
X X O X O
X O X O X
O X O - -
- - - - -
X O X O X
the output is:
O
I have problem with the diagonal checking. I wrote a code.
X = 'X'
O = 'O'
DASH = '-'
def o_left_diagonal_checker_winner(game_board, n, a):
x_counter = 0
for j in range(n):
for i in range(1, n):
if i - 1 >= 0 and n - i >= 0:
if game_board[i - 1][n - i] == X:
x_counter += 1
if n - i - 2 >= 0 and i - 2 >= 0 and x_counter == a - 1 and game_board[n - i - 2][i - 2] == DASH:
return O
else:
x_counter = 0
this part of code will check the game from left top to right. but it doesn't work. If you have better algorithm please tell me and I can't use libraries.
Consider this alternative solution.
Given that you have an array representing your game board. With values +1,-1,0 for the different states of each position. Then take a d*d size sub array and do a sum along the diagonals. rows and columns. If any value = -2 or 2 then the player +1 or -1 has a chance to win in the next state. d would be the size of your array. Here is an example for a 5*5 board with win condition of 3. So simply masking the board with the win possibilities will predict the next winner.
import numpy as np
board = np.array([[-1., -1., 1., 1., -1.],
[-1., 0., 0., 0., 0.],
[ 0., 0., 0., 0., 1.],
[ 0., 0., 0., 0., 0.],
[ 0., 0., 0., 0., 0.]])
win_length = 3
#lets assume +1 = X, -1 = 0 and 0 = nothing
# Also assume that X always starts
# You could also simply replace priority with who is moving next
def who_wins_next(board,a):
priority = sum(sum(board))
if priority >0: # If else case to automatically determine who is moving next. Alternatively you can add another input to who is moving next to replace this
target = 2
text = "X (1)"
else:
target = -2
text = "O (-1)"
width,height = board.shape
for i in range(width-a+1):
for j in range(height-a+1):
sub = board[i:i+a,j:j+a]
diagonal_forward = sum(sub[i][i] for i in range(a))
diagonal_backward = sum(sub[i][a-i-1] for i in range(a))
row_sums = np.sum(sub,axis=1) #Using numpy sum with axis to get an array of row sums
col_sums = np.sum(sub,axis=0) # Likewise for columns
if diagonal_forward == target or diagonal_backward == target or target in list(row_sums) or target in list(col_sums):
#Only need to know if win is possible. Not how.
return text + " can win in next step"
return text + " cannot win in next step"