Search code examples
javachessminimax

Best way to remove uninteresting/losing lines in chess, in time-based solution?

I'm creating a chess engine as a practice in Java, I know it's not recommended due to speed issues but I'm doing it just for practice.

After implementing minimax with alpha-beta pruning, I thought of implementing a time-limit to find the score of a given move.

Here is the code

    private int minimax(MoveNode node, MoveNodeType nodeType, int alpha, int beta, Side side, int depth) throws Exception {

//        isInterestingLine(prevscores, node, side);


        if (depth <= 0) {
            count++;
            return node.evaluateBoard(side);
        }
//         Generate Child nodes if we haven't.
        if (node.childNodes == null || node.childNodes.size() == 0) {
            node.createSingleChild();
        }

        if (nodeType == MoveNodeType.MAX) {
            int bestValue = -1000;
            for (int i = 0; i < node.childNodes.size(); i++) {
                if (node.childNodes.get(i) == null) continue;
                int value = minimax(node.childNodes.get(i), MoveNodeType.MIN, alpha, beta, side, depth - 1);
                bestValue = Math.max(bestValue, value);
                alpha = Math.max(alpha, bestValue);
                if (beta <= alpha) {
                    break;
                }
                node.createSingleChild();
            }
//            reCalculateScore();
            return bestValue;
        } else {
            int bestValue = 1000;
            for (int i = 0; i < node.childNodes.size(); i++) {
                if (node.childNodes.get(i) == null) continue;


                int value = minimax(node.childNodes.get(i), MoveNodeType.MAX, alpha, beta, side, depth - 1);
                bestValue = Math.min(bestValue, value);
                beta = Math.min(beta, bestValue);
                if (beta <= alpha) {
                    break;
                }
                node.createSingleChild();
            }
//            reCalculateScore();
            return bestValue;
        }
    }

and the driver code.

void evaluateMove(Move mv, Board brd) throws Exception {
    System.out.println("Started Comparing! " + this.tree.getRootNode().getMove().toString());
    minmaxThread = new Thread(new Runnable() {
        @Override
        public void run() {
            try {
                bestMoveScore = minimax(tree.getRootNode(), MoveNodeType.MIN, -1000, 1000, side, MAX_DEPTH);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    });
    minmaxThread.start();
}

This is how I implemented time-limit.

long time = System.currentTimeMillis();
moveEvaluator.evaluateMove(move, board.clone()); 
while((System.currentTimeMillis() - time) < secToCalculate*1000 && !moveEvaluator.minmaxThread.isAlive()) {
}
System.out.println("Time completed! score = " + moveEvaluator.bestMoveScore + " move  = " + move + " depth = " + moveEvaluator.searchDepth) ;
callback.callback(move, moveEvaluator.bestMoveScore);

Now, Here is the problem Nf3.jpg

You see, it only calculated Bb7, because of the depth-first search time runs out before even calculating another line.

So I want a way to calculate like following in a time-limit based solution. enter image description here

Here are a few solutions I taught of.

  1. Implementing an isInteresting() function. which takes all the previous scores and checks if the current line is interesting/winning if yes then and only then calculates next child nodes.

e.g.

  • [0,0,0,0,0,0] can be interpreted as a drawn line.
  • [-2,-3,-5,-2,-1] can be interpreted as a losing line.
  1. Searching for small depth-first and then elimination all losing lines.
    for (int i = min_depth; i <= max_depth; i ++) {
        scores = [];
        for(Node childnode : NodesToCalculate) {
            scores.push(minimax(childnode, type, alpha, beta, side, i));
        }
        // decide which child node to calculate for next iterations.
    }

But, none of the solutions is perfect and efficient, In the first one, we are just making a guess and In second on we are calculating one node more than once.

Is there a better way to do this?

Solution

  • The solution to this problem used by every chess engine is iterative deepening.

    Instead of searching to a fixed depth (MAX_DEPTH in your example) you start by searching to a depth of one, then when this search is done you start again with a depth of two and you continue to increase depth like this until you are out of time. When you are out of time you can play the move of the last search that was completed.

    It may seem like lots of time will be spent on lower depth iteration that are later replaced by deeper search and that the time sent doing so is completely lost, but in practice it's not true. Since searching to a depth N is so much longer than searching at depth N-1 the time spent on the lower depth search is always much less than the time spent on the last (deeper) search.

    If your engine use a transposition table, the data in the transposition table from previous iteration will help the later iterations. The alpha-beta algorithm's performance is really sensitive to the order move are searched. The time saved by alpha-beta over minimax is optimal when the best move is searched first. If you did a search for depth N-1 before the search for depth N, the transposition table will probably contains a good guess of the best move for most positions that can then be searched first.

    In practice, in a engine using a transposition table and ordering move at the root based on previous iteration it's faster to use iterative deepening than not using it. I mean for exemple it's faster to do a depth 1 search, then en depth 2 search, then a depth3 search until say a depth 10 search than it is doing a depth 10 search right away. Plus you get the option to stop the search whenever you want and still have a move to play,=.