Tic-Tac-Toe: Unbeatable AI for Android

Introduction:

Welcome to the world of Tic-Tac-Toe, where Xs and Os battle it out for supremacy on a 3x3 grid. But this isn’t your ordinary game; we’re diving deep into the realm of AI development to create an opponent that’s not just formidable but downright hilarious. Join us on a journey through code as we unveil the secrets behind building an unbeatable Tic-Tac-Toe AI in Kotlin.

// Importing necessary packages
package com.dac.tictactoe.ai

// Defining the HardAI class
class HardAI {

    internal var player = 'x'
    internal var opponent = 'o'

    internal inner class Move(var row: Int, var col: Int)

    internal fun isMovesLeft(board: Array<CharArray>): Boolean {
        for (i in 0..2)
            for (j in 0..2)
                if (board[i][j] == '_')
                    return true
        return false
    }
    // Evaluation function
    private fun evaluate(board: Array<CharArray>, symbol: Char): Int {
        var score = 0

        // Check for potential wins or blocks for the player
        for (row in 0 until 3) {
            val rowOccupiedByPlayer = (0 until 3).all { board[row][it] == player }
            if (rowOccupiedByPlayer) {
                score -= 100 // Player has a winning possibility
            }

            val rowOccupiedByOpponent = (0 until 3).all { board[row][it] == opponent }
            if (rowOccupiedByOpponent) {
                score += 100 // AI has a winning possibility
            }
        }

        for (col in 0 until 3) {
            val colOccupiedByPlayer = (0 until 3).all { board[it][col] == player }
            if (colOccupiedByPlayer) {
                score -= 100 // Player has a winning possibility
            }

            val colOccupiedByOpponent = (0 until 3).all { board[it][col] == opponent }
            if (colOccupiedByOpponent) {
                score += 100 // AI has a winning possibility
            }
        }

        val mainDiagonalOccupiedByPlayer = (0 until 3).all { board[it][it] == player }
        if (mainDiagonalOccupiedByPlayer) {
            score -= 100 // Player has a winning possibility
        }

        val mainDiagonalOccupiedByOpponent = (0 until 3).all { board[it][it] == opponent }
        if (mainDiagonalOccupiedByOpponent) {
            score += 100 // AI has a winning possibility
        }

        val antiDiagonalOccupiedByPlayer = (0 until 3).all { board[it][2 - it] == player }
        if (antiDiagonalOccupiedByPlayer) {
            score -= 100 // Player has a winning possibility
        }

        val antiDiagonalOccupiedByOpponent = (0 until 3).all { board[it][2 - it] == opponent }
        if (antiDiagonalOccupiedByOpponent) {
            score += 100 // AI has a winning possibility
        }

        // Additional evaluation factors
        // Center control
        if (board[1][1] == symbol) {
            score += 10
        }
        // Corner control
        if (board[0][0] == symbol || board[0][2] == symbol || board[2][0] == symbol || board[2][2] == symbol) {
            score += 5
        }
        // Edge control
        if (board[0][1] == symbol || board[1][0] == symbol || board[1][2] == symbol || board[2][1] == symbol) {
            score += 3
        }

        return score
    }
    // Minimax algorithm implementation
    internal fun minimax(board: Array<CharArray>, depth: Int, isMax: Boolean): Int {
        val score = evaluate(board, player)

        if (score == 100 || score == -100)
            return score

        if (!isMovesLeft(board) || depth == 4) // Increased depth for deeper search
            return 0

        var bestVal = if (isMax) Int.MIN_VALUE else Int.MAX_VALUE

        for (i in 0 until 3) {
            for (j in 0 until 3) {
                if (board[i][j] == '_') {
                    if (isMax) {
                        board[i][j] = player
                        bestVal = maxOf(bestVal, minimax(board, depth + 1, !isMax))
                    } else {
                        board[i][j] = opponent
                        bestVal = minOf(bestVal, minimax(board, depth + 1, !isMax))
                    }
                    board[i][j] = '_'
                }
            }
        }

        return bestVal
    }
    // Finding the best move
    internal fun findBestMove(board: Array<CharArray>): Int {
        // Check if AI has a winning possibility and prioritize it
        for (i in 0 until 3) {
            for (j in 0 until 3) {
                if (board[i][j] == '_') {
                    board[i][j] = opponent
                    if (evaluate(board, opponent) == 100) {
                        board[i][j] = '_'
                        return i * 3 + j + 1
                    }
                    board[i][j] = '_'
                }
            }
        }

        // If AI doesn't have a winning possibility, defend against the player
        for (i in 0 until 3) {
            for (j in 0 until 3) {
                if (board[i][j] == '_') {
                    board[i][j] = player
                    if (evaluate(board, player) == -100) {
                        board[i][j] = '_'
                        return i * 3 + j + 1
                    }
                    board[i][j] = '_'
                }
            }
        }

        // If neither player nor AI has a high chance to win, find the best move for the AI
        var bestVal = Int.MIN_VALUE
        var bestMove = -1

        for (i in 0 until 3) {
            for (j in 0 until 3) {
                if (board[i][j] == '_') {
                    board[i][j] = player
                    val moveVal = minimax(board, 0, false)
                    board[i][j] = '_'
                    if (moveVal > bestVal) {
                        bestVal = moveVal
                        bestMove = i * 3 + j + 1
                    }
                }
            }
        }

        return bestMove
    }
    // Constructing the game board
    internal fun constructBoard(player1: MutableList<Int>, comp: MutableList<Int>): Int {
        val board = Array(3) { CharArray(3) }
        if (player1.isEmpty() && comp.isEmpty()) {
            // If both player1 and comp lists are empty, choose a random position
            val randomPosition = (1..9).random()
            return randomPosition
        }
        for (cellId in 1..9) {
            if (player1.contains(cellId)) {
                when (cellId) {
                    1 -> board[0][0] = 'x'
                    2 -> board[0][1] = 'x'
                    3 -> board[0][2] = 'x'
                    4 -> board[1][0] = 'x'
                    5 -> board[1][1] = 'x'
                    6 -> board[1][2] = 'x'
                    7 -> board[2][0] = 'x'
                    8 -> board[2][1] = 'x'
                    9 -> board[2][2] = 'x'
                }
            } else if (comp.contains(cellId)) {
                when (cellId) {
                    1 -> board[0][0] = 'o'
                    2 -> board[0][1] = 'o'
                    3 -> board[0][2] = 'o'
                    4 -> board[1][0] = 'o'
                    5 -> board[1][1] = 'o'
                    6 -> board[1][2] = 'o'
                    7 -> board[2][0] = 'o'
                    8 -> board[2][1] = 'o'
                    9 -> board[2][2] = 'o'
                }
            } else {
                when (cellId) {
                    1 -> board[0][0] = '_'
                    2 -> board[0][1] = '_'
                    3 -> board[0][2] = '_'
                    4 -> board[1][0] = '_'
                    5 -> board[1][1] = '_'
                    6 -> board[1][2] = '_'
                    7 -> board[2][0] = '_'
                    8 -> board[2][1] = '_'
                    9 -> board[2][2] = '_'
                }
            }
        }
        return findBestMove(board)
    }
}

Visual Presentation: Now, let’s dive into the code and uncover the magic behind our Tic-Tac-Toe AI. First, we define the HardAI class, which encapsulates all the intelligence needed to play the game.

Explanation:

• The code begins by importing necessary packages and declaring the HardAI class.
• We initialize variables for the player and opponent symbols (‘x’ and ‘o’ respectively) and define an inner class Move to represent a move on the game board.
• The isMovesLeft function checks if there are any empty cells left on the board.
• Next, we implement the evaluation function to assess the current state of the board and assign scores based on potential wins, blocks, and positional advantages.
• The Minimax algorithm is then implemented to recursively evaluate possible moves and select the best one.
• The findBestMove function orchestrates the AI's decision-making process, prioritizing winning moves, blocking opponent victories, and strategizing for optimal gameplay.
• Lastly, the constructBoard function converts player and AI move lists into a game board representation and selects the best move for the AI.

Let’s break down the algorithm used in the HardAI class step by step:

1. Evaluation Function:

• The evaluate function analyzes the current state of the Tic-Tac-Toe board and assigns a score based on various factors.
• It checks for potential wins or blocks for both the player and the AI by examining rows, columns, and diagonals.
• Additionally, it considers positional advantages such as control of the center, corners, and edges of the board.
• The evaluation function aims to quantify the desirability of a given board configuration for the AI.

1. Minimax Algorithm:

• The minimax algorithm is a decision-making technique commonly used in two-player games to determine the optimal move for a player.
• It operates recursively, considering all possible future moves and their outcomes while assuming that both players will make the best possible moves.
• In the context of Tic-Tac-Toe, the minimax algorithm evaluates each possible move by the AI and the player, recursively exploring the game tree until reaching a terminal state (win, lose, or draw).
• The algorithm assigns scores to terminal states (win: +100, lose: -100, draw: 0) and propagates these scores back up the tree to determine the best move for the AI.
• By maximizing the AI’s score and minimizing the opponent’s score at each level of recursion, the algorithm selects the move that maximizes the AI’s chances of winning.

1. Finding the Best Move:

• The findBestMove function orchestrates the AI's decision-making process by considering various factors.
• It first checks if the AI has a winning possibility and prioritizes such moves to secure victory.
• If the AI doesn’t have a winning possibility, it focuses on blocking the opponent from winning by defending against their potential winning moves.
• If neither player nor AI has a high chance to win immediately, the function uses the minimax algorithm to find the best move for the AI.
• The AI iterates over all empty cells on the board, simulates placing its symbol in each cell, evaluates the resulting board configuration using the minimax algorithm, and selects the move with the highest score.

In summary, the HardAI class employs the minimax algorithm coupled with an evaluation function to make strategic decisions in Tic-Tac-Toe. By analyzing the current state of the board and recursively exploring possible future moves, the AI aims to outsmart its opponent and secure victory while maintaining a sense of humor throughout the game.

Git Link

Conclusion: With our Tic-Tac-Toe AI’s inner workings laid bare, it’s time to put it to the test! Armed with humor and strategic prowess, our AI is ready to take on any challenger in the ultimate game of Xs and Os. Are you up for the challenge? Let the games begin!

Stackademic 🎓

Thank you for reading until the end. Before you go:

• Please consider clapping and following the writer! 👏
• Follow us X | LinkedIn | YouTube | Discord
• Visit our other platforms: In Plain English | CoFeed | Venture | Cubed
• Tired of blogging platforms that force you to deal with algorithmic content? Try Differ
• More content at Stackademic.com