Track best move from Minimax

Question

I know this kind of question has been asked before, but i was unable to solve my doubts. I have a simple Othello Engine (it plays very well actually), that uses the class below to get the best move:

import java.util.*;
import java.util.concurrent.*;

public class MinimaxOthello implements Runnable
{
  private CountDownLatch doneSignal;    
  private int maxDepth;
  private int calls;    
  private OthelloMove bestFound;
  private OthelloBoard board;
  private static float INFINITY = Float.MAX_VALUE/1000;    
  private boolean solve = false;
  private Comparator<OthelloMove> comparator = Collections.reverseOrder(new MoveComparator());

public MinimaxOthello (OthelloBoard board, int maxDepth, CountDownLatch doneSignal, boolean solve)
{
    this.board = board;        
    this.bestFound = new OthelloMove();
    bestFound.setPlayer(board.getCurrentPlayer());
    this.maxDepth = maxDepth; 
    this.doneSignal = doneSignal;                
    this.solve = solve;
}

public OthelloMove getBestFound()
{       
    return this.bestFound;
}
public void run()
{        
    float val = minimax(board, bestFound, -INFINITY, INFINITY, 0);
    System.out.println("calls: " + calls);
    System.out.println("eval: " + val);
    System.out.println();
    doneSignal.countDown();        
}

private float minimax(OthelloBoard board, OthelloMove best, float alpha, float beta, int depth)
{
    calls++;             
    OthelloMove garbage = new OthelloMove();             
    int currentPlayer = board.getCurrentPlayer();

    if (board.checkEnd())
    {                        
        int bd = board.countDiscs(OthelloBoard.BLACK);
        int wd = board.countDiscs(OthelloBoard.WHITE);

        if ((bd > wd) && currentPlayer == OthelloBoard.BLACK)
        {                
            return INFINITY/10;
        }
        else if ((bd < wd) && currentPlayer == OthelloBoard.BLACK)
        {                
            return -INFINITY/10;
        }
        else if ((bd > wd) && currentPlayer == OthelloBoard.WHITE)
        {                
            return -INFINITY/10;
        }
        else if ((bd < wd) && currentPlayer == OthelloBoard.WHITE)
        {                
            return INFINITY/10;
        }
        else 
        {                
            return 0.0f;
        }
    }
    if (!solve)
    {
        if (depth == maxDepth)
            return OthelloHeuristics.eval(currentPlayer, board);
    }

    ArrayList<OthelloMove> moves = board.getAllMoves(currentPlayer);
    if (moves.size() > 1)
    {
        OthelloHeuristics.scoreMoves(moves);        
        Collections.sort(moves, comparator);
    }

    for (OthelloMove mv : moves)
    {                                    
        board.makeMove(mv);            
        float score = - minimax(board, garbage, -beta,  -alpha, depth + 1);           
        board.undoMove(mv);             

        if(score > alpha)
        {  
            alpha = score;                
            best.setFlipSquares(mv.getFlipSquares());
            best.setIdx(mv.getIdx());        
            best.setPlayer(mv.getPlayer());                              
        }

        if (alpha >= beta)
            break;                

    }            
    return alpha;
 }  
}

I have a bestFound instance variable and my doubt is, why a have to call

OthelloMove garbage = new OthelloMove(); 

and pass it along? The code works, but it seems very weird to me!

Is there a 'better' way to get the best move or the Principal Variation? I really not a recursion expert, and this is very very hard to debug and visualize. Thanks!

**PS: You can clone it at https://github.com/fernandotenorio/

Answer 1

It looks like you can get rid of the best parameter to minimax, thereby eliminating the need for garbage, and then replace best with this.bestFound. Only set bestFound's attributes if depth = 0.

You can get the principal variation by making this.bestFound an initially empty list. Before the moves loop, create a new move. In the if (score > alpha) part, set its attributes the same as you do now. Push the move to the list right after the loop. The principal variation will then be the reverse of the list.

If it's important, here are some changes you can make to improve the multi-threadability of your class:

• Instead of storing the bestFound list as an instance variable, make it a local variable in run and add it as a parameter to minimax
• Make Board.makeMove not modify the board, but instead return a new instance of the board with the move applied. You can implement that by cloning the board and applying your move code to the clone instead of mutating this. Then, pass the cloned board to the next invocation of minimax.

Answer 2

The second argument of minimax is used to return the best move.

The business with garbage is used to keep the best move for each turn separate. With the code you've provided, this is not important. But if you wanted to produce a sequence of moves from the current board to the end of the game, you would need to have them be separate move objects.

Using a separate best-move object for each turn allows you to do a number of tricks with threading. First, you might want to limit the thinking time of the Othello AI. Tracking the best move separately at each level means that you always have the best move so far available. It also means that you could cache the best move for a board and look that up in future minimax searches.

Second, you might want to search for the best move in parallel, and this is trivial to implement when each minimax call is independent.