Algorithms for Tic-Tac-Toe

1. Minimax

Minimax is a classic algorithm in game theory that assumes both players play optimally. It works by recursively evaluating all possible moves and choosing the best one based on the current board state.

Steps:

• Simulate every possible move for the player.
• Recursively call the algorithm for the opponent (minimizing the player's result).
• Evaluate the board:
  • Player wins = +1
  • Player loses = -1
  • Draw = 0
• Choose the move that maximizes the player's result.

Code (JavaScript):

function minimax(board, depth, isMaximizing) { if (checkWin(board, 'X')) return 1; if (checkWin(board, 'O')) return -1; if (isDraw(board)) return 0; if (isMaximizing) { let maxEval = -Infinity; for (let move of getPossibleMoves(board)) { board[move] = 'X'; let eval = minimax(board, depth + 1, false); board[move] = null; maxEval = Math.max(maxEval, eval); } return maxEval; } else { let minEval = Infinity; for (let move of getPossibleMoves(board)) { board[move] = 'O'; let eval = minimax(board, depth + 1, true); board[move] = null; minEval = Math.min(minEval, eval); } return minEval; } }

Advantages:

• Ensures the best gameplay.
• Simple implementation.

Disadvantages:

• High computational complexity (O(9!) for Tic-Tac-Toe).

2. Optimized Minimax: Alpha-Beta Pruning

Alpha-Beta Pruning enhances Minimax by eliminating unnecessary branches in the game tree where a move is no longer optimal.

Key Assumption:

Track two parameters:

• Alpha: Best value the maximizing player can guarantee.
• Beta: Best value the minimizing player can guarantee.

When Beta ≤ Alpha, further exploration is unnecessary.

Code (JavaScript):

function alphaBetaPruning(board, depth, alpha, beta, isMaximizing) { if (checkWin(board, 'X')) return 1; if (checkWin(board, 'O')) return -1; if (isDraw(board)) return 0; if (isMaximizing) { let maxEval = -Infinity; for (let move of getPossibleMoves(board)) { board[move] = 'X'; let eval = alphaBetaPruning(board, depth + 1, alpha, beta, false); board[move] = null; maxEval = Math.max(maxEval, eval); alpha = Math.max(alpha, eval); if (beta <= alpha) break; } return maxEval; } else { let minEval = Infinity; for (let move of getPossibleMoves(board)) { board[move] = 'O'; let eval = alphaBetaPruning(board, depth + 1, alpha, beta, true); board[move] = null; minEval = Math.min(minEval, eval); beta = Math.min(beta, eval); if (beta <= alpha) break; } return minEval; } }

3. Heuristic Strategies

For simpler implementations, especially against beginner opponents, heuristic-based rule algorithms can be used.

Examples of Rules:

• Occupy the center: If the center is free, take it.
• Block the opponent: If the opponent has two in a row, block them.
• Set up your line: If possible, create a line of two of your own symbols.
• Random move: If no good moves are available, make a random move.

Code (JavaScript):

function heuristicMove(board, player) { const opponent = player === 'X' ? 'O' : 'X'; // 1. Check for a winning move for (let move of getPossibleMoves(board)) { board[move] = player; if (checkWin(board, player)) { board[move] = null; return move; } board[move] = null; } // 2. Block the opponent's winning move for (let move of getPossibleMoves(board)) { board[move] = opponent; if (checkWin(board, opponent)) { board[move] = null; return move; } board[move] = null; } // 3. Take the center if available if (board[4] === null) return 4; // 4. Choose a corner if available for (let corner of [0, 2, 6, 8]) { if (board[corner] === null) return corner; } // 5. Choose a random move const possibleMoves = getPossibleMoves(board); return possibleMoves[Math.floor(Math.random() * possibleMoves.length)]; }

4. Neural Networks (Reinforcement Learning)

Machine learning algorithms, such as Q-learning or neural networks, can learn to play Tic-Tac-Toe through simulations.

Steps:

• The model generates moves and evaluates results.
• It learns optimal strategies using rewards/points.
• The result is a model capable of playing at different skill levels.

5. Algorithm Used in HTML and CSS only Tic-Tac-Toe

An innovative approach is used to implement Tic-Tac-Toe without JavaScript, relying solely on HTML and CSS. This method leverages input elements and CSS selectors to create a fully interactive game.

Key Features:

• HTML Structure: The game board is built with nested <div> elements, each containing an <input type="checkbox"> and a <label>. Each checkbox represents the state of a cell.
• CSS Interactivity: CSS pseudo-classes like :checked and sibling selectors (+, ~) are used to update the game board dynamically based on user interactions.
• Game Logic: By nesting HTML elements, the structure predefines all possible game states. CSS rules are applied to visually manage player moves without additional scripting.

This method showcases the power of HTML and CSS to create interactive applications without JavaScript. To learn more, visit the page: About Tic-Tac-Toe.