Move ordering by PST

[Onno Garms]

1. use a 17 bit index <piece><to><from> which provides more detailed information.

I had been thinking if I should post again that Thomas unintentionally tried indexing by <from+piece><to> and this didn't make the engine any weaker.

Apparently I got distracted by that, so I did not read this yesterday:

2. When a move fails high, update it's history. And also reduce the history counters for any move(s) you tried before that fail high move, since they failed to produce a cutoff.

However, none of those helped at all for me.

[lkaufman]

[quote="bob"

I was talking about "history information". Which can be applied to ordering, reductions, pruning, extensions, etc. Used to work until depths swiftly passed 20 plies and beyond... Then the numbers began to look more like random garbage...

Correct me if I am wrong, but I don't believe that Crafty approaches 20 plies at the depths you typically test at when you run off 40,000 games or so overnight. So how do you know that ideas that work at say ten plies won't work at 20?

As far as i can tell, all the top programs use history ordering, and there is no sign that they lose their lead over the other programs at longer time controls.

[Daniel Shawul]

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.

yes mobility is a major evaluation term in many variants, but becomes costly without bitboards
Mobility or/and piece square tables are good for a general game playing (GGP) program. History heuristic too.
Btw I tried PST only in Nebiyu ,which has only piece square tables for its eval. I was actually very
optimistic since eval() is very cheap. It didn't perfrom as good as history. PST ordering is perfect for a
1 ply search since it puts moves that maximize eval at the front of the list. However,for searchs with larger
depths, it becomes a _greedy_ algorithm which always tries moves that maximize eval one ply ahead first.
It also suffers from simple tactical bindness. Nb1c3 could be a good move most of the time, but not if there
is a black pawn on d4. History catches that easily.

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...

It makes sense. Patterns are such a win in GO even simple handcrafted ones do improve strength a lot.
And the integration with UCT search is very "smooth". Action (move) selection in a position takes into consideration
simulation values (Monte carlo result), online learning (history heuristic), offline learning (patterns)
are all seamlessly integrated with different weighing factors. Same idea could work for chess too but I doubt
patterns would be that important. There is a lot of work done to learn piece values and piece square tables for variants
using TD-leaf. Also for a GGP, you are given the chance to do all three. The game will be described to you in a certain format,
you are then allowed to do offline learning (collecting patterns ,history or selecting other heuristic), then
you can do online learning while playing the game (history heuristic). I like history heuristic more than
PST since it can be used in a GGP and can sometimes yield significant benefits in some games 300 elos!

[bob]

I was talking about "history information". Which can be applied to ordering, reductions, pruning, extensions, etc. Used to work until depths swiftly passed 20 plies and beyond... Then the numbers began to look more like random garbage...

Correct me if I am wrong, but I don't believe that Crafty approaches 20 plies at the depths you typically test at when you run off 40,000 games or so overnight. So how do you know that ideas that work at say ten plies won't work at 20?

As far as i can tell, all the top programs use history ordering, and there is no sign that they lose their lead over the other programs at longer time controls.

Pretty simple. I have tested at longer time controls, up to 60+60 which is about 4 hours a game or so. An "overnight" run is typically 5+5. games last 15 minutes, played up to 750 at a time depending on how many cluster nodes I find free. which is 3,000 games per hour. My more normal testing is one hour for 30,000 games, except when I modify the search itself... Then I try several different time controls to see if there is any sort of trend where deeper = better or deeper = worse.

Here's the point about history ordering. When I decided to test it exhaustively, Crafty already had an effective killer move heuristic. History was designed to replace killers, if you read Schaeffer's paper. I found that removing history ordering was a "wash" for me. It made the tree a bit bigger, but removing history made the search a bit faster, to the point that they were a perfect "wash" in terms of gain/loss. For reductions (the original idea was called "history pruning" in Fruit) it simply didn't work for me (or for fruit when I tested a modified version) at all. With or without history made no difference at all in terms of Elo, with regard to reductions. And it made no difference in move ordering...

[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).

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

Miguel

It would seem to me that you'd need this info for _all_ early moves, not just those in the current PV. You don't want to lose your move ordering when you fail high or low, that is when you need it most...

[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

It would seem to me that you'd need this info for _all_ early moves, not just those in the current PV. You don't want to lose your move ordering when you fail high or low, that is when you need it most...

That is why I use a dedicated hash table, so the info remains there even if I change the pv. Of course, with a hash table you lose info once in a while, but it should be rare enough.

Miguel