Skip to content

jordao76/aye-aye

Repository files navigation

Aye-aye npm

Build Status Dependency Status devDependency Status Codacy Badge License

Simple AI code. Minimax with some tic tac toe...

aye-aye

Nothing to do with that lemur...

Check out connect-four, ultimate-tic-tac-toe and tic-tac-toe-cli.

Intro

To use aye-aye in a node.js project:

$ npm install --save aye-aye

Minimax

Aye-aye's minimax is a textbook implementation that uses alpha-beta pruning and can also be restricted by depth.

var minimax = require('aye-aye');
var MAX = minimax.MAX, MIN = minimax.MIN;
var depth = 4;
var agent = new minimax.MinimaxAgent(depth);

You'll need a State that "implements" the following interface:

Action :: Any
State :: {
  isTerminal : () -> Bool
  nextAgent : () -> MAX|MIN
  utility : () -> Num
  possibleActions : () -> [Action]
  play : (Action) -> State
}

You can think of a State instance as a node in the game tree, where:

  • isTerminal returns if a state is an end state.
  • nextAgent returns whether it's MAX's or MIN's turn to play.
  • utility returns the "value" of the state. For terminal states, this should be its final value; for non-terminal states this should be an estimate of its final value. Values that favor MAX should be greater than values that favor MIN, since MAX will try to maximize those values, whereas MIN will try to minimize them.
  • possibleActions returns an array of the valid actions that can be taken from the current state using the next agent.
  • play executes an action and returns the new state after that action.

And then you can run minimax to find out the next action to take:

var initialState = ...
var actionToTake = agent.nextAction(initialState);

Note that depending on your State implementation and the depth of the search, this could take a very long time.

License

Licensed under the MIT license.