Idea #8430: Optimizing move ordering, very slowly

[sje]

Okay, I think I see now: ALL nodes in some CUT node subtrees might have different move counts.

This can be handled by assigning score modifiers calculated from the full minimax scan and which blend information about the subtree node counts as needed. Then, the best ranked move(s) will also have the minimal subtree node count. This leads to a canonical α/β scan with perfect move ordering, which is what we were looking for in the first place. Transpositions should work without problems.

[Zenmastur]

Idea #8430: Optimizing move ordering, very slowly

An experiment:

Step 1: Collect a small set of test positions, preferably those where a traditional search will change its PV prediction several times. Run each of these through a program to a fixed depth with A/B pruning disconnected, instead relying upon a full minimax search at each node. During each search and at each searched node, record the moves at each node along with the move's backed-up minimax evaluation. Much patience and fat disks will be necessary.

Step 2: Again, run each position through the program at a fixed depth with A/B turned on this time. Have each search access the stored search results to supply "perfect" move ordering. Record the total searched node counts to get a baseline figure, the best which can be had with all else held equal.

Step 3: Repeatedly run each position through the program again at the same fixed depth with A/B turned on while tinkering with the move ordering. Compare the node counts with the baseline (best) figures. Iteratively modify the move ordering code by examining those nodes where the ordering was very different form the baseline ordering. Perhaps an automated tuning algorithm could help with this.

While reducing the number of nodes required to reach a particular search depth is clearly a laudable goal I think there may be easier ways to go about it.

Grandmasters don't need to search billions of nodes to play very good chess. At best they can search a few hundred positions in the allotted time. The difference is they have a memory which saves a lot of searching. In addition they can analogize a remembered position to the one on the board which also saves a lot of searching. These facilities when combined allow them to search VERY selectively. In many, many cases they will simply verify that the remembered move/idea will work in the current position.
Now imagine a GM that can search millions of nodes in the allotted time instead of hundreds and doesn't make mistakes like a human GM.

Sounds like a fantasy to most, I'm sure. It has been said that a GM "knows" between 50,000 and 100,000 positions. This doesn't tell us much about how many "themes" they know, but it would seem that it has to be considerably fewer than the number of positions they know. This seems to indicate that if we are good at analogizing the search can be made very selective compared to what search engines are doing.

Modern computers are capable of storing every position from a 5,000,000 game database in memory. So providing the engine with a good memory is clearly within the technological limits of today's hardware. The position from even 500,000 games is probably in great excess of what's needed to make a system like this work. A few hundred thousand positions could be stored in memory with very little impact on the memory foot print of most engines. Regardless of the number of positions stored, what's needed to make good use of these positions is the ability to analogize a stored position to a board position. This can probably be done now with a little thought. The problem is doing it in a time and space efficient manner.


On a slightly different tac...

A few months ago I was doing a deep analysis of a game and after a while I noticed that the engine was having to repeatedly refute a particular line of play by black who was losing the game. At first I thought that the depth of the analysis was sufficient that the TT was being overwritten between different branches. On closer inspection I found that this wasn't the cause at all. The cause was the positions were not "exactly" identical so there was no way the TT could help speed up the process by "remembering" what was analyzed in a different branch. This was very annoying because it was taking about an hour per branch and it quickly became obvious that they were several hundred if not thousands of these "similar" branches that needed to be refuted. I had thought that null-move pruning would have killed many of these lines since usually an early move by white wasn't to the point so to speak. After some time I knew the refutation line by heart and spent a lot of time trying to prod SF into re-finding the line from the last branch it had searched over and aver again. If the positions were exactly identical this wouldn't have been a problem.

I got to thinking that it would be useful if there was some way to use a TT type of structure to look for similar positions so that the moves used in these positions could be tried in the current position. It was clear that in almost all cases the refutation was an identical line of play for white. So there is a "good" chance that these moves would be useful as refutations. The problem is how to store a position that is not exact but that can still be searched with a hash key. I haven't worked out all the details yet, so I guess this makes it a half-baked idea. But I thought I would throw out the basic idea and see what everyone thinks and maybe spark a few imaginations in the process. Who knows maybe a few additional ideas will allow something concrete to come of it.

After thinking about it for a while I came up with the idea of creating a different type of transposition table in addition to the "normal" TT. Before storing a position in this new TT we remove the hash value for the last piece moved by the side on the move. So instead of using the full hash key to storing the position we use it minus the last piece moved. Now this makes it a little more complicated to look up the position than a regular TT table. The first thing to note is that we should always look up the "real" position in the regular TT first. If we get a hit there may be no advantage to looking up the position in the "Similarity" TT. This would have to be tried to see if their is any advantage to using a similar position if we've already tried the move from the exact position without success.

Since the position we are trying to look up will have a different last move played than the move currently under consideration we need to do two things to find the position in the new table. First we use the key for the current position before we made a move, then in a systematic manner we remove each one of our pieces, one at a time, and check to see if this generates a hit in the similarity TT. If we get a hit we check the move for depth score and legality. If its legal and the depth is right we can try it. If not we replace the previously removed piece and remove the next piece in the list and try again. The idea is that if some move early in the line of play is irrelevant to the refutation, most are, then the same moves will still be a valid refutation. e.g. if the king is moved from b1 to a1 instead of b1 to c1 or b2 etc and this is far away from the action then this will likely have no effect on the situation so the moves to refute an otherwise identical line of play by black will be the same. By the same token if the move a2 is made instead of Ka1 etc then the moves will very likely be the same. I think this will also catch many transpositions when an early move in the search doesn't affect the main line of play.

This clearly isn't the analogy-engine needed to perform highly selective searches like a GM. But if it can be made to work it could significantly reduce the time needed to reach a particular depth.

Like I said I haven't worked out all the details but I think it is worth looking at. Anyway it's just one idea I've been playing with.

Regards,

Zen