How to make a move on a gameboard from MiniMax Alpha-Beta's returned value?

Question

The game I'm talking about is something similar to Gomoku or a "large", simplified version of Tic-Tac-Toe. Basically, you have an 8x8 board and the winner is the one that chains 4 in a row or column (no diagonal).

I've set up a minimax with alpha-beta pruning, the problem I have is that I'm not sure how returned values can let you know which move to make. Or like how to connect values to a move.

Currently, I've considered returning a GameStateNode instead. With the GameStateNode having fields: char[][] (the current state of the board), evaluationVal(the value of the current state when it is not a terminal node).

But I still can't think of a way to use the returned node to decide on the best move.

    // Alpha-Beta Pruning Search
    private static Node alphaBeta(Node initial, int depth) {
        Node bestMove = max(initial, depth, NEGATIVE_INFINITY, POSITIVE_INFINITY);
        return bestMove;
    }

    private static Node max(Node n, int depth, int alpha, int beta) {
        int value = NEGATIVE_INFINITY;
        Node currentBestMove = null;
        Node temp = null;

        // Terminal state
        if(n.fourInALine() != 0) {
            return n;
        }
        // Depth limit reached
        if(depth == 0) {
            return n;
        }

        ArrayList<Node> successors = n.generateSuccessors('X');
        // Iterate through all the successors, starting with best evaluationValues
        for(Node s : successors) {
            temp = min(s, depth - 1, alpha, beta);
            if(temp.evaluationVal > value) {
                value = temp.evaluationVal;
                currentBestMove = temp;
            }
            alpha = Math.max(alpha, value);
            if(alpha >= beta) {
                break;
            }
        }
        return currentBestMove;
    }

    // I have similar min method just with the correct comparison

Answer 1

You cannot get the move information out of the returned bestMove because that Node represents the position of the board after depth moves. If you diff bestMove's position and initial's position, you will find multiple differences, and you won't be able to tell what order the moves were played in.

To get the move to play out of your search code:

1. Add a boolean isRoot parameter to max() to tell the method whether it is called directly from alphaBeta() and n is the search tree's root node.
2. In max(), if isRoot is true, instead of keeping track of the best temp (the Node returned from min()) for currentBestMove, keep track of the best s (the Node from n.generateSuccessors()).
3. In alphaBeta(), take bestMove (the Node returned from max()) and diff its state array against initial. Find the coordinates of the slot where bestMove has an 'X' and initial doesn't.
4. That is the move to play.

Code:

private static int[] alphaBeta(Node initial, int depth) {
    Node bestMove = max(initial, depth, NEGATIVE_INFINITY, POSITIVE_INFINITY, true);
    for(int i = 0; i < bestMove.state.length; i++) {
        for(int j = 0; j < bestMove.state[i].length; j++) {
            if(bestMove.state[i][j] != initial.state[i][j]) {
                return new int[] { i, j };
            }
        }
     }
}

private static Node max(Node n, int depth, int alpha, int beta, boolean isRoot) {
    int value = NEGATIVE_INFINITY;
    Node currentBestMove = null;
    Node temp = null;

    // Terminal state
    if(n.fourInALine() != 0) {
        return n;
    }

    // Depth limit reached
    if(depth == 0) {
        return n;
    }

    ArrayList<Node> successors = n.generateSuccessors('X');
    // Iterate through all the successors, starting with best evaluationValues
    for(Node s : successors) {
        temp = min(s, depth - 1, alpha, beta);
        if(temp.evaluationVal > value) {
            value = temp.evaluationVal;
            currentBestMove = isRoot ? s : temp;
        }
        alpha = Math.max(alpha, value);
        if(alpha >= beta) {
            break;
        }
    }
    return currentBestMove;
}

// I have a similar min() method with the opposite comparison,
// and without an isRoot argument.

Note that none of this is tested, at all.