Optimal Turn Library

A TypeScript library for finding optimal moves in Tic-Tac-Toe games using the Minimax algorithm with alpha-beta pruning.

Installation

npm install @vladfvv/optimal-turn

Usage

Basic Example

import { getOptimalTurn } from '@vladfvv/optimal-turn';

// Example field:
// O O _
// X X _
// _ _ _
const field = [0, 0, -1, 1, 1, -1, -1, -1, -1];

// Find optimal move for player O (0)
const optimalMove = getOptimalTurn(field, 0);
console.log(optimalMove); // Output: 2 (O should complete the top row)

// Find optimal move for player X (1)
const optimalMoveX = getOptimalTurn(field, 1);
console.log(optimalMoveX); // Output: 2 (X should block O's winning move)

Field Representation

The game field is represented as an array of 9 integers:

• 0 means "O" (player O)
• 1 means "X" (player X)
• -1 means empty cell

Index mapping:

0  1  2
3  4  5
6  7  8

Function Signature

function getOptimalTurn(
  gameField: CellValue[], 
  player: CellValue
): number

Parameters:

• gameField: Array of 9 integers representing the current game state
• player: The player to find optimal move for (0 for O, 1 for X)

Returns:

• The index (0-8) of the optimal move
• -1 if no valid moves are available (board is full or game is over)

Examples

Example 1: Winning Move

// O O _
// X X _
// _ _ _
const field = [0, 0, -1, 1, 1, -1, -1, -1, -1];
const result = getOptimalTurn(field, 0);
// Result: 2 (O completes the top row and wins)

Example 2: Blocking Opponent

// O O _
// X X _
// _ _ _
const field = [0, 0, -1, 1, 1, -1, -1, -1, -1];
const result = getOptimalTurn(field, 1);
// Result: 2 (X blocks O's winning move)

Example 3: Strategic Move

// Empty board
const field = [-1, -1, -1, -1, -1, -1, -1, -1, -1];
const result = getOptimalTurn(field, 0);
// Result: 4 (Center is the best first move)

Example 4: Game Already Over

// O O O
// X X _
// _ _ _
const field = [0, 0, 0, 1, 1, -1, -1, -1, -1];
const result = getOptimalTurn(field, 1);
// Result: 5 (First available move, game already has winner)

Error Handling

The function will throw an error if:

• The field array doesn't contain exactly 9 cells
• The player value is not 0 or 1

try {
  const field = [-1, -1, -1]; // Invalid length
  getOptimalTurn(field, 0);
} catch (error) {
  console.error(error.message); // "Game field must contain exactly 9 cells"
}

Algorithm

The library uses the Minimax algorithm with alpha-beta pruning to find the optimal move:

1. Minimax: Evaluates all possible moves and chooses the one with the best outcome
2. Alpha-Beta Pruning: Optimizes the search by eliminating branches that won't affect the final decision
3. Scoring:
   • +10 points if the current player wins
   • -10 points if the opponent wins
   • 0 points for a draw

TypeScript Support

The library is written in TypeScript and includes type definitions:

import { getOptimalTurn, CellValue, GameField } from '@vladfvv/optimal-turn';

const field: CellValue[] = [0, 0, -1, 1, 1, -1, -1, -1, -1];
const player: CellValue = 0;
const move: number = getOptimalTurn(field, player);

Testing

Run tests:

npm test

Run tests with coverage:

npm run test:coverage

API Reference

Types

type CellValue = 0 | 1 | -1;
type GameField = [
  CellValue, CellValue, CellValue,
  CellValue, CellValue, CellValue,
  CellValue, CellValue, CellValue
];

Functions

getOptimalTurn(gameField, player)

Finds the optimal move for the given player in the current game state.

Parameters:

• gameField: CellValue[] - Array of 9 integers representing the game field
• player: CellValue - The player (0 for O, 1 for X)

Returns: number - Index of the optimal move (0-8) or -1 if no moves available

Throws: Error if input is invalid

License

MIT

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.