Negamax AI search-tree algorithm for two player games

negamax, minimax, game, ai, turn-based, negamax-algorithm, nim
nimble install negamax


negamax Overview

Negamax is a nim library for executing the Negamax AI algorithm on a turn-based game. The library uses the turn_based_game nimble library as the framework for the game itself.

The negamax algorithm searches and weighs possible future moves. It is a varation of the minimax algorithm that is optimized for games where the "value" of a game's state for one player is directly inverse of the value to the oppossing player. This is known as a zero-sum game.

This algorithm is desgined to do alpha/beta pruning, which shortens the search tree.

This algorithem is currently recursive. The author is currently working on a non-recursive one as well.

Negamax has the following restrictions:

  1. It only works for two-player games.
  2. It does not work with games that involve any randomness.
  3. It requires that the value of the board be zero-sum in nature.

Algorithm details:


The bulk of the work is in making the game itself. See the turn_based_game library for details.

Once made, simply import the negamax library and use a NegamaxPlayer instead of a normal Player. Include the depth of the search as an object parameter. The depth is measured in plies. One ply is a single play. So, one full round of play between two players is two plies.

The Negamax AI specifically requires that the

  • scoring,
  • get_state, and
  • restore_state

methods be defined. Again, see the turn_based_game docs for details.

Simple Example

import turn_based_game
import negamax

import knights

#  Game of Knights
# Knights is played on a 5 row by 5 column chessboard with standard Knight pieces. Just like
# in chess, the Knight move by jumping in an L pattern: moving one space in any direction followed by
# moving two spaces at a right angle to the first move. When a knight makes a jump, the place that it
# formerly occupied is marked with an X and it can no longer be landed on by either player. As the
# game progresses, there are fewer and fewer places to land. There are no captures in this game.
# To start, each player has one Knight placed in an opposite corner. The players then take turns jumping.
# The last player to still have a place to move is the winner.

var game = Knights()

  Player(name: "Black Knight"),
  NegamaxPlayer(name: "White Knight", depth: 7)

var history: seq[string] = @[]

history =

echo "history: " & $history

For the content pulled by "import knights", see


The following two videos (to be watched in sequence), demonstrate how to use this library and the 'turn_based_game' library:


The code for this engine mimics that written in Python at the EasyAI library located at That library contains both the game rule engine (called TwoPlayerGame) as well as a variety of AI algorithms to play as game players, such as Negamax.