I wonder how did you understand things so fast.mjlef wrote:I have spent a little time look at the Strelka source. Very clearly written, so I did not really need the Russian comments to figure out what it is doing. My impressions:
Very, Very Fruit-like. Some of the things identical to Fruit:
Same Trans table
Identical NULL move pruning (R=3, eval>beta, needs a piece, etc.). Same verification search if depth>5. It does correct for side to move bonus, which Fruit does not, since Fruit 2./1 did not have a side to move bonus.
Dual evals (opening and endgame) and interpolated the same way (Fruit uses 256 steps, but given there are only 24 "pawns" of pieces available, this is really the same as Strelka's system)
Same mobility ideas for pieces, although the increments are different. Some seem almost backward from Fruit (for example, having a bigger increment in the opening than the endgame).
Same basic terms for Rook on semi-open file, open file, 7th, and king files, but different values.
Same method of King Safety (but different attack values for the pieces)
Same PVS search
Some difference:
Strelka uses a big array for correcting material values (initial values are along the ratio of P=1, N=B=3, R=5 and Q=10). Strelka uses P=3399, but divides this by 32 at the end of the eval, so really P=106, and so on. Note this table is indexed for pieces and pawns of both sides (but only for up to 1 queen, 2 rooks, 2 bishops, 3 knights and 8 pawns). It has a lot of endgame knowledge (like a draw for KBK--it does this by simply filling in a negative value for if -value[bishop] for example, to pull the score towards 0). My program has used the same idea since the early 1990s, except it only kicked in close to the endgame, due to memory limits (try making a program run in only 640k DOS!). The same array has a bit field for flags to indicate special eval terms (like this is a bishop and pawn endgame). Note Vasik a few years ago posted some code to talkchess showing just this idea (but of course, the magic is in what numbers to put in there).
More extensive passed pawn eval (the regular pawn eval is the same as Fruit, but with different values). The passed pawn eval include things like a bonus for the squares in front of a pawn being cleared.
Uses a lookup table for king safety pawn shielding (indexed by the same side and opponent pawns). This is very fast. It is stored in the pawn hash table. It stores a value for K on 1-c files, e-d files, and f-h files.
Only does check extensions in non-PV nodes. In PV nodes it has check, one reply to check and P to the 7th extensions (using Fruits same criteria of a non negative SEE value). I have tried the same idea in the past, but found s few of the other extensions were useful to also use in non-PV nodes.
See uses a few tricks to terminate early (like if a NxP is being considered, but the pawn is protected by another pawn).
Side to move bonus, but it is very small.
I have no idea if Strelka is close to the original Rybka. It does things in very efficient, clever ways. I did not see any real "tricks" or "secrets", but one idea was new to me. I have not tried writing a bitboard program, so maybe this is common:
In the qsearch, it uses a twist on futility pruning. It starts with a bitboard set for all pieces and pawns. If the eval is significantly under the value of a pawn, it turns off the pawn bits. If under a minor piece worth, it turns them off, etc. Then it uses the new bitmap to indicate opponent pieces and only generates capture big enough to likely find a score high enough to be useful. Perhaps all bitmap programmers already know this.
It also uses one other form of futility I have used for a while. At depth<=3 in non-PV nodes, if the eval is low enough, it tries a qsearch to see if a move can be found. If not, it uses the max(eval-margin,search value) and exits the search. Note it sets the depth of the qsearch to be positive, and the qsearch includes all captures (and not just winning/equal captures) while depth>0. It also includes checks. So this means a regular search is replaced with a capture+checks only search as a way of verifying. Perhaps it should include passed pawn moves as well, but anyway in a lot of tactical positions, this can save a lot of nodes, at some risk of missing quiet moves.
I have read a lot of claims by people who have seen the code (and others who state things with little information!). My conclusion: mostly Fruit, with better values, the tweaks above, and a mystery how the values were determined. I see nothing inaccurate on what the apparent author has stated, or what Vas has stated. People have suggest Vas might have used lots of games to determine things like improved material imbalance scoring, piece value changes based on remaining material, etc. Looking at the numbers in the arrays, that seems to be the case in Strelka too. It would be interesting to zero out this array and see how much strength gain this idea is worth. When I added something similar to my program based on data from lots of gains, it was worth maybe 40 ELO, but I already have a lot of rules to adjust piece values based on remaining material, likely draw conditions etc.
My summary: no magic, just good, solid, bug free and fast code, without a lot of complexity. And a real genius behind the values for that material correction array.
Mark
Can you share us what exactly did you do to understand the code?
I am probably not good in understanding code of other people and I looked only in part of the code in order to understand(I have motivation to understand strelka because it is clearly less files and less code than fruit).
Did you print the code in paper and read it when you skip parts that you do not understand?
Did you compile the code with some changes to check things?
If you read only parts of the code than which parts of the code did you read?
Uri
