Tiny Chess Bot Coding Challenge

[leanchess]

You can compress the PST down into just 96 64-bit integers if you give each square a value between 1-256. You could go further by just storing the point differences, but the code to expand them would be longer and make the compression meaningless.

Simplifed Evaluation is symmetrical, and only requires 4 bits per value, so you can actually compress it to 128 bits per piece. Unfortunately, System.UInt128 is only available in .NET 7.0. Any chances of convincing Sebastian to upgrade?

[leanchess]

Simplifed Evaluation is symmetrical, and only requires 4 bits per value[/url]

Turns out I've been wrong in my first statement, so it's 256 bits per piece type, or 32 ulong values. After I updated Eval() the token count became 333 (I didn't optimise anything else).

I uploaded the result as LitBot 0.2. I'm not sure how strong the opponents are, but most seem to be winning (probably has something to do with my having to reduce the depth to 4).

[leanchess]

LitBot just got lucky - it faced an even weaker opponent!

[pgn][Event "Tiny Chess League"] [Site "chess.stjo.dev"] [Date "2023.08.31"] [Time "04:10:38"] [Round "?"] [White "PrincessAtta v4"] [Black "LitBot 0.2"] [Result "0-1"] [SetUp "1"] [FEN "r1b2rk1/1p3qpp/ppn5/4pp2/8/P2P1N2/1PP1BPPP/R2QR1K1 w - - 0 14"] 14. Rf1 f4 15. g3 Qf5 16. Ng5 Qxg5 17. a4 Bh3 18. Rc1 Bxf1 19. Bxf1 fxg3 20. hxg3 Nd4 21. Kh2 Rxf2+ 22. Kg1 Qxg3+ 23. Kh1 Rh2# 0-1[/pgn]

[leanchess]

Well, that's embarassing. I just incorporated the point values into the tables (dividing the result by 5), and, contrary to my intuition, LitBot got 14 tokens shorter!

Uploaded as LitBot 0.3 (0.2 is right at the median so far).

My contribution to the community project:

Code: Select all

    ulong[] pst = {
        0xE6F4B06438321400,0xEAF6B2643A341400,0xEAF2B2643A361400,0xEAF0B3653A361400,
        0xEAF0B3653A361400,0xEAF2B2643A361400,0xEAF6B2643A341400,0xE6F4B06438321400,
        0xEAF4B2633A341500,0xEAF4B4643D381600,0xF0F0B5643C3C1600,0xF0F0B4643C3D1000,
        0xF0F0B4643C3D1000,0xF0F0B4643C3C1600,0xEAF4B4643D381600,0xEAF4B2633A341500,
        0xEAEEB2633A361500,0xEEECB5643E3D1300,0xF4ECB5643E3E1200,0xF6ECB5643E3F1400,
        0xF6ECB5643E3F1400,0xF4ECB5643E3E1200,0xEEECB4643E3D1300,0xEAEEB2633A361500,
        0xEAECB4633A361400,0xEEEAB4643C3C1400,0xF6EAB5643E3F1400,0xF8E8B5643E401800,
        0xF8E8B5643E401800,0xF6EAB5643E3F1400,0xEEEAB4643C3C1400,0xEAECB3633A361400,
        0xEAEAB3633A361500,0xEEE8B4643D3D1500,0xF6E8B5643D3F1600,0xF8E6B5643E401900,
        0xF8E6B5643E401900,0xF6E8B5643D3F1600,0xEEE8B4643D3D1500,0xEAEAB3633A361500,
        0xEAEAB2633A361600,0xEEE8B4643C3C1600,0xF4E8B5643D3E1800,0xF6E6B5643E3F1A00,
        0xF6E6B5643E3F1A00,0xF4E8B5643D3E1800,0xEEE8B4643C3C1600,0xEAEAB2633A361600,
        0xEAEAB2653A341E00,0xECE8B4663C381E00,0xEEE8B4663C3C1E00,0xF0E6B4663C3C1E00,
        0xF0E6B4663C3C1E00,0xEEE8B4663C3C1E00,0xECE8B4663C381E00,0xEAEAB2653A341E00,
        0xE6EAB06438321400,0xE8E8B2643A341400,0xEAE8B2643A361400,0xECE6B3643A361400,
        0xECE6B3643A361400,0xEAE8B2643A361400,0xE8E8B2643A341400,0xE6EAB06438321400,
    };

    int Eval(Board board)
    {
        int eval = 0, value;
        foreach (PieceList list in board.GetAllPieceLists())
            foreach (Piece piece in list)
            {
                value = (byte)(pst[piece.Square.Index ^ (piece.IsWhite ? 0 : 0x38)] >>
                    ((int)piece.PieceType << 3));
                eval += (board.IsWhiteToMove ^ piece.IsWhite) ? value : -value;
            }
        return eval;
    }

[leanchess]

I got the sign wrong

Code: Select all

int Eval(Board board)
    {
        int eval = 0, value;
        foreach (PieceList list in board.GetAllPieceLists())
            foreach (Piece piece in list)
            {
                value = (byte)(pst[piece.Square.Index ^ (piece.IsWhite ? 0 : 0x38)] >>
                    ((int)piece.PieceType << 3));
                eval -= (board.IsWhiteToMove ^ piece.IsWhite) ? value : -value;
            }
        return eval;
    }

[Mike Sherwin]

I got the sign wrong

Code: Select all

int Eval(Board board)
    {
        int eval = 0, value;
        foreach (PieceList list in board.GetAllPieceLists())
            foreach (Piece piece in list)
            {
                value = (byte)(pst[piece.Square.Index ^ (piece.IsWhite ? 0 : 0x38)] >>
                    ((int)piece.PieceType << 3));
                eval -= (board.IsWhiteToMove ^ piece.IsWhite) ? value : -value;
            }
        return eval;
    }

Thank you for contributing! I wonder why this cute little competition has not garnered more interest here.

[Ras]

I wonder why this cute little competition has not garnered more interest here.

C#, that's why.

[Mike Sherwin]

Mike Sherwin made me aware of a new Youtube video from SebLague in which he announces a coding challenge where you're going to create small chess bots in C#.

The framework and documentation is provided here: https://github.com/SebLague/Chess-Challenge
I forked it and it ran with no issues in my already installed copy of Visual Studio and opened a nice simplistic GUI. If you want to take part in the challenge you have to write your own bot using his API under a fun constraint: The Bot Brain Capacity may not exceed 1024!

He explains all that in his video and on github but basically the code you submit is converted into an abstract syntax tree and then the amount of tokens are counted. I think it makes a much better constraint than counting characters or measuring the compile size

I found it incredibly easy to get started. After ~20 minutes I had negamax implemented using the provided API in a few lines of code:

Code: Select all

using ChessChallenge.API;

public class SimpleNegaMax : IChessBot
{
    //Implements the https://en.wikipedia.org/wiki/Negamax algorithm

    // Piece values: null, pawn, knight, bishop, rook, queen
    int[] PieceValues = { 0, 100, 300, 300, 500, 900 };
    int CheckmateScore = 9999;
    int Depth = 4;

    public Move Think(Board board, Timer timer)
    {
        Move bestMove = default;
        int bestScore = -CheckmateScore;
        foreach (Move move in board.GetLegalMoves())
        {
            board.MakeMove(move);
            int score = -NegaMax(1, board);
            board.UndoMove(move);

            if (score > bestScore)
            {
                bestMove = move;
                bestScore = score;
            }
        }
        return bestMove;
    }

    private int NegaMax(int depth, Board board)
    {
        if (depth == Depth)
            return Eval(board);

        if (board.IsInCheckmate())
            return -CheckmateScore;

        int bestScore = -CheckmateScore;
        foreach (Move move in board.GetLegalMoves())
        {
            board.MakeMove(move);
            int score = -NegaMax(depth + 1, board);
            board.UndoMove(move);

            if (score > bestScore)
                bestScore = score;
        }
        return bestScore;
    }

    private int Eval(Board board)
    {
        int eval = 0;
        for (int pieceType = 1; pieceType < 5; pieceType++)
        {
            var white = board.GetPieceList((PieceType)pieceType, true);
            var black = board.GetPieceList((PieceType)pieceType, false);
            eval += (white.Count - black.Count) * PieceValues[pieceType];
        }
        return board.IsWhiteToMove ? eval : -eval;
    }
}

https://github.com/lithander/Chess-Chal ... t/MyBot.cs

The above code translates into 227 of 1024 available Brain Capacity. So you can implement a somewhat sophisticated search *but* if I try to copy some basic PSTs in there (2*6*64) that will exceed the available brain power already. This means the "normal" approach to encode the evaluation in a bazillion of "weights" is not viable and that's effectively preventing most of the existing engine from being ported as a bot.

Sounds fun? I might share a few more simple bots to make it easier for the non C# programmers to get started. The code above doesn't need any explanation, right? But if you've got questions I'm sure the C# coders around here will be eager to help. (Me included, but I'm on vacaton in the next 2 weeks)

There seems to be an error in the eval function causing a queen to capture a protected piece.

Change from this

for (int pieceType = 1; pieceType < 5; pieceType++)

to this

for (int pieceType = 1; pieceType < 6; pieceType++)

seems to correct the problem.

[Mike Sherwin]

This version uses the leanchess evaluation. I added a quiescence search. Now I have to figure out how to add move sorting values to the moves and how to sort them. Can anyone help with this?

Code: Select all

using ChessChallenge.API;

public class MyBot : IChessBot
{
    //Implements the https://en.wikipedia.org/wiki/Negamax algorithm

    // Piece values: null, pawn, knight, bishop, rook, queen
    int[] PieceValues = { 0, 100, 320, 330, 500, 900 };
    int CheckmateScore = 9999;
    int Depth = 4;

    ulong[] pst = {
        0xE6F4B06438321400,0xEAF6B2643A341400,0xEAF2B2643A361400,0xEAF0B3653A361400,
        0xEAF0B3653A361400,0xEAF2B2643A361400,0xEAF6B2643A341400,0xE6F4B06438321400,
        0xEAF4B2633A341500,0xEAF4B4643D381600,0xF0F0B5643C3C1600,0xF0F0B4643C3D1000,
        0xF0F0B4643C3D1000,0xF0F0B4643C3C1600,0xEAF4B4643D381600,0xEAF4B2633A341500,
        0xEAEEB2633A361500,0xEEECB5643E3D1300,0xF4ECB5643E3E1200,0xF6ECB5643E3F1400,
        0xF6ECB5643E3F1400,0xF4ECB5643E3E1200,0xEEECB4643E3D1300,0xEAEEB2633A361500,
        0xEAECB4633A361400,0xEEEAB4643C3C1400,0xF6EAB5643E3F1400,0xF8E8B5643E401800,
        0xF8E8B5643E401800,0xF6EAB5643E3F1400,0xEEEAB4643C3C1400,0xEAECB3633A361400,
        0xEAEAB3633A361500,0xEEE8B4643D3D1500,0xF6E8B5643D3F1600,0xF8E6B5643E401900,
        0xF8E6B5643E401900,0xF6E8B5643D3F1600,0xEEE8B4643D3D1500,0xEAEAB3633A361500,
        0xEAEAB2633A361600,0xEEE8B4643C3C1600,0xF4E8B5643D3E1800,0xF6E6B5643E3F1A00,
        0xF6E6B5643E3F1A00,0xF4E8B5643D3E1800,0xEEE8B4643C3C1600,0xEAEAB2633A361600,
        0xEAEAB2653A341E00,0xECE8B4663C381E00,0xEEE8B4663C3C1E00,0xF0E6B4663C3C1E00,
        0xF0E6B4663C3C1E00,0xEEE8B4663C3C1E00,0xECE8B4663C381E00,0xEAEAB2653A341E00,
        0xE6EAB06438321400,0xE8E8B2643A341400,0xEAE8B2643A361400,0xECE6B3643A361400,
        0xECE6B3643A361400,0xEAE8B2643A361400,0xE8E8B2643A341400,0xE6EAB06438321400,
    };

    public Move Think(Board board, Timer timer)
    {
        Move bestMove = default;
        int bestScore = -CheckmateScore;
        int alpha = -CheckmateScore;
        int beta = CheckmateScore;
        foreach (Move move in board.GetLegalMoves())
        {
            board.MakeMove(move);
            int score = -NegaMax(-beta, -alpha, 1, board);
            board.UndoMove(move);

            if (score > bestScore)
            {
                bestMove = move;
                bestScore = alpha = score;
            }
        }
        return bestMove;
    }

    private int NegaQ(int alpha, int beta, Board board)
    {
        int eval = Eval(board);
        if (eval >= beta) return beta;
        if (eval > alpha) alpha = eval;
        foreach (Move move in board.GetLegalMoves())
        {
            if (move.IsCapture || move.IsPromotion || move.IsEnPassant)
            {
                board.MakeMove(move);
                int score = -NegaQ(-beta, -alpha, board);
                board.UndoMove(move);

                if (score > alpha)
                {
                    alpha = score;
                    if (score >= beta)
                        return beta;
                }
            }
        }
        return alpha;
    }

    private int NegaMax(int alpha, int beta, int depth, Board board)
    {
        if (depth == Depth)
            return NegaQ(alpha, beta, board);

        if (board.IsInCheckmate())
            return -CheckmateScore;

        int bestScore = -CheckmateScore;
        foreach (Move move in board.GetLegalMoves())
        {
            board.MakeMove(move);
            int score = -NegaMax(-beta, -alpha, depth + 1, board);
            board.UndoMove(move);

            if (score > alpha)
            {
                alpha = score;
                if (score >= beta)
                    return beta;
            }
        }
        return alpha;
    }

    int Eval(Board board)
    {
        int eval = 0, value;
        foreach (PieceList list in board.GetAllPieceLists())
            foreach (Piece piece in list)
            {
                value = (byte)(pst[piece.Square.Index ^ (piece.IsWhite ? 0 : 0x38)] >>
                    ((int)piece.PieceType << 3));
                eval -= (board.IsWhiteToMove ^ piece.IsWhite) ? value : -value;
            }
        return eval;
    }
}

[leanchess]

This version uses the leanchess evaluation.

leanchess uses just the piece values (PieceValues are now redundant BTW).

Now I have to figure out how to add move sorting values to the moves and how to sort them. Can anyone help with this?

You'll have to define an incremental eval method in the vein of

Code: Select all

int EvalMove(Board board, Move move) { /*...*/ }

Then create an ordered enumerable of tuples:

Code: Select all

        var tuples = board.GetLegalMoves()
            .Select(move => (move, EvalMove(board, move)))
            .OrderByDescending(tuple => tuple.Item2)
            .ToArray();

Finally, loop through the tuples:

Code: Select all

foreach ((Move move, int score) in tuples) { /*...*/ }

Remember to add

Code: Select all

using System.Linq;

HTH

Edit: Added .ToArray() to prevent deferred evaluation.