killer trees

[hgm]

How is the analogy key updated ? Once you have obtained a first analogy key probably at ply 1 it is never changed again. Is this intended ?

This is a good question. In my sample code only non-captures (other than the first one in any node) are able to define an analog. but they would always use the tree of previously search non-capture at that node as such. So it might be different for every move at ply 1, although in practice it might be the same (because the analog indeed worked perfectly, so that it did not have to be amended by searching alternative moves).

But you are right: once an analog is picked, it would never be changed deeper into the tree. So I guess that in practice there should be some evaluation on how well the tree worked, and abandon it when it doesn't (so you can pick another at a deeper level).

E.g. when move A from the root was searched, and another move B from there decided to use the A-tree as a template for the B tree... When after searching the first move of the node after B (say C) you get to search move D there, you have the choice:

1) use the sub-tree hanging from A-D as analog (i.e. stick to the ply-1 analog).
2) use the sub-tree hanging from B-C (if C and D were judged 'similar').

Both the analog candidates would differ in only a single move from the current path B-D (A in stead of B, or C in stead of D), and this is tpical for the entire idea. But when the A-C tree worked poorly for B-C, it would probably be a good idea to discard the A-tree as analog, and use the B-C tree rather than the A-D tree as analog for B-D.

[mcostalba]

Suppose you have this position:

Fen: rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 0 1
Key: 2A80F6B24B7DC88B (SF implementation)

Now for instance you have killer move d2d4, after this move we have:

Fen: rnbqkbnr/pppp1ppp/8/4p3/3PP3/8/PPP2PPP/RNBQKBNR w KQkq - 0 1
Key: 91D9AF16E9DFE00B

and according to your code:

killerKey[ply] = 91D9AF16E9DFE00B

Now suppose we reach this position during the search:

Fen: rnbqkbnr/pppp1ppp/4p3/8/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 0 1
Key: 8F7CF8EE9554A34B

Our previous killer move is still applicable and actually it is a real killer
even in this case, so according to your code:

analogyKey = killerKey[ply] ^ hashKey; // analogyKey = 1EA557F87C8B4340


Now what? Can you please continue from here with numeric examples?

[Evert]

But you are right: once an analog is picked, it would never be changed deeper into the tree. So I guess that in practice there should be some evaluation on how well the tree worked, and abandon it when it doesn't (so you can pick another at a deeper level).

This was the main issue I thought of when I read the idea. Basically you would end up with multiple killer trees at larger depth. Perhaps that's ok though? Or you could track a fixed number of them up to some limit. Experimentation would have to reveal where that limit is.

[Michel]

The killer heuristic is a very effective move-ordering device. It provides the first move of the refutation tree of a move B when the refutation is similar to that of a sibbling A of B, which was searched before. And as most moves in all-nodes do basically the same (namely nothing), this happens quite often. But it only provides the first move of the refutation. The 3rd, 5th etc will have to be rediscovered for any continuation on the even moves (which are all-nodes). Once a continuation has been discovered on the deeper odd moves it will of course be communicated to the sibbling moves at that level by the killer heuristic, but not all moves will have the same refutation, so usually several continuations will have to be rediscovered from scratch.

This could be avoided by not just passing a killer move to sibblings, but the entire refutation tree.Then when A is refuted in some non-specific and non-trivial way (i.e. not by gobbling up the piece that was moved, and not by a null move), and sibbling B is an equivalent (read: equally pointless) move, the entire refutation of A can be grafted onto B. The moves of the analogous refutation tree in the corresponding node could be played immediately after the hash move, or even before it: the refutation tree was obtained at the same depth as the current search, while the hash move would be what is left from a previous deepening iteration, which was a search at lower depth.

Of course it sounds very expensive to represent entire trees in killer slots, and then pass them along. But in fact there is no need to to do that, as refutation trees are already stored in the transposition table. All that is needed is to store the hash key of the position after move A in a killer-like slot. So that this could be probed after move B. From this the search can see the hash-key (XOR) difference between the 'killer key' in the slot and its current key. This difference would remain constant in the grafted tree; if A and B were truly equivalent, all nodes of corresponding positions in the refutation tree of A would be obtained by XOR-ing the key for the current node with this 'analogy key'.

So all you have to do is pass along this analogy key through the search of B. So that in any node there the search could not only probe the TT for the position itself (to obtain the hash move), but also the analogous node, to retreive the hash move from there, and use it as 'analogy killer'. The latter probes should be cheap, as the entries were stored recently, during the search of sibbling A, and should still be cached. (Quite unlike the probes for the position itself, which were likely created during the previous iteration, and would have been flushed out of cache, so that they require a DRAM access.)

The same system could also be used for 'level-spanning grafts'. I.e. rather than having analogous positions X and Y (i.e. refutable in essentially the same way) that differ by the move A having been played for one, and its sibbling B for the other, having positions that differ by move B and its reply C having been played to reach Y from X. This addresses the case where B was a pointless delaying tactic, which required counter-measure C, but otherwise did not alter the situation. In general move A from X would now be refutable by the same lines as move A made from Y. Note that in this case the analogy first occurs in all-nodes, rather than cut-nodes. Normally the killer slots in all nodes do not contain meaningful information, as there is nothing to kill there. Positions could still store their hash key in the killer-like table, but marking it as not valid for sibbling-refutation purposes when they turn out to be all-nodes. In the cut-node after B the B-C cases that are likely to be delaying tactics (like attack on a valuable piece, and its subsequent evasion, capturing a valuable piece and its recapture, blocking an attack and subsequent capture of the blocker) can be recognized, and lead to calculation of an analogy key from the XOR difference of the key after C and that in the killer-like slot two ply earlier.

That's a clever trick

Extra hash probes may be expensive though...

EDIT: Oh I missed that this point is addressed. The extra hash probes would be for supposedly cached entries...

[tpetzke]

Fen: rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 0 1
Key: 2A80F6B24B7DC88B (SF implementation)

Now for instance you have killer move d2d4, after this move we have:

Fen: rnbqkbnr/pppp1ppp/8/4p3/3PP3/8/PPP2PPP/RNBQKBNR w KQkq - 0 1
Key: 91D9AF16E9DFE00B

I haven't checked the hash codes you state (as I don't know how to display them with stockfish) but the FEN sequence has an error as after playing d2d4 it's Blacks turn. If the hash codes correspond to your FENs outlining the idea with them will probably not work.

[mcostalba]

Fen: rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 0 1
Key: 2A80F6B24B7DC88B (SF implementation)

Now for instance you have killer move d2d4, after this move we have:

Fen: rnbqkbnr/pppp1ppp/8/4p3/3PP3/8/PPP2PPP/RNBQKBNR w KQkq - 0 1
Key: 91D9AF16E9DFE00B

I haven't checked the hash codes you state (as I don't know how to display them with stockfish) but the FEN sequence has an error as after playing d2d4 it's Blacks turn. If the hash codes correspond to your FENs outlining the idea with them will probably not work.

Thanks, you are right. But the point is that I have no clear what are the following steps....

btw, just type

./stockfish d

[tpetzke]

I give it a try. I use your positions but the hash codes from iCE as it is easier for me

Code: Select all

In this position 

rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 0 1
52AEDC319F17DDEA

you play "d2d4" and come to this position

rnbqkbnr/pppp1ppp/8/4p3/3PP3/8/PPP2PPP/RNBQKBNR b KQkq - 0 1
A8C42B76B69CAFAE

now lets assume "b8c6" gives you a cutoff and you store "b8c6" as hash move for this position A8C4... 


>>> now through search you come here

rnbqkbnr/pppp1ppp/4p3/8/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 0 1
F1E3E8537244893F

You calculate the analogy key as
analogy key -> 52AEDC319F17DDEA ^ F1E3E8537244893F  =  A34D3462ED5354D5

You don't have am analogy killer yet so you play the ordinary killer
 
d2d4

and end up here

rnbqkbnr/pppp1ppp/4p3/8/3PP3/8/PPP2PPP/RNBQKBNR b KQkq - 0 1
B891F145BCFFB7B

you might not have a real hash move for this position but you can look at the analogy hash by xoring in the analogy key   

B891F145BCFFB7B ^ A34D3462ED5354D5 = A8C42B76B69CAFAE
so you look up position A8C4... and this will give you the move b8c6 (that might also be good in your position which is the idea)

After playing b8c6 you can continue to look what White has played in original position after b8c6 and try this move also early on. Means you follow the previous path.

[mcostalba]

I give it a try. I use your positions but the hash codes from iCE as it is easier for me

Code: Select all

In this position 

rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 0 1
52AEDC319F17DDEA

you play "d2d4" and come to this position

rnbqkbnr/pppp1ppp/8/4p3/3PP3/8/PPP2PPP/RNBQKBNR b KQkq - 0 1
A8C42B76B69CAFAE

now lets assume "b8c6" gives you a cutoff and you store "b8c6" as hash move for this position A8C4... 


>>> now through search you come here

rnbqkbnr/pppp1ppp/4p3/8/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 0 1
F1E3E8537244893F

You calculate the analogy key as
analogy key -> 52AEDC319F17DDEA ^ F1E3E8537244893F  =  A34D3462ED5354D5

You don't have am analogy killer yet so you play the ordinary killer
 
d2d4

and end up here

rnbqkbnr/pppp1ppp/4p3/8/3PP3/8/PPP2PPP/RNBQKBNR b KQkq - 0 1
B891F145BCFFB7B

you might not have a real hash move for this position but you can look at the analogy hash by xoring in the analogy key   

B891F145BCFFB7B ^ A34D3462ED5354D5 = A8C42B76B69CAFAE
so you look up position A8C4... and this will give you the move b8c6 (that might also be good in your position which is the idea)

After playing b8c6 you can continue to look what White has played in original position after b8c6 and try this move also early on. Means you follow the previous path.

Thanks for taking your time to properly describe the process, now the flaw is clear: your example works becuase you have calculated the analogy key out of the F1E3E8537244893F position and then you have used it from there. But this works only the first time!

What about you reach another position? the analogy key you have calculate before is no more good.

[tpetzke]

What about you reach another position? the analogy key you have calculate before is no more good.

It works in the sub-tree where F1E3E8537244893F is the root. For a sibling of F1E3... you will need to calculate a different analogy key that will then work in this sub-tree.

Lets say you have a position where you calculate move h7h6 and have tree below that. If your next move is h7h5 you might have a very similar tree (except that in the positions you reach the pawn is on h5 instead of h6) and it is not a fundamental difference where the pawn is.

But you might also play e7e5 and lets assume this makes a fundamental difference. You still dig out moves and order them to the front of the list, but they don't work. They might even provide a cutoff but need more nodes for that as the winning capture you would normally use. There is no mechanism in the base algorithm that lets you discard an analogy key even if it proves repeatably unsuccessful in the sub-tree you are in. You are also not able to calculate new analogy keys tree for sub-sub trees. You have to stick to the one you were passed from the very early plies.

So I think it is a nice idea but in the given basic form it will probably not work. With some refinements it might have potential.