Page 1 of 1

Idea in move ordering ...

Posted: Fri Feb 14, 2020 11:44 am
by De Noose Daniel
Hello dear chess programmers,

Sorry if my english is too bad. I'll try to be understandable.

Sorry too if my idea is already welknown (as good or as bad).
I'm not aware of anything in chess programming. I'm a very bad newbie.

Is this kind of move ordering could be interesting :

Making a piece probability table, from a square to another, based on millions best engines games :

i.e.: for a white knight in g6 there is 6 moves (with invented probs) : h8 (8%), f8 (6%), e7 (14%), e5 (32%), f4 (24%), h4 (16%)
so the move ordering for this knight will give : e5, f4, h4, e7, h8, f8.

So the table for each piece will be 64 squares * max possible move numbers for that piece.

Thanks in advance for your ideas.

Re: Idea in move ordering ...

Posted: Fri Feb 14, 2020 12:20 pm
by hgm
Problem with methods derived from games is that positions in search trees usually look nothing like positions in games. Most of them would look completely insane to the human eye. This is a consequence of the fact that what goes on in the tree is basically a game between a random mover and a turn-passer. So it would be kind of a miracle if statistics from games would look anything like it should be in the search tree.

Re: Idea in move ordering ...

Posted: Fri Feb 14, 2020 3:51 pm
by Dann Corbit
piece square tables can be made by calculation of hot squares

Re: Idea in move ordering ...

Posted: Fri Feb 14, 2020 3:54 pm
by D Sceviour
The idea is called a piece-square table, often seen as PST() or PSQT(). Programmers prefer to use weights rather than percentages, because weights can easily be configured for final position evaluations. Percentages could be calculated from most piece-square tables by taking the maximum weight as 100%.

Calculating the weights is problematic. The most sophisticated method is called Stochastic Gradient Tuning. A generalized method for calculating weights from games was proposed by Peter Osterlund (the Texel author) and has been called "Texel's Tuning". The results are not good enough for move ordering because each position is unique.

Thus, a method developed most recently is to calculate the piece-square tables for every unique position as part of the search process, and to use the results for move ordering. The result has been called the counter-move method. Weights are not attached to the position, but to the previous move:

counter_move_weight[previous piece][previous square][piece][square]

Re: Idea in move ordering ...

Posted: Sat Feb 15, 2020 6:33 pm
by bob
De Noose Daniel wrote:
Fri Feb 14, 2020 11:44 am
Hello dear chess programmers,

Sorry if my english is too bad. I'll try to be understandable.

Sorry too if my idea is already welknown (as good or as bad).
I'm not aware of anything in chess programming. I'm a very bad newbie.

Is this kind of move ordering could be interesting :

Making a piece probability table, from a square to another, based on millions best engines games :

i.e.: for a white knight in g6 there is 6 moves (with invented probs) : h8 (8%), f8 (6%), e7 (14%), e5 (32%), f4 (24%), h4 (16%)
so the move ordering for this knight will give : e5, f4, h4, e7, h8, f8.

So the table for each piece will be 64 squares * max possible move numbers for that piece.

Thanks in advance for your ideas.
There are variants of this already around. The original history heuristic "learned" these probabilities as the game progressed, incrementing a counter when a move failed high. I added the idea of decrementing such counters when the moves tried using this approach did not produce a cutoff, but a later move did. It was viewed as sort of a "global killer move idea".

Averaging over the entire game (millions of games) could be extremely problematic. IE Kg2 would be very good in most endgames, very bad in most middle games. Some things are almost always bad (knight in the corner for example) and those get covered by the piece/square tables usually.

Re: Idea in move ordering ...

Posted: Tue Feb 18, 2020 8:33 am
by De Noose Daniel
Thanks to all for your informed advices.

I know the PST but I thought it was a little bit different in that case.

I 'll forget this idea ... ;-)

Searching new ones ... lol

Re: Idea in move ordering ...

Posted: Tue Feb 18, 2020 11:20 am
by chrisw
De Noose Daniel wrote:
Tue Feb 18, 2020 8:33 am
Thanks to all for your informed advices.

I know the PST but I thought it was a little bit different in that case.

I 'll forget this idea ... ;-)

Searching new ones ... lol
Your idea is fine and basically a different use of PST. If you did no other move ordering and used PST deltas to sort the pseudo legal move list, you would probably get a more efficient search over random.
Given current staged moved ordering, including various history/statistical stages, the actual sorting of the remaining moves becomes less important (other than LMR complication), and there already are methods for late move sorting. You could try, either, including a PST delta term to the late sorts scoring, or using a PST delta for those late moves where there is no sort score available for. I have a suspicion I tried this once, a long time ago and got no traction from it. Is quite likely other programmers tinkering around looking for improvements have also tried the idea, as it’s the kind of idea most will independently think up.

Re: Idea in move ordering ...

Posted: Tue Feb 18, 2020 11:49 am
by PK
Another possible idea is initializing history table (which contains all zeroes at the beginning) with scores from piece/square tables. It worked for me in one engine, failed in the other.