Tiny Chess Bot Coding Challenge

Mike Sherwin · Post by **Mike Sherwin** » Sun Sep 03, 2023 6:22 pm

"Pain, pain of the ages, no kill I"
Maybe the name should be changed to"

Horta - The Devil in the Dark

There is a problem with the latest code. It loses about 800 elo.

"I'll be back."

"We'll be waiting."

"beep bloop beep bloop beep bloop"

Mike Sherwin · Post by **Mike Sherwin** » Sun Sep 03, 2023 6:57 pm

Mike Sherwin wrote: ↑Sun Sep 03, 2023 6:22 pm "Pain, pain of the ages, no kill I"
Maybe the name should be changed to"

Horta - The Devil in the Dark

There is a problem with the latest code. It loses about 800 elo.

"I'll be back."

"We'll be waiting."

"beep bloop beep bloop beep bloop"

I found the problem.

Code: Select all

if (board.IsDraw())
                    score = 0;
                else if (beta - alpha == 1)
                    score = -NegaMax(-beta, -alpha, --depth);
                else if ((score = -NegaMax(-alpha - 1, -alpha, depth - 2)) > alpha)
                    score = -NegaMax(-beta, -alpha, --depth);

score in the second "else if" can only be 1 or 0 if I understand correctly. Corrected it. It is actually winning games now but does not quite feel right.
I'll be back.

Code: Select all

using ChessChallenge.API;
using System.Linq;

public class MyBot : IChessBot
{
    ulong[] pst = {
        0x04BE53FA54055052,0x30C0140E5C47C052,0x2D41E3FA46C97852,0x1DC0D42052090052,
        0x0943C438550C7052,0x1442D3CC50C78052,0x2642C3F85D0A1052,0x2BC2E41059473052,
        0x33BE93F054C840B4,0x24BDA3FA5F4940D8,0x1B3FC42E56CCC88F,0x21C02436580BA8B1,
        0x213F145A62CB4096,0x2343A4406A0C78D0,0x1241D3EE5FCAC074,0x16C374124F8A0047,
        0x20BF43B05749104C,0x313F03E0648C6859,0x264083EE660BB06C,0x1D409402654C9071,
        0x1B41E3DC640D2893,0x2843941467CE908A,0x30430434648CD06B,0x1A43A3DA5ACBE83E,
        0x1CBE638A5A4A4044,0x1B3E63A45C8B105F,0x1F3F13C8600B2058,0x17BF13EE67CC3067,
        0x164003EA648BB069,0x18C12400648CB05E,0x1E3FF3AA5D0B1863,0x134023925ACB383B,
        0x0CBF837259CA2037,0x24BE73865E8AA850,0x17BF83A25E8B084D,0x11BF73B861CAF05E,
        0x0E3FF3CC63CB6863,0x0F3FD3AC5E4B2058,0x14C043C65DCB305C,0x0BBFE38C5C4A4839,
        0x1E3F33605B49D038,0x1E4033885F0A404E,0x1A3F639A5F0AE84E,0x0E3FF3985F0AD848,
        0x0F3FC3C05ECB2055,0x164033BA620B1055,0x1DC0F3B05FCB5073,0x17C063785DCA0846,
        0x25BDE3625C49A02F,0x28BF939A5F08E051,0x2140C3925F4A283E,0x054033A85B4A703B,
        0x0FC093B85D0A8043,0x1D4103D0608B186A,0x29BFE3AE638A1878,0x2940232C5B89F03C,
        0x1DC0039453074052,0x373EF3A05A89E052,0x2B3F83BC57C8B852,0x0A40B3DC56098052,
        0x293F23DA580A0052,0x173E83C85849A852,0x313E23705189F052,0x2C3CF3865609D052,
        0x0039F41A46C6F85E,0x13BBE4144507985E,0x1C3BE4244788605E,0x1C3C341E4847E85E,
        0x1FBC34184887D05E,0x2CBBB4184807F05E,0x273B24104606D05E,0x1CBBC40A4445B05E,
        0x1F39741648480110,0x2DBBC41A4948890B,0x2C3C841A4C0800FC,0x2DBD14164748B8E4,
        0x2DBE23FA498880F1,0x383C1406470800E2,0x30BC641049480903,0x2ABA840646C72919,
        0x2A39440E4AC808BC,0x2DBAE40E484828C2,0x30BB140E4A4918B3,0x2CBD940A4A0910A1,
        0x2F3D740849C8C096,0x3BBCB3FA4BC88093,0x3B3BB3F64A4830B0,0x2BBB13FA4B4780B2,
        0x213AB4084988407E,0x303BE4064C88E076,0x313C041A4D49786B,0x32BD54024C897863,
        0x323E14044DC9785C,0x35BD04024CC92062,0x323E13FE4B09086F,0x26BCC4044AC8386F,
        0x1C39640648C8386B,0x233C440A4B089867,0x2FBBB4104D89485B,0x313D74084F099057,
        0x32BC73F64C094857,0x30BCA3F44CC95056,0x29BCF3F04988E861,0x1FBBF3EA4808385D,
        0x1BB983F847481062,0x23B8D4004988B065,0x2ABB73F64C48C058,0x2FBAE3FE4CC9405F,
        0x30BB13F24D89185E,0x2D3B93E84B08B059,0x28BB23F04888285D,0x20BAD3E046881856,
        0x17B923F446C7786B,0x1FB913F445C82866,0x2738A40048887866,0x2BB984044A08A068,
        0x2C3983EE4B48B86B,0x273913EE4808285E,0x22B843EA46881060,0x1CB883FA43876857,
        0x0AB873EE4487E05E,0x1438C4044807305E,0x1AB924064488105E,0x1FB7D3FE4908505E,
        0x173A33F64808185E,0x1E3883E64648385E,0x193944084907385E,0x0FB7F3D84606C85E
    };

    public Move Think(Board board, Timer timer)
    {
        int alpha, depth = 1;
        var moves = GetOrderedMoves(false);
        for (; timer.MillisecondsElapsedThisTurn <= timer.MillisecondsRemaining / 100;
            depth++)
        {
            System.Console.WriteLine(depth); //TODO remove
            alpha = -99999;
            for (int i = 0; i < moves.Length; i++)
            {
                Move move = moves[i];
                board.MakeMove(move);
                if (board.IsInCheckmate())
                {
                    board.UndoMove(move);
                    return move;
                }
                int score = board.IsDraw()
                    ? 0
                    : -NegaMax(-99999, -alpha, depth);
                board.UndoMove(move);

                if (score > alpha)
                {
                    moves[i] = moves[0];
                    moves[0] = move;
                    alpha = score;
                }
            }
        }
        return moves[0];

        int NegaMax(int alpha, int beta, int depth)
        {
            int score = Eval();
            bool q = depth <= 0;

            if (q)
            {
                if (score >= beta) return beta;
                if (score >= alpha) alpha = score;
            }
            else if (depth > 1 && score - 10 >= beta && board.TrySkipTurn())
            {
                //Hack: reuse the boolean for beta cutoff
                q = -NegaMax(-beta, -beta + 1, depth - 3 - depth / 4) >= beta;
                board.UndoSkipTurn();
                if (q)
                    return beta;
            }

            var moves = GetOrderedMoves(q);
            for (int i = 0; i < moves.Length; i++)
            {
                Move move = moves[i];
                board.MakeMove(move);
                if (board.IsInCheckmate())
                {
                    board.UndoMove(move);
                    return 9999 - board.PlyCount;
                }
                if (board.IsDraw())
                    score = 0;
                else if (beta - alpha == 1)
                    score = -NegaMax(-beta, -alpha, --depth);
                else
                {
                    score = -NegaMax(-alpha - 1, -alpha, depth - 2);
                    if (score > alpha)
                        score = -NegaMax(-beta, -alpha, --depth);
                } 
                board.UndoMove(move);

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

        int Eval()
        {
            int eval = 0, mg = 0, eg = 0;
            foreach (PieceList list in board.GetAllPieceLists())
                foreach (Piece piece in list)
                {
                    int square = piece.Square.Index ^ (piece.IsWhite ? 0x38 : 0),
                        type = (int)piece.PieceType - 1,
                        mul = piece.IsWhite ? 1 : -1;
                    mg += mul * (int)(pst[square] >> type * 11 & 0b11111111111);
                    eg += mul * (int)(pst[square + 64] >> type * 11 & 0b11111111111);
                    eval += 0x00042110 >> type * 4 & 0x0F;
                }
            if (eval > 24) eval = 24;
            return (mg * eval + eg * (24 - eval)) / 24 * (board.IsWhiteToMove ? 1 : -1);
        }

        Move[] GetOrderedMoves(bool capturesOnly) =>
            board.GetLegalMoves(capturesOnly)
                .OrderByDescending(m => m.CapturePieceType)
                .ToArray();
    }
}

leanchess · Post by **leanchess** » Sun Sep 03, 2023 7:17 pm

lithander wrote: ↑Sun Sep 03, 2023 3:20 pm I haven't spent any time on the challenge since my last post here. Only today I logged into the Discord for the first time and also checked out the Stockfish-equivalent of the competition called Tyrant: https://github.com/Tyrant7/Chess-Challenge

It's open source, strong and there seem to be many clones already. If we plan to submit something as a community effort I think our contribution should win a decent amount of games against but without taking it's ideas. Otherwise it's just too embarrassing.

Yes, Tyrant is great. I had to use at least his idea of phase weight compression, and I fully intend to use decimal PST compression. There might have been some additional influences, but those are up to Mike to admit

Spoiler: Currently Tyrant wins all games against the EvalBot. So how could we get there? What are the next steps?

A transposition table might be a good idea. Or we could try a mobility based eval like OliThink?

I think TT is a necessity. Would you like to contribute it?

As for OliThink, I'm unfamiliar. is it better than PeSTO? How about your 20-second tuning technique?

lithander · Post by **lithander** » Mon Sep 04, 2023 3:31 am

leanchess wrote: ↑Sun Sep 03, 2023 7:17 pm I think TT is a necessity. Would you like to contribute it?

I implemented one tonight to the most recent version posted here. Improved the search depth quite significantly and seemed to work well but it used up all the remaining tokens.

As I understand it now the last posted version is no longer the latest revision so I refrain from posting anything today. I'll try to catch up tomorrow.

Btw... we could use github and pull requests

but copy pasting also works as long as the code is severely size constrained like this one, lol.

leanchess · Post by **leanchess** » Mon Sep 04, 2023 4:17 am

lithander wrote: ↑Mon Sep 04, 2023 3:31 am I implemented one tonight to the most recent version posted here. Improved the search depth quite significantly and seemed to work well but it used up all the remaining tokens.

Excellent!

As for token savings, using decimal compression (as seen on Tyrant) should definitely help.

As I understand it now the last posted version is no longer the latest revision so I refrain from posting anything today. I'll try to catch up tomorrow.

I PMed you our latest and greatest revision. Great to have you back on the team!

Mike Sherwin · Post by **Mike Sherwin** » Mon Sep 04, 2023 5:08 am

leanchess wrote: ↑Mon Sep 04, 2023 4:17 am
lithander wrote: ↑Mon Sep 04, 2023 3:31 am I implemented one tonight to the most recent version posted here. Improved the search depth quite significantly and seemed to work well but it used up all the remaining tokens.

Excellent!

As for token savings, using decimal compression (as seen on Tyrant) should definitely help.

As I understand it now the last posted version is no longer the latest revision so I refrain from posting anything today. I'll try to catch up tomorrow.

I PMed you our latest and greatest revision. Great to have you back on the team!

The latest problem testifies how good the new version is. It has played 6 games and won 4 of them. The other two were drawn after v3 sacked a piece on turn one and managed to draw a dead lost position some 20 moves later, lol. And I have no clue why.

leanchess · Post by **leanchess** » Mon Sep 04, 2023 5:50 am

Mike Sherwin wrote: ↑Mon Sep 04, 2023 5:08 am The latest problem testifies how good the new version is. It has played 6 games and won 4 of them. The other two were drawn after v3 sacked a piece on turn one and managed to draw a dead lost position some 20 moves later, lol. And I have no clue why.

Do you mean this game?

Mike Sherwin · Post by **Mike Sherwin** » Mon Sep 04, 2023 5:58 am

leanchess wrote: ↑Mon Sep 04, 2023 5:50 am
Mike Sherwin wrote: ↑Mon Sep 04, 2023 5:08 am The latest problem testifies how good the new version is. It has played 6 games and won 4 of them. The other two were drawn after v3 sacked a piece on turn one and managed to draw a dead lost position some 20 moves later, lol. And I have no clue why.
Do you mean this game?

Yes as well as game 6.https://chess.stjo.dev/game/654402/

Mike Sherwin · Post by **Mike Sherwin** » Mon Sep 04, 2023 11:07 pm

At the live games there are so many bots now, approaching 800, that it is really hard to get games.
iPlayChess v2 has 29 games completed and just past 1200 elo at 1202. I deleted v3 because it was buggy. Didn't find the bug(s) but v4 is now playing and does not appear to be buggy. V4 has played 8 games and is at 1065 and climbing.

leanchess · Post by **leanchess** » Tue Sep 05, 2023 3:22 am

Mike Sherwin wrote: ↑Mon Sep 04, 2023 11:07 pm At the live games there are so many bots now, approaching 800, that it is really hard to get games.
iPlayChess v2 has 29 games completed and just past 1200 elo at 1202. I deleted v3 because it was buggy. Didn't find the bug(s) but v4 is now playing and does not appear to be buggy. V4 has played 8 games and is at 1065 and climbing.

Yes, I just use it the leaderboard for quick tests, then mostly delete. iPlayChess v2 is at 1230 "ELO" ATM. Looking great!

Tiny Chess Bot Coding Challenge

Re: Tiny Chess Bot Coding Challenge

Re: Tiny Chess Bot Coding Challenge

Re: Tiny Chess Bot Coding Challenge

Re: Tiny Chess Bot Coding Challenge

Re: Tiny Chess Bot Coding Challenge

Re: Tiny Chess Bot Coding Challenge

Re: Tiny Chess Bot Coding Challenge

Re: Tiny Chess Bot Coding Challenge

Re: Tiny Chess Bot Coding Challenge

Re: Tiny Chess Bot Coding Challenge