T-3PO — Tic-Tac-Toe Played Optimally

Tic-Tac-Toe, noughts and crosses, Xs and Os, three in a row or whatever you want to call it may be the simplest perfect information game that is enjoyable by humans. Two players set their pieces (X or O) on an 3×3 grid, alternating their turns. The first player to get three of their pieces in a line, wins. If no player succeeds to get a line, the game ends in a draw.

Tic-Tac-Toe’s simplicity may become clear, if you consider that skilled players — people who have played a few rounds — can reliably achieve a draw, thereby playing perfectly. Two perfect players playing Tic-Tac-Toe will — whoever starts — always tie, so one may call the game virtually pointless, due to there practically never being a winner.
Because of its simple rules and short maximal number of turns (nine) it is also a game that can be solved by a computer using brute-force and trees.

The first Tic-Tac-Toe-playing program I wrote is a Python shell script. It lets you, the human player, make the first move and then calculates the best possible move for itself, leading to it never loosing. On its way it has a little chat whilst pretending to think about its next move. The Python source code can be seen below or downloaded here.

The second Tic-Tac-Toe-playing program I wrote uses the exact same method of optimizing its play, though it lets you decide who should begin and is entirely written in JavaScript. You can play against it by following this link.

Both programs look at the entire space of possible games based on the current board’s status, assumes you want to win and randomly picks between the moves that either lead to a win for the computer or to a draw. I did not include random mistakes to give the human player any chance of winning against the computer. Other Tic-Tac-Toe-playing computers, such as Google’s (just google the game), have this functionality.


# Python 2.7.7 Code
# Jonathan Frech, 31st of March 2017
#          edited  1st of April 2017

# import
import random, sys, time

# determine whose turn it is
turn = lambda board: not board.count(-1)%2

# print board
def p(board):
	b = map(lambda n: ("X", "O", " ")[n], board)
	for _ in (b[0:3], b[3:6], b[6:9]):
		print "{%s }" % " |".join(_)
	print

# determine a board's winner
def winner(board):
	for a, b, c 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[a] == board[b] == board[c] != -1:
			return board[a]
	return -1

# calculate the board's endstate (winner) assuming both players play perfectly
def endstate(board):
	if board.count(-1) <= 0 or winner(board) != -1:
		return winner(board)
	else:
		t = turn(board)
		win = False
		draw = False
		loss = False
		for _ in range(9):
			if board[_] == -1:
				b = board[:]
				b[_] = t
				e = endstate(b)
				if e == t:
					win = True
				elif e == (not t):
					loss = True
				elif e == -1:
					draw = True
		if win:
			return t
		elif draw:
			return -1
		return not t

# run the game
def game():
	# header
	print 
	print "========================"
	print " IMPOSSIBLE TIC-TAC-TOE "
	print "========================"
	print "  > You cannot win. <   "
	print "       > Never. <       "
	print "========================"
	print
	
	# initialize board (-1: empty, draw)
	board = [-1]*9
	
	# player: 0, computer: 1
	ply = 0
	com = 1
	
	# main game loop
	while -1 in board and winner(board) == -1:
		# print board
		p(board)
		
		# human's turn
		if turn(board) == ply:
			# get input, place piece
			i = ""
			while i == "":
				i = raw_input("Player's turn. ")
				if i in ("0", "1", "2", "3", "4", "5", "6", "7", "8"):
					i = int(i)
					if board[i] == -1:
						board[i] = ply
					else:
						print "This position is already occupied."
						i = ""
				else:
					print "Please place your mark."
					i = ""
		
		# computer's turn
		else:
			# winning positions (one gets pseudo-randomly chosen for more interesting gameplay)
			wins = []
			draws = []
			
			# consider all valid positions
			for _ in range(9):
				if board[_] == -1:
					# calculate endstate if piece placed at postion
					b = board[:]
					b[_] = com
					
					# winning endstate!
					e = endstate(b)
					if e == com:
						wins.append(_)
					elif e == -1:
						draws.append(_)
			
			# choose choice, computer talk
			if len(wins) > 0:
				choice = random.choice(wins)
				pool = ["Calculating odds of defeating you... @100%.", "Probability of me loosing this battle... @0.0000000%.", "If I win, I @win.", "I will crush you."]
			elif len(draws) > 0:
				choice = random.choice(draws)
				pool = ["Considering position %d..." % random.choice(wins+draws), "Planning to end humanity...", "Processing placing at position %d..." % random.choice(wins+draws), "Your tactics are truly @pathetic.", "If I were you, I would @surrender.", "Found strong evidence for this game ending in a @draw.", "The best you can do is achieve a draw.", "You poor human have no chance."]

			# computer talk
			msg = "Computer's turn. "
			sys.stdout.write(msg)
			sys.stdout.flush()
			for _ in random.choice(pool):
				# longer delay
				if _ == "@":
					time.sleep(.3)
				
				else:
					sys.stdout.write(_)
					sys.stdout.flush()
					time.sleep(.1)
			time.sleep(1)
			
			# choose position, place
			sys.stdout.write("\r\033[K%s%d" % (msg, choice))
			sys.stdout.flush()
			time.sleep(1)
			
			# pick a winning endstate
			board[choice] = com
		
		print "\n"*3
	
	# game ended, announce winner
	p(board)
	w = winner(board)
	if w == -1:
		print "The game ended in a draw."
	else:
		print "The winner is %s." % "XO"[winner(board)]
	print

# run
if __name__ == "__main__":
	try:
		game()
	
	# handle keyboard interrupt
	except KeyboardInterrupt:
		print
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s