matthewlai wrote:bob wrote:
Your numbers look a bit strange. Most of us keep a simple fail high counter for the first move, which means we count the number of fail highs that occur, and the number that fail high on the first move. This is typically > 90%, at least for my program. Not the 15% or so you mentioned. This with all the usual ordering such as hash, non-losing captures, killers, counter moves, then history heuristic and the rest of the moves...
It is entirely possible that path-dependent heuristics is the way to go. I haven't established that's not the case yet, and I am not really convinced that it's not the case.
However, this is with no path-dependent stuff at all. No hash move, no killer, no history, no counter moves, etc. And no winning captures.
The moves are predicted simply by looking at the position, with no other information.
Do you happen to have data for history heuristics? I would be very interested in that. Of the positions where either there's no hash move, killers, etc, or where those moves failed to produce a cutoff, how many cutoffs happen on the first move sorted by history? And second move, third move, etc?
Also, the original spirit of this post would still hold with history heuristics.
For example, if hash, killer, good captures, etc don't produce a cutoff, and the history counters are "100, 99, 98, 97", the reduction schedule should probably be different from if it was "100, 0, 0, 0".
I've not had good luck with history and did not use it for a LONG time. I added it back in (again) last year because it does offer some benefit with LMR, since moving "good moves" in front of "bad moves" causes the good moves to be reduced less, and vice-versa. Years ago (Cray Blitz days) I had converted to using two killers per ply, and in the current ply trying first the two killers saved here, and then searching the two killers from two plies back (closer to the root). Once I started doing this, history heuristic stopped giving me any performance gain and I stopped using it.
One other note, Somewhere during the few months as I have been cleaning up my office in preparation for moving about 50 feet, I decided to skim through the ICCA/ICGA journals. I ran across a reference to "relative history counters" or something similar and I thought about it for a bit. Schaeffer recommended using 1<<depth to update the history counter but that obviously only worked back in the days of 5 ply or so searches. I started to use depth * depth as an alternative since the Cray was significantly faster and most still use that today. the relative history idea was to get rid of the depth, and just increment history counters by some sort of constant, and since I am not convinced that a good move at ply=3 is better than a good move at ply=15, when I am ordering moves at ply=31, I decided to give this a try and I like the results better than the depth*depth.
I also switched to a "saturating counter" so that the values don't get too large, nor wrap around when decrementing them. I have not really tested this on how much it improves ordering compared to killers and such, but it did seem to improve LMR performance. I am again re-tuning LMR as I write this as it appears that a more aggressive reduction schedule is working better as move ordering has been improved. The old ICGA journals have lots of info that I had not thought about. Counter-moves actually offer some interesting things when combined with LMR, the idea being to get potential moves searched earlier rather than later, as opposed to just producing a quicker cutoff.
LMR opens up a whole world of such ideas, and I have other to-do things to try (a very simple per-piece eval so that better moves get tried before worse moves (i.e. Nc3-e4 before Nc3-a2) for the same reason.