What pruning techniques should I add to my engine?

[OliveriQ]

There are some evaluation features that should not be very costly, and would improve the engine a lot. E.g. Pawn structure (in particular recognizing passers, and pushing those at the right moment) should be very helpful, and cheap when implemented through a Pawn hash table. The table could also be helpful in maintaining a healthy Pawn shield in front of the King, and cheaply identifying open files for the Rook evaluation. Recognizing drawishness in the end-game through a material hash table is usually also worthwile; the table can also take care of the Bishop-pair bonus.

Your search already looks pretty advanced. I you don't get above 2200 with that (and assuming it is all correctly implemented) this suggests the evaluation is not good enough. In that case better search might not help much.

Hey, thanks for the feedback and sorry for the late reply. Could you elaborate a bit on the pawn hash table and material hash table? How do they work? And do you know any resources that I could use in order to implement them? Thanks again in advance.

[alvinypeng]

There are some evaluation features that should not be very costly, and would improve the engine a lot. E.g. Pawn structure (in particular recognizing passers, and pushing those at the right moment) should be very helpful, and cheap when implemented through a Pawn hash table. The table could also be helpful in maintaining a healthy Pawn shield in front of the King, and cheaply identifying open files for the Rook evaluation. Recognizing drawishness in the end-game through a material hash table is usually also worthwile; the table can also take care of the Bishop-pair bonus.

Your search already looks pretty advanced. I you don't get above 2200 with that (and assuming it is all correctly implemented) this suggests the evaluation is not good enough. In that case better search might not help much.

Hey, thanks for the feedback and sorry for the late reply. Could you elaborate a bit on the pawn hash table and material hash table? How do they work? And do you know any resources that I could use in order to implement them? Thanks again in advance.

Instead of reevaluating pawn structure every time you call your evaluation function, you can evaluate it once and save that evaluation in a dedicated hash table. Pawn structure isn't very dynamic, so pawn tables have very high hit rates. You index the pawn hash table with a pawn key, which is like the zobrist hash key but only for pawns.

Material hash tables store information regarding piece counts. You could use it to store things like game phase or material imbalance. Lots of chess engines keep an incrementally updated material key, which updates whenever there is a capture or promotion. This key is used to index the material hash table, as well as check for drawn material.

In terms of resources, you could take a look at implementations in other chess engines. Many of them will have a "pawnKey" or "materialKey" member in their board structures.

[hgm]

The idea behind these hash tables is similar to that of the Transposition Table: you map the features for which you want to tabulate something onto a number through Zobrist hashing to get a hash key. For the TT you want the key to be dependent on all pieces and their location, plus a number of other infos (side to move, castling and e.p. rights). So you give every (color, pieceType, square) combination a different random number as base key, and XOR all of those. Since in general only one of the pieces moves, this is easy to update incrementally.

The Pawn key should only identify the Pawn structure, so you only need to have a key for every Pawn (and possibly the e.p. rights). You could calculate it exactly the same as the TT hash key, by setting the base keys for all non-Pawns to 0. For the material key you are only interested in what pieces are on the board, not where these are. So you only need a base key for every (color, pieceType) combination. You would only have to update it for moves that change material, i.e. for the captured piece, and for promotions.

The hashing scheme is always the same: part of the key you use to derive an 'index' to a table, which tells where in the table the information for this position / pawn structure / material combination is stored. In that place you store the remaining part of the key as 'signature', so you can test if the other data that is stored there indeed corresponds to the case you were looking for. If that signature matches your key, you use the information. If it doesn't, you have to calculate the information you were hoping to find from scratch for the current position, and you store it in the table (together with the signature for the current position). And then use it.

The idea is that most of the time (say 95% or 99% of the cases) you would have a matching signature, and can use the information without calculating anything. Then you would only have to do an actual calculation in 5% or 1% of the cases, effectively speeding up the calculation by a factor 20 or 100. Then you don't care too much whether the calculation was time-consuming.

The tables could store all kinds of data in addition to the signature. E.g. for a Pawn table you could have the total score (e.g. white POV) for all passers, doubled Pawns, isolated Pawns etc. You could also store information that helps speeding up other evaluation terms that do not purely depend on Pawns. E.g. you could store the number of Pawns of either color on light and dark squares, to know whether you have a good or a bad Bishop. Or you could list half-open files for white and black (e.g. as a byte where each bit represents a file), to give a bonus for Rooks being on these files. You could store the location and promotion square of the most advanced passer, to quickly calculate in a Pawn ending whether a player has an unstoppable passer. You could calculate the quality of the King-side and Queen-side Pawn shield that a King would have when it had castled in that direction, for use if the King is indeed on the c- or g-file, or determining the value of castling rights if it can still castle.

In the material table you could store score corrections on the PST + material score for combinations of pieces. Such as the Bishop pair. Or factors with which the normal evaluation score should be multiplied for white and black (whichever naively seems to be ahead), to indicate drawishness. (E.g. for KBK you would want to multiply with 0, so that the naive +3 score is annihilated, and for KBPKN you would like a multiplier close to zero, to express that the Pawn will likely be lost through a Knight sacrifice.) Or you could indicate that a special evaluation routine should be called, and which one. (E.g. for KPK, which would determine whether it is a win and a draw depending on the actual K and P locations.)

[abulmo2]

Is this your program: https://github.com/OliveriQ/Horowitz ?
I gave a quick look on this code, and it seems you are returning the "stand pat" evaluation in quiescence search even when you are in check. When in check, it should be better to continue the search to detect some mate or good sacrifice during the quiescence search.

Good luck with your program.