Storing Countermoves by Ply

[jfern2011]

I had this idea to store counter moves by ply, i.e. create the array counter_moves[ply][piece_moved][to_square], as opposed to the usual indexing by piece and "to" square (or by "from" and "to" squares). However, this idea gives me pretty bad results, namely that the search tree grows significantly larger. My idea was that two nodes at a given ply that do not share the same parent node will likely share many of the same legal moves. If one of these is a refutation, then that refutation will work in other node. I think of it as an extension to killers, except that here I'm storing more than a couple of moves per ply.

Has anyone else tried something similar?

[hgm]

A node also shares many legal moves with its grant parent. I think one of the benefits of the normal counter-move heuristic is that it still provides useful moves if the opponent interjects a delaying tactic. You would lose that when separating by ply.

I am thinking of getting counter moves from the hash table, rather than from a separately maintained data structure. The idea is that many moves will have similar refutation trees. This applies for instance to completely passive moves. Or to different captures of the same hanging piece (when you have to recapture, but it doesn't matter much how). If one such move has been searched, you could use its refutation tree as a source for cut-move ideas when refuting a similar move.

Also here the problem of a shift in ply-level can occur, e.g. after a delaying tactic. E.g. after a check + (neutral) evasion to delay an unavoidable material loss, the situation is basically the same as before it. So it could be nice to use the search tree of the current node as inspiration for the search after the check. Problem is that this search is not completed yet. But at least for the moves that already have been searched you would expect the same fate when played after the check. And those not yet searched might still be in the TT from the previous root iteration, at a 1-ply-lower depth, which would still be good enough for after the check, even with a chck extension of 1 ply.

[Evert]

I had this idea to store counter moves by ply, i.e. create the array counter_moves[ply][piece_moved][to_square], as opposed to the usual indexing by piece and "to" square (or by "from" and "to" squares). However, this idea gives me pretty bad results, namely that the search tree grows significantly larger. My idea was that two nodes at a given ply that do not share the same parent node will likely share many of the same legal moves. If one of these is a refutation, then that refutation will work in other node. I think of it as an extension to killers, except that here I'm storing more than a couple of moves per ply.

Has anyone else tried something similar?

I have not tried, but the idea sounds flawed.
In general, what you want is to pass along information. Cut-moves should be tried again in "similar" positions, to see if they cause a cut there too. The question is what makes positions "similar".
You already mentioned killer moves: here, positions are similar if they are siblings, so it makes sense that they are indexed by ply. You can try the cut move from two plies up in the tree as well, because the opponent may have used some delaying tactic to postpone the killer.
The counter-move heuristic considers positions as "similar" if they originate from the same opponent move (with some restrictions on captures/recaptures/check evasions).
You can extend that further with "follow up" moves where you index by your last move (rather than the opponent's move), or use the last two moves rather than the last move.

What you're proposing narrows the definition of "similar" to a point where it becomes too specific (almost "identical"). That being said, you can expect that an indexing scheme that does not take into account the size of the tree in some way does not scale so well when the tree grows (with large search depth, say). Information gathered in one part of the tree will not help when searching another part of the tree, but will overwrite otherwise useful data. Perhaps an SMP scheme where killer/counter/history information is not shared between threads benefits from this: different threads can effectively search different parts of the tree, and keep their useful data more efficiently than a single thread can.
If that is true, then perhaps an indexing scheme that tries to balance number of nodes in each bin will work. So information from ply 1-9 goes into one bin (say), while plies 10-13 go into the second bin, etc.

[hgm]

There is a delicate balance here between generality and specificity. Too liberal sharing of counter moves will lead to many inapplicable counter moves being tried, delaying discovery of the proper refutation. Being too specific will leave you without any counter move too often.

My idea of obtaining the counter move from the TT entries made in an analogous sub-tree might be too specific, and in addition it might be too hard to find the proper analogy. Recognizing the analogous situation by just the previous move sounds way too general. I have heard of implementations where the position is recogized from a preceding sequence of moves.

How do people implement this. It seems the table could grow very large if you do that. It soes seem a very good compromise between generality and specificity, though. Is this done by hashing on move sequence? I suppose the hash key change compared to the position N-ply before would give a reasonably unique indication of which N ply were played. So you could hash the counter moves in a big table using this key change as index. Like with killers you could store two counter moves per key change.

[Evert]

My idea of obtaining the counter move from the TT entries made in an analogous sub-tree might be too specific, and in addition it might be too hard to find the proper analogy. Recognizing the analogous situation by just the previous move sounds way too general. I have heard of implementations where the position is recogized from a preceding sequence of moves.

How do people implement this. It seems the table could grow very large if you do that. It soes seem a very good compromise between generality and specificity, though. Is this done by hashing on move sequence? I suppose the hash key change compared to the position N-ply before would give a reasonably unique indication of which N ply were played. So you could hash the counter moves in a big table using this key change as index.

From what I remember, Stockfish does something like this, which works out to "countermove[their move][my previous move]", which seems manageable (if a move is 16 bits, it's 32 MB if you use from/to square to index the table, or 512 kB if you use piece type/to square). Obviously storing longer sequences this way becomes intractable fast, although the table implicitly stores these sequences of course.

Like with killers you could store two counter moves per key change.

This occurred to me too the other day. I haven't tried it yet, but plan to.

[AlvaroBegue]

I might these ideas a try, but currently I don't have a counter-move heuristic at all. At what point should I try the move suggested by this heuristic? My current move order is:

* Hash move
* SEE > 0 captures (in MVV-LVA order)
* SEE == 0 captures (in MVV-LVA order)
* Killers
* Other non-captures (in history heuristic order)
* SEE < 0 captures

[hgm]

Shouldn't that be SEE >= 0 captures? Normally you would want to search Q x protected Q before B x R.

I am still looking for a heuristic that gives me a move to play directly after the hash move. Or perhaps even before it. Based on information from sibblings. (So killer-like, but then also for captures.) Info like "This hash move is (consistently?) failing low at this new depth / new beta, but this other move was the first in the static ordering that managed to replace it".

This could be done by keeping a list of hash move for each ply level, and for each such moves counters how often they failed high and low. And some of the moves that failed high instead, with a counters to keep their success rate. (The whole thing cleared when you enter the node at the ply below.) If your hash move failed low, and there is a move in the list with a good track record, it might be a good idea to try that next. Or when the track record of your hash move is very poor, perhaps try it immediately.

[AlvaroBegue]

Shouldn't that be SEE >= 0 captures? Normally you would want to search Q x protected Q before B x R.

I think I tried both ways and separating SEE == 0 captures was slightly better. But that was a few months ago and my program has improved much since then, so perhaps the result is not applicable. I am retesting it now.

[Evert]

I might these ideas a try, but currently I don't have a counter-move heuristic at all. At what point should I try the move suggested by this heuristic?

After killers, before other quiet moves. You can try to do it the other way around too, but that was worse the last time I tried it.

[jfern2011]

Thanks for your help guys!