Piece square tables

[Pio]

I have another question or thought in this discussion.
Some people use piece square tables in the evaluation and for move ordering in the search.
May be the piece square tables for evaluation - especially if auto tuned - are not the best tables
to be used for move ordering. What do you think?

Hi Harald, good to see you joining!

Most likely so.
In most tuned PSTs I've researched e4 and d4 usually have miserable bonuses which looks like strange but the moves e4 and d4 are likely
to be played just like if you have +20 bonuses for those squares. The reason for that is that search finds e4 and d4 moves not due to PST
directly but more likely due to PV. For move ordering on the other hand bonuses like +20 for moves e4, d4, Nf3, Nc3 would be beneficial
to order them first but with tuned knight PST values we have a similar story like with e4 and d4.

I tried using PST for move ordering but it didn't give any significant advantage - in some positions it may strip 2k nodes, but in other
it can slow down the search. I know Rebel was using PST for move ordering, but I guess the way it did is more sophisticated than just a lookup.
History heuristic seems more beneficial because moves that has raised alpha within previous iteration are more likely to produce beta cutoffs than
relative PST values. IMO this is so because score > alpha is more likely to become score >= beta (because it's already within the alpha-beta bounds)
it's more likely to produce a cutoff than PST move ordering because PST move ordering does not even guarantee to improve alpha, not even talking
about exceeding beta.

But without tests all this doesn't mean much.

History heuristics should be much better. I don’t know how you have implemented the PST move ordering but if you just take the toSquare into account you will run into trouble. The reason is that good piece square tables for evaluation should be evaluated so that squares close to each other in shortest path metric should have values close to each other. When using the PST in move ordering it will very likely put pieces with great PST values first in the ordering since they will have neighbouring PST values of similar value. The result will be that you try to move the best placed pieces first, when in fact you should do the opposite. What you have to do to fix this problem is that you will have to order the moves according to the difference between the PST for the toSquare and the PST for the fromSqure.

Hope this helps.

Gods luck with your engine!

PS how did it go by minimising the absolute error in your Texel tuning compared to minimising the squared error?

[maksimKorzh]

I have another question or thought in this discussion.
Some people use piece square tables in the evaluation and for move ordering in the search.
May be the piece square tables for evaluation - especially if auto tuned - are not the best tables
to be used for move ordering. What do you think?

Hi Harald, good to see you joining!

Most likely so.
In most tuned PSTs I've researched e4 and d4 usually have miserable bonuses which looks like strange but the moves e4 and d4 are likely
to be played just like if you have +20 bonuses for those squares. The reason for that is that search finds e4 and d4 moves not due to PST
directly but more likely due to PV. For move ordering on the other hand bonuses like +20 for moves e4, d4, Nf3, Nc3 would be beneficial
to order them first but with tuned knight PST values we have a similar story like with e4 and d4.

I tried using PST for move ordering but it didn't give any significant advantage - in some positions it may strip 2k nodes, but in other
it can slow down the search. I know Rebel was using PST for move ordering, but I guess the way it did is more sophisticated than just a lookup.
History heuristic seems more beneficial because moves that has raised alpha within previous iteration are more likely to produce beta cutoffs than
relative PST values. IMO this is so because score > alpha is more likely to become score >= beta (because it's already within the alpha-beta bounds)
it's more likely to produce a cutoff than PST move ordering because PST move ordering does not even guarantee to improve alpha, not even talking
about exceeding beta.

But without tests all this doesn't mean much.

History heuristics should be much better. I don’t know how you have implemented the PST move ordering but if you just take the toSquare into account you will run into trouble. The reason is that good piece square tables for evaluation should be evaluated so that squares close to each other in shortest path metric should have values close to each other. When using the PST in move ordering it will very likely put pieces with great PST values first in the ordering since they will have neighbouring PST values of similar value. The result will be that you try to move the best placed pieces first, when in fact you should do the opposite. What you have to do to fix this problem is that you will have to order the moves according to the difference between the PST for the toSquare and the PST for the fromSqure.

Hope this helps.

Gods luck with your engine!

PS how did it go by minimising the absolute error in your Texel tuning compared to minimising the squared error?

As mentioned - I've dropped using PST for move ordering after unsuccessful attempts (this was in my previous engine)
re: absolute vs square error: didn't try it yet. My implementation is very slow but I've already managed to improve at around 20 Elo
using only 3000 positions from gm2600.pgn. Now I'm generating data self from self play to try it next.

[Pio]

I have another question or thought in this discussion.
Some people use piece square tables in the evaluation and for move ordering in the search.
May be the piece square tables for evaluation - especially if auto tuned - are not the best tables
to be used for move ordering. What do you think?

Hi Harald, good to see you joining!

Most likely so.
In most tuned PSTs I've researched e4 and d4 usually have miserable bonuses which looks like strange but the moves e4 and d4 are likely
to be played just like if you have +20 bonuses for those squares. The reason for that is that search finds e4 and d4 moves not due to PST
directly but more likely due to PV. For move ordering on the other hand bonuses like +20 for moves e4, d4, Nf3, Nc3 would be beneficial
to order them first but with tuned knight PST values we have a similar story like with e4 and d4.

I tried using PST for move ordering but it didn't give any significant advantage - in some positions it may strip 2k nodes, but in other
it can slow down the search. I know Rebel was using PST for move ordering, but I guess the way it did is more sophisticated than just a lookup.
History heuristic seems more beneficial because moves that has raised alpha within previous iteration are more likely to produce beta cutoffs than
relative PST values. IMO this is so because score > alpha is more likely to become score >= beta (because it's already within the alpha-beta bounds)
it's more likely to produce a cutoff than PST move ordering because PST move ordering does not even guarantee to improve alpha, not even talking
about exceeding beta.

But without tests all this doesn't mean much.

History heuristics should be much better. I don’t know how you have implemented the PST move ordering but if you just take the toSquare into account you will run into trouble. The reason is that good piece square tables for evaluation should be evaluated so that squares close to each other in shortest path metric should have values close to each other. When using the PST in move ordering it will very likely put pieces with great PST values first in the ordering since they will have neighbouring PST values of similar value. The result will be that you try to move the best placed pieces first, when in fact you should do the opposite. What you have to do to fix this problem is that you will have to order the moves according to the difference between the PST for the toSquare and the PST for the fromSqure.

Hope this helps.

Gods luck with your engine!

PS how did it go by minimising the absolute error in your Texel tuning compared to minimising the squared error?

As mentioned - I've dropped using PST for move ordering after unsuccessful attempts (this was in my previous engine)
re: absolute vs square error: didn't try it yet. My implementation is very slow but I've already managed to improve at around 20 Elo
using only 3000 positions from gm2600.pgn. Now I'm generating data self from self play to try it next.

Did you try ordering as the difference between toSquare’s and fromSqure’s PST?

[Pio]

Something I haven’t tried but might be very good is giving the piece that moved two plies before a bonus for all its moves or even better you can generalise this giving a bonus for all new moves you got in this position compared to the moves two plies before.

[maksimKorzh]

Something I haven’t tried but might be very good is giving the piece that moved two plies before a bonus for all its moves or even better you can generalise this giving a bonus for all new moves you got in this position compared to the moves two plies before.

No, I tried only toSquare.
Interesting idea. Maybe I'll try it when get done with tuning.

[Pio]

Something I haven’t tried but might be very good is giving the piece that moved two plies before a bonus for all its moves or even better you can generalise this giving a bonus for all new moves you got in this position compared to the moves two plies before.

No, I tried only toSquare.
Interesting idea. Maybe I'll try it when get done with tuning.

If you take toSquare minus fromSquare you will get an improvement.

[hgm]

Using toSquare value only is not consistent. PST values have no meaning; only differences in PST values have meaning. I think that when people say they order by PST, they always mean by the change in PST score.

History should work better. Nevertheless, intrinsically poor moves (such as putting a Knight on an edge) probably should be eyed with suspicion, and although they can occasionally cause beta cutoffs for tactical reasons, such successes are less likely to generalize through the tree. So it doesn't seem unreasonable to somehow weight in the 'delta-PST' for ordering the moves that only have mediocre history scores. So that effectively for the moves that almost never did any good (usually a quite large fraction) are ordered by delta-PST, rather than just tried randomly.

Remember that history is very much a self-fulfilling prophecy. In quiet cut nodes there are usually many cut moves. But the one with the best history score will be tried first, improving its history score further when it works. Moves that are better might never get a chance to catch up, unless in a large part of the tree the situation is more precarious, and you really need the better move. So the quality of the initial ordering of the moves (before significant history information has been collected) will remain frozen-in for a long time. Using historyScore + w*deltaPST as a sort key (with a tunable weight w) would make the initial choice less arbitrary.

[maksimKorzh]

Using toSquare value only is not consistent. PST values have no meaning; only differences in PST values have meaning. I think that when people say they order by PST, they always mean by the change in PST score.

History should work better. Nevertheless, intrinsically poor moves (such as putting a Knight on an edge) probably should be eyed with suspicion, and although they can occasionally cause beta cutoffs for tactical reasons, such successes are less likely to generalize through the tree. So it doesn't seem unreasonable to somehow weight in the 'delta-PST' for ordering the moves that only have mediocre history scores. So that effectively for the moves that almost never did any good (usually a quite large fraction) are ordered by delta-PST, rather than just tried randomly.

Remember that history is very much a self-fulfilling prophecy. In quiet cut nodes there are usually many cut moves. But the one with the best history score will be tried first, improving its history score further when it works. Moves that are better might never get a chance to catch up, unless in a large part of the tree the situation is more precarious, and you really need the better move. So the quality of the initial ordering of the moves (before significant history information has been collected) will remain frozen-in for a long time. Using historyScore + w*deltaPST as a sort key (with a tunable weight w) would make the initial choice less arbitrary.

Could you please explain what is tunable weight w?

[hgm]

Just a number, for which you take the value that results in the strongest play.

[maksimKorzh]

Something I haven’t tried but might be very good is giving the piece that moved two plies before a bonus for all its moves or even better you can generalise this giving a bonus for all new moves you got in this position compared to the moves two plies before.

No, I tried only toSquare.
Interesting idea. Maybe I'll try it when get done with tuning.

If you take toSquare minus fromSquare you will get an improvement.

Hi Pio

Actually I'm getting more nodes traversed instead, here's the code:

Code: Select all

function addMove(moveList, move) {
    let moveScore = 0;
    
    let piece = board[getMoveSource(move)]
    
    if (getMoveCapture(move)) {
      moveScore = mvvLva[board[getMoveSource(move)] * 13 + board[getMoveTarget(move)]];
      moveScore += 10000;
    } else {
      if (killerMoves[searchPly] == move) moveScore = 9000;
      else if (killerMoves[maxPly + searchPly] == move) moveScore = 8000;
      else {
        moveScore = historyMoves[board[getMoveSource(move)] * 128 + getMoveTarget(move)];
        //let delta = (piece < 7) ? 1: 7;
        //moveScore += 3 * (pst[opening][piece - delta][getMoveTarget(move)] - pst[opening][piece - delta][getMoveSource(move)])
      }
    }

    moveList.push({
      move: move,
      score: moveScore
    });
  }

output (no PST ordering)

Code: Select all

info score cp 26 depth 1 nodes 50 time 19 pv g1f3 
wukong.js:1682 info score cp -22 depth 2 nodes 151 time 63 pv g1f3 g8f6 
wukong.js:1682 info score cp 22 depth 3 nodes 775 time 181 pv g1f3 g8f6 b1c3 
wukong.js:1682 info score cp -22 depth 4 nodes 1852 time 413 pv g1f3 g8f6 b1c3 b8c6 
wukong.js:1682 info score cp 14 depth 5 nodes 6097 time 534 pv g1f3 g8f6 b1c3 b8c6 e2e4 
wukong.js:1682 info score cp -22 depth 6 nodes 25513 time 1268 pv g1f3 g8f6 d2d4 b8c6 d4d5 c6b4 
wukong.js:1694 bestmove g1f3

output (PST ordering)

Code: Select all

info score cp 26 depth 1 nodes 40 time 18 pv g1f3 
wukong.js:1682 info score cp -22 depth 2 nodes 120 time 58 pv g1f3 g8f6 
wukong.js:1682 info score cp 22 depth 3 nodes 726 time 189 pv g1f3 g8f6 b1c3 
wukong.js:1682 info score cp -22 depth 4 nodes 1753 time 441 pv g1f3 g8f6 b1c3 b8c6 
wukong.js:1682 info score cp 14 depth 5 nodes 5843 time 604 pv g1f3 g8f6 b1c3 b8c6 e2e4 
wukong.js:1682 info score cp -22 depth 6 nodes 27827 time 1276 pv g1f3 g8f6 d2d4 b8c6 d4d5 c6b4 
wukong.js:1694 bestmove g1f3

Did I do something wrong?

EDIT:
changed (fromSq - toSq) to abs(fromSq - toSq)
now in starting position have only a few more nodes with PST ordering and in position with lots of captures
have a slight improvement:

no PST ordering

Code: Select all

info score cp 36 depth 1 nodes 2960 time 277 pv e2a6 b4c3 
wukong.js:1682 info score cp 36 depth 2 nodes 6033 time 432 pv e2a6 b4c3 
wukong.js:1682 info score cp 22 depth 3 nodes 10262 time 501 pv e2a6 b4c3 d2c3 h3g2 f3g2 e6d5 
wukong.js:1682 info score cp 22 depth 4 nodes 16621 time 615 pv e2a6 b4c3 d2c3 h3g2 f3g2 e6d5 
wukong.js:1682 info score cp 9 depth 5 nodes 34325 time 898 pv e2a6 b4c3 d2c3 e6d5 e4d5 h3g2 f3g2 b6d5 
wukong.js:1682 info score cp 9 depth 6 nodes 78751 time 1299 pv e2a6 b4c3 d2c3 e6d5 e4d5 h3g2 f3g2 b6d5 
wukong.js:1694 bestmove e2a6

PST ordering

Code: Select all

info score cp 36 depth 1 nodes 2957 time 293 pv e2a6 b4c3 
wukong.js:1682 info score cp 36 depth 2 nodes 6137 time 480 pv e2a6 b4c3 
wukong.js:1682 info score cp 22 depth 3 nodes 10418 time 562 pv e2a6 b4c3 d2c3 h3g2 f3g2 e6d5 
wukong.js:1682 info score cp 22 depth 4 nodes 16845 time 682 pv e2a6 b4c3 d2c3 h3g2 f3g2 e6d5 
wukong.js:1682 info score cp 9 depth 5 nodes 34951 time 981 pv e2a6 b4c3 d2c3 e6d5 e4d5 h3g2 f3g2 b6d5 
wukong.js:1682 info score cp 9 depth 6 nodes 78385 time 1427 pv e2a6 b4c3 d2c3 e6d5 e4d5 h3g2 f3g2 b6d5 
wukong.js:1694 bestmove e2a6