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