On history and piece square tables

[Evert]

I've read a lot of discussion on the use of history tables and if, when and why they do or do not work. My understanding is that if they do work, they tend to resemble the piece-square tables, which makes sense in that the piece-square tables are a "constant" part of the evaluation while the rest is "noise". Putting pieces on generally good squares is most likely to improve your position and generally good squares have high scores in the piece-square tables.

Someone correct me if I'm wrong on any of that (or the following).

In Jazz I've never managed to make history (for move ordering) work. Every time I try it it's a regression. Move ordering in Jazz (without history tables) is the reasonably standard hash move/winning captures/killer moves/losing captures/quiet moves. Quiet moves are sorted according to the change in score from the piece square tables.

Here's the catch: Jazz' piece square tables are not static, they are calculated (and cached) from the pawn structure (and some other material considerations, but as few as possible to maximise the hit rate of the cache). This works fine, but it turns out that it is very slow to query the cache at every node for the purpose of move ordering, so just for move ordering I use the piece square tables from the root position. These become less and less relevant as the search becomes deeper, so move ordering deteriorates at larger depths (a conjecture, not something I've actually measured). So I would like to replace the piece square table for move ordering with something else, either a static table that never changes (and so is always equally relevant/irrelevant), or (preferably) with something dynamic (history). Doing either of those results in a clear elo drop however.

My hope was that the history table would naturally "converge" to some sort of "average" piece square table for the search tree that is more relevant than the value at the root. I wonder why this doesn't work, and the best explanation I've come up with is that this is exactly because there is no constant table hidden in the noise of the evaluation function: all it records is the noise from the variable part of the evaluation, which is useless. Does this make sense?

Perhaps there's something I'm missing with respect to my history implementation, so here's the way I've implemented it (based on looking at some other open-source programs and reading discussions here):

- if a quiet move improves alpha, I increment the history value by depth**2. The indexing scheme for the table is [side][piece][to].
- if a quiet move fails to improve alpha, I decrement the history value by -depth**2.
- if the largest score in the table (which I keep track of) exceeds HISTORY_MAX, all entries in the table are divided by 2 (aging).
- during move ordering, quiet moves are given a score MOVE_HISTORY_BASE + (MOVE_HISTORY_TOP - MOVE_HISTORY_BASE) * (history score) / (max history), so scores are in the range HISTORY_BASE .. HISTORY_TOP. They are then sorted in order of increasing score.

Am I missing something here, or is the conclusion that history just doesn't work for Jazz (possibly because of the lack of static piece square tables)?

[Sven]

- if a quiet move improves alpha, I increment the history value

Have you also tried to restrict this to "if a quiet move becomes the final best move of a node and gets a value better than original alpha"?

- if a quiet move fails to improve alpha, I decrement the history value

That might apply to a lot of quiet moves, maybe even for the second-best move. I would propose to skip this part if you try the other point above.

Sven

[Chan Rasjid]

Hello Evert,

It seems you're going the way of 'complexity'. At times, the best way may be the way of simplicity. And the 'experience' of the top engines should tell us the way to go. There is usually no perfect way to do a thing and, in such cases, simplicity may be best.

Don gave good pointers on how move ordering is done in komodo. He uses history[color][type][to] as you do. Quite moves are ordered by calling SEE and sorted back if they are losing. If you use PST, then you cannot use history - so there is a choice to be made.

It may be enough to just increase the history counter for good moves (beta cutoff). Reducing history may not help very much - a low history count, in itself, indicates 'badness' without the need to add history reduction. It is like what Bob use to say - when a move is extended, it is like a reduction for moves that are not extended, killing two birds with one stone.

I've got hints about simplifying things from this forum. After I actually made the simplification, I come to realize that it is better. An example is not to have a separate quiescent search routine, but just to merge it with a single search routine.

Best Regards,
Rasjid.

[Chan Rasjid]

The idea of dynamic PST tables that are updated with search don't seem correct.

PST is like a basic foundation upon which evaluation is founded. As the basic foundation, it should be static - fixed and not changing dynamically. It is exactly within the evaluation routine that we consider the dynamic of the pieces - scoring patterns due to the placement of pieces on the chess board. So the dynamic aspect should not be mingled with what should be static - the PST tables.

Only an opinion.

Best Regards,
Rasjid.

[Mincho Georgiev]

Why it should be e quiet move in a first place, if move improves alpha it just improves it. Here comes the question of how do you manage the scores. By doing tones of testing on history, on my side I'm convinced, move ordering based on history is just an addition, you can't expect miracle, therefore the scores collected shouldn't mess with any other score term in move ordering you might need to lower them a bit /again - depending on the rest of the scores/. However I've always had a best results when I take into account tree cases:
- If move is above BETA.
- if move is within the window /improves alpha, but it's below BETA/.
- combination of both:

Code: Select all

if(value > ALPHA)
{ if(value >= BETA) improve history type 1 (the one with higher scores)
  else improve history type 2 (the one with lower scores)
}

If move just improves ALPHA as you said is something that never worked
at least for me.
And again - it's all about the scores, I don't even see a big difference whether I'm using a butterfly board or anything else like [S][P][SQ] or whatever it is, it's all about the scores and how they will get managed in move ordering.
Just my 2 cents.

[Mincho Georgiev]

The "quiet move" made me think that you're dividing the history moves from the rest like captures, promotions and so on. But why? Can't you just raise MVV/LVA capture type above another, based on a history result if it's so good, on the other hand if you're using low scores in your tables that might never happen, since captures,proms, etc are scored with much higher scores usually?
And something else, you might need a criteria for clearing them, they can't of course get filled infinitely.

[Evert]

Have you also tried to restrict this to "if a quiet move becomes the final best move of a node and gets a value better than original alpha"?

No, but that only makes a difference at PV nodes, right?

That might apply to a lot of quiet moves, maybe even for the second-best move. I would propose to skip this part if you try the other point above.

I've tried that first (the decrease moves that didn't improve part was something I picked up from discussions here); I can try it again, but when I tested this earlier it wasn't better...

Note that the penalty is applied to moves that are searched. Moves that are never searched (because of a cut-off) are never penalised.

Having said that, there is a difference in implementation between what I do and what an engine like Stockfish does. I penalise moves that don't improve alpha immediately after they're searched, while Stockfish penalises them by going through the move list again after all moves have been searched. This seemed, to me, to be a bit clumsy in that the move list has to be run through twice. It's possible that I missed the point here though, which may be not to penalise quiet moves at all in ALL nodes, where move ordering is meaningless and we can learn nothing from it.

Something to try...

[Evert]

It seems you're going the way of 'complexity'.

In what sense?

Don gave good pointers on how move ordering is done in komodo. He uses history[color][type][to] as you do. Quite moves are ordered by calling SEE and sorted back if they are losing. If you use PST, then you cannot use history - so there is a choice to be made.

That's really not much different from what I do though. As I said, I'd like to get rid of piece square tables in favour of something like history (for move ordering) but it doesn't seem to work...

An example is not to have a separate quiescent search routine, but just to merge it with a single search routine.

Debatable, because it makes the normal search routine (marginally perhaps, but still) more complicated.

Note that Stockfish uses templates to generate multiple specialised search routines from a single general one. That probably is better than doing the same type of thing by hand, but not an option in C (as opposed to C++).

[Evert]

The idea of dynamic PST tables that are updated with search don't seem correct.

Why?

PST is like a basic foundation upon which evaluation is founded. As the basic foundation, it should be static - fixed and not changing dynamically. It is exactly within the evaluation routine that we consider the dynamic of the pieces - scoring patterns due to the placement of pieces on the chess board. So the dynamic aspect should not be mingled with what should be static - the PST tables.

Again, why?

What you need is a way to score piece placement (open files, strong squares, blocked diagonals, trapped pieces, "rook on 7th"). Either you do this every time by looking at the position of the piece and testing for the properties of the piece's current position (is it an open file? Can I attack a weak pawn? Is this diagonal blocked? Is the piece trapped here? Can I attack the base of the enemy pawn structure?) or you do it once by assigning a bonus to all squares on an open file or a penalty to squares on a blocked diagonal and pulling the result from a cache when you need it again. If you do the latter, the evaluation term takes the form of a simple piece square table, except that it isn't static but dynamic and calculated for the position at hand. In which case you might as well get rid of the static piece square table (any contribution can be absorbed in the dynamical one - I actually do that though, so it's perhaps not entirely correct to say that I don't have a static piece square table component at all).

[Evert]

Why it should be e quiet move in a first place, if move improves alpha it just improves it.

For the same reason you don't consider tactical moves for killers: because non-quiet moves get special treatment and are scored towards the top of the movelist anyway (unless they're losing captures). Ultimately it's signal-to-noise that needs to be optimised; in this case I want the best signal for sorting quiet moves, and non-quiet moves just add noise to that (because they may only be good because of the piece they capture, not because they're generally good, for instance NxQa1 is a good move, but Na1 generally is not).

Here comes the question of how do you manage the scores. By doing tones of testing on history, on my side I'm convinced, move ordering based on history is just an addition, you can't expect miracle,

Personally I'd just like it to not be a regression at this point...

However I've always had a best results when I take into account tree cases:
- If move is above BETA.
- if move is within the window /improves alpha, but it's below BETA/.
- combination of both:

That surprises me though: for most of the tree, > alpha implies >= beta. Do PV nodes really have such a strong impact here?