Github: https://github.com/S-abk/tictactoe Browser: https://s-abk.github.io/tictactoe/
Welcome to the Tic-Tac-Toe game where a human player competes against a computer. This documentation provides a detailed walkthrough of the game's design and implementation.
Tic-Tac-Toe is a classic game where two players take turns marking spaces in a 3x3 grid. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins the game.
A 3x3 grid where players place their symbols ('X' or 'O').
Two players:
- Human (typically 'X')
- Computer ('O')
The board is represented as a 2D list, where each cell can have three states: 'X', 'O', or ''. The '' represents an empty cell.
initial_board = [
['_', '_', '_'],
['_', '_', '_'],
['_', '_', '_']
]A simple function iterates over the board's rows and prints them, providing a visual representation of the current game state.
Functions are implemented to check if there's a winner or if the board is full (a draw). The game checks all rows, columns, and both diagonals for three of the same symbols.
- Human: The game prompts the user for row and column input.
- Computer: The game uses the Minimax algorithm to determine the best move.
The Minimax algorithm is a decision-making algorithm used for finding the best move in games like Tic-Tac-Toe, Chess, and Go. The algorithm predicts the opponent's moves and chooses the most optimal move for the current player.
- Recursive Nature: Minimax is a recursive algorithm that simulates all possible moves in the game for both players.
- Evaluation: After reaching a terminal state (win, lose, or draw), the algorithm evaluates the board and assigns a score.
- Maximizing and Minimizing: The algorithm tries to maximize the score when it's the computer's turn and minimize the score when it's the opponent's turn.
-
Baseline Minimax: This is the basic version of the algorithm. It explores all possible moves and all possible game states. While it's guaranteed to find the best move, it can be very slow for games with a large number of possible moves or deep search trees.
-
Alpha-Beta Pruning: This is an optimization technique for the Minimax algorithm. It reduces the number of nodes evaluated in the search tree by pruning branches that don't need to be explored. The main idea is to maintain two values, alpha and beta, which represent the minimum score the maximizing player is assured of and the maximum score the minimizing player is assured of respectively.
- Efficiency: Alpha-beta pruning significantly reduces the number of nodes evaluated, making the algorithm faster.
- Depth: With alpha-beta pruning, the algorithm can search deeper in the same amount of time, leading to better decision-making.
- Optimality: Despite pruning parts of the search tree, alpha-beta pruning always produces the same move as the baseline Minimax algorithm.
Consider a game where the search tree has a depth of 4. With baseline Minimax, the algorithm would evaluate every possible move at every depth. If there are an average of 10 possible moves at each level, the algorithm evaluates 10,000 nodes.
With alpha-beta pruning, the algorithm might only evaluate 5,000 nodes or even fewer, depending on the order in which nodes are evaluated and the values of alpha and beta at each step. This means alpha-beta pruning can be twice as fast (or even faster) than baseline Minimax.
While the baseline Minimax algorithm is powerful and guarantees finding the best move, it can be slow for complex games. Alpha-beta pruning offers a significant optimization, allowing the algorithm to search deeper and make better decisions without sacrificing optimality.
After implementation, it's essential to test the game by playing multiple rounds. Below are screenshots of output from running the python script and the web based version
