Move ordering idea (old and new?)

[diep]

I am currently allowing all moves that cause a cutoff to go into this table, but it might be useful to restrict it in some fashion. I am also not doing any kind of collision testing.

Played around with this combination hash table some more last night. I decided to store the key in the table, although it triples the table size... it does allow collision testing. Not sure the collision testing improves play at all, but it does give peace-of-mind and more reliable testsuite results

The second change was to only allow losing captures and quiet moves into the combination hash table. I realized that winning captures would be ranked highly anyway, and are very common, so they will 'pollute' the table with unnecessary entries. After this change, I was able to shrink the table by a factor of 8 and get about the same performance on testsuites. After 3600 games, it seems to be about +5-10 elo better than the version with all moves allowed into a much larger table, but I need many more games to confirm that (LOS only 85% right now).

As Vincent says, the 'success' of these techniques in my program may simply be a function of otherwise sub-optimal move ordering to begin with. This is something I will be looking at, particularly my 'killer' move implementation.

- Dan

I don't think you can measure 5-10 elo with 3600 games.

[dchoman]

I am currently allowing all moves that cause a cutoff to go into this table, but it might be useful to restrict it in some fashion. I am also not doing any kind of collision testing.

Played around with this combination hash table some more last night. I decided to store the key in the table, although it triples the table size... it does allow collision testing. Not sure the collision testing improves play at all, but it does give peace-of-mind and more reliable testsuite results

The second change was to only allow losing captures and quiet moves into the combination hash table. I realized that winning captures would be ranked highly anyway, and are very common, so they will 'pollute' the table with unnecessary entries. After this change, I was able to shrink the table by a factor of 8 and get about the same performance on testsuites. After 3600 games, it seems to be about +5-10 elo better than the version with all moves allowed into a much larger table, but I need many more games to confirm that (LOS only 85% right now).

As Vincent says, the 'success' of these techniques in my program may simply be a function of otherwise sub-optimal move ordering to begin with. This is something I will be looking at, particularly my 'killer' move implementation.

- Dan

I don't think you can measure 5-10 elo with 3600 games.

Oops, I should have said "seems to be running" rather than "seems to be" in my sentence above. I meant it as an 'in-progress' report rather than a conclusion. My apologies for any confusion. Otherwise the rest of my statement is correct... I do need many more games to reach any conclusion on such a small difference.

[dchoman]

I am currently allowing all moves that cause a cutoff to go into this table, but it might be useful to restrict it in some fashion. I am also not doing any kind of collision testing.

Played around with this combination hash table some more last night. I decided to store the key in the table, although it triples the table size... it does allow collision testing. Not sure the collision testing improves play at all, but it does give peace-of-mind and more reliable testsuite results

The second change was to only allow losing captures and quiet moves into the combination hash table. I realized that winning captures would be ranked highly anyway, and are very common, so they will 'pollute' the table with unnecessary entries. After this change, I was able to shrink the table by a factor of 8 and get about the same performance on testsuites. After 3600 games, it seems to be about +5-10 elo better than the version with all moves allowed into a much larger table, but I need many more games to confirm that (LOS only 85% right now).

As Vincent says, the 'success' of these techniques in my program may simply be a function of otherwise sub-optimal move ordering to begin with. This is something I will be looking at, particularly my 'killer' move implementation.

- Dan

I don't think you can measure 5-10 elo with 3600 games.

Oops, I should have said "seems to be running" rather than "seems to be" in my sentence above. I meant it as an 'in-progress' report rather than a conclusion. My apologies for any confusion. Otherwise the rest of my statement is correct... I do need many more games to reach any conclusion on such a small difference.

And once again, I learn the problem with progress reports.... both versions are now virtually equal after about 5000 games for one and 6000 for the other... I so can't say whether including winning captures in a large table is worse or better than not including them in a small table. Although both versions are about +30 elo better (edit: LOS 99%) than the version before I tried any of this counter-move and combination table stuff, so some overall benefit to my move-ordering seems solid. Now I just need to work out whether it is covering up weaknesses in my other move-ordering heuristics.

Thanks to everyone for their comments!

- Dan

[diep]

I am currently allowing all moves that cause a cutoff to go into this table, but it might be useful to restrict it in some fashion. I am also not doing any kind of collision testing.

Played around with this combination hash table some more last night. I decided to store the key in the table, although it triples the table size... it does allow collision testing. Not sure the collision testing improves play at all, but it does give peace-of-mind and more reliable testsuite results

The second change was to only allow losing captures and quiet moves into the combination hash table. I realized that winning captures would be ranked highly anyway, and are very common, so they will 'pollute' the table with unnecessary entries. After this change, I was able to shrink the table by a factor of 8 and get about the same performance on testsuites. After 3600 games, it seems to be about +5-10 elo better than the version with all moves allowed into a much larger table, but I need many more games to confirm that (LOS only 85% right now).

As Vincent says, the 'success' of these techniques in my program may simply be a function of otherwise sub-optimal move ordering to begin with. This is something I will be looking at, particularly my 'killer' move implementation.

- Dan

I don't think you can measure 5-10 elo with 3600 games.

Oops, I should have said "seems to be running" rather than "seems to be" in my sentence above. I meant it as an 'in-progress' report rather than a conclusion. My apologies for any confusion. Otherwise the rest of my statement is correct... I do need many more games to reach any conclusion on such a small difference.

And once again, I learn the problem with progress reports.... both versions are now virtually equal after about 5000 games for one and 6000 for the other... I so can't say whether including winning captures in a large table is worse or better than not including them in a small table. Although both versions are about +30 elo better (edit: LOS 99%) than the version before I tried any of this counter-move and combination table stuff, so some overall benefit to my move-ordering seems solid. Now I just need to work out whether it is covering up weaknesses in my other move-ordering heuristics.

Thanks to everyone for their comments!

- Dan

In diep i do have a special capturekiller. Not sure when i 'invented' it. Maybe 1995 or so?

It's pretty trivial to invent yet only years later i heard someone speak about it, and that was someone who debugged my engine...

Note the 'matekiller' never worked for Diep. The matekiller works great at testsets though as many positions have to do with mates... ...elowise i'm sure it's a loser.

The capturekiller is more generic and short term than your idea probably - yet i don't think for such thing testing things elowise is the most wise idea.

Trivially it also means i'm not including captures for the normal killers nor other special moves (such as promotions), as those already get ordered pretty high.

The whole point is.

I first want on a paper see that it delivers a reduction in number of nodes when LMR has been turned off

That's a pretty easy test to do so, nowadays, i would say.

Though even start this century i was the only one posting about testing hundreds of positions to test something, doing that nowadays should be pretty easy. Don't take 'testset positions' for that of course. Just use all moves from a bunch of games.

Only if the difference is really close it's worth doing more tests or just kick it out as it eats more cycles of course

Playing games is only interesting i'd say as a last resort and also the last test to do. It's nearly total impossible to measure elowise changes except if you have the hardware of Bob. Even at the 64 cores here it's not easy to measure things - though i'll do some attempts there. I'm actually busy fixing bigger things right now - the evaluation function - and work at the MPI search also has a priority - in short the SMP search, though i doubt whether it's theoretical entirely correct to call the MPI search a form of SMP, as of course it has some asymmetric forms of logics in it.

It's going to win hundreds of elopoints there - so measuring 40k games in order to 'measure' 1 elopoint with changes in a killertable - that's not very attractive as for now

Now i'm not a big hero in statistics - i understand Uri Blass did do his PHD in it - yet for some weird reason he never comments on statistical discussions here (speaking of feeding the dogs) - yet let's suppose you manage to reduce your total nodecount by 1% by improvements of killertable or whatever sort of table you modified conditions for or some new table you invented.

So a constant 1% reduction in nodes - not something exponential. Killertables also seem to have more of a lineair effect rather than exponential there (though i'm guessing here without modern proof).

Let's say 1%.

If you already get a 20 plies search depth at a core or 8 in games, what's 1% extra depth?

Most report that moving from search depth 20 plies to 26 plies search depth or so, that won them an elopoint or 50-70. Optimistically that's 10 elopoints a ply.

Now what's 1% from 1 ply?

1 ply means a reduction of 50%. Now you can all calculate it more accurate than i do here.

1% is 50 times less than 50%.

2% from 10 elopoints = 0.2 elopoint.

You're trying to measure in your current run 0.2 elopoint if i may say so.
You sure you want to continue your testrun?

[mcostalba]

What's the difference between a counter move and a killer move?

If a move is good (cut-offs) for many opponent's previous ply moves, it is a counter move or a killer?

IMHO a counter move has a sense if given a move of the opponent there is only one good counter move and if that counter move is good only for that opponent's previous move. There should be some kind of exclusivisity in the move-counter move pair, otherwise we are talking of a narrow scoped killer.

[dchoman]

What's the difference between a counter move and a killer move?

If a move is good (cut-offs) for many opponent's previous ply moves, it is a counter move or a killer?

IMHO a counter move has a sense if given a move of the opponent there is only one good counter move and if that counter move is good only for that opponent's previous move. There should be some kind of exclusivisity in the move-counter move pair, otherwise we are talking of a narrow scoped killer.

I think the combination hash does provide some exclusivity by requiring a match to the hash signature of the two previous moves as an index to the current move. This provides some exclusivity of context, the move's ordering score is only increased if it caused a cutoff in the same context, i.e. 'completing' the same 3-move sequence, in some other place in the tree. One could imaging generalizing this to an N-move sequence, not sure if that would help. Of course, the ultimate exclusivity of context is the hash move, so this is perhaps somewhere in between killer and hash move (closer to a killer move, as you say).

I don't know how to provide exclusivity of success: guaranteeing that this is the only (or most likely) move that would be successful to complete that combination. For the hash move, the depth priority provides some of this exclusivity, so some kind of depth priority might be useful here as well? (edit: Or perhaps a success counter, stored in the table, which in incremented if the move causes a cutoff in another node?)

- Dan

[diep]

What's the difference between a counter move and a killer move?

If a move is good (cut-offs) for many opponent's previous ply moves, it is a counter move or a killer?

IMHO a counter move has a sense if given a move of the opponent there is only one good counter move and if that counter move is good only for that opponent's previous move. There should be some kind of exclusivisity in the move-counter move pair, otherwise we are talking of a narrow scoped killer.

A countermove is a response to the previous move. A killermove is more local than that and is 'killing' in generic. In this a countermove in more details would hold the response of the opponent. In a fullwidth environment it's not a bad idea actually, especially knowing all those academic programs always search random trees without checking whether playing a move loses you that piece. They only see that AFTER the piece gets captured.

For example if white plays away its knight from d5 to f4 allowing Nb5-c7, then countermove will detect that, is the idea. Without playing Nd5-f4, Nc7 simply isn't possible as you will capture it!

So in general a countermove requires an entire searchtree to reproduce
the same move for the opponent in order for Nc7 to get tried.

Knowing we nowadays use nullmove, and in case of SF lots of other pruning algorithms as well, odds for quickly being able to use a countermove is rather tiny, whereas in fullwidth searched trees odds for that is a lot higher.

That soon pushes the countermove heuristic to a much bigger tree, obviously odds the same move gives a cutoff there is a lot smaller then.

I'm not claiming chance is near 0 that countermove can get reused in a similar position, yet that's usually the case.

Killermoves are more local there and give you a much higher chance for getting used quickly again.

That defines practical a huge difference between countermoves and killermoves.

[mcostalba]

For example if white plays away its knight from d5 to f4 allowing Nb5-c7, then countermove will detect that, is the idea. Without playing Nd5-f4, Nc7 simply isn't possible as you will capture it!

So in general a countermove requires an entire searchtree to reproduce
the same move for the opponent in order for Nc7 to get tried.

This sounds like Nc7 will end up in the hash move, especially at high depths when engine has the chance to properly analyze the variations.

Knowing we nowadays use nullmove, and in case of SF lots of other pruning algorithms as well, odds for quickly being able to use a countermove is rather tiny, whereas in fullwidth searched trees odds for that is a lot higher.

Most of pruning is enabled only at low depths (say less than 7 plies). I call it low depths because I refer to average search depth as reference, not at the absolute depth value.

That defines practical a huge difference between countermoves and killermoves.

IMHO implementation of this counter move idea should try hard to reduce overlap with Hash and killers moves to succed, but this seems more easy to say than to do.

[diep]

For example if white plays away its knight from d5 to f4 allowing Nb5-c7, then countermove will detect that, is the idea. Without playing Nd5-f4, Nc7 simply isn't possible as you will capture it!

So in general a countermove requires an entire searchtree to reproduce
the same move for the opponent in order for Nc7 to get tried.

This sounds like Nc7 will end up in the hash move, especially at high depths when engine has the chance to properly analyze the variations.

Knowing we nowadays use nullmove, and in case of SF lots of other pruning algorithms as well, odds for quickly being able to use a countermove is rather tiny, whereas in fullwidth searched trees odds for that is a lot higher.

Most of pruning is enabled only at low depths (say less than 7 plies). I call it low depths because I refer to average search depth as reference, not at the absolute depth value.

That defines practical a huge difference between countermoves and killermoves.

IMHO implementation of this counter move idea should try hard to reduce overlap with Hash and killers moves to succed, but this seems more easy to say than to do.

Correct - countermove is having fierce competition from hashtable and of course loses it from killermoves; any long term form of move ordering will lose it from hashtables always of course.

Even then - it's a real invention.

It's not difficult to imagine the given implementation works for certain programs from back then. Maybe it might work also for some other games where hashtable won't help you out like it will in chess.

[Uri Blass]

I am currently allowing all moves that cause a cutoff to go into this table, but it might be useful to restrict it in some fashion. I am also not doing any kind of collision testing.

Played around with this combination hash table some more last night. I decided to store the key in the table, although it triples the table size... it does allow collision testing. Not sure the collision testing improves play at all, but it does give peace-of-mind and more reliable testsuite results

The second change was to only allow losing captures and quiet moves into the combination hash table. I realized that winning captures would be ranked highly anyway, and are very common, so they will 'pollute' the table with unnecessary entries. After this change, I was able to shrink the table by a factor of 8 and get about the same performance on testsuites. After 3600 games, it seems to be about +5-10 elo better than the version with all moves allowed into a much larger table, but I need many more games to confirm that (LOS only 85% right now).

As Vincent says, the 'success' of these techniques in my program may simply be a function of otherwise sub-optimal move ordering to begin with. This is something I will be looking at, particularly my 'killer' move implementation.

- Dan

I don't think you can measure 5-10 elo with 3600 games.

Oops, I should have said "seems to be running" rather than "seems to be" in my sentence above. I meant it as an 'in-progress' report rather than a conclusion. My apologies for any confusion. Otherwise the rest of my statement is correct... I do need many more games to reach any conclusion on such a small difference.

And once again, I learn the problem with progress reports.... both versions are now virtually equal after about 5000 games for one and 6000 for the other... I so can't say whether including winning captures in a large table is worse or better than not including them in a small table. Although both versions are about +30 elo better (edit: LOS 99%) than the version before I tried any of this counter-move and combination table stuff, so some overall benefit to my move-ordering seems solid. Now I just need to work out whether it is covering up weaknesses in my other move-ordering heuristics.

Thanks to everyone for their comments!

- Dan

In diep i do have a special capturekiller. Not sure when i 'invented' it. Maybe 1995 or so?

It's pretty trivial to invent yet only years later i heard someone speak about it, and that was someone who debugged my engine...

Note the 'matekiller' never worked for Diep. The matekiller works great at testsets though as many positions have to do with mates... ...elowise i'm sure it's a loser.

The capturekiller is more generic and short term than your idea probably - yet i don't think for such thing testing things elowise is the most wise idea.

Trivially it also means i'm not including captures for the normal killers nor other special moves (such as promotions), as those already get ordered pretty high.

The whole point is.

I first want on a paper see that it delivers a reduction in number of nodes when LMR has been turned off

That's a pretty easy test to do so, nowadays, i would say.

Though even start this century i was the only one posting about testing hundreds of positions to test something, doing that nowadays should be pretty easy. Don't take 'testset positions' for that of course. Just use all moves from a bunch of games.

Only if the difference is really close it's worth doing more tests or just kick it out as it eats more cycles of course

Playing games is only interesting i'd say as a last resort and also the last test to do. It's nearly total impossible to measure elowise changes except if you have the hardware of Bob. Even at the 64 cores here it's not easy to measure things - though i'll do some attempts there. I'm actually busy fixing bigger things right now - the evaluation function - and work at the MPI search also has a priority - in short the SMP search, though i doubt whether it's theoretical entirely correct to call the MPI search a form of SMP, as of course it has some asymmetric forms of logics in it.

It's going to win hundreds of elopoints there - so measuring 40k games in order to 'measure' 1 elopoint with changes in a killertable - that's not very attractive as for now

Now i'm not a big hero in statistics - i understand Uri Blass did do his PHD in it - yet for some weird reason he never comments on statistical discussions here (speaking of feeding the dogs) - yet let's suppose you manage to reduce your total nodecount by 1% by improvements of killertable or whatever sort of table you modified conditions for or some new table you invented.

So a constant 1% reduction in nodes - not something exponential. Killertables also seem to have more of a lineair effect rather than exponential there (though i'm guessing here without modern proof).

Let's say 1%.

If you already get a 20 plies search depth at a core or 8 in games, what's 1% extra depth?

Most report that moving from search depth 20 plies to 26 plies search depth or so, that won them an elopoint or 50-70. Optimistically that's 10 elopoints a ply.

Now what's 1% from 1 ply?

1 ply means a reduction of 50%. Now you can all calculate it more accurate than i do here.

1% is 50 times less than 50%.

2% from 10 elopoints = 0.2 elopoint.

You're trying to measure in your current run 0.2 elopoint if i may say so.
You sure you want to continue your testrun?

reducing the node count by 1% for the same depth by better move ordering can give at least 1 elo improvement(maybe slightly more than it because it also means improving LMR)

"Most report that moving from search depth 20 plies to 26 plies search depth or so, that won them an elopoint or 50-70." is not correct
assuming that you compare the same search.

Note that
Comparing search with LMR with search without LMR is not relevant here
because LMR comes with a price of pruning and better move ordering does not have that price.