# Minimax Algorithm for Games

```package <package>;

import <package>.GameBoard;

/*
*     class:    GameAI
*     Desc:    Game Minimax AI algorithm
*     Author:    #gr, Aug-2013
*/

class GameAI
{
public    static var MINMAX_INF_VAL = 1000;

private    static var m_gameBoard:GameBoard;
private    static var MINMAX_DEPTH = 1;
private    static var m_nextGameMove :GameMove;

static public function NextMove(currGameBoard: GameBoard, playerColor:Int) : Void {
m_gameBoard = currGameBoard;
m_nextGameMove = null;
Negamax(null, MINMAX_DEPTH, -MINMAX_INF_VAL, MINMAX_INF_VAL, playerColor);
// set us to orig player color
m_gameBoard.SetPlayerColor(playerColor);
// apply the found move
if (m_nextGameMove != null) {
m_gameBoard.GameMoveApply(m_nextGameMove);
}
}

static private    function Negamax(gameMove:GameMove, depth:Int, alpha:Int, beta:Int, color:Int): Int {
// if it's a leaf, calc it's value by gameMove
if (m_gameBoard.IsTerminal(gameMove) || depth == 0) {
return - m_gameBoard.HeuristicValue(gameMove);
} else {
// no leaf, we must generate more
// - first apply the move that brought us here
// - and save so we can undo it
m_gameBoard.GameMoveApply(gameMove);

// now start generating new moves for this player
var newGameMove = new GameMove();
m_gameBoard.SetPlayerColor(color);

while (m_gameBoard.GenGameMove(newGameMove)) {
var val = -Negamax(newGameMove, depth - 1, -beta, -alpha, -color);
if (val >= beta) {
// got a val/move to return
if (MINMAX_DEPTH == depth) { // if first tier
m_nextGameMove = newGameMove; // save this move
}
m_gameBoard.SetPlayerColor(-color); // get back to caller color
m_gameBoard.GameMoveUndo(gameMove);
return val;
}
if (val > alpha) {
// got a val/move to return
if (MINMAX_DEPTH == depth) { // if first tier
m_nextGameMove = newGameMove.clone(); // save this move
}
alpha = val;
}
}
m_gameBoard.SetPlayerColor(-color); // get back to caller color
m_gameBoard.GameMoveUndo(gameMove);
return alpha;
}
}
}
```

This adapted for Haxe Minimax (Negamax) algorithm can be used in any 2-player board game as an AI engine to allow a single user mode.
You must implement the classes GameBoard and GameMove accorgin to the specific game. The class GameBoard implements the methods:
SetPlayerColor - set a player's turn; the following calls regards this player's perspective
GenGameMove - generate the next game move to test
GameMoveApply - apply the given game move
GameMoveUndo - un-apply the given game move
IsTerminal - return true when no move can be made anymore
HeuristicValue - establish a value accoring to the state of the game (inc. the given param). A win should return the value MINMAX_INF_VAL.
The value MINMAX_DEPTH depends on the application and platform. I've run JS with depth=4 at a reasonable respone time.
You can read some more theory here.

Gille R.

version #19653, modified 2013-08-19 21:50:33 by gillerotgold