Killer and move encoding

[hgm]

Killers don't necessarily come from same parent. And, at least in my case, I also try killers from earlier plies as well, which produces a measurable speed gain in time to depth (better ordering).

Ippolit clears the killer slots of the level of daughter nodes, when it enters a node. I thought this was pretty common, and I could not imagine that is was done for no Elo-reason.

[hgm]

Will he get any speed up at all? I assume he is on a 32-bit PC. In general programing I haven't noticed any improvement in using 16-bits when the machine is 32-bit native. I imagine some speed up could come from reduced cache misses but is that going to be significant?

In fact 16-bit operations are very much slower on i386 and x64 architectures than either 8 or 32 (and ond x64 also 64) bit operations. The hardware doesn't support them, so access of those data types takes many extra mask and shift operations. It only makes sense to use 16-bit data when it would give huge memory savings. Like in the hash entry.

[bob]

Killers don't necessarily come from same parent. And, at least in my case, I also try killers from earlier plies as well, which produces a measurable speed gain in time to depth (better ordering).

Ippolit clears the killer slots of the level of daughter nodes, when it enters a node. I thought this was pretty common, and I could not imagine that is was done for no Elo-reason.

I wouldn't make any bets at all about what/why ippolit does something. But this is trivial to check, I'll report back this evening since making Crafty clear P+1 killers is trivial. The last time I tested this, which was several years ago to be sure, using killers from 2 plies back in the tree was a + elo gain, as was NOT clearing the killers for P+1. I'll have real data tonight from current Crafty.

However, this seems analogous to history counters, and we certainly use history counters from deeper in the search to influence move ordering closer to the root

[bob]

Killers don't necessarily come from same parent. And, at least in my case, I also try killers from earlier plies as well, which produces a measurable speed gain in time to depth (better ordering).

Ippolit clears the killer slots of the level of daughter nodes, when it enters a node. I thought this was pretty common, and I could not imagine that is was done for no Elo-reason.

I wouldn't make any bets at all about what/why ippolit does something. But this is trivial to check, I'll report back this evening since making Crafty clear P+1 killers is trivial. The last time I tested this, which was several years ago to be sure, using killers from 2 plies back in the tree was a + elo gain, as was NOT clearing the killers for P+1. I'll have real data tonight from current Crafty.

However, this seems analogous to history counters, and we certainly use history counters from deeper in the search to influence move ordering closer to the root

After 1500 games this is a -10 Elo change. More later when the full 30K games have completed.

[bob]

Killers don't necessarily come from same parent. And, at least in my case, I also try killers from earlier plies as well, which produces a measurable speed gain in time to depth (better ordering).

Ippolit clears the killer slots of the level of daughter nodes, when it enters a node. I thought this was pretty common, and I could not imagine that is was done for no Elo-reason.

I wouldn't make any bets at all about what/why ippolit does something. But this is trivial to check, I'll report back this evening since making Crafty clear P+1 killers is trivial. The last time I tested this, which was several years ago to be sure, using killers from 2 plies back in the tree was a + elo gain, as was NOT clearing the killers for P+1. I'll have real data tonight from current Crafty.

However, this seems analogous to history counters, and we certainly use history counters from deeper in the search to influence move ordering closer to the root

After 1500 games this is a -10 Elo change. More later when the full 30K games have completed.

After 24,000 games, it has settled toward a -5/-6 Elo loss to zero the ply+1 killer moves.

[bob]

OK, first I did a little memory check. And I recalled the chapter of Frey's book Slate wrote, where he explained killers. The example he gave was pretty simple. Black rook on a8, black king on e8, white knight on b5, normal setup otherwise except that the c7 square is not defended by black, but it is black to move. Slate pointed out that it was unlikely that black would have any ordering trick to protect against the Nxc7+ fork, so black would try a move, white eventually discovers the fork, and since it is a good move, it is remembered as a killer. Black tries another move and white immediately tries Nxf7+ first.

If you zero the ply+1 move list, this might be missed. If you back up two plies, do something else, go down one ply and let black try a move, we still want to try Nxc7+ first, but when you moved from ply-2 to ply-1, you missed that opportunity if you cleared the ply+0 killer moves at ply-1.

In any case, here's the early results after one round of testing:

Code: Select all

   3 Crafty-24.0-2           2620    3    3 30080   56%  2585   23% 
   4 Crafty-24.0-1           2618    3    3 30080   56%  2585   23% 
   5 Crafty-24.1R01-1        2613    3    3 30080   55%  2585   23% 

Crafty-24.0-1 and -2 are the standard crafty. 24.1R01 is 24.0 with the ply+1 killers cleared when entering search at ply. Not a huge drop, but a measurable one. 5-7 Elo is certainly not something one wants to give up on.

Notice the win percentage dropped from 56 to 55%, which is definitely noticeable here.