Move ordering by PST

[Daniel Shawul]

History is better for the simple fact that it is dynamic (it learns).
I am sure PST is as garbage as history at larger depths. There is a variation
of history used in GO known as RAVE (Rapid Action Value Estimation) which is claimed
to give a 300 ELO over plain UCT. The idea is that on each node history information
only below that node is collected to quickly estimate the score of that node.
History works best in games where a move's value has less association of where in the tree
it is played. Havannah is one such example..order of moves played at different plies does not
affect the outcome since there are _only_drop moves. In Go there is some difficulty since captures
remove pieces off the board..

An improvement in history for chess I think can be using them like killers are used..
Instead of collecting one history table for all the depths, have them for each 6 plies f.i
to stress the fact that chess is different from Havannah.

[Evert]

An improvement in history for chess I think can be using them like killers are used..
Instead of collecting one history table for all the depths, have them for each 6 plies f.i
to stress the fact that chess is different from Havannah.

I tried that, and it didn't improve anything.
Now, given that my chess program is nowhere near as strong as many of the other ones out there, I probably have some bugs or other issues that handicap things and that may be why this didn't work when I tried it.
Here's why I think it doesn't work so well though: for a 6 (say) ply search from the root, all positions are fairly closely related (separated from their common parent by at most 6 plies). However, for a 6 ply search at 6 ply from the root, you will probe positions that are 12 ply removed from their common parent. The related-ness of positions far away from the root of the tree goes down, there's nothing you can do to prevent that - and it's this information from unrelated positions that destroys the idea.
Of course, on closer consideration, you'd think that you search closely related positions close together and unrelated positions with a large separation in number of nodes searched, so you could theoretically clean out the table when you think you're about to search a position that is very different from the ones that contributed to the history table so far, but there's a cost associated with that, which can go up a lot since you're doing this closer to the leaves of the tree.
That's the impression I had for why this idea didn't work for me, but I could be wrong of course.
I should probably also mention that I have a few other "history-like" ideas in my program: I use counter moves (a history table indexed by the last move made by the opponent) and I try killer moves from two plies down in the tree. These ideas combined already transport information between otherwise unrelated parts of the tree and maybe adding more doesn't do anything useful. Afterall, you only need enough information to sort the move that causes the cut-off (assuming there is one) high up the list. Your move ordering beyond that point doesn't matter.

[mcostalba]

I am not sure to agree here,the key is how fast it is in penalize bad moves, an history that very quicly. Moves up the bonus for good moves and very quicly penalize bad ones increases the locality, you can search also at depth 30 but if the history changes quiclly then will be always tuned to the 10-15 plies sub tree it is searching in a given moment.

Seems that history tables are a relict of the history of chess engines when they searched 7 plies

[bob]

I am not sure to agree here,the key is how fast it is in penalize bad moves, an history that very quicly. Moves up the bonus for good moves and very quicly penalize bad ones increases the locality, you can search also at depth 30 but if the history changes quiclly then will be always tuned to the 10-15 plies sub tree it is searching in a given moment.

That's the key. Move ordering in early plies is much more critical than move ordering in late plies, yet history is a local idea because of the number of local updates done, which hurts globally. I had marginally better results using an array of history counters indexed by ply, but "marginal" is the key word.

Seems that history tables are a relict of the history of chess engines when they searched 7 plies

[Onno Garms]

Move ordering in early plies is much more critical than move ordering in late plies,

But there are many late plies and few early. So ordering many late plies well might still have value. For early plies, at least the first move should be determined by IID (or by the TT, if there is a match) anyway.

Comparing Fruit to Stockfish, an important(?) difference is that Stockfish decrements the history score on a bad move while Fruit just increments on good moves. Bob, have you tried something like that?

Another question: Has anybody tried node count on early plies? (I mean, if you do IID, to sort the following moves)? I know this has been discussed at least for the root node (currently I am too lazy to look that up), but one might try it at other nodes too.

[Daniel Shawul]

I should probably also mention that I have a few other "history-like" ideas in my program: I use counter moves (a history table indexed by the last move made by the opponent) and I try killer moves from two plies down in the tree. These ideas combined already transport information between otherwise unrelated parts of the tree and maybe adding more doesn't do anything useful. Afterall, you only need enough information to sort the move that causes the cut-off (assuming there is one) high up the list. Your move ordering beyond that point doesn't matter.

Interesting stuff. I used killers at plies different from the current ply and am sure many other do, but never tried anything special with the last good move of the opponent. In games like Go this makes perfect sense since refuting the last move of the opponent is a big deal to resolve local
fights. My Qsearch for Go is based on that idea which otherwise will explode if I check other places too... I am sure there is an 'algorithm' by that name..

Here's why I think it doesn't work so well though: for a 6 (say) ply search from the root, all positions are fairly closely related (separated from their common parent by at most 6 plies). However, for a 6 ply search at 6 ply from the root, you will probe positions that are 12 ply removed from their common parent. The related-ness of positions far away from the root of the tree goes down, there's nothing you can do to prevent that - and it's this information from unrelated positions that destroys the idea.
Of course, on closer consideration, you'd think that you search closely related positions close together and unrelated positions with a large separation in number of nodes searched, so you could theoretically clean out the table when you think you're about to search a position that is very different from the ones that contributed to the history table so far, but there's a cost associated with that, which can go up a lot since you're doing this closer to the leaves of the tree.
That's the impression I had for why this idea didn't work for me, but I could be wrong of course.

I was thinking more like to use one table for a 1-6 plies, another for 7-13, another for 14-20 etc...
This should keep the "related" positions in one table.

I doubt that any improvement on history will be significant since the conventional chess
move ordering is very good to begin with. But now that LMR is added to the mix, a small improvement
in history could be significant, maybe much more than a PST could ever do.

[michiguel]

Move ordering in early plies is much more critical than move ordering in late plies,

But there are many late plies and few early. So ordering many late plies well might still have value. For early plies, at least the first move should be determined by IID (or by the TT, if there is a match) anyway.

Comparing Fruit to Stockfish, an important(?) difference is that Stockfish decrements the history score on a bad move while Fruit just increments on good moves. Bob, have you tried something like that?

Another question: Has anybody tried node count on early plies? (I mean, if you do IID, to sort the following moves)? I know this has been discussed at least for the root node (currently I am too lazy to look that up), but one might try it at other nodes too.

I did. but it did not work at all. It hurts me because I had this in my to-try list for at least 10 years (I am not kidding).

However, I did not discard the concept and I still have the code commented out. I still believe it could work but combined with something else. The main problem is that it needs several iterations for the counters to mean something. At the root, this is not a problem, but close to the leaves the counters are meaningless. I have some ideas to take the best out of this concept and avoid the worst but I had no time to try them. One of the possibilities is to use this when draft is big, and another thing when draft is small. I still have faith in it, but no much to show for now

Miguel

[bob]

Move ordering in early plies is much more critical than move ordering in late plies,

But there are many late plies and few early. So ordering many late plies well might still have value. For early plies, at least the first move should be determined by IID (or by the TT, if there is a match) anyway.

Certainly late plies are important. But try to break your move ordering for early plies and see what happens. This is still an exponential problem.

Comparing Fruit to Stockfish, an important(?) difference is that Stockfish decrements the history score on a bad move while Fruit just increments on good moves. Bob, have you tried something like that?

That idea was something I created, in fact. I mentioned it in a previous post in this thread. The idea is to inc history for the fail-high move, but decrement for all the preceding moves that failed low. I used that for a while, you can probably find code if you have enough older versions of Crafty (the versions that came out maybe 6-months to a year after fruit...)

Another question: Has anybody tried node count on early plies? (I mean, if you do IID, to sort the following moves)? I know this has been discussed at least for the root node (currently I am too lazy to look that up), but one might try it at other nodes too.

I sort the root based on node counts already. Have since the days of Cray Blitz, in fact. I've not tried it deeper in the tree because it requires exponential storage (with respect to depth).

[michiguel]

Move ordering in early plies is much more critical than move ordering in late plies,

But there are many late plies and few early. So ordering many late plies well might still have value. For early plies, at least the first move should be determined by IID (or by the TT, if there is a match) anyway.

Certainly late plies are important. But try to break your move ordering for early plies and see what happens. This is still an exponential problem.

Comparing Fruit to Stockfish, an important(?) difference is that Stockfish decrements the history score on a bad move while Fruit just increments on good moves. Bob, have you tried something like that?

That idea was something I created, in fact. I mentioned it in a previous post in this thread. The idea is to inc history for the fail-high move, but decrement for all the preceding moves that failed low. I used that for a while, you can probably find code if you have enough older versions of Crafty (the versions that came out maybe 6-months to a year after fruit...)

Another question: Has anybody tried node count on early plies? (I mean, if you do IID, to sort the following moves)? I know this has been discussed at least for the root node (currently I am too lazy to look that up), but one might try it at other nodes too.

I sort the root based on node counts already. Have since the days of Cray Blitz, in fact. I've not tried it deeper in the tree because it requires exponential storage (with respect to depth).

You can use a dedicated (small) hash table for it. Not many nodes are part of PVs and their siblings.

Miguel

[Evert]

Interesting stuff. I used killers at plies different from the current ply and am sure many other do, but never tried anything special with the last good move of the opponent. In games like Go this makes perfect sense since refuting the last move of the opponent is a big deal to resolve local
fights.

I picked up the idea from the chess programming wiki. It's not a big deal (after you hit once, the move becomes a killer move anyway) but it seems to help a little. I've also tried storing good combination moves (the same indexing, but applied to your own last move instead of the opponent's) with the idea that you store a (short) combination so you try it again if it caused a cut-off earlier. That doesn't even seem to help in test positions though, so I didn't even try games.
I've also experimented with special killer slots for losing captures that cause a cut-off, but that again doesn't seem to help much.

I was thinking more like to use one table for a 1-6 plies, another for 7-13, another for 14-20 etc...
This should keep the "related" positions in one table.

Yeah, that's what I meant. The problem is that the positions you search for plies 7-13 have (much) less in common than the ones you search for plies 1-6.
I suppose it's possible to just use history for the first 6 plies of search and ignore it for deeper plies, but I suspect it won't really help much even then, since a 6-ply search is done very quickly.

I doubt that any improvement on history will be significant since the conventional chess
move ordering is very good to begin with. But now that LMR is added to the mix, a small improvement
in history could be significant, maybe much more than a PST could ever do.

The question is also how you define a PST for an arbitrary chess variant.
My idea for that was essentially to use mobility instead of a PST as a major component in the evaluation. The idea behind this is that mobility is a more general concept and the PST score is something of a proxy for it anyway.
Jazz actually constructs a PST as part of its evaluation (which is in principle called at every node), but I probably wouldn't recommend doing that in general since it's pretty expensive even if you reuse it as much as possible.

Ultimately, the goal is to sort moves that lead to better positions higher up in the move list. The idea behind using the PST for move ordering is that the delta(evaluation) is just the change in PSQ for quiet moves. That's not true for pawn moves or situations where non-linear evaluation features are important. It should be possible to take that into account, but then scoring a single move may be as expensive as calculating the evaluation function, which would be much too slow. Still, it may be possible to work out a way to detect "obvious" patterns and implement those in a way that is a net gain. Not for a general variant engine though, there you really do want something that is based more on dynamical information than on static pre-computed data.
Thinking as I type here...