Tic-Tac-Toe AI With Tkinter Visualization

Introduction

Tic-tac-toe ,consisting of Xs and Os is a paper-and-pencil game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row is the winner.

Each player takes alternative turn. In order to win, a player places three of their marks in a horizontal, vertical, or diagonal row. This article focuses on the development of a programmatic approach with its GUI visualization.

Tic-Tac-Toe Game

Approaches

The following are different ways of thinking about building the AI with incremental complexity :

1. Random Placement method : In this approach, the marking is simply made by the AI randomly in any available cell. The downside is obvious, the AI is not interested in the game at all! But still it has to find out the available cells and track the termination of the game. Here is the pseudocode for this approach :

function ai_move(curr_state){
     game_has_ended(curr_state)
     l = [list of all blank cells]
     r,c = select one at random
     curr_state[r][c] = 'X' 
     game_has_ended(curr_state)
}
function game_has_ended(curr_state){
   if all cells are filled:
    exit("Game is Drawn")
   for each row or column in curr_state{
    if row or column is filled with same mark: 
     exit(" Game is won ")
   }
   if diagonals are filled with same mark:
    exit("Game is won ")
}

2. Static Scoring method : Building on top of the previous approach, a priority score is assigned to each cell in the grid. The unmarked cell with the highest priority is marked in the next move. The middle cell has the highest priority followed by the corner and then the other cells, based on the degree of control offered by them. Here is the pseudocode for this approach :

function ai_move(curr_state){
     game_has_ended(curr_state)
     r,c = select cell position of highest priority 
     curr_state[r][c] = 'X'
     game_has_ended(curr_state)
}
sample static scoring :
  |3 | 1 |3 |
  |1 | 7 |1 |
  |3 | 1 |3 |

3. Brute Force method : The disadvantages of both the methods above is that, they miss to read the opponent and fail to play moves to advantage. So, this method is built on the above methods. When the opponent has two markings in a row or column or diagonal, it is blocked. Otherwise, static scores are used to fill the empty cells. In the case where two cells are previously marked, it is completed to win the game. Here is the pseudocode for this approach :

function ai_move(curr_state){
     game_has_ended(curr_state)
     for each row,col in curr_state{
        if row has two markings:
           fill the unfilled cell of row and return
        if col has two markings,
           fill the unfilled cell of column and return
     }
     game_has_ended(curr_state)
     if row or column or diagonal exists with 2 markings:
         curr_state[that_row][that_column] = 'X'
         return
     l = [list of all blank cells]
     r,c = select one at random of highest priority
     curr_state[r][c] = 'X'
     game_has_ended(curr_state)
}

4. Minimax method : The approach above is enough to draw the game or winning simple games but to win by tricking a shrewd opponent is more desirable. This method is illustrated as follows :

minmax approach

leaf_scores -> min_of_all_scores -> max_of_all_min_scores -> min_of_all_scores -> ..... -> max_of_all_min_scores (root)
   ( This is applied across all children of each node )

Here, it is assumed that the opponent plays the game in the most optimal way. Thus, this approach could be used in zero-sum game scenario. Each level of the game tree deals with the actions of alternating players. The result computed is calculated with respect to the player at the root as shown above. The root in tic-tac-toe is the AI player.

The leaf nodes consists of scores at end positions of the tic-tac-toe game. The scores are based on a heuristic which is the nucleus of this approach. The heuristic assigns positive, negative or non-negative scores based on winning, losing or draw positions.

The pseudocode of the heuristic employed here is :

function heuristic(curr_state){
 if is_draw(curr_state):
      return 0
 if has_won(curr_state):
      number of unfilled_cells + 1
 if has_lost(curr_state):
      -number_of_unfilled_cells - 1
}

Recursive implementation is used. The pseudocode of the approach is :

function ai_move(curr_state, ai = True){
     if (res = heuristic(curr_state)) != nil: return res
     
     poss_moves = get_all_possible_moves
     
     for move in poss_moves{
            scores.append(ai_move(move, ~ai))   
     }
     
     return max(scores) if ai is True else min(scores)
}
// a move is chosen with the maximum score at the current state (root) based on priority index or randomly if scores clash

Building Tic-Tac-Toe-AI With GUI

Find the full code here : https://github.com/praguna/ai-puzzels/tree/master/tic_tac_toe

Tkinter is a Python binding to the Tk GUI toolkit. It is the standard Python interface to the Tk GUI toolkit, and is Python’s de facto standard GUI. It is a fast and easy way of creating GUI applications.

Initially, a frame is created in which all the widgets are placed :

class App(tk.Frame):
    def __init__(self, parent, dim, **kw):
        super().__init__(parent, **kw)
        parent.minsize(dim[0], dim[1])
        parent.title("Tic Tac Toe")
        self.define_display_widgets()
        messagebox.showinfo("Info", "Welcome to Tic Tac Toe Game ")
        self.ttt_grid = Grid(self, {"tile_color": "red", "text": "Puzzle Grid"})
def define_display_widgets(self):
        self.label = tk.Label(self, text="Let's play Tic Tac Toe", font=('Verdana', 15, 'bold'))
        self.label.pack(side=tk.TOP)
        self.reset = tk.Button(self, text="Reset", bg="grey", fg="white", command=self.reset_all)
        self.reset.pack(side=tk.LEFT, anchor=tk.N)
        ttk.Separator(self, orient=tk.HORIZONTAL).pack(after=self.label, fill=tk.X)
def reset_all(self):
        self.ttt_grid.disable_or_reset(disable=False)

The grid class is where the tic-tac-toe game is played and it is created as follows :

class Grid(tk.Frame):
def __init__(self, parent, config, **kw):
        super().__init__(parent, **kw)
        self.b = [[], [], []]
        self.config = config
        self.draw_grid()
        tk.Label(parent, text=config["text"], font=('Verdana', 20, 'bold'), pady=5).pack()
        self.score = tk.Label(parent, text="", font=('Verdana', 10, 'bold'), pady=2)
        self.score.pack()
        self.pack(pady=15)
        self.set_algo()
def draw_grid(self):  
        # draws the grid inside the main frame
        for i in range(3):
            for j in range(3):
                self.b[i].append(self.button())
                self.b[i][j].config(command=lambda row=i, col=j: self.fill(row, col))
                self.b[i][j].grid(row=i, column=j)
def button(self):
        return tk.Button(self, bd=5, width=2, font=('arial', 50, 'bold'))

It looks like this :

GUI Layout

Once the move is played it is handled as follows in the fill method :

def fill(self, i, j):
    self.b[i][j].config(text=get_symbol(self.turn),    state=tk.DISABLED, bg="black", fg="white")
    self.algo_value[i * 3 + j] = get_symbol(self.turn)
    status  = self.check_if_game_ended("Player")
    if status: return
    self.turn = update_state(self.algo_value, i, j, self.turn)
    self.ai_move()

It can be noticed that the ai_move is called here which will use the minimax algorithm in its method as follows :

def ai_move(self, start=None):
        if start:
            move, s = start, 0
        else:
            move, s = find_best_move(self.algo_value, True, self.turn) # applies minmax 
        self.score.config(text="current minimax score {}".format(s))
        index = 0
        for i in range(9):
            if self.algo_value[i] != move[i]:
                index = i
                break
        self.algo_value = move
        self.b[index // 3][index % 3].config(text=get_symbol(self.turn), state=tk.DISABLED, fg="white", bg="red")
        self.turn = not self.turn
        self.check_if_game_ended("Computer")

The method call find_best_move implements minimax algorithm as follows :

def find_best_move(curr, is_ai, v):
    if is_won(curr): return curr, 1 + final_score(curr) if not is_ai else -final_score(curr) - 1  # invert the flag
    if is_draw(curr): return curr, 0
    poss_moves = gen_moves(curr, v)
    b = -10 if is_ai else 10
    next_move = None
    for move in poss_moves:
        _, score = find_best_move(move, not is_ai, not v)
        if (score > b and is_ai) or (score < b and not is_ai):
            next_move, b = move, score
    return next_move, b

This logic is same as the pseudocode discussed above. The game is found out to be won or drawn as follows :

def has_won(self):
    curr = self.algo_value
    for i in range(3):
        if curr[3 * i] == curr[3 * i + 1] == curr[3 * i + 2] != -1:
            return True, (3 * i, 3 * i + 1, 3 * i + 2)
        if curr[0 + i] == curr[3 + i] == curr[6 + i] != -1:
            return True, (0 + i, 3 + i, 6 + i)
    if curr[0] == curr[4] == curr[8] != -1:
        return True, (0, 4, 8)
    if curr[2] == curr[4] == curr[6] != -1:
        return True, (2, 4, 6)
    return False, None
def is_draw(curr: list):
    return -1 not in curr

The user can also decide to let the AI play first by selecting in a prompt defined as :

def set_algo(self):
    val = messagebox.askquestion("Info", "Do you want me to start ?")
    self.algo_value = [-1] * 9
    self.turn = True
    if val == "yes":
        i = r.choice([2, 0, 6, 8, 1, 3, 5, 7])
        m = self.algo_value[:]
        m[i] = 'X'
        self.ai_move(m)

Lastly, the winner’s cells must get highlighted which is implemented as :

def highlight(self, v):
        for x in v:
            self.b[x // 3][x % 3].config(fg="black", bg="blue")
        self.disable_or_reset()
# disable the grid after the game is own or lost by ai
def disable_or_reset(self, disable=True):
    for i in range(3):
        for j in range(3):
            if disable:
                self.b[i][j].config(state=tk.DISABLED)
            else:
                self.b[i][j].config(text="", bg=self.cget('bg'), fg="black", state=tk.NORMAL)
    if not disable: self.set_algo()

Finally, Let’s see it in action

play tic-tac-toe with AI

Thanks for going through, Have a nice Day :)

References

Tic-tac-toe

Minimax Algorithm in Game Theory | Set 1 (Introduction) - GeeksforGeeks

praguna/ai-puzzels

Minimax