Tiny Chess Bot Coding Challenge

[leanchess]

Didn't even know about it.

Well, I just did. Funny thing is its first match was against my experimental derivative that avoids repetitions, and it drawed due to repetition

Besides, the requested depth is now 99!

I meant that 8 is too deep (hadn't noticed your addition of time management).

[Mike Sherwin]

Didn't even know about it.

Well, I just did. Funny thing is its first match was against my experimental derivative that avoids repetitions, and it drawed due to repetition

Besides, the requested depth is now 99!

I meant that 8 is too deep (hadn't noticed your addition of time management).

Oops, I did also, name = TalkChess. Also two games.

TalkChess
1031 ELO
Uploaded on 2023-09-01T08:30:16.764Z
2 Games
+14
BossyFart
TalkChess
White timed out [debug 1]
2023-09-01T08:36:20.626Z
+17
TalkChess
LUNA ROBAT V2.1
Checkmate
2023-09-01T08:34:50.902Z

[leanchess]

It really pains me to see it draw on so many repetitions. Here's my take with some token optimisations:

Code: Select all

    public Move Think(Board board, Timer timer)
    {
        Move bestMove = default;
        Move[] moves = board.GetLegalMoves();
        for (Depth = 1; Depth < 99; Depth++)
        {
            int alpha = -CheckmateScore;
            int score, bestScore = -CheckmateScore;
            bestMove = default;
            Move bestNew = default;
            for (int i = 0; i < moves.Length; i++)
            {
                Move move = moves[i];
                board.MakeMove(move);
                bool checkmate = board.IsInCheckmate(),
                    repeated = board.IsRepeatedPosition();
                score = board.IsDraw()
                    ? 0
                    : -NegaMax(-CheckmateScore, -alpha, 1, board);
                board.UndoMove(move);
                if (checkmate)
                    return move;
                if (score > bestScore)
                {
                    moves[i] = moves[0];
                    bestMove = moves[0] = move;
                    if (!repeated)
                        bestNew = bestMove;
                    bestScore = score;
                }
            }
            bestMove = bestNew.IsNull ? bestMove : bestNew;
            if (timer.MillisecondsElapsedThisTurn > timer.MillisecondsRemaining / 40)
                break;
        }
        return bestMove;
    }

Now that I'm looking at your code, shouldn't bestScore be replaced with alpha?

[Mike Sherwin]

It really pains me to see it draw on so many repetitions. Here's my take with some token optimisations:

Code: Select all

    public Move Think(Board board, Timer timer)
    {
        Move bestMove = default;
        Move[] moves = board.GetLegalMoves();
        for (Depth = 1; Depth < 99; Depth++)
        {
            int alpha = -CheckmateScore;
            int score, bestScore = -CheckmateScore;
            bestMove = default;
            Move bestNew = default;
            for (int i = 0; i < moves.Length; i++)
            {
                Move move = moves[i];
                board.MakeMove(move);
                bool checkmate = board.IsInCheckmate(),
                    repeated = board.IsRepeatedPosition();
                score = board.IsDraw()
                    ? 0
                    : -NegaMax(-CheckmateScore, -alpha, 1, board);
                board.UndoMove(move);
                if (checkmate)
                    return move;
                if (score > bestScore)
                {
                    moves[i] = moves[0];
                    bestMove = moves[0] = move;
                    if (!repeated)
                        bestNew = bestMove;
                    bestScore = score;
                }
            }
            bestMove = bestNew.IsNull ? bestMove : bestNew;
            if (timer.MillisecondsElapsedThisTurn > timer.MillisecondsRemaining / 40)
                break;
        }
        return bestMove;
    }

Now that I'm looking at your code, shouldn't bestScore be replaced with alpha?

Yes, it should be alpha, good catch.
I will put my last code in place of Evil Bot and then make your changes.

[Mike Sherwin]

It really pains me to see it draw on so many repetitions. Here's my take with some token optimisations:

Code: Select all

    public Move Think(Board board, Timer timer)
    {
        Move bestMove = default;
        Move[] moves = board.GetLegalMoves();
        for (Depth = 1; Depth < 99; Depth++)
        {
            int alpha = -CheckmateScore;
            int score, bestScore = -CheckmateScore;
            bestMove = default;
            Move bestNew = default;
            for (int i = 0; i < moves.Length; i++)
            {
                Move move = moves[i];
                board.MakeMove(move);
                bool checkmate = board.IsInCheckmate(),
                    repeated = board.IsRepeatedPosition();
                score = board.IsDraw()
                    ? 0
                    : -NegaMax(-CheckmateScore, -alpha, 1, board);
                board.UndoMove(move);
                if (checkmate)
                    return move;
                if (score > bestScore)
                {
                    moves[i] = moves[0];
                    bestMove = moves[0] = move;
                    if (!repeated)
                        bestNew = bestMove;
                    bestScore = score;
                }
            }
            bestMove = bestNew.IsNull ? bestMove : bestNew;
            if (timer.MillisecondsElapsedThisTurn > timer.MillisecondsRemaining / 40)
                break;
        }
        return bestMove;
    }

Now that I'm looking at your code, shouldn't bestScore be replaced with alpha?

I changed your code a little bit. I will upload this version.

Code: Select all

// TalkChess Bot

// contributors:
// Thomas Jahn - Leorik
// Mike Sherwin - RomiChess
// Dmitry Shechtman - LeanChess
// (Get your name added here)
// Deadline October 1st 2023

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, 10000 };
    int CheckmateScore = 9999;
    int Depth;

    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)
    {
        int score;
        Move bestMove = default;
        Move[] moves = board.GetLegalMoves();
        for (Depth = 1; Depth < 99; Depth++)
        {
            int alpha = -CheckmateScore;
            bestMove = default;
            Move bestNew = default;
            for (int i = 0; i < moves.Length; i++)
            {
                Move move = moves[i];
                board.MakeMove(move);
                bool checkmate = board.IsInCheckmate();
                if (board.IsRepeatedPosition())
                    score = 0;
                else
                score = board.IsDraw()
                    ? 0
                    : -NegaMax(-CheckmateScore, -alpha, 1, board);
                board.UndoMove(move);
                if (checkmate)
                    return move;
                if (score > alpha)
                {
                    moves[i] = moves[0];
                    bestMove = moves[0] = move;
                    bestNew = bestMove;
                    alpha = score;
                }
            }
            bestMove = bestNew.IsNull ? bestMove : bestNew;
            if (timer.MillisecondsElapsedThisTurn > timer.MillisecondsRemaining / 100)
                break;
        }
        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;
        Move[] move = board.GetLegalMoves();
        for (int i = 0; i < move.Length; i++)
        {
            if (move[i].IsCapture || move[i].IsPromotion || move[i].IsEnPassant)
            {
                Move tempMove;
                Piece capturedPiece1 = board.GetPiece(move[i].TargetSquare);
                int capturedPieceValue1 = PieceValues[(int)capturedPiece1.PieceType];
                for (int j = i + 1; j < move.Length; j++)
                {
                    Piece capturedPiece2 = board.GetPiece(move[j].TargetSquare);
                    int capturedPieceValue2 = PieceValues[(int)capturedPiece2.PieceType];
                    if (capturedPieceValue2 > capturedPieceValue1)
                    {
                        tempMove = move[i];
                        move[i] = move[j];
                        move[j] = tempMove;
                    }
                }

                board.MakeMove(move[i]);
                if (board.IsInCheckmate())
                {
                    board.UndoMove(move[i]);
                    return CheckmateScore - board.PlyCount;
                }
                if (board.IsDraw())
                {
                    board.UndoMove(move[i]);
                    return 0;
                }
                int score = -NegaQ(-beta, -alpha, board);
                board.UndoMove(move[i]);

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

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

        int bestScore = -CheckmateScore;
        Move[] move = board.GetLegalMoves();
        for (int i = 0; i < move.Length; i++)
        {
            Move tempMove;
            Piece capturedPiece1 = board.GetPiece(move[i].TargetSquare);
            int capturedPieceValue1 = PieceValues[(int)capturedPiece1.PieceType];
            for (int j = i + 1; j < move.Length; j++)
            {
                Piece capturedPiece2 = board.GetPiece(move[j].TargetSquare);
                int capturedPieceValue2 = PieceValues[(int)capturedPiece2.PieceType];
                if (capturedPieceValue2 > capturedPieceValue1)
                {
                    tempMove = move[i];
                    move[i] = move[j];
                    move[j] = tempMove;
                }
            }

            board.MakeMove(move[i]);
            if (board.IsInCheckmate())
            {
                board.UndoMove(move[i]);
                return CheckmateScore - board.PlyCount;
            }
            if (board.IsDraw()) {
                board.UndoMove(move[i]);
                return 0;
            }
           if (beta - alpha > 1)
            {
                score = -NegaMax(-alpha - 1, -alpha, depth + 2, board);
                if (score > alpha)
                    score = -NegaMax(-beta, -alpha, depth + 1, board);
            }
            else
            {
                score = -NegaMax(-beta, -alpha, depth + 1, board);
            }
            board.UndoMove(move[i]);

            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;
    }
}

[Mike Sherwin]

Two versions now competing:
316 TalkChess 1079 elo 13 games
383 TalkChess02 1015 elo 2 games

[leanchess]

Two versions now competing:
316 TalkChess 1079 elo 13 games
383 TalkChess02 1015 elo 2 games

I don't know how you're doing this. I uploaded exactly the same bot (unless you are hiding something ) as TalkChess Bot 0.5, and it got just 1021 ELO.

[leanchess]

(PieceValues are now redundant BTW)

I believe that still holds. You don't need piece values for sorting, since the values themselves are monotonous.

Here's a much simpler method:

Code: Select all

Move[] GetOrderedMoves(Board board) =>
    board.GetLegalMoves()
        .OrderByDescending(move => move.CapturePieceType)
        .ToArray();

You may now remove all sorting code and just enumerate:

Code: Select all

foreach (Move move in GetOrderedMoves(board)) { /*...*/ }

Edit: The code you posted most recently behaves identically to your previous version w.r.t. repetitions, since IsDraw() uses IsRepeatedPositions().

[Mike Sherwin]

Two versions now competing:
316 TalkChess 1079 elo 13 games
383 TalkChess02 1015 elo 2 games

I don't know how you're doing this. I uploaded exactly the same bot (unless you are hiding something ) as TalkChess Bot 0.5, and it got just 1021 ELO.

I'm not being tricky!
TalkChess after 16 games 1094 elo
TalkChess02 after 12 games 1102 elo

Edit: After 13 games TalkChess02 1108 elo
Has only lost 1 game.
Has checkmated an opponent 4 times.
Made 4 3-fold repetitions.
Opponents timed out 3 times.
One opponent made an Illegal move.

[Mike Sherwin]

(PieceValues are now redundant BTW)

I believe that still holds. You don't need piece values for sorting, since the values themselves are monotonous.

Here's a much simpler method:

Code: Select all

Move[] GetOrderedMoves(Board board) =>
    board.GetLegalMoves()
        .OrderByDescending(move => move.CapturePieceType)
        .ToArray();

You may now remove all sorting code and just enumerate:

Code: Select all

foreach (Move move in GetOrderedMoves(board)) { /*...*/ }

Edit: The code you posted most recently behaves identically to your previous version w.r.t. repetitions, since IsDraw() uses IsRepeatedPositions().

I tried removing the piece values and it gave me an error.
As for the rest, I'm on it. Thanks!