Java minimax on dots and boxs game

Question 1

I would like to suggest that you completely re-factor your code. The problem with looking at your code (and why there haven't been many responses here) is that it's hard to follow and hard to debug. For instance, what is gs.getRemainingLines and what does it do exactly? (Why remaining lines and not all legal lines?)

But, with some simplifications it will be much easier to figure out what is going on and to fix it.

At an abstract level minimax is just this procedure:

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

I haven't shown exactly how to get/use the last move at the end, but it isn't that hard. You also need another procedure for minimax_min, or you can put an if statement into the code.

If you look at your code, you've written it close to this, but you've left a lot of game specific details in the code. But, you shouldn't have to think about those things to get minimax working correctly.

In particular, most games can be reasoned with abstractly if you provide functions for GetMoves(), ApplyMove(), UndoMove(), and eval(), which evaluates a state. (Further search enhancements would require more functions, but this will get you a long ways.)

Some reasons why you might want to re-factor in this way:

You can now test minimax and your other code separately.
You can test your dots and boxes code by validating that all legal moves are generated and that after applying a move you have a legal 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 afterwards.)
You can 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.)
You can test minimax by using a simple evaluation function and testing to see if the right moves are made. (e.g. if you prefer moves on the edges, a 1-ply search should return a move on the edge)
Other people can read your code more easily. We can look at each piece of code and see if it is correct on its own, instead of having to mix the game-specific implementation details into the minimax-specific details.
If you can apply and undo moves properly, you don't need to make copies of the game states. This will make the code much more efficient.

While you could try to fix your code without refactoring (e.g. just find the first place it returns null, and that will point out where your error is), in the long term your code will be hard to debug and improve without these changes.

Question 2

The first thing to check is that gs.getRemainingLines() actually has lines remaining.

A separate problem is that you are adding every line to the GameState g to check. You either need to remove each added line after calling evaluate or put the clone inside the loop at the top such as

int minscore = -1;
Line lnew = null;
List<Line> l = gs.getRemainingLines();
for (Line l2 : l) {
    GameState g = gs.clone();
    g.addLine(l2);
    if (evaluate(g) > minscore) {
        minscore = (evaluate(g));
        lnew = l2;
    }
}

or

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;
    }
    g.removeLine(l2);
}

However if you are trying to use minimax (http://en.wikipedia.org/wiki/Minimax) then you will need to change your code to recursively call makeMove (unless you modify the algorithm to do determine the min-max using loop constructs).

public GameState makeMove(GameState gs) {
   if (gs.getRemainingLines().size() == 1) {
       GameState g = gs.clone();
       g.addLine(gs.getRemainingLines().get(0));
       return g;
   }

   if (gs.getPlayer() == 1) {
       GameState g = gs.clone();
       g.setPlayer(2);
       int bestValue = -1;
       Line lbest = null;
       List<Line> lines = gs.getRemainingLines();
       for (Line line : lines) {
           g.addLine(line);
           GameState val = makeMove(g);
           g.removeLine(line);
           if (evaluate(val) > bestValue) {
               bestValue = evaluate(g);
               lbest = line;
           }
       }
       g.addLine(lbest);
       return g;
   } else {
       GameState g = gs.clone();
       g.setPlayer(1);
       int bestValue = 999;
       Line lbest = null;
       List<Line> lines = gs.getRemainingLines();
       for (Line line : lines) {
           g.addLine(line);
           GameState val = makeMove(g);
           g.removeLine(line);
           if (evaluate(val) < bestValue) {
               bestValue = evaluate(g);
               lbest = line;
           }
       }
       g.addLine(lbest);
       return g;
   }

}