Killer Curiosity

[bob]

I see what you mean, but in this particular engine I don't even do a null move when curEval < beta, so what you describe can't happen. The opponent really has to work to refute the null move.

As to the killers: the stats below are with the conventionl dual-killer algorithm, with LRU replacement. (It is only for a single position, so one should not put too much value on it, but it still gives some indication.)

Code: Select all

 d  tot.node null-cuts other-cut hash-cut kill-1  kill-2 1st-mov     2nd   3rd
 0. 18574353  9156253   947419     1159       54       64 922963  21118   2567
 1.  2125229  1655035  2476247     3634    44993    11933 2377179  56905  23328
 2.   716146   558076   104229    23382     7916     2794  91784   6569   2557
 3.   231939   169150    36318    17082     3921     1153  32716   2047    618
 4.    97283    79073    11186     5177     1625      544   9239   1222    335
 5.    28147    21007     3716     2203      446      137   3365    200     68
 6.     9740     7387     1690     1317      275       79   1556     77     18
 7.     2792     1960      520      472      111       30    498     10      5
 8.      887      676      184      153       46       12    167      6      6
 9.      148       86       53       53       27        2     53      0      0
10.       47       30       17       17        9        3     17      0      0
11.        0        0        1        1        0        0      1      0      0

Kill-1 is the LRU killer, kill-2 the older one. You can see that kill-1 is 3-4 times as successful as kill-2. Note that this is not necessarily because it is tried first: they are actually tried in move-generator order, so the older killer might very well have been tried before the LRU one. (But the move generator generates moves piece by piece from the piece list, so it is likely to be pretty consistent in the order.)

(That the number of nodes is so much smaller here as in the previous case is not a consequence of the other killer algorithm, but because I have switched from alpha-beta to PVS in the mean time.

I don't limit null-move searches anywhere. I've tried all sorts of limits and never found anything that played better overall. In the case of killers for me, I try those before I even generate moves so either one can be tried first with no penalty...

[hgm]

I do it the same way as you.

To Miguel:

In the null-killer algorithm, if I get a cutoff I test if the move leading to the node was null, and if it was it goes into slot A. If it was not, and is different from what was in slot A, it goes into slot B.

[bob]

Here's what I _think_ you should do and I am going to test this once these other tests are finished... I have two killers. When I go to store a killer, if it is the first one in the list (a match) I do nothing. If it does not match the first one, I always overwrite the second. I have had a note for months to try a LRU-type replacement mechanism, so that I always try the one last stored, rather than the one at the top of the list which is most popular. I had decided that since killers are somewhat local in nature, for most cases, it makes sense to first try the one that worked the last time around, and then try the more common killer when that does not apply. There may well be a way to measure this so that you try a killer that is from a position "close" to this before trying one that came from some other part of the three... That's also on my to-do list to try...

That does not seem to make logical sense to me, although nothing surprises me here. If I understand you correctly, the first move to become a killer will ALWAYS be a killer. Because if a different move produces a cutoff it is always stored in slot B.

In my implementation I also have 2 killers - A and B. If a move produces a cutoff and it's already killer A, I do nothing. Otherwise, it becomes the NEW killer A. The old killer A gets moved over to the killer B slot to make room and now it becomes the new killer B.

I think it's common for a move to be the best killer, and occasionally get replaced for just 1 move. For instance Nf3 might be best 90% of the time, but something gets attacked and must move, so the escape move gets to be killer A but really shouldn't be. So it may be worthwhile to explore a scheme where you use the killer than worked best the last N times where N should be pretty small so that it adapts quickly.

There are two kinds of killers. One is a killer in a general sense. That is, a good move but somewhat independent of the actual position. O-O is a very common example, it is a good move most of the time. The other type is a local killer, and is something that only works in a local part of the tree, because some move a ply or two or three back exposed a weakness that this particular killer exploits.

The general belief has been that the more common killer should be tried first, and that may well be true unless you can recognize somehow that the "local" killer still applies and will be a sure killer where the more common killer doesn't work here as it allows the opponent to escape the local threat, whatever it is.

[Don]

Here's what I _think_ you should do and I am going to test this once these other tests are finished... I have two killers. When I go to store a killer, if it is the first one in the list (a match) I do nothing. If it does not match the first one, I always overwrite the second. I have had a note for months to try a LRU-type replacement mechanism, so that I always try the one last stored, rather than the one at the top of the list which is most popular. I had decided that since killers are somewhat local in nature, for most cases, it makes sense to first try the one that worked the last time around, and then try the more common killer when that does not apply. There may well be a way to measure this so that you try a killer that is from a position "close" to this before trying one that came from some other part of the three... That's also on my to-do list to try...

That does not seem to make logical sense to me, although nothing surprises me here. If I understand you correctly, the first move to become a killer will ALWAYS be a killer. Because if a different move produces a cutoff it is always stored in slot B.

In my implementation I also have 2 killers - A and B. If a move produces a cutoff and it's already killer A, I do nothing. Otherwise, it becomes the NEW killer A. The old killer A gets moved over to the killer B slot to make room and now it becomes the new killer B.

I think it's common for a move to be the best killer, and occasionally get replaced for just 1 move. For instance Nf3 might be best 90% of the time, but something gets attacked and must move, so the escape move gets to be killer A but really shouldn't be. So it may be worthwhile to explore a scheme where you use the killer than worked best the last N times where N should be pretty small so that it adapts quickly.

I may have misunderstood you. I think you do the same thing I do.

Also, my suggested things to try was not worded clearly. I am suggesting that it might be worthwhile to try using the move that worked the most number of times out of the last N stores. So if N is 5, you might have 5 slots in a circular queue with a pointer to the head of the queue. You simply store them in the order the occur. The move you consider your killer is the one that occurs the most in those 5 slots, or the most recently used if there is a tie.

[MattieShoes]

I normally have two killers, with the default replacement scheme - when killer 1 doesn't match, bump 1 down to 2 and replace 1. Move ordering still sucks. Right now nulls are tried everywhere beta is <INF but there's no special null move refutation killer stuff. I have some testing code that does time to ply stuff in 48 different positions. I found that adding a killer helped significantly with time to ply, and the second killer doesn't seem to help much at all.

Code: Select all

0 Killers
   Openings: 22.368 seconds
Middlegames: 45.692 seconds
   Endgames: 18.278 seconds

1 Killer
   Openings: 19.500 seconds
Middlegames: 39.749 seconds
   Endgames: 17.306 seconds

2 Killers
   Openings: 19.490 seconds
Middlegames: 39.520 seconds
   Endgames: 17.165 seconds

I haven't looked at indiviual positions, but given how marginal it is, I wouldn't be surprised if the second killer hurt slightly in many positions.

I had never thought about how null moves and the killers array interact -- it seems not good. I'll have to mess with this once I fix my book code.

Edit: I also calculate EBF for the last two plies and noticed somthing odd. 1 killer actually hurts the EBF in most of the 16 endgame positions, but time to ply is better. Presumably the killers near the root are doing well and outweighing the killers up the tree? I'll have to look more. Adding a second killer helped EBF in endgames significantly but time to ply is about the same.

[hgm]

What do you mean by 'helps' if time-to-ply is the same? Isn't the only effect that he killer heuristic is supposed to have that it reducd the time-to-ply?

[Uri Blass]

What do you mean by 'helps' if time-to-ply is the same? Isn't the only effect that he killer heuristic is supposed to have that it reducd the time-to-ply?

I understand that he means smaller effective branching factor in the last 2 plies.

Here are possibe numbers:

0 killers:
time to depth 8:5 seconds
time to depth 9:10 seconds
time to depth 10:20 seconds

1 killers:
time to depth 8:1 second
time to depth 9:3 seconds
time to depth 10:9 seconds

time to ply is better for 1 killer but the effective branching factor with 1 killer is 3 in the last 2 plies when the effective branching factor with no killers is 2 in the last 2 plies.

Uri

[MattieShoes]

Yes that's exactly what I meant, but now I think I made a mistake when I typed it. 0 killers -> 1 killer helped EBF on the last two plies and 1 killer -> 2 killers hurt EBF, but 2 killers hit depth marginally faster. I ran 0, 1, and 2 killers to different depths just now on the same 16 positions. I was calculating EBF as:
sqrt(totalNodes[depth]/totalNodes[depth-2])

Code: Select all

8 ply
0: 2.522 seconds, 2.570 EBF
1: 2.255 seconds, 2.567 EBF
2: 2.192 seconds, 2.500 EBF

9 ply
0: 7.680 seconds, 2.451 EBF
1: 6.705 seconds, 2.370 EBF
2: 6.582 seconds, 2.374 EBF (?)

10 ply
0: 18.279 seconds, 2.829 EBF
1: 16.781 seconds, 2.727 EBF
2: 16.713 seconds, 2.867 EBF (?)

11 ply
0: 54.227 seconds, 2.485 EBF
1: 63.215 seconds, 2.385 EBF (?)
2: 57.998 seconds, 2.595 EBF (?)

12 ply
0: 132.352 seconds, 2.443 EBF
1: 108.007 seconds, 2.277 EBF 
2: 107.038 seconds, 2.217 EBF

So time to ply is better for 2 killers at any of the depths, but EBF for the last 2 ply looks worse sometimes. The 11 ply results are bizarre.

Watching more closely, I think it'd take a lot more than 16 positions to get a reasonable average. One of the positions takes up about 2/3 of the total time for instance (a KQP vs KRR position).

I suppose one could say if the 2nd killer is helping significantly, then move ordering is probably still bad.

[michiguel]

Here's what I _think_ you should do and I am going to test this once these other tests are finished... I have two killers. When I go to store a killer, if it is the first one in the list (a match) I do nothing. If it does not match the first one, I always overwrite the second. I have had a note for months to try a LRU-type replacement mechanism, so that I always try the one last stored, rather than the one at the top of the list which is most popular. I had decided that since killers are somewhat local in nature, for most cases, it makes sense to first try the one that worked the last time around, and then try the more common killer when that does not apply. There may well be a way to measure this so that you try a killer that is from a position "close" to this before trying one that came from some other part of the three... That's also on my to-do list to try...

That does not seem to make logical sense to me, although nothing surprises me here. If I understand you correctly, the first move to become a killer will ALWAYS be a killer. Because if a different move produces a cutoff it is always stored in slot B.

In my implementation I also have 2 killers - A and B. If a move produces a cutoff and it's already killer A, I do nothing. Otherwise, it becomes the NEW killer A. The old killer A gets moved over to the killer B slot to make room and now it becomes the new killer B.

I think it's common for a move to be the best killer, and occasionally get replaced for just 1 move. For instance Nf3 might be best 90% of the time, but something gets attacked and must move, so the escape move gets to be killer A but really shouldn't be. So it may be worthwhile to explore a scheme where you use the killer than worked best the last N times where N should be pretty small so that it adapts quickly.

I may have misunderstood you. I think you do the same thing I do.

Also, my suggested things to try was not worded clearly. I am suggesting that it might be worthwhile to try using the move that worked the most number of times out of the last N stores. So if N is 5, you might have 5 slots in a circular queue with a pointer to the head of the queue. You simply store them in the order the occur. The move you consider your killer is the one that occurs the most in those 5 slots, or the most recently used if there is a tie.

I dd the following experiment with two killers (A & B): Each slot has a move and a counter.
When I add a new killer move to the table, if it is a different move than A and B, I replace B with the new killer. If it is the same move than A or B, I just increase the respective counter by 32. At this point, if the counter for B is higher than A, I swap them. B becomes killer A and vice versa. This is what I have doing (except that the counter was 1 rather than 32).

The key of the experiment is that before adding a killer to the table, I "age" the counters multiplying them by a factor X and divide by 32. of course, X should be lower than 32 to have an aging effect. If X==32 there is no aging and that is the same to what I have been doing (not very good...).

I found that the optimum is X = 19 as you can in this plot at the end:
Tree size is related to no aging at all (X=32, tree size=100%).

This 19/32 aging factor implies the following: if a killer was the same two times in a row (slot A), it will be displaced to slot B by a new incoming killer. But if it was a killer three times out of the last four, a new incoming killer will not displace it to slot B.

My conclusion is: killers should be aging pretty quickly, but not so fast.

Calculations were done with 335 quiet positions (from Dann Corbit) to sd=8. The average tree size was obtained by the geometric average

for each position "i" (n = 335):

S = [summatory of log(nodes(i) ] / n
average tree size = 10 ^ S

This solves the problem that some positions have denser trees than others.
In addition, a similar result was obtained with just the total node count.

Miguel