Accessing the move sequence that negamax bases its evaluation upon

[kaapipo]

Hello everyone! I am in the process of creating my own chess engine based on negamax. It would greatly help debugging if I was be able to access the move sequence that the negamax algorithm bases its evaluation on (where on the decision tree the evaluated value is found).

The relevant part of the decision tree algorithm is:

Code: Select all

    private double deepEvaluateBoard(Board board, int currentDepth, double alpha, double beta, Move initialMove) {
        if (board.isCheckmate() || board.isDraw() || currentDepth <= 0) {
            this.moveHistorys.put(initialMove, board.getMoveHistory()); // this is not working
            return evaluateBoard(board); // evaluateBoard evaluates from the perspective of color whose turn it is.
        } else {
            double totalPositionValue = -1e40;

            List<Move> allPossibleMoves = board.getAllPossibleMoves();
            for (Move move : allPossibleMoves) {
                board.makeMove(move);
                totalPositionValue = max(-deepEvaluateBoard(board, currentDepth - 1, -beta, -alpha, initialMove), value);
                board.unMakeMove(1);

                alpha = max(alpha, totalPositionValue);
                if (alpha >= beta) {
                    break;
                }
            }

            return totalPositionValue;
        }
    }
    

Currently I am trying to save the move history of the board into a hashmap that is a field of the enclosing class. However, it is not working for some reason, as the produced move sequences are not optimal.

Since developing an intuition for negamax is not very easy, I have ended up on banging my head against the wall on this one for quite some time now. I would much appreciate if someone could point me in the right direction! Thank you in advance!

[delphi_coder]

This was also one of my problems on first day. This code from my engine (at this moment simply alpha beta TT) maybe useful. I think its much better for understanding than explanation

Code: Select all

function Search(Board: TBitBoard; Depth: Integer; Alpha, Beta: Integer; CurrentBoardKey: UInt64; MoveInfo: TMoveInfo): TMoveWithScore;
var
  i: Integer;
  MoveList: TInt64List;
  TmpBoard: TBitBoard;
  Score: TMoveWithScore;
  CurScore: TMoveWithScore;
  MovStr: string;
  Key: UInt64;
  Entry: TTEntry;
  CurMove: TMoveInfo;
begin
  nodes := nodes + 1;
  Score.Move := 0;
  Result.Move := 0;
  if Depth = 0 then
  begin
    Result.MovStr :='';
    Result.Score := QuiescenceSearch(Board,2,Alpha,Beta).Score;
    Exit;
  end;
  if GetTTEntry(CurrentBoardKey,Entry) and (entry.Depth>=Depth) then
  begin
    if Entry.EntryType = EXACT_VALUE then
    begin
      Result.Score := Entry.Value;
      Exit;
    end
    else
    if entry.EntryType = LOWERBOUND then
      Alpha := max(Alpha,Entry.Value)
    else
    if Entry.EntryType = UPPERBOUND then
      Beta := min(Beta,Entry.Value);
    if Alpha>=Beta then
    begin
      Result.Score := Entry.Value;
      Exit;
    end
  end;
  MoveList := TInt64List.Create;
  GenMoves(Board,MoveList);
  Score.Score := -MAXINT;
  if (MoveList.Count = 0) then
  begin
    if (Board.IsWhiteToMove and IsWhiteKingInCheck(Board)) or ((not Board.IsWhiteToMove) and IsBlackKingInCheck(Board)) then
      Score.Score := -10000 - Depth
    else
      Score.Score := 0;
  end
  else
  begin
    SortMoves(Board,MoveList{,CurrentBoardKey});
    for i := 0 to MoveList.Count - 1 do
    begin
      Key := CurrentBoardKey;
      TmpBoard := Board;
      CurMove := MoveList.Items[i];
      MovStr := MoveToStr(CurMove);
      DoMoveBK(TmpBoard,CurMove,Key);
      if IsThreefoldRepeatition(Key) or (TmpBoard.FiftyMove = 50) then
      begin
        PositionKeyList.Add(Key);
        Score.Score := 0;
      end
      else
      begin
        CurScore := Search(TmpBoard,Depth-1, -beta, -alpha, Key,MoveList.Items[i]);
        CurScore.Score := -CurScore.Score;
        CurScore.Move := CurMove;
        if CurScore.Score>Score.Score then
        begin
          Score := CurScore;
          Score.Move := Integer(CurMove);
        end;
      end;

      if Score.Score>=Beta then
      begin
        Result.Score := Score.Score;
        Result.MovStr := MoveToStr(CurMove)+' '+Score.MovStr;
        Result.Move := CurMove;
        break;
      end;

      if Score.Score>Alpha then
      begin
        Alpha := Score.Score;
        Result.MovStr := MoveToStr(CurMove)+' '+Score.MovStr;
        Score.Move := CurMove;
      end;
    end;
  end;
  Entry.Value := Score.Score;
  if Score.Score<=Alpha then
    Entry.EntryType := LOWERBOUND
  else
  if Score.Score>=Beta then
    Entry.EntryType := UPPERBOUND
  else
    Entry.EntryType := EXACT_VALUE;
  Entry.Depth := Depth;
  StoreTTEntry(CurrentBoardKey, Entry.Value, Entry.EntryType, Depth);
  Result.Score := Score.Score;
  Result.Move := Score.Move;
  MoveList.Free;
end;