Rustic vs. Shallow Blue: one of us is weird somehow

[hgm]

That is really strange, as collecting info on the PV should not affect move choice at all. Problems of this type are indicative of using an uninitialized variable.

Best way to debug this seems to find a position where the version with and without PV collection show a different result already at low search depth (even if it is just a 0.01 score difference or a node count that differs by 1), and then let them dump the entire search tree on file to see in which node this difference originates.

[Terje]

Are you using the collected PV for anything outside of printing it?

[mvanthoor]

@HGM: not possible in Rust. If you have an uninitialized variable, the compiler won't build the program and throw an error.
@Terje: No, I only use the PV for printing now.

I have implemented the A/B-function (and qsearch) the same way as Vice does:

Code: Select all

start_alpha = alpha;

... all your a/b stuff ...

// If alpha was improved, save the best move of this depth.
if alpha != start_alpha {
	... replace your best move here with "best_move" from this depth ...
	... and I also replaced the pv with the best one from this depth ...
	(and it works now)
}

This works. I implemented the PV using vectors instead of a triangular PV, using this article:
http://vajoletchess.blogspot.com/2013/1 ... cipal.html

It basically finds the best move for the depth, puts it at index 0 of the PV, and then sticks the PV from the nodes below it after it.

Now, I just put the PV next to the best_move in "if alpha != start_alpha" (in my "search_info" struct which basically passes it up to iterative_deepening()), and use it for printing, without having changed the rest of the engine.

It now works as intended. I have played a few games against some engines, and I see no weird things. Rustic scores around 1700 Elo as before. I could actually leave it like this, but because "best_move" is the first move of the PV, can go and remove this if I want to.

Previously, I ALSO removed "if alpha != start_alpha" (by accident), and that broke everything. I think it breaks, because it is possible that you are searching (say) depth 10, and you have a best_move there. Then you break in the middle of that search due to time up. If you then pass THIS best_move to iterative deepening, then you get weird results. It might be a very strange move to play (it actually isn't better than the best_move of the previous depth), or it might not even be legal in the previous depth. (edit: I did indeed get my engine killed by Arena for not playing legal moves when I removed that last "alpha != start_alpha" - statement.)

PS: I have also seen some "weird" moves in the beginning of the game, which I thought were caused by the last change I made, so i reverted that... until I thought of the opening book. Arena has some opening books that come with it by default, and they have some VERY strange variations in there that completely don't jive with my PSQT... so after Arena plays the variation, my engine will either revert the moves, or play the pieces around in strange ways, to get them to go where it thinks they should be. Therefore I now test changes like this without opening books.

PV done... only a bit of cleaning up to do. Next up will be GameTime (go wtime btime binc inc... etc).

[Ras]

This works.

What happens if one move improves start_alpha, and another one improves alpha even further? Or, what happens if another move doesn't improve alpha further, then alpha would still be different from start_alpha after the first alpha raising move?

[mvanthoor]

This works.

What happens if one move improves start_alpha, and another one improves alpha even further? Or, what happens if another move doesn't improve alpha further, then alpha would still be different from start_alpha after the first alpha raising move?

start_alpha will never improve when running through the function. It is set at the beginning, outside of the move loop. It is just alpha that improves inside the move loop, so "alpha != start_alpha" (after the move loop) will be true if alpha improves even once.

The thing is that, if I remove this and set the best_move and the pv directly in the move loop (in "if eval_score > alpha { }"), then the engine falls apart and starts playing weird or even illegal moves. I think it is because of the fact that the "best_move" set in that if-statement, is the one that is best up until that point, but not necessarily better than the one from the previously completed depth.

[Ras]

It is just alpha that improves inside the move loop, so "alpha != start_alpha" (after the move loop) will be true if alpha improves even once.

Exactly. But the moves after the move that has increased alpha, but which don't improve alpha furthermore, will also run into this condition while they shouldn't.

[mvanthoor]

No, they don't.

When alpha improves, the current move is saved as best_move, which is exists outside the move loop.

If alpha doesn't improve further, best_move doesn't change.

So if alpha != start_alpha is true, best_move will have the best move that came out of the loop.

I'll paste some code tomorrow. The strange thing is that I can't make it work without "kicking" the best current move into another variable. Most other engines don't do that.

[Ras]

When alpha improves, the current move is saved as best_move, which is exists outside the move loop.

If alpha doesn't improve further, best_move doesn't change.

Ah OK, so that's a bit of an indirect implementation because usually, the node's alpha itself is increased (and mutable), and the comparison is like "if (score_of_current_move > alpha)", so that the "start_alpha" variable is just unnecessary. However, you still have to keep track of the bestmove so far somehow, either via copying the last alpha-raising move into a dedicated best_move variable, or via tracking a best_index variable that gives the index of best move within the move list.

If however the current node fails low because no move has improved alpha, then the "best_move" resp. "best_index" needs to have some reliable sort of init value, like "move = 0" or "index = -1" or so.

[hgm]

My engines usually do IID, so I cannot just increase the alpha that was passed to them: the next internal depth iteration will have to start at the original alpha. So I have to remember the start_alpha, and reset alpha to it at the start of every depth iteration. And afterwards I can test for a fail low by comparing alpha to start_alpha, and possibly do extra iterations (at higher depth or with open window) when it does.

[mvanthoor]

Ah OK, so that's a bit of an indirect implementation because usually, the node's alpha itself is increased (and mutable)...

Alpha is is increased in my case, and mutable.

I think (alpha == start_alpha) is something specific to VICE; it's indeed not necessary. If alpha starts at -INF, you can't NOT improve it; every legal move improves it. I have now removed it, and the engine still works as before. The reason why it didn't at first was as follows:

Many engines have a "best_move" in the global space. If they increase alpha, they have something like "current_best_move" or "best_move" or something. At some point they just do "best_move == current_best_move", where they "kick" the alpha/beta's best move out of the function into the global space.

In Rust, this isn't possible. I use VICE's method: I have a SearchInfo struct, where the search saves all its info. (Duh...) it is passed into alpha/beta by a mutable reference. (In C this would be a pointer.) Within alpha/beta, I keep a "best_move" variable. After the move loop, just before returning alpha, I have to store the best move found in search_info. (Rustic's way of moving the best_move value out of alpha/beta in the end.)

In an effort to get rid of start_alpha, I was storing my best_move and PV into the search_info struct within the "if value > alpha {...}" part. In that case, when the recursive function unwinds, it overwrites search_info.best_move and search_info.pv each time on the way up. (In short, I was losing my alpha/beta-local best_move and pv, which obviously destroys everything.)

I now just removed "alpha != start_alpha", and left the rest as it is, and everything still works.

I shouldn't try to write recursive functions at 22:00 in the evening after a day of coding at work. Better just stick to interpreting the next "go" command.