Move ordering idea (old and new?)

[dchoman]

I was thinking about move ordering last night, and two ideas came to mind. The first is an old idea of 'counter-move' killers...

http://chessprogramming.wikispaces.com/ ... +Heuristic

which was quick and easy to implement. I ordered these moves just before killers and got a +10 elo boost in quick (6+0.1s) games.

The second idea is related to this, but might be new? Not sure... The idea is to have a 'combo' move hash table. So I setup a hash table which uses as an index the difference between the current hash signature and the hash signature from two ply earlier...

Code: Select all

index = (pos.hcode ^ 2ply_earlier_pos.hcode)&(TABLE_SIZE-1)

So this index should only depend on the last two moves made. Then when I get a cutoff, the move causing the cutoff is stored in the table. It can later be retrieved at other nodes that match the same two previous moves.

I currently am using a bonus when ordering these 'combo move' replies. The bonus is scaled to put a losing capture ahead of a killer or a killer ahead of a winning capture. 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.

I haven't finished my test run on this new idea, but it is looking promising +24 elo after 1200 games.... not enough yet to say, but I am hopeful.

Is anyone doing anything like this, and if so, what experience have you had? There are probably quite a few tweaks to improve performance.

- Dan[/code]

[Gerd Isenberg]

I was thinking about move ordering last night, and two ideas came to mind. The first is an old idea of 'counter-move' killers...

http://chessprogramming.wikispaces.com/ ... +Heuristic

which was quick and easy to implement. I ordered these moves just before killers and got a +10 elo boost in quick (6+0.1s) games.

The second idea is related to this, but might be new? Not sure... The idea is to have a 'combo' move hash table. So I setup a hash table which uses as an index the difference between the current hash signature and the hash signature from two ply earlier...

Code: Select all

index = (pos.hcode ^ 2ply_earlier_pos.hcode)&(TABLE_SIZE-1)

So this index should only depend on the last two moves made. Then when I get a cutoff, the move causing the cutoff is stored in the table. It can later be retrieved at other nodes that match the same two previous moves.

I currently am using a bonus when ordering these 'combo move' replies. The bonus is scaled to put a losing capture ahead of a killer or a killer ahead of a winning capture. 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.

I haven't finished my test run on this new idea, but it is looking promising +24 elo after 1200 games.... not enough yet to say, but I am hopeful.

Is anyone doing anything like this, and if so, what experience have you had? There are probably quite a few tweaks to improve performance.

- Dan

I am not aware of this "generalized" counter move heuristic. Interesting idea, thanks for sharing. Do you use the usual counter move heuristic plus combo, or combo alone?

edit: seems Steven Edwards LBR looks similar
https://chessprogramming.wikispaces.com/Last+Best+Reply

Gerd

[dchoman]

I am not aware of this "generalized" counter move heuristic. Interesting idea, thanks for sharing. Do you use the usual counter move heuristic plus combo, or combo alone?

edit: seems Steven Edwards LBR looks similar
https://chessprogramming.wikispaces.com/Last+Best+Reply

Gerd

Thanks for pointing this out! Indeed it seems that Variant 1 is the same idea.

To answer your other question, right now I am running the two together (+31 elo after 3400 games). When I tried countermoves alone they were +10 after 10000 games.

- Dan

[Evert]

I am not aware of this "generalized" counter move heuristic. Interesting idea, thanks for sharing. Do you use the usual counter move heuristic plus combo, or combo alone?

edit: seems Steven Edwards LBR looks similar
https://chessprogramming.wikispaces.com/Last+Best+Reply

I have a very similar idea in Jazz. I index counter moves using the last move from the opponent and "combination moves" using my own last move. Both are sorted immediately after killer moves.

I didn't find that it actually made the program play better though...

[diep]

I was thinking about move ordering last night, and two ideas came to mind. The first is an old idea of 'counter-move' killers...

http://chessprogramming.wikispaces.com/ ... +Heuristic

which was quick and easy to implement. I ordered these moves just before killers and got a +10 elo boost in quick (6+0.1s) games.

The second idea is related to this, but might be new? Not sure... The idea is to have a 'combo' move hash table. So I setup a hash table which uses as an index the difference between the current hash signature and the hash signature from two ply earlier...

Code: Select all

index = (pos.hcode ^ 2ply_earlier_pos.hcode)&(TABLE_SIZE-1)

So this index should only depend on the last two moves made. Then when I get a cutoff, the move causing the cutoff is stored in the table. It can later be retrieved at other nodes that match the same two previous moves.

I currently am using a bonus when ordering these 'combo move' replies. The bonus is scaled to put a losing capture ahead of a killer or a killer ahead of a winning capture. 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.

I haven't finished my test run on this new idea, but it is looking promising +24 elo after 1200 games.... not enough yet to say, but I am hopeful.

Is anyone doing anything like this, and if so, what experience have you had? There are probably quite a few tweaks to improve performance.

- Dan[/code]

I tested countermove in diep since mid 90s. It's one of those algorithms i sometimes retest. It's a real invention. However it doesn't generalize killermoves at all. So that wiki statement is dead wrong.

The proof of this is so simple that i won't even bother writing it down.

Killermoves on the other hand is a very generic short term concept. A move M that works in position X might also work in position X'.

Countermoves do not share this property. The smaller branching factors of today also make is less likely you can try a countermove in the short term.

It's therefore a long term move ordering concept.

In Diep countermove is very counterproductive and always was. I didn't even find a single position where it worked, that's how bad it works for Diep.

Now that said realize History heuristic, also a long term generic move ordering concept, it also doesn't work for Diep, whereas many programmers are using it with big success improving their move ordering.

Both countermove and history heuristic share they are long term move ordering concepts. Long term in Diep the hashtablemove wins every battle.

A lot of the old move ordering concepts at todays search depths are hopelessly outdated of course, short term killers excepted.

Note that there is many ways how you can implement killertables. It would be worth it to investigate clearly the differences there.

Though it'll be a difference somewhere behind the dot, it still is interesting.

[diep]

I was thinking about move ordering last night, and two ideas came to mind. The first is an old idea of 'counter-move' killers...

http://chessprogramming.wikispaces.com/ ... +Heuristic

which was quick and easy to implement. I ordered these moves just before killers and got a +10 elo boost in quick (6+0.1s) games.

The second idea is related to this, but might be new? Not sure... The idea is to have a 'combo' move hash table. So I setup a hash table which uses as an index the difference between the current hash signature and the hash signature from two ply earlier...

Code: Select all

index = (pos.hcode ^ 2ply_earlier_pos.hcode)&(TABLE_SIZE-1)

So this index should only depend on the last two moves made. Then when I get a cutoff, the move causing the cutoff is stored in the table. It can later be retrieved at other nodes that match the same two previous moves.

I currently am using a bonus when ordering these 'combo move' replies. The bonus is scaled to put a losing capture ahead of a killer or a killer ahead of a winning capture. 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.

I haven't finished my test run on this new idea, but it is looking promising +24 elo after 1200 games.... not enough yet to say, but I am hopeful.

Is anyone doing anything like this, and if so, what experience have you had? There are probably quite a few tweaks to improve performance.

- Dan

I am not aware of this "generalized" counter move heuristic. Interesting idea, thanks for sharing. Do you use the usual counter move heuristic plus combo, or combo alone?

edit: seems Steven Edwards LBR looks similar
https://chessprogramming.wikispaces.com/Last+Best+Reply

Gerd

Most interesting you were not aware of it - but i guess you would have had it worked. It's the same problem like with history heuristics with all forms of countermove (there is a 20 variations or so i saw people try out and report to me).

Basically if you look in a program like Fruit 2.1 how history heuristics order moves, it's pretty close to the piece square tables.

So we can prove for fruit that a small piece of chessknowledge is total beating those tables for move ordering (not to confuse with history pruning that also uses these tables with a success %) when combined with killertables.

Killertables are short term and there is a 100 different variations or so i saw posted and/or authors speak about and/or figured out.

For todays search depths it would be interesting to know what sort of implementation for killertables is most effective.

As for countermove and history table - basically if they work for you, you do something wrong in move ordering.

[Gerd Isenberg]

I tested countermove in diep since mid 90s. It's one of those algorithms i sometimes retest. It's a real invention. However it doesn't generalize killermoves at all. So that wiki statement is dead wrong.

Thanks for pointing that out.

[Gerd Isenberg]

Most interesting you were not aware of it - but i guess you would have had it worked.

What is so interesting with that? Counter move did not work for me.

To index a table with (hashkey[ply] xor hashkey[ply-2]) mod tblsize was old news for you for countermove purpose? Did you invent it by yourself?

[diep]

Most interesting you were not aware of it - but i guess you would have had it worked.

What is so interesting with that? Counter move did not work for me.

To index a table with (hashkey[ply] xor hashkey[ply-2]) mod tblsize was old news for you for countermove purpose? Did you invent it by yourself?

If i recall well Jos Uiterwijk, the inventor of countermove, had written something about it in Dutch, which i read. If not Jos someone else did, Dennis Breuker maybe?

It's trivial to experiment with all sorts of things around the way how to index and which conditions to use.

Note that it's trivially easy to get a better move ordering. Just use your evaluation to order moves - just it slows down a lot - too much for Diep.

Vincent

[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