Chess Bot not playing to expected level - Monte Carlo Tree Search

136 Views Asked by At

I am creating a chess bot for Sebastian Lague's "Tiny Chess Bots" competition. It is using Monte Carlo Tree Search with Upper Confidence Bounds, and the issue is that it is playing very poorly - so much more that I question whether the code is correct.

The only code I have is in this C# Mybot.cs file, and the MCTS implementation is towards the bottom.

public static class Rand{
    public static Random random = new ();
}

public class Node{
    public int visits = 2;
    public double score = 1;
    public Move move;
    public Node parent;
    public List<Node> children = new List<Node>{};
    //public Node LastBestChild = null!;

    public Node(Move m, Node p){
        move = m; //move is from parent to node
        parent = p;
    }

    public void ExpandNode(Board b){
        Move[] moves = b.GetLegalMoves();
        for(int l=0; l<moves.Length; l++){
            children.Add(new Node(moves[l], this));
        }
    }

    public void Update(double result){
        visits += 1;
        //result: 0 for loss and 1 for win and 0.5 for draw
        score +=  result;

        }

    public bool IsLeaf(){
        return (children.Count == 0);
    }

    public bool HasParent(){
        return (parent != null);
    }

    public double UCBValue(){
        return ((score/visits)+ 0.4*Math.Sqrt(Math.Log(parent.visits)/visits));
    }

    public Node MaxUCB(){
        double maxVal = children[0].UCBValue();
        Node maxNode = children[0];
        foreach(Node n in children){
            double temp = n.UCBValue();
            //Console.WriteLine(n.move.ToString() + ": UCB = " + temp.ToString());
            if(temp > maxVal || (temp == maxVal && Rand.random.Next(0,1) == 0)){
                maxVal = temp;
                maxNode = n;
            }
        }
        return maxNode;
    }

    public Node MaxVisits(){
        double maxVal = children[0].visits;
        Node maxNode = children[0];
        foreach(Node n in children){
            Console.WriteLine(n.move.ToString() + ": visits = " + n.visits.ToString() + ": score = " + n.score.ToString());
            double temp = n.visits;
            if(temp > maxVal || (temp == maxVal && Rand.random.Next(0,1) == 0)){
                maxVal = temp;
                maxNode = n;
            }
        }
        Console.WriteLine("###########################################################################");
        return maxNode;
    }

};



public class MyBot : IChessBot
{
    public Move Think(Board board, Timer timer)
    {
        Move[] moves = board.GetLegalMoves();
        Node root = new Node(Move.NullMove, null!);

        for(int i = 0; i < 20000; i++){
            Board board1 = Board.CreateBoardFromFEN(board.GetFenString());
            Node currentNode = root;
            
            //Select
            while (!currentNode.IsLeaf()){
                currentNode = currentNode.MaxUCB();
                
                //Update Board when moving from Node to Node
                board1.MakeMove(currentNode.move);
            }

            //Expansion
            if (board1.GetLegalMoves().Length > 0){
                currentNode.ExpandNode(board1);
                currentNode = currentNode.children[Rand.random.Next(0, currentNode.children.Count)];
                
                //Update Board when moving from Node to Node
                board1.MakeMove(currentNode.move);
            }


            //Rollouts
            Move[] legalMoves = board1.GetLegalMoves();
            int numCurrentMoves = legalMoves.Length;
            bool colour = board.IsWhiteToMove;

            while (!board1.IsInCheckmate() && !board1.IsDraw()){ 
                Move moveToMake = legalMoves[Rand.random.Next(0, numCurrentMoves)];
            
                //Update board
                board1.MakeMove(moveToMake);
            
                legalMoves = board1.GetLegalMoves();
                numCurrentMoves = legalMoves.Length;

                colour  = !colour;
            }

            //Get results
            double result =0;
            if(board1.IsDraw()){
                result = 0.5;
            } else{
                if (board1.IsWhiteToMove == colour){
                    result = 1;
                }
            }

            //Back propagation
            while (currentNode.HasParent()){
                currentNode.Update(result);
                currentNode = currentNode.parent;
                result = 1-result;
            }
            currentNode.Update(result);


        }

        //Select Best Move
        Move bestMove = root.MaxVisits().move;
        return bestMove;
    }
}

I have reason to suspect my code is incorrect, since even when increasing the number of iterations to obscenely high amounts (400,000 1,000,000+), the engine still makes blunders like hanging the queen on move 4.

To try fix this I have:

  1. Inverted boolean flags - maybe I simply negated a flag one to many times and was maximising instead of minimising my losses.
  2. Logged the score and visits of the top level of nodes - didn't show too much.
  3. Tweaked the iteration size and exploration constant (in the UCBValue function). Didn't change much either.
0

There are 0 best solutions below