Why does my engine want to perpetually check?

[Sven]

Oh, this is actually benefitial? I thought it a flaw and dilberately collect all moves with the same score and then pick one of those at random. Now it seems the presumed bug is a feature.

If you properly implemented alpha-beta, you will NEVER get two moves with the same score. The same 'score' can come up in a later move, but then it will not be a score, but a score bound. In particular an upper bound. The true score of the move can be arbitrarily lower. So if you first find a move that scores +80 centiPawn, and then find a second one that scores +80 centiPawn, and decide to play the second one, you should not be surprised when you lose your Queen or get mated in 1.

I don't think I messed up that badly. When you start the search for each root-move again with an infinitely wide open alpha-beta window you can legitimately get the same score on several root-moves. Now you consider all moves 'best' that lead to the same score.

So I think I do proper alpha-beta pruning and discard nodes with equal score everywhere but on the first ply, if that makes sense?

Searching each root move with the same full window is *not* proper alpha-beta pruning, unless you intend to only support multi-PV N with N=numberOfRootMoves ... Instead, you'd search *the root node* with a (full) window, and that window gets tighter for each root move that follows to a move raising alpha.

[Sven]

Oh, this is actually benefitial? I thought it a flaw and dilberately collect all moves with the same score and then pick one of those at random. Now it seems the presumed bug is a feature.

If you properly implemented alpha-beta, you will NEVER get two moves with the same score. The same 'score' can come up in a later move, but then it will not be a score, but a score bound. In particular an upper bound. The true score of the move can be arbitrarily lower. So if you first find a move that scores +80 centiPawn, and then find a second one that scores +80 centiPawn, and decide to play the second one, you should not be surprised when you lose your Queen or get mated in 1.
...

I'm not sure I fully understand you re: never getting two moves with the same score. Are you saying that you'll never have two different positions with the same static evaluation? Or that you need to programmatically modify that static evaluation so that no two will be the same?

In your example above, I would expect the second move that scores +80 cP to not raise alpha, right?

If the subtree of the second root move returns with +80 then it means that its true score is <= 80. It will very often be <80 due a beta cutoff at one of the child nodes, and therefore you don't know how bad that second move actually is. It is crucial to understand this alpha-beta stuff before continuing.

[hgm]

I'm not sure I fully understand you re: never getting two moves with the same score. Are you saying that you'll never have two different positions with the same static evaluation? Or that you need to programmatically modify that static evaluation so that no two will be the same?

No, I am talking about the score of moves as reported by the search. Not about the score of positions produced by the static evaluation.

In your example above, I would expect the second move that scores +80 cP to not raise alpha, right?

Correct; in normal alpha-beta a 'score' that appears for the second time will not raise alpha. And it wouldn't be a real score, it would be an upper bound to the score. So the move should never be eligible for playing (when it happens in the root), it can be an arbitrarily poor move that leaves an unprotected Queen hanging. Only moves that raised alpha can be relied on.

Of course you can deviate from the normal alpha-beta algorithm, and not raise alpha as much as you could. Than moves that really have the same score, or even a lower score, can still raise alpha, so that their score can be trusted. This is how some of my engines do multi-PV.

I don't think I messed up that badly. When you start the search for each root-move again with an infinitely wide open alpha-beta window you can legitimately get the same score on several root-moves. Now you consider all moves 'best' that lead to the same score.

So I think I do proper alpha-beta pruning and discard nodes with equal score everywhere but on the first ply, if that makes sense?

It will allow you to do what you do, but (as Sven already pointed out) it is NOT a proper alpha-beta implementation. In the latter you always raise alpha to the score of the best move so far, also in the root.

What you do is VERY expensive (= inefficent). In a normal alpha-beta search the engine spends about 30-50% of the time searching the first move (the PV move of the previous iteration), and then very quickly discards the other 30-40 moves in the remaining time. Meaning they are each handled about 20 times faster than the first move. This is because they are searched with the raised alpha. Only when the engine changes move there will be a move that raises alpha further, and that then might take as much time as the first move (so that the total time for the iteration will be significantly longer).

So what you do causes the engine to think some 28 times longer than necessary to reach the same depth, for no benefit. Even if you want equally scoring moves to be above alpha, so that you could randomly choose from these, it would have been far better to raise alpha to bestScore - 1. Because moves that would score lower, even if it is just 1cP lower, are of no interest to you. Most moves would then be dealt with nearly as fast as when alpha had been set to bestScore, since it has to find only marginally better counter-play to refute them. But when there really is a second move with the same score, this might then take again as much time as the PV move.

If you want randomization between moves with the same or nearly the same score, it is more efficient to add a small random bonus to the score of each move. Then there will still be only one best move, but it would be a different one each time you run the engine in the same position. You would have to make the alpha-beta search aware that you are going to timker with the score of the move afterwards, or you will start to confuse scores with bounds. But this is always OK:

score = delta - Search(-beta+delta, -alpha+delta, ...);

The values returned by Search between -beta+delta and -alpha+delta will then be exact (rather than bounds), and after flipping they ly between alpha-delta and beta-delta, so that after adding delta they will again ly between alpha and beta. Even when alpha was raised to bestScore, that means that any score larger than that indeed proves the move is better.

If you do this with small random numbers delta, it would be important to use the same delta for each move in different iterations, or it would switch moves too often. (Which is time consuming.) You only want it to be random w.r.t. different runs of the engine. Or perhaps different searches. But it should not change between iterations of the same search, as that would subvert the purpose of iterative deepening (to find the best move in a cheap way, so you can start with it in the deeper search). You can achieve this by crawing a single random number for each search, and then derive the random score additions from that and the move (or the hash key after the move). E.g.

delta = (r ^ toSqr + 256*fromSqr)*1123456789 >> 28;

with r the random number for the current search, to get a pseudo-random value ranging from -8 to +7.

[mvanthoor]

That's a little surprising that option 2 is faster, but I suppose that may have to do with Rust. I presume you don't have to allocate from the heap to push the game state.

No, there are no allocations. It's just a back-and-forth straight copy of about 24 bytes from one location in memory to the other. The reason that this is faster is because Rust works with multiples of 8 bytes. So even if I do an inverse incremental update on most variables, and I have to copy a few lets say, 10 bytes in total, Rust will copy 16 bytes back and forth. Therefore I cant just add a 1 byte variable to the game state. If I do, it becomes 25 bytes, so Rust will start copying 32 bytes back and forth.

Racket has a very fast garbage collector, but I'm still allocating as little as possible to speed things up. It would certainly simplify the code to copy the game state.

"Fast" is in the eye of the beholder. Is your engine available somewhere, and can it do perft and/or search positions already? Rustic perfts at 35-45 million leaves/sec, and searches at 3-5+ million positions per second (on an i7-6700K), and I -still- think it should be faster... even though it is faster than any of the engines I tested it against. (And there are indeed some optimizations that can still be done in the move generator, but that is for later.)

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.

Maybe I was overly influenced by this CPW page that stated:

Incremental update on the same global or shared data ever and ever, will likely keep it in fast cache memory, and saves memory bandwidth compared to a Copy-Make approach, which needs a make-update on the copy as well, but no unmake-update rather than decrementing a ply-index or fetching a pointer.

I suppose I could set up a simple benchmark comparing copy-make to incremental-update in Racket, and see how the numbers stack up.

Copy/make is something different than what I'm doing.

Copy/make copies the ENTIRE BOARD, then makes the move, and instead of unmaking it, the board is thrown away. This is indeed very slow, but relatively simple to implement. And as I said: some states such as half-move clock, or the ep-square, can't be incrementally updated. If the board changes and the ep-square gets erased, you either have to remember that it was set so you can re-set it when unmaking, or you have to deduce / calculate the state again. The ep-square is only 1 byte, but when I copy ONLY this, Rust copies 8 bytes back and forth. Same goes for some of the other fields, and in the end it turned out that just incrementally updating (during the move of a piece) whatever is possible, and push/popping the gamestate, was the fastest approach in Rust.

[lithander]

Even if you want equally scoring moves to be above alpha, so that you could randomly choose from these, it would have been far better to raise alpha to bestScore - 1. [...] But when there really is a second move with the same score, this might then take again as much time as the PV move.

That's what I actually did. But I didn't realize that this meant that a position that has N root-moves with the same score will also be N times as expensive to evaluate compared to proper alpha-beta. That's too expensive indeed! Thanks for making me aware of that!

If you want randomization between moves with the same or nearly the same score, it is more efficient to add a small random bonus to the score of each move.

Okay, that makes sense!

I could also imagine a 3rd approach: With proper alpha-beta the first PV that produces the best possible end-score sticks, right? When the search iterates over the possible moves in a random pattern (e.g. list of moves the move generator produces for a position would be in random order) wouldn't that also cause the alpha-beta to result in a PV that is always correct but not deterministic?

[hgm]

And as I said: some states such as half-move clock, or the ep-square, can't be incrementally updated.

There are two different situations in which 'incremental update' has any meaning: when there is a collection of separately modifiable items, of which only a subset has to change. (E.g. the mailbox representation of a chess board.) Or when you have the result of a complex calculation, where just a small part of that calculation changes, and there is a way to calculate how the change of that part affects the change of the whole result. (E.g. for the hash key, or the PST evaluation.)

The 50-move counter is updated incrementally: you increment it to incorporate the effect of doing yet another reversible move, rather than recounting the number of reversible moves that has been done from scratch. Since the update is irreversible (in the case of a reset), you must make a copy to undo it. As an alternative to copy-make you still have save-restore, depending on whether you do the update on the original or the copy.

[hgm]

That's what I actually did. But I didn't realize that this meant that a position that has N root-moves with the same score will also be N times as expensive to evaluate compared to proper alpha-beta.

And even worse than that, the moves that do not have the same score would add similar amounts of time as well.

I could also imagine a 3rd approach: With proper alpha-beta the first PV that produces the best possible end-score sticks, right? When the search iterates over the possible moves in a random pattern (e.g. list of moves the move generator produces for a position would be in random order) wouldn't that also cause the alpha-beta to result in a PV that is always correct but not deterministic?

Some engines do that, but it is difficult to combine with iterative deepening. The point is that the first move you search takes always long, because it has to raise alpha. If you don't start with the best move, sooner or later that best move will have to raise alpha too, and will again take a long time. And who knows how many moves there still were before that, which were not the best, but still better than the move you started with, which also have to raise alpha? So you save lots of time by starting with the best move. And your best guess for that is the best move of the previous iteration. Just randomizing before the first iteration is no problem, as it would take negligible time anyway, even if it would take 30 times longer than needed. But there is no guarantee that two moves that have equal score will have equal score in every iteration. If there is one iteration where there only is a single best that one will get to the top of the list irrespective of the initial sorting, and has a good chance to stick there even if others later rival it.

[lojic]

...

Racket has a very fast garbage collector, but I'm still allocating as little as possible to speed things up. It would certainly simplify the code to copy the game state.

"Fast" is in the eye of the beholder. Is your engine available somewhere, and can it do perft and/or search positions already? Rustic perfts at 35-45 million leaves/sec, and searches at 3-5+ million positions per second (on an i7-6700K), and I -still- think it should be faster... even though it is faster than any of the engines I tested it against. (And there are indeed some optimizations that can still be done in the move generator, but that is for later.)

Easy there, I think you misunderstood me. I said the Racket garbage collector is fast. I'm not comparing Racket's overall speed to non-gc'd languages such as Rust :) In fact, my actual point was that despite the speed of Racket's GC, it's wise to avoid allocation as much as possible.

I think my current single threaded perft is a little over 3M nodes per second on a fairly fast 2.3 GHz 8-Core Intel Core i9 on my Macbook Pro 16", so significantly slower than Rustic. My search is between 500K and 900K, but it's a very simple evaluator right now, so that will slow down (although I also haven't done much performance tuning). Racket is certainly fast enough to achieve my original goal of beating me in a 10+5 game (I'm ~ 1,650). And now I'm inspired to make a great didactic engine. With Racket's unparalleled meta-programming facilities, I think I'll be able to create a super readable/understandable engine that plays "reasonably" strong.

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.
...

It all depends on your goals :)

I originally began this project with Julia which, while it's not quite as fast as C++/Rust, is pretty darn speedy once the JIT has done its thing. However, I simply enjoy programming in Racket much more, and it's my primary programming language for my business, so I thought it would be fun to see how it could do with a chess engine despite being significantly slower than some languages. Switching to Racket was the right decision because I'm having a blast, and I never intended to win a computer chess tournament with this project.

...
Copy/make is something different than what I'm doing.

Copy/make copies the ENTIRE BOARD, then makes the move, and instead of unmaking it, the board is thrown away. This is indeed very slow, but relatively simple to implement. And as I said: some states such as half-move clock, or the ep-square, can't be incrementally updated. If the board changes and the ep-square gets erased, you either have to remember that it was set so you can re-set it when unmaking, or you have to deduce / calculate the state again. The ep-square is only 1 byte, but when I copy ONLY this, Rust copies 8 bytes back and forth. Same goes for some of the other fields, and in the end it turned out that just incrementally updating (during the move of a piece) whatever is possible, and push/popping the gamestate, was the fastest approach in Rust.

Gotcha - I understand what you're doing now, and I'm doing something similar i.e. incrementally updating the squares, and a few other things, but pushing some state onto a stack.

[mvanthoor]

Easy there, I think you misunderstood me. I said the Racket garbage collector is fast. I'm not comparing Racket's overall speed to non-gc'd languages such as Rust In fact, my actual point was that despite the speed of Racket's GC, it's wise to avoid allocation as much as possible.

No problem. I'm just of the opinion that if you want a fast program, you should use a fast programming language. Why spend the time trying to optimize a slow language for speed, if you can't even come close to a non-optimized fast language... I've seen highly optimized engines that run slower in release mode than my engine does in debug mode.

And now I'm inspired to make a great didactic engine. With Racket's unparalleled meta-programming facilities, I think I'll be able to create a super readable/understandable engine that plays "reasonably" strong.

"I'm going to write a didactic engine."

I hope you do. I've seen too many engines that use this phrase, and what they are, in the end, is a pile of code without explanation, where the writer thinks that new chess programmers can magically divine why an engine needs to do what. A real didactic engine comes with good comments that explain WHY an engine does something and good documentation. (Or even a video series, in the case of VICE and BBC/Wukong.)

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. "It plays chess, done. Good luck with it." That's not didactic.

So...
1. I like the fact that you are using something else besides C or C++... but I'm doubtful with regard to the speed.
2. I hope you really DO write a didactic engine, of which I can read the code and understand what it does, with comments about WHY, even though I don't know the programming language.

Good luck

Switching to Racket was the right decision because I'm having a blast

That is the most important thing. It's the only important thing. The only person you're doing this for, in the end, is you.

and I never intended to win a computer chess tournament with this project.

Uh oh. Here we have another one. 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. If you get this engine tested and it sits there in the rating list, staring at you from place 600, you're going to feel guilty. It should have been at place 500, at the very least. It won't be long before you're not satisfied with your engine before it's at place 400 in the list, and then the next 2500 or even 3000 ELO target looks SO tempting. If you could _just_ get it into the top 100. And you're engine is making those puppy eyes, you know...

Then, when you play it, it will CRUSH YOU. If you run it under the Fritz GUI, it'll probably make a disparaging remark too, about how you're SO DUMB at playing chess.

You've chosen a programming language that isn't C or C++. So now you want to prove that yes, you CAN write a strong engine in that language despite the drawback in speed. You're in for it. You're doomed. You'll be writing at this chess engine in another 30 or 40 years. Even if you manage to quit, you'll be back later. I've seen it happen on this forum; people saying "I'm done with chess programming", "I've had enough of it", or "I'm quitting because...", and then something interesting happens (such as NNUE, or whatever) and then they're right back at it.

You're doomed. On the way down to the burning, raging flames in optimization hell and the grinding wheel of feature addition. Just accept it... you're stick with us, down here, forever. Mwuhahahaha!

Uh... sorry. I guess. But it's still true.

[lojic]

...

And now I'm inspired to make a great didactic engine. With Racket's unparalleled meta-programming facilities, I think I'll be able to create a super readable/understandable engine that plays "reasonably" strong.

"I'm going to write a didactic engine."

I hope you do. I've seen too many engines that use this phrase, and what they are, in the end, is a pile of code without explanation, where the writer thinks that new chess programmers can magically divine why an engine needs to do what. A real didactic engine comes with good comments that explain WHY an engine does something and good documentation. (Or even a video series, in the case of VICE and BBC/Wukong.)

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. "It plays chess, done. Good luck with it." That's not didactic.
...

I agree, I've looked through the source of some didactic engines, and they're not as beginner friendly as they could be.

I enjoy watching chess programming video tutorials, but I'm planning on a series of blog posts that will take a beginner from nothing to a complete engine step by step. The purpose will be twofold - to learn how to write a chess engine, and to learn some things about lisp programming. The parentheses throw people with lisp, but once you get over that, the syntax is so simple that it should be very easy to follow even for non-lisp programmers.

I'd like to have the simplest version I can that will still play about 1,200 human ELO, or so. Then show how making each additional change will increase its strength. Should be fun.