Why does my engine want to perpetually check?

[lithander]

Also MVV-LVA will help because the recapture will be higher in the move list, thus searched earlier, and alpha-beta will keep earlier moves unless later ones score higher. A later move with only equal score will not be selected.

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.

But tbh I don't get it: without any randomness at all don't your engines just play the same game over and over again vs other equally deterministic engines?

[lojic]

...
I also now realize (probably) why Stockfish doesn't sort it's perft/divide output! By printing it w/o sorting, I can see the move ordering at the first level. When I removed sorting from my divide it shows the first two moves are h1d1 followed by h1h3, so w/ no material gain, it chose the first one.

Sorry, I'm just confusing the issue. It *didn't* chose h1d1, and in fact h1e4 is near the end of the list. Clearly the queen must move, and if you eliminate the obviously stupid moves, you're left with the following in the order they are in the generated move list. h1d1 before h1h3 due to MVV-LVA.

h1d1, h1h3, h1g2, h1e4, h1h2,

So h1e4 was considered after h1he and must've scored better. I think I'll code up a simple function to accept a FEN and show the evaluation :)

Mystery solved! It's my goofy, interim, evaluation function. I have a 5 cP bonus for a pawn on one of the four center squares, and the QxP followed by BxP lowers the score by 5 cP :) Of course, I'm just looking at ply 1 evaluations, but it makes sense that losing that center pawn might carry through all the way to depth 6.

Even without that, I still have a problem if the material advantage is equal, there's a chance I'd move the Queen back to e4. Avoiding repetitive positions seem simple enough, but moving the game forward in a meaningful way will involve more thought.

For hacking up that evaluate function quickly, it's worked reasonably well in openings.
* 5 cP for pawn on a center square
* 1 cP for moving a bishop and/or knight
* 5 cP for a king on a castled square - this ignored the rook and made for some goofy move sequences where the king got to the castled square in 2 moves and left the rook on the original square (face palm), but in my defense, the engine often does castle :)

[hgm]

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.

Some engines randomize the initial move ordering in the root, to avoid determinism. They still play the first move they find with the best score, but if two moves really have the same score, it is then randomized which one they find first. But mostly determinism is avoided by using an opening book that randomly selects a line from its repertoire, so that the engine never reallystarts from the same position.

[mvanthoor]

But tbh I don't get it: without any randomness at all don't your engines just play the same game over and over again vs other equally deterministic engines?

Yes, they do; and therefore you have opening books to introduce variety. In a UCI engine, the interface plays the first X moves for both sides, before the engine starts to think. If you don't do that and the engine starts from move 1, you can indeed introduce some randomness for the first X number of moves.

[mvanthoor]

For hacking up that evaluate function quickly, it's worked reasonably well in openings.
* 5 cP for pawn on a center square
* 1 cP for moving a bishop and/or knight
* 5 cP for a king on a castled square - this ignored the rook and made for some goofy move sequences where the king got to the castled square in 2 moves and left the rook on the original square (face palm), but in my defense, the engine often does castle

- Award a bonus for the king on a castled square.
- Also award a bonus for a rook on f1 and d1.
- Add a malus for the king being on e1 (but not too large, or it will move over to d1 or f1)

This will make sure your engine castles almost as soon as possible, mostly immediately after (or during) the development of the pieces.

[lithander]

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?

[lojic]

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?

[lojic]

Is it standard practice to store the position hash in the move list along with the move to easily detect a repeated position?

No. it makes your move data massive. You store it in a history array that contains game states.

I think maybe what you call "history array" I called "move list" i.e. the list of moves previously made by both sides.

...
It works like this:
- At the beginning of make_move(), I copy the board's game_state variable.
- Then I add the move that make_move() will be executing to "next_move"
- Then I push the game state INTO the history array.
...

Just out of curiosity, why did you choose to copy the game state vs. doing an incremental make/unmake? It seems like the latter would be faster, and by using Rust, you have the chance to have a *really* speedy engine. Or maybe I'm misunderstanding your implementation.

[mvanthoor]

I think maybe what you call "history array" I called "move list" i.e. the list of moves previously made by both sides.

Well... in most chess engines, MoveList or move_list is the one that contains the moves that have just been generated by the move generator. What I have noticed is that there is a sort of a "language" that has developed, because of all the interchange of information.

Just out of curiosity, why did you choose to copy the game state vs. doing an incremental make/unmake? It seems like the latter would be faster, and by using Rust, you have the chance to have a *really* speedy engine. Or maybe I'm misunderstanding your implementation.

This is my Board struct:

Code: Select all

pub struct Board {
    pub bb_pieces: [[Bitboard; NrOf::PIECE_TYPES]; Sides::BOTH],
    pub bb_side: [Bitboard; Sides::BOTH],
    pub game_state: GameState,
    pub history: History,
    pub piece_list: [Piece; NrOf::SQUARES],
    zr: Arc<ZobristRandoms>,
}

As you can see, I packed all the information except for the arrays holding the piece bitboards into the GameState struct. ("zr" is a reference to the ZobristRandoms struct that creates the Zobrist keys.)

There are two options:

1.
When making a move, I incrementally update all the values in the game state.
When making a move, I could of course incrementally reverse all the values in the game state.

However, moving the pieces does not cause thing such as the ep-square being set, or half-move clock to be reset, etc... it's make that does this. Therefore I would have to recalculate what those values would have been, or I would have to copy them back and forth.

2.
I could also just get the game state, add the move that is going to be made to it, and push it into the history list. When reversing, I pop the game state off the list (directly into the board), and then reverse the move using a helper function that ONLY reverses the move and does not touch any of the just restored game state values.

I have tested both, and the second is MUCH faster, at least in my engine. It is also cleaner with regard to code.

(I actually use an intermediate variable "current_game_state" in between, to which I copy the current game state, and then add the move to it before I push it. I could also immediately add the move to the game-state, directly in the board and then copy/push it from the board to the history array. When I do that however, the program becomes 3% slower. It seems that the compiler can optimize better, or the memory layout is better, when there's an intermediate variable.)

[lojic]

...
There are two options:

1.
When making a move, I incrementally update all the values in the game state.
When making a move, I could of course incrementally reverse all the values in the game state.

However, moving the pieces does not cause thing such as the ep-square being set, or half-move clock to be reset, etc... it's make that does this. Therefore I would have to recalculate what those values would have been, or I would have to copy them back and forth.

2.
I could also just get the game state, add the move that is going to be made to it, and push it into the history list. When reversing, I pop the game state off the list (directly into the board), and then reverse the move using a helper function that ONLY reverses the move and does not touch any of the just restored game state values.

I have tested both, and the second is MUCH faster, at least in my engine. It is also cleaner with regard to code.

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

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.