easy-hard moves (again)

[bob]

So far, nothing spectacular has been found. Here's what does NOT work well:

(1) comparing the total nodes for each root move. Sometimes, the second move seed its node count pass the first, which might be a warning for a potential PV change, but not always.

(2) we discussed the fh percentages for each root move. Absolutely nothing useful there. The fh% values are consistent as possible and don't say anything about a potential PV change when analyzed statistically.

(3) the frequency of best move changes comes a bit closer, but there are those positions where the best moves are going to cycle iteration by iteration, not because one is better significantly, but because they are close in terms of score.

The only thing that did catch my eye, and which I am currently playing with, is the percentage of growth iteration by iteration, root-move by root-move. I have seen some strong indications of correlation between growth rate of an individual move, with a potential PV change. I was trying to use various ratios (best-move size compared to second-biggest root move tree, and such, to no avail) but did notice that each move might double iteration by iteration until suddenly one move way more than doubles, and becomes a new best move a ply or two later.

Studying this now...

[hgm]

How about offsetted aspiration in the root for all non-PV moves? In stead of setting alpha to the score of the first move for the rest of the moves in the root, set it to alpha - gap, where gap starts at 300cP before the search. If moves fail high compared to this alpha, reduce gap to 100cP, and re-search them. If they again fail high compared to this new null window, set gap = 0, so alpha becomes the score of the first move, and re-search. If it fails high again, search with open window. (The last two ssearches would be normal PVS.)

While gap == 300cP, use 1/10 of your normal time limits. While it is 100, use 1/3 of those.

Sure enough, on most moves the first few iterations will require re-searches, and gap will quickly reach zero. But who cares how many re-searches you do at depth < 5? They take no time.

If it manages to hold off the other moves by a margin of a piece or a pawn, sure enough, it will require somewhat more nodes than with the more relaxed PVS alpha. But who cares if you reach not as much depth with the same number of nodes? This is an easy move, and depth is supposedly not that important.

[BubbaTough]

Hannibal1.2 used this approach, with a cutoff of 150 and 60. The result was very natural time usage, but it was not at all clear it was an elo winner.

-Sam

How about offsetted aspiration in the root for all non-PV moves? In stead of setting alpha to the score of the first move for the rest of the moves in the root, set it to alpha - gap, where gap starts at 300cP before the search. If moves fail high compared to this alpha, reduce gap to 100cP, and re-search them. If they again fail high compared to this new null window, set gap = 0, so alpha becomes the score of the first move, and re-search. If it fails high again, search with open window. (The last two ssearches would be normal PVS.)

While gap == 300cP, use 1/10 of your normal time limits. While it is 100, use 1/3 of those.

Sure enough, on most moves the first few iterations will require re-searches, and gap will quickly reach zero. But who cares how many re-searches you do at depth < 5? They take no time.

If it manages to hold off the other moves by a margin of a piece or a pawn, sure enough, it will require somewhat more nodes than with the more relaxed PVS alpha. But who cares if you reach not as much depth with the same number of nodes? This is an easy move, and depth is supposedly not that important.

[bob]

Hannibal1.2 used this approach, with a cutoff of 150 and 60. The result was very natural time usage, but it was not at all clear it was an elo winner.

-Sam

How about offsetted aspiration in the root for all non-PV moves? In stead of setting alpha to the score of the first move for the rest of the moves in the root, set it to alpha - gap, where gap starts at 300cP before the search. If moves fail high compared to this alpha, reduce gap to 100cP, and re-search them. If they again fail high compared to this new null window, set gap = 0, so alpha becomes the score of the first move, and re-search. If it fails high again, search with open window. (The last two ssearches would be normal PVS.)

While gap == 300cP, use 1/10 of your normal time limits. While it is 100, use 1/3 of those.

Sure enough, on most moves the first few iterations will require re-searches, and gap will quickly reach zero. But who cares how many re-searches you do at depth < 5? They take no time.

If it manages to hold off the other moves by a margin of a piece or a pawn, sure enough, it will require somewhat more nodes than with the more relaxed PVS alpha. But who cares if you reach not as much depth with the same number of nodes? This is an easy move, and depth is supposedly not that important.

I had tried something similar for "easy moves". And it seemed to be reasonable. But in Crafty, I can actually disable easy moves and the Elo effect is not measurable, because the normal easy move code is triggered infrequently.

But the other end seems harder. That is, "is this move hard?" as opposed to "easy"?

What I am REALLY looking for is not something that particularly recognizes positions that are easy, but something that recognizes that something is "hard" but before it fails low (which is sometimes too late). But maybe there is something in this "idea" that might be able to help there. Still thinking, testing and observing.

[BubbaTough]

I am looking forward to following your research on this. I have spent way to much time of the years for very little elo following my intuition that more human time management is worth some elo (and makes it much less annoying to watch games). I have never tried anything like what you are exploring though, maybe it will lead somewhere interesting.

-Sam

[rreagan]

I'm not sure if this applies or not, but I'll throw it out there. I recall discussing something like this a long time ago with a guy (a grad student or professor, I assumed), and the answer I got was to look into one of these topics:

http://en.wikipedia.org/wiki/Minimum_message_length
http://en.wikipedia.org/wiki/Maximum_likelihood

The idea was to use classification, and I guess these boil down to some kind of entropy measurement. The guy wasn't sure if there was an answer to this, but he was "quite sure" that if there was, MML was the framework that would provide the answer. Or maybe this was "his area", and when all you have is a hammer...

I don't know if this is even in the ballpark, but I'll let you sort that out

[bob]

I am looking forward to following your research on this. I have spent way to much time of the years for very little elo following my intuition that more human time management is worth some elo (and makes it much less annoying to watch games). I have never tried anything like what you are exploring though, maybe it will lead somewhere interesting.

-Sam

Right now it is leading to sharp pains in the ass and headaches.

[bob]

I'm not sure if this applies or not, but I'll throw it out there. I recall discussing something like this a long time ago with a guy (a grad student or professor, I assumed), and the answer I got was to look into one of these topics:

http://en.wikipedia.org/wiki/Minimum_message_length
http://en.wikipedia.org/wiki/Maximum_likelihood

The idea was to use classification, and I guess these boil down to some kind of entropy measurement. The guy wasn't sure if there was an answer to this, but he was "quite sure" that if there was, MML was the framework that would provide the answer. Or maybe this was "his area", and when all you have is a hammer...

I don't know if this is even in the ballpark, but I'll let you sort that out

The problem is that MML and such depends on having more than one possible solution to a problem, first. To date, I've not found anything that works reliably to classify a particular position / move as "easy, typical or hard."

There are a few semi-reasonable ways to classify moves as easy. So far, nothing really helps with "hard". The problem is that when you classify something as hard, you are going to burn more time. The more frequently you are wrong, the worse you play because you burn time unnecessarily. Hence my "search for the holy grail" at the moment.

[bob]

Just a clarification. The "windowed" approach for easy moves does NOT do what I want, which is why I have been looking at this for a bit. Here's a sample position where the "easy move" detection might claim "easy" when it is not, or it might miss the fact that the best move is actually easy after a second or so:

[d] 5r1k/6p1/1n2Q2p/4p3/8/7P/PP4PK/R1B1q3 w - - 0 1

In very early iterations (at least first 4 for Crafty) Qxb6 looks good. Then it fails low. This would "disable" the easy-move code we were discussing (offset the window for rest of moves after score for first has been found).

But then you find Bxh6 which is the ONLY move that saves the position for white, and I want to recognize that it is "easy". Which my old easy move code did not do, nor does the offset window code either.

I could not get it to display correctly and didn't have time since I am on the way to class. Will try again later to re-enter the position so it will display

This was a game played between Belle and Cray Blitz at the 1981 ACM computer chess event. Qxb6 is tempting (was more tempting back then) but it loses. Bxh6 is a forced draw that was fairly hard to find back in 1981.

[Uri Blass]

Just a clarification. The "windowed" approach for easy moves does NOT do what I want, which is why I have been looking at this for a bit. Here's a sample position where the "easy move" detection might claim "easy" when it is not, or it might miss the fact that the best move is actually easy after a second or so:

[d] 5r1k/6p1/1n2Q2p/4p3/8/7P/PP4PK/R1B1q3 w - - 0 1

In very early iterations (at least first 4 for Crafty) Qxb6 looks good. Then it fails low. This would "disable" the easy-move code we were discussing (offset the window for rest of moves after score for first has been found).

But then you find Bxh6 which is the ONLY move that saves the position for white, and I want to recognize that it is "easy".

Bxh6 is not the only move that saves the position for white.
It seems that Bf4 also saves the position for white