SebLague / Chess-Challenge

Create your own tiny chess bot!
https://www.youtube.com/watch?v=Ne40a5LkK6A
MIT License
1.77k stars 1.06k forks source link

Black king mysteriously pulled towards a1 square #386

Closed NechZ closed 1 year ago

NechZ commented 1 year ago

Using the minimax algorithm, the bot wins almost every game with the white pieces, with the black ones however the black king sprints to the a1 square as soon as he can and that is really devastating because neither I nor the forums I asked around in can spot the bug. What is most curious is that it truly thinks moving to the a1 square is gonna be good because the default move (should no move be better than the other) is a random move from the legal move array and there are plenty moves to choose from aside moving king to a1.

Please help, this is giving me a headache

using System;
using System.Collections.Generic;

public class MyBot : IChessBot
{
    //Adjusts accuracy of bot
    private int searchDepth = 4;

    //Diagnostic
    private int nodesearches = 0;

    //Stores the values of Piecetypes in a dictionary
    static readonly Dictionary<PieceType, int> pieceValues = new()
    {
            { PieceType.None, 0 },
            { PieceType.Rook, 50 },
            { PieceType.Bishop, 30 },
            { PieceType.Knight, 30 },
            { PieceType.Queen, 100 },
            { PieceType.Pawn, 10 },
            { PieceType.King, 10000 }
        };

    public Move Think(Board board, Timer timer)
    {
        //Diagnostic
        nodesearches = 0;

        //Store all legal moves in Array
        Move[] legalMoves = board.GetLegalMoves();

        //In case a better move isn't found, play a random move
        Random rand = new Random();
        Move bestMove = board.GetLegalMoves()[rand.Next(board.GetLegalMoves().Length)];

        //Chooses the best move out of all legal moves
        int bestEvaluation = int.MinValue;
        int evaluation;
        foreach (Move move in legalMoves)
        {
            if (move.IsPromotion && move.PromotionPieceType == PieceType.Queen)
            {
                return move;
            }

            board.MakeMove(move);
            int minimax = Minimax(board, searchDepth - 1, int.MinValue, int.MaxValue, false, timer);

            //Adjusts evaluation depending on if the bot has the white or black pieces
            evaluation = minimax * (board.IsWhiteToMove ? -1 : 1);
            board.UndoMove(move);

            //After the adjustement, a higher evaluation is favourable regardless of the pieces the bot plays
            if (evaluation > bestEvaluation)
            {
                bestEvaluation = evaluation;
                bestMove = move;
            }
        }

        //Diagnostic
        Console.WriteLine(nodesearches + " " + bestMove.ToString() + " " + bestEvaluation + " " + board.GetLegalMoves().Length);

        return bestMove;
    }

    public int Minimax(Board board, int depth, int alpha, int beta, bool isMaximizingPlayer, Timer timer)
    {
        //Ending clause of Algorithm
        if (depth == 0)
        {
            return Evaluate(board);
        }

        if (board.IsDraw())
        {
            return 0;
        }

        //Moves that result in Checkmates are the most important
        if (board.IsInCheckmate())
        {
            return isMaximizingPlayer ? int.MinValue : int.MaxValue;
        }

        //Looks into all possible evaluation outcomes
        Move[] legalMoves = board.GetLegalMoves();

        if (isMaximizingPlayer)
        {
            int maxEvaluation = int.MinValue;
            foreach (Move move in legalMoves)
            {
                board.MakeMove(move);

                //Recursively calls the method
                int evaluation = Minimax(board, depth - 1, alpha, beta, false, timer);

                //Diagnostic
                nodesearches++;

                board.UndoMove(move);
                maxEvaluation = Math.Max(maxEvaluation, evaluation);
                alpha = Math.Max(alpha, evaluation);

                //If a better move was found before, this one should not be considered
                if (beta <= alpha)
                {
                    break; // Beta cutoff
                }
            }
            return maxEvaluation;
        }
        else
        {
            int minEvaluation = int.MaxValue;
            foreach (Move move in legalMoves)
            {
                board.MakeMove(move);

                //Recursively calls the method
                int evaluation = Minimax(board, depth - 1, alpha, beta, true, timer);

                //Diagnostic
                nodesearches++;

                board.UndoMove(move);
                minEvaluation = Math.Min(minEvaluation, evaluation);

                //If a better move was found before, this one should not be considered
                beta = Math.Min(beta, evaluation);
                if (beta <= alpha)
                {
                    break; // Alpha cutoff
                }
            }
            return minEvaluation;
        }
    }
    public static int Evaluate(Board board)
    {
        //Evaluates the current state of the board based on how many pieces of each piecetype the players have
        int evaluation = 0;
        foreach (PieceType piecetype in Enum.GetValues(typeof(PieceType)))
        {
            int whitePieceCount = board.GetPieceList(piecetype, true)?.Count ?? 0;
            int blackPieceCount = board.GetPieceList(piecetype, false)?.Count ?? 0;

            // For white pieces, add their value to the evaluation
            if (piecetype != PieceType.None)
            {
                evaluation += pieceValues[piecetype] * whitePieceCount;
            }

            // For black pieces, subtract their value from the evaluation
            if (piecetype != PieceType.None)
            {
                evaluation -= pieceValues[piecetype] * blackPieceCount;
            }
        }

        //A positive evaluation is favourable for white, whereas a negative evaluation is favourable for black
        return evaluation;
    }

}
NechZ commented 1 year ago

Ive tried setting the value of the king to 0

Zadmur commented 1 year ago

Tried to play against your bot, I did see suspiciously many king moves, however they were happening with both colors and not towards the corner. It would help if you have some move series for white to play (as a human) which would evoke the behavior your described.

NechZ commented 1 year ago

I fixed it!

It turned out I was starting the minimax function in the think function with "is maximising player" as false regardless of the color of the bot.

NechZ commented 1 year ago

Closed!