Negamax test

gistfile1.hx

// http://try.haxe.org/#fC600
// minmax: http://old.haxe.org/doc/snip/minimax_algorithm
// negamax: http://en.wikipedia.org/wiki/Negamax


class GameMove
{
    public function new()
    {
        
    }
    
    public function clone() :GameMove
    {
		return this;
    }
    
    public function toString() :String
    {
        return 
    }
}

class GameBoard
{
    public function new()
    {
        
    }
    
	public function SetPlayerColor(color :Int) :Void //set a player's turn; the following calls regards this player's perspective
    {

    }

    public function GenGameMove(move :GameMove) :Bool  //generate the next game move to test
    {
		return true;
    }

    public function GameMoveApply(move :GameMove) :Void  //apply the given game move 
    {
		trace('GameMoveApply: $move')
    }

    public function GameMoveUndo(move :GameMove) :Void  //un-apply the given game move 
    {

    }

    public function IsTerminal(move :GameMove) :Bool  //return true when no move can be made anymore
    {
		return true;
    }

    public function HeuristicValue(move :GameMove) :Int // establish a value accoring to the state of the game (inc. the given param). A win should return the value MINMAX_INF_VAL.
    {
		return GameAI.MINMAX_INF_VAL;
    }
    
}

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;
        }
    }
}


class Test {
    static function main() {
        trace("Haxe is great!");
        var gameBoard = new GameBoard();
        trace(GameAI.NextMove(gameBoard, 42));
    }
}