Tic Tac Toe(Program Form)

Not to be confused with Tic Tac Toe.

Tic-tac-toe is a three-in-a-row game invented by the Germans that requires players to take turns to draw crosses or circles on a nine-grid square board, and whoever first arranges three identical marks into horizontal lines, straight lines, and diagonal lines is the winner. Since the rules of tic-tac-toe are simple and easy to understand, it can be played anywhere, making it a must-have casual game to pass the time effectively.

How to make it in program?

Programming tic-tac-toe is a classic problem in traditional artificial intelligence, and a computer can easily calculate the sum of three numbers and determine whether it is equal to fifteen.

We can use the ancient Chinese legend "Luoshu" third-order magic square to isomorphize the tic-tac-toe game. We can use two sets (lists, arrays, etc.) X and O to hold the slots occupied by two players.

Sheet 1-1

4	9	2
3	5	7
8	1	6

Luoshu magic square is like the sheet 1-1. What did you see?

Steps

Ideas

We have two ways of thinking about solving this problem. The first is to enumerate all the rows, columns, and diagonals (8 triples) in the Luoshu Magic Square, and then determine whether a triplet is included in the player-occupied set.

The second idea is more interesting, assuming that the player occupies the cells X={x1, x2, ......, xn}, and the serial numbers of these grids are arranged in ascending order according to the elements in the Luoshu magic square (4,9,2,3,5,7,8,1,6). We can first select x1, then use the left and right pointers l and r to point to the next element and the last element respectively, and then add up these three numbers Σ=x1+xl+xr. If Sigma is equal to fifteen, the player is connected in a straight line and can tell that he or she has won. If it is less than fifteen, since the elements are arranged in "ascending" order, we can add one to the left pointer and try again; If it's greater than fifteen, subtract the right pointer by one and try again. If the left and right pointers meet, it means that fixed x1 did not find a triplet that adds up to fifteen, and we select x2 to perform such a check again. In this case, a total of (n-2) + (n-3) + ...... + 1 checks will be performed in the worst-case scenario to know if the player wins.

def win(s)
	n = len(s)
	if n < 3:
		return False
	s = sorted(s)
	for i in range(n - 2):
		l = i + 1
		r = n - 1
		while l < r:
			total = s[i] + s[l] + s[r]
			if total == 15:
				return True
			elif total < 15:
				l = l + 1
			else:
				r = r + 1
	return False

This way, given X and O, the situation can be judged. If X and O occupy all 9 squares and still have no winner, it is a tie.

Method

Next, we use the min-max method in traditional AI to implement tic-tac-toe. We give each position a score, and one side tries to maximize the score, called the positive side, while the other side tries to minimize the score, called the negative side, so that the confrontation is achieved. In the event of a draw, the rating is 0, and if the positive side wins, the rating is 10, and vice versa (the rating is -10).

WIN = 10
INF = 1000
MAGIC_SQUARE = [4, 9, 2, 
			    3, 5, 7, 
			    8, 1, 6]

def eval(x, o):
	if win(x):
		return WIN
	if win(o)
		return -WIN
	return 0

def finished(x, o)
	return (len(x) + len(o) >= 9)

For any game, we let the computer keep exploring until we find a sure win, loss, or draw. The way to explore is to exhaust all the slots you can currently occupy, then switch identities and consider how you should fight if you are the other party. For all candidates, if it's positive, choose the one with the highest score, and vice versa. min-max is a recursive search process, and in order to win as quickly as possible, we add to the score the number of steps to explore forward. If it's positive, subtract the recursive depth from the score and vice versa.

def minmax(x, o, depth, maximize):
	score = _eval(x, o)
	if score == WIN:
		return score - depth
	if score == -WIN:
		return score + depth
	if finished(x, o):
		return 0  # Draw
	best = -INF if maximize else INF
	for i in MAGIC_SQUARE:
		if (i not in x) and (i not in o):
			if maximize:
				best = max(best, minmax(
						[i] + x,
						o,
						depth + 1,
						not maximize))
			else:
				best = min(best, minmax(
						x,
						[i] + o,
						depth + 1,
						not maximize))


def findbest(x, o, maximize):
	best = -INF if maximize else INF
	move = 0
	for i in MAGIC_SQUARE:
		if (i not in x) and (i not in o):
			if maximize:
				val = minmax(
					[i] + x, o,
					0,
					not maximize)
				if val > best:
					best = val
					move = i
			else:
				val = minmax(
					x, [i] + o,
					0,
					not maximize)
				if val < best:
					best = val
					move = i
	return move

Done!

Now we have made an "invincible" tic-tac-toe AI, and our program uses Luoshu Magic Square against human players behind the scenes:

def play():
	print("A1 is 4, A2 is 9, A3 is 2, \n"
	      "B1 is 3, B2 is 5, B3 is 7, \n"
	      "C1 is 8, C2 is 1, C3 is 6. \n")
	x = []
	o = []
	while not (win(x) or win(o) or finished(x, o)):
		board(x, o)
		while True:
			i = int(input("Please input your piece: "))
			if (i not in MAGIC_SQUARE) 
				or (MAGIC_SQUARE[i - 1] in x) 
				or (MAGIC_SQUARE[i - 1] in o):
				print("Invalid move!!!!!!!!")
			else:
				x = (MAGIC_SQUARE[i - 1]) + x
				break
		o = (findbest(x, o, False)) + o
	board(x, o)