Idea in move ordering ...

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
De Noose Daniel
Posts: 29
Joined: Tue Dec 13, 2016 9:36 am

Idea in move ordering ...

Post by De Noose Daniel » 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.

User avatar
hgm
Posts: 24517
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Idea in move ordering ...

Post by hgm » Fri Feb 14, 2020 12:20 pm

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.

Dann Corbit
Posts: 11070
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Idea in move ordering ...

Post by Dann Corbit » Fri Feb 14, 2020 3:51 pm

piece square tables can be made by calculation of hot squares
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

D Sceviour
Posts: 510
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Idea in move ordering ...

Post by D Sceviour » Fri Feb 14, 2020 3:54 pm

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]

bob
Posts: 20912
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Idea in move ordering ...

Post by bob » Sat Feb 15, 2020 6:33 pm

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.

De Noose Daniel
Posts: 29
Joined: Tue Dec 13, 2016 9:36 am

Re: Idea in move ordering ...

Post by De Noose Daniel » 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

chrisw
Posts: 3186
Joined: Tue Apr 03, 2012 2:28 pm

Re: Idea in move ordering ...

Post by chrisw » Tue Feb 18, 2020 11:20 am

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.

PK
Posts: 861
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: Idea in move ordering ...

Post by PK » Tue Feb 18, 2020 11:49 am

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.

Post Reply