Simplest possible Tic Tac Toe AI in Python

Question

Last week I challenged myself to create the smallest possible code for a Tic Tac Toe game with an AI as opponent. Smallest possible in regards to say least number of characters used. The requirements on the game are as follows:

• A "nice" playing experience (ability to get user input and print the board after every move)
• Handling wrong input data without crashing.
• Having an unbeatable AI as opponent.
• The ability to play again or exit after game is over

The result is this code:

def p(b):
 c = [' ' if i == 0 else 'X' if i == -1 else 'O' if i == 1 else i for i in b]
 [print(f'\n{c[r*3:3+r*3]}') if r == 0 else print(c[r*3:3+r*3]) for r in range(3)]
def e(b, t):
 for p in ([0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]):
 if b[p[0]] == b[p[1]] == b[p[2]] == t: return 1
def n(b, d, t):
 if e(b, t): return 0, (9+d)
 if e(b, -t): return 0, -(9 + d)
 if 0 not in b: return 0, 0
 x = -20
 for m in [i for i in range(9) if not b[i]]:
 b[m] = t
 s = -n(b, d - 1, -t)[1]
 b[m] = 0
 if s > x: x, y = s, m
 return y, x
def r():
 b, w = [0]*9, -1
 p(b)
 while 1:
 if w == -1 and not (e(b, w) or e(b, -w)) and 0 in b:
 while 1:
 u = input('\nPlease enter your move (1-9): ')
 if u.isnumeric():
 u = int(u)-1
 if 0 <= u < 9 and not b[u]:
 b[u], w = -1, w*-1
 p(b)
 break
 elif w == 1 and not (e(b, w) or e(b, -w)) and 0 in b:
 m, s = n(b, 8, 1)
 b[m], w = 1, w*-1
 p(b)
 else:
 f = 'You won!' if e(b, -1) else 'AI won!' if e(b, 1) else 'Game drawn!'
 if input(f'\n{f} Do you want to play again (y/n)? ') != 'y': break
 r()
 break
r()

And with a bit of commentary to easier understand what is going on:

# Printing the board on the "standard" format with X:s and O:s instead of -1, 0, 1. 
def print_board(board):
 new_board = [' ' if i == 0 else 'X' if i == -1 else 'O' if i == 1 else i for i in board]
 [print(f'\n{new_board[row*3:3+row*3]}') if row == 0 else print(new_board[row*3:3+row*3]) for row in range(3)] # Print with new line to get nicer format
 
# Evaluates the board
def evaluate(board, turn):
 for pos in ([0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]): # Go through all possible winning lines
 if board[pos[0]] == board[pos[1]] == board[pos[2]] == turn: return 1 # Return 1 if player turn has 3 in a row
# Recursive negamax function which goes through the entire game tree.
# Depth d is used in the returned scores to get shortest possible route to victory. 
def negamax(board, depth, turn):
 if evaluate(board, turn): return 0, (9+depth) # Return positive score if maximizing player
 if evaluate(board, -turn): return 0, -(9 + depth) # Return negative score if minimizing player wins
 if 0 not in board: return 0, 0 # Drawn game, return 0
 best_score = -20 # Initiate with less than smallest possible score
 for move in [i for i in range(9) if not board[i]]: # Go through all empty squares on board
 board[move] = turn # Make move
 score = -negamax(board, depth - 1, -turn)[1] # Recursive call to go through all child nodes
 board[move] = 0 # Unmake the move
 if score > best_score: best_score, best_move = score, move # If score is larger than previous best, update score
 return best_move, best_score # Return the best move and its corresponding score
# Main game loop.
def run():
 board, turn = [0]*9, -1 # Initiate board and turn to move (-1 is human to start, 1 AI to start)
 print_board(board)
 while 1: # Loop until game is over
 if turn == -1 and not (evaluate(board, turn) or evaluate(board, -turn)) and 0 in board: # Human turn if game is not over and there are places left on board
 while 1: # Loop until a valid input is given
 user_input = input('\nPlease enter your move (1-9): ') # Get input
 if user_input.isnumeric(): # Find if a number is entered
 u = int(user_input)-1 # Get it on the right board format (square 1 corresponds to array[0])
 if 0 <= u < 9 and not board[u]: # Check if number is in the correct range and on an empty square
 board[u], turn = -1, turn*-1 # Make move and change turn
 print_board(board)
 break
 elif turn == 1 and not (evaluate(board, turn) or evaluate(board, -turn)) and 0 in b: # Ai turn if game is not over and there are places left on board
 move, score = negamax(board, 8, 1) # Run Negamax loop to get a best move and the score
 board[move], turn = 1, turn*-1 # Make move and change turn
 print_board(board)
 else: # This means the game is over or board is full
 text = 'You won!' if evaluate(board, -1) else 'AI won!' if evaluate(board, 1) else 'Game drawn!' # Check who won or if there is a draw
 if input(f'\n{text} Do you want to play again (y/n)? ') != 'y': break # Ask to play again, break if answer is not 'y'
 run() # Run game again if answer is 'y'
 break
run() # Run the game loop

My question is if there are any other approaches that are simpler in terms of number of characters for a functioning game with the given requirements above? Of course the input/output text to console can be shorter, but I think that doesn't count :)

In terms of readability and PEP 8 style there are of course lots of things to improve, I wanted to keep the code to a reasonable minimum of lines.

I hope this type of question is allowed here, otherwise please remove it.

EDIT: Example game as proposed by user "superb rain" in the comments:

[' ', ' ', ' ']\
[' ', ' ', ' ']\
[' ', ' ', ' ']
Please enter your move (1-9): 5
[' ', ' ', ' ']\
[' ', 'X', ' ']\
[' ', ' ', ' ']
['O', ' ', ' ']\
[' ', 'X', ' ']\
[' ', ' ', ' ']
Please enter your move (1-9): 4
['O', ' ', ' ']\
['X', 'X', ' ']\
[' ', ' ', ' ']
['O', ' ', ' ']\
['X', 'X', 'O']\
[' ', ' ', ' ']
Please enter your move (1-9): 2
['O', 'X', ' ']\
['X', 'X', 'O']\
[' ', ' ', ' ']
['O', 'X', ' ']\
['X', 'X', 'O']\
[' ', 'O', ' ']
Please enter your move (1-9): 3
['O', 'X', 'X']\
['X', 'X', 'O']\
[' ', 'O', ' ']
['O', 'X', 'X']\
['X', 'X', 'O']\
['O', 'O', ' ']
Please enter your move (1-9): 9
['O', 'X', 'X']\
['X', 'X', 'O']\
['O', 'O', 'X']
Game drawn! Do you want to play again (y/n)? 

• Graipher: We cannot really help you in reducing the number of characters needed. That would be code-golfing and is something we have decided we can not really do here. However, there is our sister site Code Golf, which also has a nice guide on some general tips on golfing Python.
• theProgrammer: I find it hard to review code with one letter variables everywhere. You might want to consider using clear, concise names.
• eligolf: @theProgrammer, I totally understand, I did it to save on characters to get a measurement of "minimal". The commented version is now updated with better naming, sorry if I missed a place or made any typo.
• pacmaninbw: Please don't update the question after it has been answered, everyone needs to see what the reviewer saw. Please read What should I do when someone answers?.
• eligolf: @pacmaninbw, I put an EDIT in there so it should be clear to everyone I think.

Answer 1

Your

def evaluate(board, turn):
 for pos in ([0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]):
 if board[pos[0]] == board[pos[1]] == board[pos[2]] == turn: > return 1

could be

def evaluate(board, turn):
 for i, j, k in [0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]:
 if board[i] == board[j] == board[k] == turn: return 1

That is, for indices, single letters i, j and k are common and totally fine. And the tuple doesn't need parentheses.

You could also define each line with just two values instead of three. Like I did in mine that I wrote a while ago:

def show():
 for i in range(0, 9, 3):
 print(*board[i : i+3])
def possible_moves(board):
 return (i for i in range(9) if isinstance(board[i], int))
def move(board, p, i):
 return board[:i] + [p] + board[i+1:]
def won(board):
 for i, d in (0, 1), (3, 1), (6, 1), (0, 3), (1, 3), (2, 3), (0, 4), (2, 2):
 if board[i] == board[i + d] == board[i + 2*d]:
 return True
def value(board, p, q):
 if won(board):
 return -1
 return -min((value(move(board, p, i), q, p)
 for i in possible_moves(board)),
 default=0)
def best_move():
 return min(possible_moves(board),
 key=lambda i: value(move(board, 'O', i), 'X', 'O'))
board = list(range(1, 10))
try:
 while True:
 show()
 board = move(board, 'X', int(input('your move: ')) - 1)
 if won(board):
 raise Exception('You won!')
 if board.count('X') == 5:
 raise Exception('Draw!')
 board = move(board, 'O', best_move())
 if won(board):
 raise Exception('You lost!')
except Exception as result:
 show()
 print(result)

Demo game:

1 2 3
4 5 6
7 8 9
your move: 5
O 2 3
4 X 6
7 8 9
your move: 3
O 2 X
4 X 6
O 8 9
your move: 4
O 2 X
X X O
O 8 9
your move: 8
O O X
X X O
O X 9
your move: 9
O O X
X X O
O X X
Draw!

Like I said I wrote mine a while ago, you just gave me an excuse to dump it here :-). So my program is not "reviewy" regarding yours and it doesn't handle invalid input and doesn't ask for another game (the user can just run the program again), but maybe you'll find something useful in it.

• eligolf: Thanks, that is nice! I like the simplifications but don't really get your AI move logic, I will have to take a closer look at it tonight :)
• superb rain: @eligolf Yeah, I guess some documentation would help. I think the lack thereof is one of the reasons I hadn't posted this yet (I had considered making it a question similar to yours). Main thing would be to note that the value function returns -1 if the board is a lost state (because the game is already won, in the last move made), 1 if it's a winning state (you can force a win from there), or 0 if it's a draw state (neither player will win if both play perfectly).

Answer 2

you can type over an already filled square

• Sᴀᴍ Onᴇᴌᴀ: Welcome to code review! Are you inferring that a player can specify a spot that is already occupied? If so, can you please provide more details, for instance sequence of input?