Why does my engine want to perpetually check?

[emadsen]

To me, the phrase "I'm going to write a didactic engine" has become a cop-out, to be able to quit after the engine gets to the stage of playing legal chess somehow... You think this is funny? Thought you could just write an engine and then NOT see how well (or not) it does against other engines? Think again...

Marcel, this seems out of character for you. Why the hostility? Excuse me for being direct, but don't you feel your harsh criticism here is a bit misaligned with the strength of the engine you've written? Sorry, I said it. I don't know, maybe you're just having a bad day.

So now you want to prove that yes, you CAN write a strong engine in that [non C or C++] language despite the drawback in speed. You're in for it. You're doomed... I couldn't even begin to write a chess engine in software such as C#, Java, Python, Kotlin, or whatever... I'd never be satisfied with the speed.

What are you talking about? Combusken (3111) is written in Go. Chess22k (3077) is written in Java. TomitankChess (2818) is written in JavaScript. My modest engine (2530) is written in C#. All of these languages have a managed-memory runtime with a garbage collector.

Algorithms matter more than programming language. Your advice reminds me of a guy who gets really into poker and shows up at a home game wearing a hoodie and sunglasses. But can't count outs, figure pot or implied odds, size bets relative to stacks, or do any of the relevant math. Yes, observing an opponent's sweat glands, pulse (neck vein), and eye movements matter... at the margins, at the extreme margins at the upper echelon of the game. Everywhere else, math dominates. Same here: algorithms and code correctness dominate.

Brian, I'll read through your code and let you know if I spot anything suspect that could lead to perpetual checks...

[Nomis]

What are you talking about? Combusken (3111) is written in Go. Chess22k (3077) is written in Java. TomitankChess (2818) is written in JavaScript. My modest engine (2530) is written in C#. All of these languages have a managed-memory runtime with a garbage collector.

I don't think that was his point. I read his message as:

It would eat me alive to think that my engine could be (even marginally) faster and have 20+ elo had I chosen C++

[emadsen]

Why does my engine want to perpetually check? ... Is it advisable to check for the 3 repetitions, and if ahead by "enough" either don't generate a move that will allow that draw claim, or score it appropriately?

Oh I see now you didn't post any code... A few ideas:

Ensure your search function recognizes terminal draws. At the beginning of my search function (other than determining if maximum time / nodes have elapsed) I determine if the current position is a draw.

Code: Select all

var (terminalDraw, repeatPosition) = _evaluation.IsTerminalDraw(Board.CurrentPosition);
if ((Depth > 0) && terminalDraw) return 0; // Game ends on this move.

Be careful to distinguish terminal draws from drawish endgames (KRkbn). Repetitions, 50 move rule, and insufficient material should terminate the search at that node.

Code: Select all

public (bool TerminalDraw, bool RepeatPosition) IsTerminalDraw(Position Position)
{
    // Only return true if position is drawn and no sequence of moves can make game winnable.
    if (_isRepeatPosition(DrawMoves)) return (true, true); // Draw by repetition of position.
    if (Position.HalfMoveNumber >= 99) return (true, false); // Draw by fifty moves without a capture or pawn move.
    // Determine if insufficient material remains for checkmate.
    if (Bitwise.CountSetBits(Position.WhitePawns | Position.BlackPawns) == 0)
    {
        // Neither side has any pawns.
        if (Bitwise.CountSetBits(Position.WhiteRooks | Position.WhiteQueens | Position.BlackRooks | Position.BlackQueens) == 0)
        {
            // Neither side has any major pieces.
            if ((Bitwise.CountSetBits(Position.WhiteKnights | Position.WhiteBishops) <= 1) && (Bitwise.CountSetBits(Position.BlackKnights | Position.BlackBishops) <= 1))
            {
                // Each side has one or zero minor pieces.  Draw by insufficient material.
                return (true, false);
            }
        }
    }
    return (false, false);
}


// Repeats == 2 in analysis mode, 3 otherwise.
public bool IsRepeatPosition(int Repeats)
{
    var currentPositionKey = CurrentPosition.Key;
    var positionCount = 0;
    // Examine positions since the last capture or pawn move.
    var firstMove = Math.Max(_positionIndex - CurrentPosition.HalfMoveNumber, 0);
    for (var positionIndex = _positionIndex; positionIndex >= firstMove; positionIndex -= 2) // Advance by two ply to retain same side to move.
    {
        if (_positions[positionIndex].Key == currentPositionKey) positionCount++;
        if (positionCount >= Repeats) return true;
    }
    return false;
}

Be aware of this nasty draw-by-repetition bug.

Drawish endgames still can be won by your engine's opponent if your engine is careless, so allow the search to continue but return a score of zero from the evaluation function.

Another possibility is your quiescence search returns a really low score when the king is in check (== really high score when the opponent king is in check). This combined with no or buggy draw-by-repetition detection would cause the engine to harass the opponent king with perpetual checks. If the quiescence search returns a really high score for opponent king in check, and no mate is in sight, the engine will prefer perpetual checking over grabbing a pawn.

Another possibility is your quiescence search only searches captures even when the king is in check. It should search only captures when the king is not in check. It should search all moves when the king is in check. To verify your implementation is correct, in the quiescence search function, I suggest setting the staticScore variable to a sentinel value when the king is in check (rather than calling evaluation function). Check for the sentinel value in the line of code immediately after a call to the quiescence search function and throw an exception if staticScore == sentinelValue. A Debug.Assert is perfect for this kind of test because it's not included in Release builds.

[lojic]

To me, the phrase "I'm going to write a didactic engine" has become a cop-out, to be able to quit after the engine gets to the stage of playing legal chess somehow... You think this is funny? Thought you could just write an engine and then NOT see how well (or not) it does against other engines? Think again...

Marcel, this seems out of character for you. Why the hostility? Excuse me for being direct, but don't you feel your harsh criticism here is a bit misaligned with the strength of the engine you've written? Sorry, I said it. I don't know, maybe you're just having a bad day.
...

I took this as (very) dry humor i.e. he was hinting that despite my original goals, I'm going to get hooked by the competitive aspect that seems to happen so frequently :) I didn't take any offense.

You're of course right about the importance of algorithms/data structures - I was just reading in Jon Bentley's "Programming Pearls" about Andrew Appel's account of progressively reducing the run time of his n-body simulation from a year to a day. He didn't change programming languages, but he did identify one function, through profiling, that he re-wrote in assembler.

I find enjoyment in working with certain constraints and pushing the boundary of what can be done within them. If I do get the competitive itch, I would probably give Julia a try - I'm pretty sure it would get me close enough to C++ w/ less pain :)

[lojic]

Why does my engine want to perpetually check? ... Is it advisable to check for the 3 repetitions, and if ahead by "enough" either don't generate a move that will allow that draw claim, or score it appropriately?

Oh I see now you didn't post any code... A few ideas:
...

The code is here: https://github.com/lojic/RacketChess

I'll look into the things you mentioned - thanks!

[emadsen]

I don't think that was his point. I read his message as "It would eat me alive to think that my engine could be (even marginally) faster and have 20+ elo had I chosen C++."

You're missing my point. Why worry about marginal 20 Elo benefits when your engine is 1416 Elo beneath the top managed-runtime engine? In my opinion, that's worrying about an insignificant factor. Same as the poker newbie worrying his eyes and facial expressions are giving away his hole cards and compromising his game. No, his inadequate math skills are compromising his game.

[Nomis]

You're missing my point. Why worry about marginal 20 Elo benefits when your engine is 1416 Elo beneath the top managed-runtime engine?

I think the number 20 and the word 'marginal' should hint that no, I'm not.

[mvanthoor]

I took this as (very) dry humor i.e. he was hinting that despite my original goals, I'm going to get hooked by the competitive aspect that seems to happen so frequently I didn't take any offense.

The second part of that post was indeed intended as such. I hope you really do write a didactic engine with good documentation and no bugs. I have looked into your code, and... eh... I don't understand zilch about it. Racket (Lips/Scheme?) is completely alien to me as a programming language. I don't know the language, but it seems interesting, and I like the fact that you're not "just" using C or C++ like most people do, because you "just write chess engines in C or C++, and that's how it is".

Just don't get distracted by the urge to add as many features as you can as quickly as possible, trying to get as high as possible in the rating list; it'll be a great source of bugs. First write the engine; make the code as clean and fast as you reasonably can. The features will come later.

I saw you intend to keep a rating progression per feature, the same way Eric has done, and as I am doing; so I assume you're indeed going to write the most basic engine first, and then add ONE feature at a time, test it, and then add ONE more... and so on.

(Re: Combusken, TomiTank, etc... with them, I also like the fact that they use something different than C or C++, but I don't like the languages themselves.)

I find enjoyment in working with certain constraints and pushing the boundary of what can be done within them. If I do get the competitive itch, I would probably give Julia a try - I'm pretty sure it would get me close enough to C++ w/ less pain

ANYTHING will get you anywhere with less pain. The only "C++" I've ever written was actually "C, with classes and Boost where possible". That was still doable.

[mvanthoor]

Marcel, this seems out of character for you. Why the hostility? Excuse me for being direct, but don't you feel your harsh criticism here is a bit misaligned with the strength of the engine you've written? Sorry, I said it. I don't know, maybe you're just having a bad day.

Maybe it came across a bit too harsh. Sorry. That wasn't the intention. I *REALLY HOPE* that hojic writes a really didactic engine that can teach people how to write a chess engine, in Racket, if they want to do so. The reason why I'm skeptical about "I'm going to write a didactic engine" often turns out to be "I wrote a pile of code that somehow plays chess, and I flung it onto GitHub. Good luck." You can't image how many "didactic" engines I tried to compile and use in my early tests as comparisons and either failed to either compile, or run them properly because of missing documentation or bugs. Engines with uncommented, and nearly unreadable code.

Rustic is going to be what people would call a "didactic engine", with commented code (35%+ of Rustic's source code is actually comments, explaining what and why the code is doing), and documentation to go with it. (I'm writing that now, actually.) Not because I want to write a didactic engine, but because that is how I write software.

The strength of the engine is of no consequence at this point. "The engine you've written" sounds as if it's done and over with. It isn't. It has no features, and it sits there in the rating list at +/- 300 ELO stronger than similar featureless engines. You have a particular rating in mind (stronger than Madchess 2, probably) before you release the engine as Madchess 3. I have no previous engine to use as a benchmark, so I can just release the first, most basic version and build on that.

What are you talking about? Combusken (3111) is written in Go. Chess22k (3077) is written in Java. TomitankChess (2818) is written in JavaScript. My modest engine (2530) is written in C#. All of these languages have a managed-memory runtime with a garbage collector.

I am convinced that if Combusken was written in Rust, which is about 4-5x faster than Go for the same application, the engine would have been in the 3200 range already. I'm not going to discuss why I dislike Go, Java, JavaScript, Python, PHP and quite some other programming languages, because then I'll probably seriously offend some people, which I don't want to do.

Of the managed languages I've used up until now, I think that C# is the only one moving in the right direction, if Microsoft can manage to get it to compile to a single 1 MB executable with .NET 5; maybe they can now. They couldn't with Core 2.x and 3.x.)

Algorithms matter more than programming language. Your advice reminds me of a guy who gets really into poker and shows up at a home game wearing a hoodie and sunglasses...

The difference between the hoody/sunglass guy is that I can indeed play chess, and write software. Rustic's basis is solid (with the exception of using int instead of enum for pieces and squares, which I'll have to look into someday). I'm convinced that the only limitation of my engine's strength is how much effort, time, and computing power I'm willing or able to put into it.

I don't think that was his point. I read his message as:

It would eat me alive to think that my engine could be (even marginally) faster and have 20+ elo had I chosen C++

Basically, yes. I work(ed) in industrial engineering, where software is required to do things like package 50 units per minute. If the software is only 10% slower than expected and handles 45 objects/min, that means it'll fall short by 5 units * 60 minutes * 8 hours = 2.400 objects in a working day, or about 50.000 units a month.

So yes... when I added incremental evaluation to my engine, the evaluation function (and search) got MUCH faster, but it took me some time to accept the 10% speed drop of the Perft function, even though I _knew_ beforehand that this function was going to slow down.

Seeing the search speed become slower and slower as I add more evaluation to my engine fills me with dread even only thinking about it... even though I know the engine will become stronger because of the extra evaluation terms.

[lojic]

I took this as (very) dry humor i.e. he was hinting that despite my original goals, I'm going to get hooked by the competitive aspect that seems to happen so frequently :) I didn't take any offense.

The second part of that post was indeed intended as such. I hope you really do write a didactic engine with good documentation and no bugs. I have looked into your code, and... eh... I don't understand zilch about it. Racket (Lips/Scheme?) is completely alien to me as a programming language. I don't know the language, but it seems interesting, and I like the fact that you're not "just" using C or C++ like most people do, because you "just write chess engines in C or C++, and that's how it is".

To be very clear, the code as it stands now is not in the form it will need to be in to be instructive for beginners. It's going to take a lot of work to take it from "working well", once I get there, to "very readable/understandable", but I'm looking forward to that process. I expect it will involve a fair amount of refactoring, and I'll likely sacrifice some speed for clarity. Having said that, I understand that even when it's in good shape, it may still be difficult to understand for a set of people simply due to being a lisp.

Rather than blog about the process as I go, I think I'd rather complete version 1.0, and then essentially re-build it piece by piece and post a blog article about each piece. With me doing manual time management, it's beaten a number of 1,800+ human players, so I think I'm making reasonable progress. It seems much weaker against other chess engines, e.g. I have to give it a decent amount of time per move to beat Wukong at the "Code Monkey King (1700)" level :) If my engine moved as fast, it would be crushed every time, but I've yet to add TT & other features; I only have quiescent search & a super simple PST now.