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.
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.