Pawn table does not help

[Rebel]

I also store the location of passed pawns in the table because they interact very heavily with the pieces surrounding them.

That's one reason I never got it to work. It's pretty normal to check the square(s) before a passer, so how do you deal with that? You can't just take the score of the table without checking the square(s).

Another example, I measure the pressure on an opponent weak pawn. How can a pawn hash table help?

[Sven]

In my current implementation I did not do table look-ups near the leaves just to make sure it would not become a performance bottleneck.

Why should a hash table lookup that helps to avoid searching again many subtrees, and/or helps to improve move ordering, become a performance bottleneck?

EDIT: here I assume your remark was about TT lookup, since you previously wrote that your current implementation does not include a pawn hash table.

Perhaps it doesn't but I wanted to make sure it certainly does not. Also I was focusing on nodes/second because Skipper was five times slower than fairy-max.

I suggest not to focus on nodes per second. Your engine will never reach any reasonable strength as long as your strategy is to focus on nodes per second.

Here is what I suggest you should focus on, basically in this order (although steps 5 and 6 might be interchangeable, don't worry).

1. Focus on having no bugs.

2. Focus on still having no bugs Especially make sure to start based on a 100% correct board representation, make/unmake, move generator, attack calculation and other very basic routines. ASSERT, Perft and others are your friends ...

3. Start with a very simple and very fast evaluation with just material, a roughly reasonable piece-square table and maybe a simple passed pawn eval. Ideally material and PST eval are calculated incrementally during makeMove() so that the actual evalution function is really minimal in the beginning. Keep this version of eval until you have a really fast and decent search (i.e., after step 7 further down is completed). It is definitely possible to reach ELO 2200 or even much more with a simple eval combined with a strong search. A world-class engine needs a decent evaluation, of course, but ELO 2200 doesn't.
Also use tapered eval to be well prepared for endgame evaluation (especially important for kings).

4. Implement a simple and obviously correct basic alpha-beta search with quiescence search, MVV/LVA-based move ordering, and iterative deepening, where the best move of the previous iteration is always searched first. The initial search code should not take significantly more than about 100 lines of code (depending on the programming language, of course).

5. Add a transposition hash table. Use it for TT pruning first, then for move ordering as well.

6. Add a simple and obviously working implementation of nullmove pruning.

7. Improve the search step by step while still keeping the very simple evaluation. Take care not to introduce new bugs. Watch the branching factor and time-to-depth instead of NPS.
Test really a lot, invest much more time in testing than in changing the code. Search features to be added step by step may include PVS, IID, LMR, killer move, history heuristic, "delta pruning", mate distance pruning, SEE (to skip losing captures in QS), nullmove verification, and many others. Don't add two of them at once, only add the next one after ensuring that the previous one has definitely improved the engine (otherwise leave it out!) and no new bugs were introduced.

8. Now you should have an engine with an effective branching factor lower than, say, 4.0 (should be even less), and with a strength above ELO 2000 at least (should be even more). Now it might be time to do any of the following steps, ideally in this order:

a) Add evaluation features, one at a time. When adding pawn structure evaluation it may make sense to also add a pawn hash table.

b) Tune evaluation parameters.

c) Take care about speed, in terms of nodes per second.

That should be sufficient to make progress.

[bob]

I also store the location of passed pawns in the table because they interact very heavily with the pieces surrounding them.

That's one reason I never got it to work. It's pretty normal to check the square(s) before a passer, so how do you deal with that? You can't just take the score of the table without checking the square(s).

Another example, I measure the pressure on an opponent weak pawn. How can a pawn hash table help?

I do the latter in Crafty. You can detect and flag weak pawns and then store that as an 8 bit mask to identify the file the weak pawn is on. Then you can use that in regular piece evaluation. Ditto for recognizing passed pawns as opposed to actually evaluating them. I evaluate them in a separate place, but I recognize and use the hash to remember which are passed...

[bob]

As a global example of speed of evaluation, Andscacs is maybe 3 MN/s with very simple evaluation in my main computer, and 1,2 MN/s with the current evaluation. But the difference of course is the later is maybe 400 elo stronger.

If an engine is slow and has a minimal evaluation making it significantly slower with a less minimal evaluation does not help. Maybe making it very slow with a moderate evaluation might help but I doubt that too.

If you do pawn hashing right, even if you get zero hits, the speed impact is minimal. I assume you are using the usual Zobrist hashing? I just keep two hash signatures, one with all pieces and pawns, used in the normal transposition table probes, and one with just pawns, used to probe the pawn hash table. One memory access is not going to be much of a deal here. Not doing a pawn evaluation is going to get you killed in chess games.

Skipper does not use Zobrist hashing. So creating and comparing keys is not for free.

I don't see any sense in complaining about the cost of a poorly written bit of code. Zobrist hashing is quite efficient and fast, and solves all of this cost concern instantly...

[Daniel Anulliero]

In my current implementation I did not do table look-ups near the leaves just to make sure it would not become a performance bottleneck.

Why should a hash table lookup that helps to avoid searching again many subtrees, and/or helps to improve move ordering, become a performance bottleneck?

EDIT: here I assume your remark was about TT lookup, since you previously wrote that your current implementation does not include a pawn hash table.

Perhaps it doesn't but I wanted to make sure it certainly does not. Also I was focusing on nodes/second because Skipper was five times slower than fairy-max.

I suggest not to focus on nodes per second. Your engine will never reach any reasonable strength as long as your strategy is to focus on nodes per second.

Here is what I suggest you should focus on, basically in this order (although steps 5 and 6 might be interchangeable, don't worry).

1. Focus on having no bugs.

2. Focus on still having no bugs Especially make sure to start based on a 100% correct board representation, make/unmake, move generator, attack calculation and other very basic routines. ASSERT, Perft and others are your friends ...

3. Start with a very simple and very fast evaluation with just material, a roughly reasonable piece-square table and maybe a simple passed pawn eval. Ideally material and PST eval are calculated incrementally during makeMove() so that the actual evalution function is really minimal in the beginning. Keep this version of eval until you have a really fast and decent search (i.e., after step 7 further down is completed). It is definitely possible to reach ELO 2200 or even much more with a simple eval combined with a strong search. A world-class engine needs a decent evaluation, of course, but ELO 2200 doesn't.
Also use tapered eval to be well prepared for endgame evaluation (especially important for kings).

4. Implement a simple and obviously correct basic alpha-beta search with quiescence search, MVV/LVA-based move ordering, and iterative deepening, where the best move of the previous iteration is always searched first. The initial search code should not take significantly more than about 100 lines of code (depending on the programming language, of course).

5. Add a transposition hash table. Use it for TT pruning first, then for move ordering as well.

6. Add a simple and obviously working implementation of nullmove pruning.

7. Improve the search step by step while still keeping the very simple evaluation. Take care not to introduce new bugs. Watch the branching factor and time-to-depth instead of NPS.
Test really a lot, invest much more time in testing than in changing the code. Search features to be added step by step may include PVS, IID, LMR, killer move, history heuristic, "delta pruning", mate distance pruning, SEE (to skip losing captures in QS), nullmove verification, and many others. Don't add two of them at once, only add the next one after ensuring that the previous one has definitely improved the engine (otherwise leave it out!) and no new bugs were introduced.

8. Now you should have an engine with an effective branching factor lower than, say, 4.0 (should be even less), and with a strength above ELO 2000 at least (should be even more). Now it might be time to do any of the following steps, ideally in this order:

a) Add evaluation features, one at a time. When adding pawn structure evaluation it may make sense to also add a pawn hash table.

b) Tune evaluation parameters.

c) Take care about speed, in terms of nodes per second.

That should be sufficient to make progress.

Very good post Sven thanks !
I'll save it in my Isa's docs files !
But imho to Henk it was à waste of time .It seems this guy never followed chess programmer experts advices.
It seems he focuse only for nps and to beat Fairy max
Then , Skipper never improve
Even Isa crush Skipper in few moves and it is weak ... for the moment
Bests
Dany

[hgm]

I would advice to implement using the TT move in move sorting before implementing TT cutoffs, though. Sorting moves is a tricky thing, and often hard to add as an afterthought. If you already have MVV/LVA sorting (either in advance, or extracting them one by one as next move to search), it is rather trivial to assign the hash move, or the best move from a previous IID iteration the highest search key, so it can participate in this process.

Also, IID is probably more fundamental than having a TT. The TT is basically just a cheap way of getting the result of the previous IID iteration from when you visited the same node before, during the previous root iteration, so that there is no need to do the IID anymore.

[Sven]

I would advice to implement using the TT move in move sorting before implementing TT cutoffs, though. Sorting moves is a tricky thing, and often hard to add as an afterthought. If you already have MVV/LVA sorting (either in advance, or extracting them one by one as next move to search), it is rather trivial to assign the hash move, or the best move from a previous IID iteration the highest search key, so it can participate in this process.

Also, IID is probably more fundamental than having a TT. The TT is basically just a cheap way of getting the result of the previous IID iteration from when you visited the same node before, during the previous root iteration, so that there is no need to do the IID anymore.

Both of your suggestions certainly make sense but they are also a matter of taste. My taste is different than yours in this case, but I think both views are valid.

In my view introducing TT hash table technology itself is one of the bigger steps, and as soon as you have done that, there is not much difference between first using the TT to cut off transpositions or to improve move ordering. Both speed up the search somehow.

IID does that as well, but it is very different from TT by not needing a sophisticated technical infrastructure. Therefore TT belongs to the basic engine stuff for me, nowadays a must-have for everyone, while IID is one of several possible search enhancements which some view as essential and others don't.

[Joost Buijs]

I also store the location of passed pawns in the table because they interact very heavily with the pieces surrounding them.

That's one reason I never got it to work. It's pretty normal to check the square(s) before a passer, so how do you deal with that? You can't just take the score of the table without checking the square(s).

Another example, I measure the pressure on an opponent weak pawn. How can a pawn hash table help?

Well, very simple by storing the location of the weak pawn(s) in the table.
You don't have to recalculate your pawn structure each time in this case.
Since calculating the pawn structure is rather costly it gives you a nice boost.

Calculating the pawn structure is the first thing I do in my evaluation function, after that comes all the interaction with pieces.

[hgm]

Exactly. In the simple demo engine code I started writing the PawnInfo stored in the Pawn hash contains the fields (for each side).

*) Location of most advanced passer
*) Promotion square of that passer
*) Number of turns it needs to promote
*) A bit flag to indicate there are additional passers
*) A bit flag to indicate if the passer is protected
*) A bit flag to indicate if it is a Rook Pawn
*) A byte to flag half-open files
*) The quality of the King shield on both castling locations
*) The difference between the number of Pawns on light and dark squares
*) A score associated with weakness against orthogonal attacks
*) A score associated with weakness against diagonal attacks

I use the passer information in the evaluation by awarding Kings to be in front of the passers, inside the 'square', (distance[promoSqr-xKing] < promoDist) and being actually in the path (which is bad for its supporting King). The promoDist is also useful in Pawn endings to immediately detect unstoppable passers and promotion races you will win.

The shield quality is used to quickly evaluate the value of castling rights, and for positions where the King is conventionally castled; for random King positions it has to calculate the shield quality on the fly.

The last three data items are currently not used yet:

The Pawn-shade difference can be used to evaluate Bishop quality if you only have a single Bishop.

The weakness scores (which currently are not even calculated) can be added to the total score based on presence of opponent pieces that move orthogonally or diagonally. (E.g. a backward Pawn in a half-open file with own Pawns diagonally in front of it on both sides is obviously a much bigger liability if the opponent has Rooks or Queens.)

I guess in the future I will also split the over-all Pawn score into a passer contribution and the rest. The passer contribution can then be scaled depending on whether you have a numerical advantage in piece material. (This proved very helpful in Joker.)

Another item I might add is the number of Pawns on 7th rank, to facilitate accurate calculation of the Rook-on-7th bonus.