Root move order (again)

[Harald]

What you want to see is that if a move is easy, such as the only obvious reply to a capture, the others should be cut of quickly and thus most of the time spent on this easy move. You are looking for this to reflect the move that is best. If the move is hard and many other moves are just as good or it's changing its mind frequently, you should see a lot of time spent on more than one move. Don

Here is a definition-of-easy idea. Though I have not tested it.
Perhaps someone can test it or tell me if it sounds good or bad.

Every move that is done and evaluated should get an additional value
together with its score. That value should be backed up in the search
and be written in the hash table or even in the triangular PV array.
The value should be short, like 4 bits, and in the range [0..15].

What value? An easy_value or predicted_value.
It is basically the move number in which you try the moves after they are
sorted by captures, killers, piece-square-tables and so on. But the real
number is based on the current move and its PV deeper in the tree.

Code: Select all

easy_value = (MIN(15, move_number) + easy_value_from_deeper_pv) / 2

easy_value == 0 means easy to find, easy_value == 15 means hard to find.
If the move is the first move that comes out of the hash table you use the
stored easy_value instead of the move_number. Static evaluation counts as 0.
The effective weights of easy_values with increasing depth are
(1/2, 1/4, 1/8, 1/16, ...).

Example:
If the moves of a PV are (A, B, C, D, E, F, G) and the move numbers are
(1, 3, 2, 8, 1, 1, 4) then the easy_values are (2, 3, 3, 4, 1, 1, 2).
If the moves of a PV are (A, B, C, D_from_hash_with_easy_value_4)
and the move numbers are (10, 12, 4, 1#) then the easy_values are
(9, 8, 4, 4).
The PV in the first example was easy to find (2) and the PV in the second
example was hard to find (9).

After each iteration you have an easy_value for all the root moves and their PVs.

Harald

[Don]

What you want to see is that if a move is easy, such as the only obvious reply to a capture, the others should be cut of quickly and thus most of the time spent on this easy move. You are looking for this to reflect the move that is best. If the move is hard and many other moves are just as good or it's changing its mind frequently, you should see a lot of time spent on more than one move. Don

Here is a definition-of-easy idea. Though I have not tested it.
Perhaps someone can test it or tell me if it sounds good or bad.

I would say your idea is not a definition but a methodology. The only good way to know how good it is is to test it and see how it works!

The definition is related strongly to its likelihood to change. For a chess program that is what it's about. If you know it will never change then any time you spend beyond that is just taking time away from all the rest of the moves. The only time you can be 100% sure is if there is only 1 move (or if you can prove every move but one leads to a checkmate against you.)

You can estimate the effectiveness of whatever you do by taking a large set of positions and trying to minimize the time you would take to play the same moves you would at a deeper level. To get a reference value you could do this:

1. search each position to 2 minutes.
2. measure how many were found at 1 minute.

How many you played at 1 minute is the reference number, the number to beat if you can. You want to find an algorithm which will find the same number of moves in less time where you are allowed to take more time or less time on any individual position - it's the average that you want to beat. If you can "solve" the same number of positions in 50 seconds it's probably a big win.

The only other thing which is harder to measure is the impact when you are wrong but you could also try to do that by looking at the scores to determine if your algorithm blundered - that would have to be checked for those positions where you played a different move because you took less time.

Every move that is done and evaluated should get an additional value
together with its score. That value should be backed up in the search
and be written in the hash table or even in the triangular PV array.
The value should be short, like 4 bits, and in the range [0..15].

What value? An easy_value or predicted_value.
It is basically the move number in which you try the moves after they are
sorted by captures, killers, piece-square-tables and so on. But the real
number is based on the current move and its PV deeper in the tree.

Code: Select all

easy_value = (MIN(15, move_number) + easy_value_from_deeper_pv) / 2

easy_value == 0 means easy to find, easy_value == 15 means hard to find.
If the move is the first move that comes out of the hash table you use the
stored easy_value instead of the move_number. Static evaluation counts as 0.
The effective weights of easy_values with increasing depth are
(1/2, 1/4, 1/8, 1/16, ...).

Example:
If the moves of a PV are (A, B, C, D, E, F, G) and the move numbers are
(1, 3, 2, 8, 1, 1, 4) then the easy_values are (2, 3, 3, 4, 1, 1, 2).
If the moves of a PV are (A, B, C, D_from_hash_with_easy_value_4)
and the move numbers are (10, 12, 4, 1#) then the easy_values are
(9, 8, 4, 4).
The PV in the first example was easy to find (2) and the PV in the second
example was hard to find (9).

After each iteration you have an easy_value for all the root moves and their PVs.

Harald

[asanjuan]

This has proved to be slightly better than going by node counts. Your mileage may vary. One strength of this system is that if a move is good in one iteration it will stay near the top of the list - but that could be a bad thing if it turns out that this same move is horrible and that is why it got replaced. Most of the time however the search choice is between just 1 or 2 moves and this guarantees that will stay the first 2 entries.

Well there are two ways to do the root move ordering by nodes. The first one uses number of nodes spent on a move only at the previous iteration of iterative deepening. The other method (and the one i use) saves the cumulative nodes from all the previous iterations so if a move proved best at any of the previous iterations, it will hang around the top of the move list. This has the same effect as your approach and probably allows for a smoother overtaking if a best moves becomes bad.

I have commented out code where I basically sort by nodes and then place the best move at the front if it's not already there. I think I go by the total accumulated nodes though. I did not try the other way but it could be better.

We are probably talking about less than 1 ELO improvement no matter how you do it. Of course Komodo tries hard to always finish an iteration which means it will see every move - but we do LMR at the root and if a good move is late in the list it might not get discovered on a given iteration if it's profound. That would imply that sorting by nodes could be a slight win as it is sometimes the case that a good move starts taking more nodes to search even before it is discovered.

I had no luck with this. I even tried using the ratio between iteration N-2 and iteration N-1 to order moves for iteration N, thinking that this might catch moves whose trees are growing signficantly, but not enough to move very far up the list yet. Nothing useful there. I am 100% convinced that with today's searches, the node counters are meaningless. I also used Cray Blitz to test the same things, and there they all seemed to work as expected. But CB did no forward pruning and no reductions other than null-move, R=1, as was common in late 80's.

I have found absolutely nothing useful about the node counts for each ply 1 move. And believe me, I have looked exhaustively over the past 6 months. With some statistical help to see if there was ANY correlation between node counts and future best moves. Nothing turned up, and I did, of course, have a veritable mountain of data for the correlation analysis to use...

Unfortunately, it just doesn't seem to work. I removed that move ordering and reverted to the original crafty approach of a new best move goes to the front, the rest move down one slot, keeping past best moves near the front. Only thing I do a bit differently is that when a move goes to the front, I save an "age" with it (currently using 4). At the end of each iteration, all the ages are reduced by 1, with a lower bound of zero. If a move has a non-zero age, it is not searched in parallel with any other move, nor is it reduced at the root. This handles the flip-flop case that occasionally happens, where the thing keeps changing its mind.

That's odd because it does work for us. Another measure of how easy a move is how often the search changes it's mind. If it changes it's mind on the current iteration is it not easy at all, if it changed on the previous it is not quite as easy and if it changed many iteration ago or never changed at all it is relatively easy. When that happens the first move will consume a lot of nodes but so will the new move so I find it odd that your program has no correlation - it should be that way for almost any program.

The re-search logic in Komodo is such that if the sub tree's are conflicted similar logic holds. A move tends to be easy when the PV is stable and even if the program doesn't change it's mind the recursive PV's may be more "conflicted" and consume more nodes. I wonder if the fact that I have cut and all nodes affects this and in particular HOW I do cut and all nodes. In Komodo every other node is a cut node once you leave the PV but if there is a search failure that propagates to a PV node there is a flip of node types.

Don

Note that my comments were directed ONLY and node count approaches. PV changes are a little more interesting, and I am now running a large test on the idea I explained to you, namely that PV changes indicate hard. If you change 2 or more times, harder still. Previous iterations are kept, but atrophied out over a few iterations. So far I am not seeing ANY benefit to the easy side of this, and am now testing the "hard" part where the search time goes up some if the best move changes at any point, later iterations having more influence than older ones.

More when I get results.

But the node counts, all I can say is "wow". I started playing long games (automated) and dumping the ply-1 move list after each iteration along with the node counts, and was astounded at what I saw. Compared to when I did the same thing with Cray Blitz where it behaved consistently (as expected with more uniform-shaped trees...)

The node counts are probably not valid in general for the entire list. For example this wont' give you a nice list in order of how good the moves are.

What matters is the ratio of the first move to all the rest when the first move is actually chosen. In the case of a very easy move, perhaps the only wining move, all the other moves will look terrible and will quickly be refuted so that should fly by. In the case where 2 or 3 moves are in competition the second move should take some time to search even if it's not kept.

But I remember you saying that Crafty does LMR on every move right away except for the very first move. That might change things considerably. Komodo does LMR at the root but only after looking at several moves full width and at PV nodes we sill do a lot of full depth moves. That could make this not work.

There are ways to instrument this isn't there? One way is to look at opening moves from a huge database and you can assume that easy moves are the ones that are played 100 out of 100 times. In fact the percentage of time played is a rough measure of "easiness" but make sure you have a lot of sample, perhaps positions that have been seen at least 100 times or more.

A controlled experiment is to take a few thousand positions and search them each with crafty for perhaps 1 minute each. The goal is to produce a heuristic that will play as many of the same moves as possible in some fraction of the time. You can get a baseline by checking how many you would play the same in half the time, then see if you can beat that with the same amount of time or less time and check how it compares to various approximations you can come up with for "easiness." The real goal here is not to play easy moves quickly but to play the same move you wasted 3 minutes on in a fraction of the time and you can instrument that very easily. The trick of course is not to stop early when a much better move might easily be found if you take a little longer.

If you try something like this, also try to measure how much you sacrifice when you are wrong. For example you may exit early but the move you play is no better than the one you would have played if you spend the full time searching.

Don

I don't want to ruin the surprise, but do what I did. Play a long game against a good opponent. After each iteration, dump the ply=1 move list and node count for each move. Sometimes the move that will be best the next iteration will have a fairly large count when compared to the rest. But just as frequently, it will have a SMALLER node count than most. The idea sounds good, but with reductions and pruning, it doesn't seem to actually work that way.

I can post a log file showing this if you can't do it easily for your program. I searched for all sorts of correlation. second-best move is at least 50% of the PV move (node counts) suggests another iteration will be useful. Didn't work. Second best move has MORE nodes than the first. Fails. There are so many places where node counts get broken. Every hash hit inside the PV short-changes the node count, ditto for any other root move. If you do what I suggested, you might actually see this kind of output on occasion:

Code: Select all

       Bxe4      335949     0 0
         d5     1051118     0 0
       Rfd8      645743     0 0
        Nh5      585859     0 0
         e5      377863     0 0
       Nxe4      197655     0 0
        Ne5       91882     0 1
        Nh7       84857     0 1
        Bd5       39302     1 1
        Ng4       29087     1 1
        Bc6       15676     1 1
        Qc5       13615     1 1
        Qb8       12134     1 1
       Qxc4       12001     1 1
        Nd5       11762     1 1
        Kh7       11133     1 1
       Rce8        8839     1 1
        Ba6        6896     1 1
         g5        6423     1 1
       Rfe8        6301     1 1
        Ba8        6186     1 1
        Ne8        5770     1 1
        Kh8        5561     1 1
         h5        4288     1 1
        Ra8        4219     1 1
         g6        3887     1 1
        Qc6        3731     1 1
        Nb8        3695     1 1
        Rb8        3649     1 1
        Bd8        2960     1 1
        Qd8        2926     1 1
       Rcd8        2792     1 1
        Nc5           0     1 1

Notice anything unusual? It is NOT a bug. Our good friend the TT causes that. zero nodes searched below that node because at ply=2 there'a hash entry waiting.

Here's a simple tactical position, win at chess #141, Qxf4 leads to a forced mate...

The iteration before it discovers Qxf4, the counters look like this:

Code: Select all

       move       nodes     R/P            
        Kf1       23401     0 0
        Kh2         911     1 1
        Kg3         863     1 1
       Rxf4         858     1 1
        Kg1         666     1 1
       Qxf4         385     1 1

here's the values after the next iteration where the correct move is found:

Code: Select all

       move       nodes     R/P
       Qxf4       11987     0 0
        Kf1       42124     1 0
        Kg3       28800     1 0
        Kg1       14674     1 0
        Kh2        1225     1 1
       Rxf4        1078     1 1
      total       99888

Any surprises? As in PV move is NOT the biggest node count? It is actually #4. In the iteration preceding this, it was at the bottom...

They really don't have a lot of "information content" after all the analysis I have done (node counts)...

It doesn't have to be the biggest node count. It could be least node count or anywhere in between. Checkmates especially should rarely come across as the "easiest" move so this is not a surprise. I think you are expecting the best move to always have the highest node count but that is not the point.

The whole point is that percentage of time spent on the first move will probably vary considerably and that has something to say about how easy the move is.

What you want to see is that if a move is easy, such as the only obvious reply to a capture, the others should be cut of quickly and thus most of the time spent on this easy move. You are looking for this to reflect the move that is best. If the move is hard and many other moves are just as good or it's changing its mind frequently, you should see a lot of time spent on more than one move.

Actually the canonical case is where this only 1 move. 100% of the nodes will be spent on that one move.

There is a human analogy here, don't know if it's completely appropriate but we will spend very little time on the other moves if we believe one is obviously best. A good chess program is highly focused on the best move(s) and should have similar behavior.

Don

For the record, I posted this previously. I had already tried looking at nodes for first move vs nodes for rest of the moves, and using that to detect "easiness or hardness". I found absolutely no correlation between that ratio and whether I was going to either stick with the best move on the next iteration, or whether I was going to change to a different move. The node counts depend on MUCH more than just alpha/beta cutoffs. Where the thinking is that as you begin to change your mind, move ordering gets worse and the tree gets larger. They are sensitive to extensions, reductions, TT hits, pruning decisions, root score (alpha/beta bounds) and such.

I'm old enough and wise enough to not say "nothing will work." But I spent almost 9 months trying everything related to node counts. Nothing worked.

YMMV of course.

Bob,

I'll try to look into this when I get a chance, perhaps what is happening with Komodo is not what I think is happening, it certainly wouldn't be the first time. Whatever it is doing it is working very well for me though so I think I have it right.

On the other hand I have fixed bugs in Komodo where the bug fix made Komodo play weaker! I call it these "fortuitous bugs!"

One thing is crystal clear to me though. There is a LOT to potentially be gained by better time usage decisions. Probably more than half the thinking time, perhaps even 3/4 of the thinking time is spent thinking about the same move you are going to play anyway. So that is an upper bound on how much could be potentially saved. Of course you will only be able to get a little bit of this back, but it is certainly worth going after.

It's also possible that I am inadvertently measuring the branching factor or some other thing and my heuristics are changing the time control with the BF and it's a good thing. So I will take a deeper look at this in view of your results.

Don

I'm very confused... and I'm guessing... but, wouldn't the eval returned by the search be a better predictor for easy moves, or for move ordering, better than any other trick?

I mean:

I've detected that a 1-ply search can predict about 32-33% of every move, in fact, it can solve 75% of the easy captures. A 6 or 7-ply search can solve about 90% of the easy tactical problems, and about 40% of the quiet positions.

At the end, the search is a max() function, so the eval must have something to do here.

Why not to use the eval returned by the search, and compare it against the eval of a (say) 1-ply search of every root move? then, if a move is found better, move it to the first place?
I'm sure that doing this, and using a static margin, every easy move can be found, and a good move ordering can be done.

Also, I don't know, but I guess how many old (or today's) programs tried this before.

Alberto.

[bob]

This has proved to be slightly better than going by node counts. Your mileage may vary. One strength of this system is that if a move is good in one iteration it will stay near the top of the list - but that could be a bad thing if it turns out that this same move is horrible and that is why it got replaced. Most of the time however the search choice is between just 1 or 2 moves and this guarantees that will stay the first 2 entries.

Well there are two ways to do the root move ordering by nodes. The first one uses number of nodes spent on a move only at the previous iteration of iterative deepening. The other method (and the one i use) saves the cumulative nodes from all the previous iterations so if a move proved best at any of the previous iterations, it will hang around the top of the move list. This has the same effect as your approach and probably allows for a smoother overtaking if a best moves becomes bad.

I have commented out code where I basically sort by nodes and then place the best move at the front if it's not already there. I think I go by the total accumulated nodes though. I did not try the other way but it could be better.

We are probably talking about less than 1 ELO improvement no matter how you do it. Of course Komodo tries hard to always finish an iteration which means it will see every move - but we do LMR at the root and if a good move is late in the list it might not get discovered on a given iteration if it's profound. That would imply that sorting by nodes could be a slight win as it is sometimes the case that a good move starts taking more nodes to search even before it is discovered.

I had no luck with this. I even tried using the ratio between iteration N-2 and iteration N-1 to order moves for iteration N, thinking that this might catch moves whose trees are growing signficantly, but not enough to move very far up the list yet. Nothing useful there. I am 100% convinced that with today's searches, the node counters are meaningless. I also used Cray Blitz to test the same things, and there they all seemed to work as expected. But CB did no forward pruning and no reductions other than null-move, R=1, as was common in late 80's.

I have found absolutely nothing useful about the node counts for each ply 1 move. And believe me, I have looked exhaustively over the past 6 months. With some statistical help to see if there was ANY correlation between node counts and future best moves. Nothing turned up, and I did, of course, have a veritable mountain of data for the correlation analysis to use...

Unfortunately, it just doesn't seem to work. I removed that move ordering and reverted to the original crafty approach of a new best move goes to the front, the rest move down one slot, keeping past best moves near the front. Only thing I do a bit differently is that when a move goes to the front, I save an "age" with it (currently using 4). At the end of each iteration, all the ages are reduced by 1, with a lower bound of zero. If a move has a non-zero age, it is not searched in parallel with any other move, nor is it reduced at the root. This handles the flip-flop case that occasionally happens, where the thing keeps changing its mind.

That's odd because it does work for us. Another measure of how easy a move is how often the search changes it's mind. If it changes it's mind on the current iteration is it not easy at all, if it changed on the previous it is not quite as easy and if it changed many iteration ago or never changed at all it is relatively easy. When that happens the first move will consume a lot of nodes but so will the new move so I find it odd that your program has no correlation - it should be that way for almost any program.

The re-search logic in Komodo is such that if the sub tree's are conflicted similar logic holds. A move tends to be easy when the PV is stable and even if the program doesn't change it's mind the recursive PV's may be more "conflicted" and consume more nodes. I wonder if the fact that I have cut and all nodes affects this and in particular HOW I do cut and all nodes. In Komodo every other node is a cut node once you leave the PV but if there is a search failure that propagates to a PV node there is a flip of node types.

Don

Note that my comments were directed ONLY and node count approaches. PV changes are a little more interesting, and I am now running a large test on the idea I explained to you, namely that PV changes indicate hard. If you change 2 or more times, harder still. Previous iterations are kept, but atrophied out over a few iterations. So far I am not seeing ANY benefit to the easy side of this, and am now testing the "hard" part where the search time goes up some if the best move changes at any point, later iterations having more influence than older ones.

More when I get results.

But the node counts, all I can say is "wow". I started playing long games (automated) and dumping the ply-1 move list after each iteration along with the node counts, and was astounded at what I saw. Compared to when I did the same thing with Cray Blitz where it behaved consistently (as expected with more uniform-shaped trees...)

The node counts are probably not valid in general for the entire list. For example this wont' give you a nice list in order of how good the moves are.

What matters is the ratio of the first move to all the rest when the first move is actually chosen. In the case of a very easy move, perhaps the only wining move, all the other moves will look terrible and will quickly be refuted so that should fly by. In the case where 2 or 3 moves are in competition the second move should take some time to search even if it's not kept.

But I remember you saying that Crafty does LMR on every move right away except for the very first move. That might change things considerably. Komodo does LMR at the root but only after looking at several moves full width and at PV nodes we sill do a lot of full depth moves. That could make this not work.

There are ways to instrument this isn't there? One way is to look at opening moves from a huge database and you can assume that easy moves are the ones that are played 100 out of 100 times. In fact the percentage of time played is a rough measure of "easiness" but make sure you have a lot of sample, perhaps positions that have been seen at least 100 times or more.

A controlled experiment is to take a few thousand positions and search them each with crafty for perhaps 1 minute each. The goal is to produce a heuristic that will play as many of the same moves as possible in some fraction of the time. You can get a baseline by checking how many you would play the same in half the time, then see if you can beat that with the same amount of time or less time and check how it compares to various approximations you can come up with for "easiness." The real goal here is not to play easy moves quickly but to play the same move you wasted 3 minutes on in a fraction of the time and you can instrument that very easily. The trick of course is not to stop early when a much better move might easily be found if you take a little longer.

If you try something like this, also try to measure how much you sacrifice when you are wrong. For example you may exit early but the move you play is no better than the one you would have played if you spend the full time searching.

Don

I don't want to ruin the surprise, but do what I did. Play a long game against a good opponent. After each iteration, dump the ply=1 move list and node count for each move. Sometimes the move that will be best the next iteration will have a fairly large count when compared to the rest. But just as frequently, it will have a SMALLER node count than most. The idea sounds good, but with reductions and pruning, it doesn't seem to actually work that way.

I can post a log file showing this if you can't do it easily for your program. I searched for all sorts of correlation. second-best move is at least 50% of the PV move (node counts) suggests another iteration will be useful. Didn't work. Second best move has MORE nodes than the first. Fails. There are so many places where node counts get broken. Every hash hit inside the PV short-changes the node count, ditto for any other root move. If you do what I suggested, you might actually see this kind of output on occasion:

Code: Select all

       Bxe4      335949     0 0
         d5     1051118     0 0
       Rfd8      645743     0 0
        Nh5      585859     0 0
         e5      377863     0 0
       Nxe4      197655     0 0
        Ne5       91882     0 1
        Nh7       84857     0 1
        Bd5       39302     1 1
        Ng4       29087     1 1
        Bc6       15676     1 1
        Qc5       13615     1 1
        Qb8       12134     1 1
       Qxc4       12001     1 1
        Nd5       11762     1 1
        Kh7       11133     1 1
       Rce8        8839     1 1
        Ba6        6896     1 1
         g5        6423     1 1
       Rfe8        6301     1 1
        Ba8        6186     1 1
        Ne8        5770     1 1
        Kh8        5561     1 1
         h5        4288     1 1
        Ra8        4219     1 1
         g6        3887     1 1
        Qc6        3731     1 1
        Nb8        3695     1 1
        Rb8        3649     1 1
        Bd8        2960     1 1
        Qd8        2926     1 1
       Rcd8        2792     1 1
        Nc5           0     1 1

Notice anything unusual? It is NOT a bug. Our good friend the TT causes that. zero nodes searched below that node because at ply=2 there'a hash entry waiting.

Here's a simple tactical position, win at chess #141, Qxf4 leads to a forced mate...

The iteration before it discovers Qxf4, the counters look like this:

Code: Select all

       move       nodes     R/P            
        Kf1       23401     0 0
        Kh2         911     1 1
        Kg3         863     1 1
       Rxf4         858     1 1
        Kg1         666     1 1
       Qxf4         385     1 1

here's the values after the next iteration where the correct move is found:

Code: Select all

       move       nodes     R/P
       Qxf4       11987     0 0
        Kf1       42124     1 0
        Kg3       28800     1 0
        Kg1       14674     1 0
        Kh2        1225     1 1
       Rxf4        1078     1 1
      total       99888

Any surprises? As in PV move is NOT the biggest node count? It is actually #4. In the iteration preceding this, it was at the bottom...

They really don't have a lot of "information content" after all the analysis I have done (node counts)...

It doesn't have to be the biggest node count. It could be least node count or anywhere in between. Checkmates especially should rarely come across as the "easiest" move so this is not a surprise. I think you are expecting the best move to always have the highest node count but that is not the point.

The whole point is that percentage of time spent on the first move will probably vary considerably and that has something to say about how easy the move is.

What you want to see is that if a move is easy, such as the only obvious reply to a capture, the others should be cut of quickly and thus most of the time spent on this easy move. You are looking for this to reflect the move that is best. If the move is hard and many other moves are just as good or it's changing its mind frequently, you should see a lot of time spent on more than one move.

Actually the canonical case is where this only 1 move. 100% of the nodes will be spent on that one move.

There is a human analogy here, don't know if it's completely appropriate but we will spend very little time on the other moves if we believe one is obviously best. A good chess program is highly focused on the best move(s) and should have similar behavior.

Don

For the record, I posted this previously. I had already tried looking at nodes for first move vs nodes for rest of the moves, and using that to detect "easiness or hardness". I found absolutely no correlation between that ratio and whether I was going to either stick with the best move on the next iteration, or whether I was going to change to a different move. The node counts depend on MUCH more than just alpha/beta cutoffs. Where the thinking is that as you begin to change your mind, move ordering gets worse and the tree gets larger. They are sensitive to extensions, reductions, TT hits, pruning decisions, root score (alpha/beta bounds) and such.

I'm old enough and wise enough to not say "nothing will work." But I spent almost 9 months trying everything related to node counts. Nothing worked.

YMMV of course.

Bob,

I'll try to look into this when I get a chance, perhaps what is happening with Komodo is not what I think is happening, it certainly wouldn't be the first time. Whatever it is doing it is working very well for me though so I think I have it right.

On the other hand I have fixed bugs in Komodo where the bug fix made Komodo play weaker! I call it these "fortuitous bugs!"

One thing is crystal clear to me though. There is a LOT to potentially be gained by better time usage decisions. Probably more than half the thinking time, perhaps even 3/4 of the thinking time is spent thinking about the same move you are going to play anyway. So that is an upper bound on how much could be potentially saved. Of course you will only be able to get a little bit of this back, but it is certainly worth going after.

It's also possible that I am inadvertently measuring the branching factor or some other thing and my heuristics are changing the time control with the BF and it's a good thing. So I will take a deeper look at this in view of your results.

Don

I have made a "SLIGHT" improvement to Crafty now. My "easy/hard" classification is working, within the range of 60% to 200%. A position migrates toward 60% with many successive iterations with just one best move. It moves toward 200% when there are PV move changes in an iteration. I've tuned both bounds, and these work best and are a 5-6 Elo improvement over what I was doing...

Going below 60 drops Elo pretty quickly, and going above 200 does the same.

Note that I an not, and probably never will be a "complete the current iteration at all costs" because I believe my current approach addresses that problem in a more efficient way, that is, when time is up, I don't stop searching, but I do stop searching new root moves. This makes the search examine anything in progress before exiting, which picks up most of those PV changes since in the measurements I did, in the majority of the times in real games, the best move often comes from previous iterations, if one comes at all. This solves that without committing the time to search the end of the move list which usually has nothing of interest at all.

Still have a few more things to play with, but I did give up on node counts completely. Seemed like a good idea, but as commonly happens, what sounds good works poorly... If I had a nickel for every such idea that didn't pan out...

One interesting thing to look at is to measure the fh% (percentage of times a fail high happens on the first move as opposed to later moves). I generally don't see that changing when a new best move is working its way to the top. And it is hard as hell to measure with reductions and pruning going on.

[bob]

The thing I want is some way to recognize a position as easy, typical, or hard (with a range, obviously, not just 3 states). A 1-ply search doesn't seem to come anywhere near to helping expose this detail about the tree that a deep search will traverse.

[bob]

What you want to see is that if a move is easy, such as the only obvious reply to a capture, the others should be cut of quickly and thus most of the time spent on this easy move. You are looking for this to reflect the move that is best. If the move is hard and many other moves are just as good or it's changing its mind frequently, you should see a lot of time spent on more than one move. Don

Here is a definition-of-easy idea. Though I have not tested it.
Perhaps someone can test it or tell me if it sounds good or bad.

Every move that is done and evaluated should get an additional value
together with its score. That value should be backed up in the search
and be written in the hash table or even in the triangular PV array.
The value should be short, like 4 bits, and in the range [0..15].

What value? An easy_value or predicted_value.
It is basically the move number in which you try the moves after they are
sorted by captures, killers, piece-square-tables and so on. But the real
number is based on the current move and its PV deeper in the tree.

Code: Select all

easy_value = (MIN(15, move_number) + easy_value_from_deeper_pv) / 2

easy_value == 0 means easy to find, easy_value == 15 means hard to find.
If the move is the first move that comes out of the hash table you use the
stored easy_value instead of the move_number. Static evaluation counts as 0.
The effective weights of easy_values with increasing depth are
(1/2, 1/4, 1/8, 1/16, ...).

Example:
If the moves of a PV are (A, B, C, D, E, F, G) and the move numbers are
(1, 3, 2, 8, 1, 1, 4) then the easy_values are (2, 3, 3, 4, 1, 1, 2).
If the moves of a PV are (A, B, C, D_from_hash_with_easy_value_4)
and the move numbers are (10, 12, 4, 1#) then the easy_values are
(9, 8, 4, 4).
The PV in the first example was easy to find (2) and the PV in the second
example was hard to find (9).

After each iteration you have an easy_value for all the root moves and their PVs.

Harald

Here's one point that is critical to understand in reading this thread. "Risk and Reward".

If you want to classify a move as "easy", the only reason for doing so is so that you can save some time by making the move quicker. This dates back to the days of Chess 4.x, Cray Blitz, HiTech and everyone else that used some form or another (very restrictive forms) by the way to say "this move is obvious." Chess 4.x used the idea "move must be a recapture that captures on the TO square of the opponent's last move, AND, it must restore the material balance to what it was after the last normal search.

What is the reward? Time. CB (and chess 4.x I believe) used 1/3 of the target time if a move was easy. If you figure a 40 move / 2hr game, where you might have 4-5 easy moves in the first 40, you would average 3 minutes a move, but for the 5 easy moves you use only one minute each. Saving 10 minutes, applied (averaged) over the remaining moves. In a 2 hour search time, you would play like you had 130 minutes rather than 120.

What is the risk? Ending the search before you realize the "easy move" is a mistake. And here the risk is devastating. You will likely lose the game if you overlook an important tactic.

So, save a little time, or throw a game. Which is more important? With a very restrictive "easy" classifier, you minimize the risk, and the reward, but at least whatever reward you get is relatively safe. For example, sometimes the opponent plays BxN and you can recapture immediately, to recover the material, or you can threaten something and still make the recapture later. If you move too quickly, you will recap immediately instead of playing the better move. Doesn't happen so often with a restrictive form, but it does happen. It happens often enough that when I disabled the restrictive easy move code in Crafty, there was zero Elo loss or gain, meaning the occasional blunders offset the time gain exactly.

If you want to be less restrictive, say in an endgame where the opponent plays KxP and you play KxP to keep material equality, this gets riskier. It obviously is not a classic "recapture" and is more of a "you take mine over here and I'll take yours over there" sort of thing. That will happen more often, which exposes you to more risk and reward.

Or you can try to take it further, as I am working on right now, where you say something like "OK< this move has been best for a bunch of consecutive iterations, I am willing to stop searching and move early and save the time for later." The risk is climbing along with the reward, and if you are not careful, it passes the reward easily. How many times have you seen the best move remain constant for 20 consecutive iterations, and then suddenly fail low and the program changes to something better? With this scheme, it would have moved before the fail low happened, hitting you with a very large risk to go against that modest reward.

That's what I want to do. I have been partially successful, but I remain convinced there is more to this idea than I have extracted, to date...

[Don]

Here's one point that is critical to understand in reading this thread. "Risk and Reward".

That is what I tried to say earlier, but you have said it better here. It all comes down to risk vs reward, a nice way to put it.

I once packaged this up as "wise use of time" which at the highest level is what this is. But risk vs reward gets more the nuts and bolts of the problem we are grappling with. It's really a game within a game and time usage is all a calculated gamble in the face of a great deal of uncertainty.

If you want to classify a move as "easy", the only reason for doing so is so that you can save some time by making the move quicker. This dates back to the days of Chess 4.x, Cray Blitz, HiTech and everyone else that used some form or another (very restrictive forms) by the way to say "this move is obvious." Chess 4.x used the idea "move must be a recapture that captures on the TO square of the opponent's last move, AND, it must restore the material balance to what it was after the last normal search.

What is the reward? Time. CB (and chess 4.x I believe) used 1/3 of the target time if a move was easy. If you figure a 40 move / 2hr game, where you might have 4-5 easy moves in the first 40, you would average 3 minutes a move, but for the 5 easy moves you use only one minute each. Saving 10 minutes, applied (averaged) over the remaining moves. In a 2 hour search time, you would play like you had 130 minutes rather than 120.

What is the risk? Ending the search before you realize the "easy move" is a mistake. And here the risk is devastating. You will likely lose the game if you overlook an important tactic.

So, save a little time, or throw a game. Which is more important?

It's not quite that simple because how much you decide to spend on a move is arbitrary anyway. Whether you think too long or not long enough you are introducing risk. If you fail to take less time you risk making a mistake later and if you DO take less time you risk it on this move.

Every program decided how much time to spend on the early moves vs late moves and so if you spend more time in the early part of the game like almost every good author does you accept the increased risk "throwing the game" in the ending. In Komodo we go the other way too in any stage, we may take more time on any individual move.

It's all a calculated gamble, hence your "risk worth reward" statement which really is the right way to put it. We all make risk worth reward decisions every day, every time you get in a car you take a chance with your life.

With a very restrictive "easy" classifier, you minimize the risk, and the reward, but at least whatever reward you get is relatively safe. For example, sometimes the opponent plays BxN and you can recapture immediately, to recover the material, or you can threaten something and still make the recapture later. If you move too quickly, you will recap immediately instead of playing the better move. Doesn't happen so often with a restrictive form, but it does happen. It happens often enough that when I disabled the restrictive easy move code in Crafty, there was zero Elo loss or gain, meaning the occasional blunders offset the time gain exactly.

If you want to be less restrictive, say in an endgame where the opponent plays KxP and you play KxP to keep material equality, this gets riskier. It obviously is not a classic "recapture" and is more of a "you take mine over here and I'll take yours over there" sort of thing. That will happen more often, which exposes you to more risk and reward.

Or you can try to take it further, as I am working on right now, where you say something like "OK< this move has been best for a bunch of consecutive iterations, I am willing to stop searching and move early and save the time for later." The risk is climbing along with the reward, and if you are not careful, it passes the reward easily. How many times have you seen the best move remain constant for 20 consecutive iterations, and then suddenly fail low and the program changes to something better? With this scheme, it would have moved before the fail low happened, hitting you with a very large risk to go against that modest reward.

That's what I want to do. I have been partially successful, but I remain convinced there is more to this idea than I have extracted, to date...

[Kempelen]

Code: Select all

       Bxe4      335949     0 0
         d5     1051118     0 0
       Rfd8      645743     0 0
        Nh5      585859     0 0
         e5      377863     0 0
       Nxe4      197655     0 0
        Ne5       91882     0 1
        Nh7       84857     0 1
        Bd5       39302     1 1
        Ng4       29087     1 1
        Bc6       15676     1 1
        Qc5       13615     1 1
        Qb8       12134     1 1
       Qxc4       12001     1 1
        Nd5       11762     1 1
        Kh7       11133     1 1
       Rce8        8839     1 1
        Ba6        6896     1 1
         g5        6423     1 1
       Rfe8        6301     1 1
        Ba8        6186     1 1
        Ne8        5770     1 1
        Kh8        5561     1 1
         h5        4288     1 1
        Ra8        4219     1 1
         g6        3887     1 1
        Qc6        3731     1 1
        Nb8        3695     1 1
        Rb8        3649     1 1
        Bd8        2960     1 1
        Qd8        2926     1 1
       Rcd8        2792     1 1
        Nc5           0     1 1

Notice anything unusual? It is NOT a bug. Our good friend the TT causes that. zero nodes searched below that node because at ply=2 there'a hash entry waiting.

Hello Bob,

Do you think storing node count in TT could help later in move ordering?. That way you will always have the "true" effort needed for each node. Of course there is a drawback, you have less space in the whole table.

[jdart]

Unfortunately, it just doesn't seem to work. I removed that move ordering and reverted to the original crafty approach of a new best move goes to the front, the rest move down one slot, keeping past best moves near the front. Only thing I do a bit differently is that when a move goes to the front, I save an "age" with it (currently using 4). At the end of each iteration, all the ages are reduced by 1, with a lower bound of zero. If a move has a non-zero age, it is not searched in parallel with any other move, nor is it reduced at the root. This handles the flip-flop case that occasionally happens, where the thing keeps changing its mind.

Based on this thread, I tried a variant of this. Arasan actually searches the first few iterations with all moves having a nonzero window, for easy move detection. So I actually have scores for the moves at that point and for those iterations I sort on the scores. This gives a rough starting ordering.

Formerly after the wide window part of the search I sorted on node counts but I tried as you suggested just moving the new PV to the front and pushing all other moves down.

I think from what you said this is a better founded approach. However, in fact, this tested equal with a sort based on node counts. It wasn't any better, but it wasn't worse either.

[Don]

Code: Select all

       Bxe4      335949     0 0
         d5     1051118     0 0
       Rfd8      645743     0 0
        Nh5      585859     0 0
         e5      377863     0 0
       Nxe4      197655     0 0
        Ne5       91882     0 1
        Nh7       84857     0 1
        Bd5       39302     1 1
        Ng4       29087     1 1
        Bc6       15676     1 1
        Qc5       13615     1 1
        Qb8       12134     1 1
       Qxc4       12001     1 1
        Nd5       11762     1 1
        Kh7       11133     1 1
       Rce8        8839     1 1
        Ba6        6896     1 1
         g5        6423     1 1
       Rfe8        6301     1 1
        Ba8        6186     1 1
        Ne8        5770     1 1
        Kh8        5561     1 1
         h5        4288     1 1
        Ra8        4219     1 1
         g6        3887     1 1
        Qc6        3731     1 1
        Nb8        3695     1 1
        Rb8        3649     1 1
        Bd8        2960     1 1
        Qd8        2926     1 1
       Rcd8        2792     1 1
        Nc5           0     1 1

Notice anything unusual? It is NOT a bug. Our good friend the TT causes that. zero nodes searched below that node because at ply=2 there'a hash entry waiting.

Hello Bob,

Do you think storing node count in TT could help later in move ordering?. That way you will always have the "true" effort needed for each node. Of course there is a drawback, you have less space in the whole table.

That could be mitigated significantly by storing the log of the node count. Of course you throw away some resolution. If you already have a history table I'm not sure how useful that is.

Perhaps it would be more useful if it were used in the logic to decide which hash table slot to replace when there is a choice? Surely something like this has already been tried I would think.