An idea I have... "semi-TT"...

[voyagerOne]

The idea is simple...and most likely been thought of before.

We have a separate TT for white and black.

For move ordering. We look up if we have a full TT hit (ordinary way). If no match is found we will next look at the semi TT position. So for white move ordering we look to see if only black position is in the TT.... if we found a match, we will used that "best move" even though white position is different.

Thoughts/feedback...?

[hgm]

Wouldn't you have an enormous number of collisions, of all positions with the same white constellation, but a different black one?

[Codesquid]

The best move is highly situational and depends very much on the full position. In particular in positions with hanging pieces, only looking at one side to find a table entry seems to be suboptimal.

It might be useful for ordering noncaptures though after dealing with all captures first.

[voyagerOne]

HG:

I think you got your colors switch. We only care about black position. But your point is still valid.

An idea to resolve this is to keep key pieces of white. Such as white Pawns, Queen, King. So we look for an exact black position AND white key pieces position.

The whole idea behind this because a full TT probe for best move will fail because a rook was on a1 instead of b1. Semi TT will say "heck the position is nearly identical...lets try the move anyways".

Bill

[hgm]

The problem is that 'nearly identical' is a very difficult concept (for a computer). Moving a Queen to a neighbor square can make it 'totally different', because the Queen is now hanging, while first it was delivering checkmate... Moving a Pawn so that it now attacks a Queen that was delivering checkmate accomplishes the same.

I think it would be better to first think what you hope to improve on move ordering. Which cut-moves are found only very late, and how could a 'second hash move' help to identify such moves? One could for instance think of Knight forks, or skewers. To detect the possibility for those you could hash on King, Queen Rooks and opposing Knights only. Then, if you find a position that has these in the same constellation, you might see the same fork.

But I have no great hopes this would give significant search improvement. The main importance of hash moves is that you can immediately walk the same tree you walked on the previous iteration. If you are in 'uncharted territory' a move that uses general, simple guidelines to do something in the actual position (like capturing the most valuable piece) is much more likely to be any good than a move transplanted from some 'similar' position. It might even make things worse, because you give priority to moves that on the average are less good than simple MVV/LVA.

[Pio]

I agree with you HG but I also think the idea of Bill is really interesting. I have thought of a related idea.

My idea is a way of overcomming some of the problems with the history heuristics. The basic idea is to store a type of history heuristics for all (???) positions with a locked pawn structure. The idea is that there should not be too many pawn structures that are locked so it should hopefully be possible to store all of them. Why I think this would be advantageous is that you could reach the same locked pawn structure in many parts of the search tree and that the information gathered will still be valid.

The history should be updated so that the series of your moves belonging to the same locked pawn constellation that finally would result in a good position for you should get a bonus, i.e the principle variation from the start of the pawn constallation. In that way you would favour some strange moves for example moving the knight to the back or side of the board if it proved to be good for the same fixed pawn constallation in another part of the tree.

[tpetzke]

I did a lot of experiments with move ordering but with the usual tricks (hash move, winning captures, killers) you get it already quite good. In my tests I got a cutoff with the 1st move in 95% of the cut nodes. So be careful not to put to much effort in something that only works in 1 out of 20 cases but costs something in all 20.

And from the way it works it might even hurt if you put a move early in the remaining moves list that looks good at first but is just not good enough to cut off compared with having some random bad moves in front of the move that will finally cut off. The bad moves will fail low very cheaply.

Thomas...

[Rebel]

An idea I once tried in the early 90's was to maintain 2 best moves in the TT, kind of killer slot but then for the TT. It did not made much of a difference. But at that time TT sizes were small, 4-8 Mb, that is, if you were rich. The 2 bytes extra also limited the already skimpy TT entries and so I dumped the idea. Perhaps it works better today with large TT's.

Rethinking it I would also include a score-check, research back then learned me that when a best-move is replaced in the TT you won't see it back most of the time. But maybe if one uses a small margin the quality of the previous best move you maintain goes up.