Java minimax on dots and boxes game

Question

I'm trying to implement an AI that uses Minimax for the dots and boxes game (http://en.wikipedia.org/wiki/Dots_and_Boxes)

Here is what I have so far:

 public Line makeMove(GameState gs) {

    if (gs.getRemainingLines().size() == 1) {

        return gs.getRemainingLines().get(0);

    }

    if (gs.getPlayer() == 1) {

        int minscore = -1;

        GameState g = gs.clone();

        Line lnew = null;

        List<Line> l = gs.getRemainingLines();

        for (Line l2 : l) {

            g.addLine(l2);

            if (evaluate(g) > minscore) {

                minscore = (evaluate(g));

                lnew = l2;

            }

        }

        return lnew;

    } else {

        int maxscore = 999;

        GameState g = gs.clone();

        Line lnew = null;

        List<Line> l = gs.getRemainingLines();

        for (Line l2 : l) {

            g.addLine(l2);

            if (evaluate(g) < maxscore) {

                maxscore = (evaluate(g));

                lnew = l2;

            }

        }

        return lnew;

    }

}

However, it keeps returning null and I don't think I'm implementing minimax correctly. Can anyone give me some pointers?

getRemainingLines() returns a list of moves that are still possible.

evaluate() returns an int for the score.

Answer 1

The problem is that looking at your code, it is hard to follow and hard to debug. so you can rewrite your code as follows. with the help of this code, you can test your dots and boxes code by validating that all right moves are generated and that after applying a move you have the right state with the correct player moving next. (You can play and undo long sequences of random moves to help validate that you always end up back in the start state afterward.)

You can also test your evaluation function easily on individual states to make sure it works properly. (In practice you can't usually search to the end of the game to determine the winner.)

The code is as follows:

float minimax_max(GameState g)

{

    if (g is terminal or max depth reached)

        return eval(g);

    float bestVal = -inf;

    bestMove = null;

    moves = g->getLegalMoves();

    for (m : moves)

    {

        ApplyMove(m);

        if (g->nextPlayer == maxPlayer)

            nextVal = minimax_max(g);

        else

            nextVal = minimax_min(g);

        if (nextVal > bestVal)

        {

            bestVal = nextVal;

            bestMove = m;

        }

        UndoMove(m);

    }

    return bestVal;

}