Class: XO::AI::Minimax

Inherits:
Object
  • Object
show all
Includes:
Singleton
Defined in:
lib/xo/ai/minimax.rb

Overview

This class provides an implementation of the minimax algorithm. The minimax algorithm is a recursive search algorithm used to find the next move in a 2-player (or n-player) game.

The search space forms a tree where the root is the empty grid and every other node is a possible grid configuration that can be reached by playing through a game of Tic-tac-toe.

Minimax is a Singleton which can be used as follows:

The first time the instance of Minimax is created, it runs the minimax algorithm to compute the value of all the nodes in the search space. This of course takes a bit of time (~ 4 seconds), but subsequent calls are super fast.

Examples:

Minimax.instance.moves(XO::Grid.new('xox x o o'), XO::Grid::O) # => [[3, 2]]

Instance Method Summary collapse

Instance Method Details

#moves(grid, turn) ⇒ Array<Array(Integer, Integer)>

Determines the best moves that can be made on the given grid, knowing that it’s turn’s time to play.

Parameters:

Returns:

  • (Array<Array(Integer, Integer)>)

Raises:

  • (ArgumentError) —

    if turn is not a token or the combination of the values of grid and turn doesn’t make sense



35
36
37
38
 
# File 'lib/xo/ai/minimax.rb', line 35

def moves(grid, turn)
  check_turn(turn)
  best_moves(*normalize(grid, turn))
end