Progress on Rustic

[mvanthoor]

...

Thanks Eric

In the other topic "Hitting a wall", I explained the problem I have, that history doesn't seem to work (well), and aspiration windows also don't work. Niels (from Loli) identified some problems with regard to bounding of the history values. I had already merged everything into the master branch because each feature _did_ increase playing strength.

I'm rerunning a few gauntlets (again), and after that I'll disable history and aspiration windows, and test the killer moves again.

Then I'll add PVS and test this (as this seems to be almost mandatory, where AW could possibly fall by the wayside), and then I'll re-enable AW and re-do the history heuristic.

My PST's are sensible, as far as I can tell from Rustic's playing style, apart from the fact that it just doesn't know anything about dynamic stuff yet (king safety, pawn structure, etc.)

I'll take a look at history after killers, PVS, and AW.

The one problem with history I have is....

How do I make that fast in Rust?

Now, I recreate the history (and the killers) with each new search. If I need to keep them the entire game, they'll end up in the Search object, which is in a different thread. I can't go and mutex the history and killers because that's terribly slow. I can implement unsafe shared memory, but it's called unsafe for a reason, because the values can't be guaranteed. How do other engines do this; just write whenever they please, and hope the values are mostly correct...?

[Ras]

Now, I recreate the history (and the killers) with each new search.

Should be OK because there shouldn't be much difference between clearing them entirely, reducing them, or keeping them - Bob Hyatt examined that IIRC. Killers in particular would need to be downshifted anyway in the next turn. What you should keep is the hash table.

How do other engines do this; just write whenever they please, and hope the values are mostly correct...?

In Stockfish, each search thread has its own history and killers. Makes sense because it's the hash table where threads communicate with each other.

[mvanthoor]

Now, I recreate the history (and the killers) with each new search.

Should be OK because there shouldn't be much difference between clearing them entirely, reducing them, or keeping them - Bob Hyatt examined that IIRC. Killers in particular would need to be downshifted anyway in the next turn. What you should keep is the hash table.

Yes, I found a thread where Bob tested several different heuristic schemes with regard to reducing in different ways or clearing them entirely. The difference in Elo was within the error bar. The thread was from the late 90's, in Google Groups, so I didn't know if it was still relevant.

The thing I'm still not clear about is the indexing of the history array. I've found information about engines doing... this is how I'm interpreting it.


1. piece/to-square (A specific piece of unknown side moved to that square... "Once, there was a knight on b5")
2. side/from/to (An unknown piece from a specific side moved from here to there. "A piece moved from e2 to e4"; could be a pawn, a rook, or a queen.)
3. I haven't seen my version, but it feels more logical: side/piece/to (A specific side moved a specific piece to a square. "White moved a knight to b5")

Is my implementation (3) completely faulty? Why would implementation 1 or 2 be better?

I have no basis for discounting implementations 1 or 2 other than the fact that they don't "feel" right to me. I could try all three, obviously, but maybe I need a specific one to work with LMR. I don't know yet. So even if my implementation is best standalone, version 1 or 2 might work better with LMR.

How do other engines do this; just write whenever they please, and hope the values are mostly correct...?

In Stockfish, each search thread has its own history and killers. Makes sense because it's the hash table where threads communicate with each other.
[/quote]

Same in my engine.

My engine object (struct-with-methods in Rust) runs in the main thread. The engine struct creates a Search struct with its own thread. This thread controls the search, so it can (in the future) spawn other search threads. At this time, it doesn't, and runs iterative deepening in its own thread. Each time a search is started, it gets its own newly created SearchInfo object, which holds everything the search needs, including the killers and history.

I don't yet know if each thread is going to have its own iterative deepening, or that iterative deepening is the one spawning them. I haven't looked into it yet.

(I'm often saying "I don't know yet / haven't looked into it yet", because I actually haven't; I'm still only reading text and concepts, and then doing the implementation completely independently, without looking at source code.)

[Ras]

1. piece/to-square (A specific piece of unknown side moved to that square... "Once, there was a knight on b5")

Yes, but a white knight is a different piece kind than a black knight. Or you have white and black history (that's what I have). Or one history, but indexed by side, i.e. your version.

2. side/from/to (An unknown piece from a specific side moved from here to there. "A piece moved from e2 to e4"; could be a pawn, a rook, or a queen.)

I think that doesn't make as much sense, but seems to work, too.

I don't yet know if each thread is going to have its own iterative deepening, or that iterative deepening is the one spawning them. I haven't looked into it yet.

Typically, the main thread does the main ID, and also the top level search up to maybe three plies depth, and then spawns the other workers from there. That's because the last few moves of the root move list are finished very quickly compared to the first few moves because by then, you already have good alpha and beta values.

[mvanthoor]

By the way, with regard to history:

Where is it updated? I've seen (across the internet) that some people update it only where alpha is raised, others where a beta-cutoff occurs (that's also in CPW), and sometimes people mention that they update in both places.

As there is no cutoff when alpha is raised (the move loop continues), I don't know if it's actually useful to update the search history there.

[amanjpro]

By the way, with regard to history:

Where is it updated? I've seen (across the internet) that some people update it only where alpha is raised, others where a beta-cutoff occurs (that's also in CPW), and sometimes people mention that they update in both places.

As there is no cutoff when alpha is raised (the move loop continues), I don't know if it's actually useful to update the search history there.

I'm doing it in beta cutoff... So in a sense my history is a version of killer moves that lives longer but less accurate/specific

[mvanthoor]

I'm doing it in beta cutoff... So in a sense my history is a version of killer moves that lives longer but less accurate/specific

That is what most of the literature says: "The history heuristic is a generalized, non-ply-specific version of the killer move heuristic." If history should only be used like this, I seem to remember that the VICE engine (and probably many others, because of it) updates its history in the alpha-area. I'll have to rewatch the video to see if I remember correctly.

[Ras]

Where is it updated?

I'm doing beta-cutoffs only because the leftmost path will always increase alpha, no matter how bad the moves are - simply because alpha is still so low at that point. And if you follow the PV in the leftmost path, you're just highlighting PV moves again, and PV moves are rarely unconditionally good since they deal with the opponent's moves as well.

[mvanthoor]

Where is it updated?

I'm doing beta-cutoffs only because the leftmost path will always increase alpha, no matter how bad the moves are - simply because alpha is still so low at that point. And if you follow the PV in the leftmost path, you're just highlighting PV moves again, and PV moves are rarely unconditionally good since they deal with the opponent's moves as well.

Thanks for confirming. I've been unsure about VICE's implementation of history:



(At 4m05s)

I remembered correctly. VICE updates the history table in the alpha area (which I found strange already, because there's no cutoff there, as the move loop continues), and it indexes it by piece/square-to only (i.e.: "At some time, there was a knight on b5"). Because I didn't believe in that implementation, I started experimenting, adding "side" to the indexes, and also updating the history in the beta-cutoff area. That seemed much more logical:

- Try to order on the hash move.
- Fails? Try MVV-LVA.
- Fails? Try Killers.
- Fails? I once played Knight to b5, and that move is possible now. Try it, because I have nothing else to sort on."

So that is the reason why history kept improving when I added the side, and then also updated in in the beta-cutoff area, but I never removed it from the alpha area. (And as Niels suggested in the other topic: I didn't set bounds on it.)

I'll disable the implementation, and test killers, PVS, and Aspiration Windows, in that order, and then I'll add history again with some changes.

[Ras]

Thanks for confirming. I've been unsure about VICE's implementation of history:

Yeah, I wouldn't do it that way, and with the killers, I don't just shift the current quiet killer move into the killer slots. I do it only it the current killer move is not already the one in the first killer slot, or else I'd end up with two identical killers, which defeats the point of having two slots.

and it indexes it by piece/square-to only (i.e.: "At some time, there was a knight on b5").

Which doesn't make too much sense because say moving a white knight to e6 and having an outpost there is a totally different thing from Black moving his knight there where it is probably in the way. Or moving a white rook to the 7th rank and controlling it is doing much more than Black putting a rook on the 7th rank.

I guess my history implementation is one of the few that have both static aging, dividing everything by 8 when search starts, and dynamic aging, halving everything when the 0-2047 range would overflow during search. This happens rarely enough so that it doesn't cost time.

- Try to order on the hash move.
- Fails? Try MVV-LVA.
- Fails? Try Killers.

I also rank the move from the null search of on level up because that's a threat move, and if the opponent's move from one level up hasn't addressed the threat, that can cut off here.