A few questions :)

[oriyonay]

Hi you wonderful people! I've had some time to think and learn some new stuff (after fixing many bugs in my engine), and I have some questions!

1) I had an idea of skipping any move with a negative SEE value in qsearch. According to my tests, this approach is faster but leads to missed mates. Has anyone tried this, and is it worth it?
2) Where exactly should I use SEE in my engine? I already have a working implementation that returns the SEE value relative to the side whose turn it is.
3) How should I go about testing the strength (and elo gains) of my engine? I’m using a mac and currently just running tournaments against other engines on ScidvsMac.
4) Would anyone be willing to have a look at my code and give me feedback? (DM me
5) I’ve been experimenting with different move ordering schemes. which one has worked best for you, and what are the top engines using?
6) Delta pruning: my implementation is slightly different than the CPW implementation. Does this make sense?

Code: Select all

best_case = see(move) + (MOVE_IS_PROMOTION(move) ? 900 : 0);
if (eval + best_case < alpha) return alpha;

7) Should I be focusing more on pruning or on improving evaluation? Out of curiosity, which do you think (on the more advanced level) provides more of an improvement?
8) What kinds of advanced evaluation improvements should I add? I'm currently using tapered evaluation, bishop pair, doubled/isolated/passed pawns, semi/fully open rook files, piece mobility, and king safety.
9) What should be the next steps for the development of my engine? I’d estimate its current playing strength at 2350 elo.

Thank you once again for all of your help!!!
- Ori

[Henk]

Hi you wonderful people! I've had some time to think and learn some new stuff (after fixing many bugs in my engine), and I have some questions!

1) I had an idea of skipping any move with a negative SEE value in qsearch. According to my tests, this approach is faster but leads to missed mates. Has anyone tried this, and is it worth it?

I don't know but maybe It's bad for Elo if it prevents to skip any mates.
Although it looks stupid if it can't find a mate in 3 or 4.

[smatovic]

Hi Ori.

3) How should I go about testing the strength (and elo gains) of my engine? I’m using a mac and currently just running tournaments against other engines on ScidvsMac.

My engines are in the 2000 CCRL Elo range and I still prefer STS 1-15 with CCRL Elo estimation for testing changes:

http://talkchess.com/forum3/viewtopic.php?t=56653

STS 1-15 as LAN.epd:
https://github.com/smatovic/ZetaDva/blo ... 15_LAN.EPD

IIRC it was said before that you need to run ~10K games in self-play to test ~10 Elo differences.

7) Should I be focusing more on pruning or on improving evaluation? Out of curiosity, which do you think (on the more advanced level) provides more of an improvement?

There is the concept of search/evaluation imbalance, if you improve only your search and not eval it won't work out.

9) What should be the next steps for the development of my engine? I’d estimate its current playing strength at 2350 elo.

I myself work on speed (nps), the branching-factor via selective AB search heurisitcs, evaluation, and parallel search for example.

--
Srdja

[JimmyRustles]

I don't see how changing your qsearch can cause your engine to miss mates since qsearch isn't involved in mate finding.

I prune all nodes with SEE < 0 in qsearch.

I also reduce moves by one ply in my main alphabeta search if they have SEE < 0.

[MartinBryant]

I now prune -ve SEE moves in the QS in the latest version of Colossus and it was a small ELO gain when tested.
(Also FWIW I think that Stockfish does the same.)

I don't however prune them if they also give check... which I think is the only way it would affect finding occasional mates in the QS... are you testing for that?

[j.t.]

Code: Select all

best_case = see(move) + (MOVE_IS_PROMOTION(move) ? 900 : 0);
if (eval + best_case < alpha) return alpha;

SEE should already include promotions.

Test your engine with cutechess-cli.
The command that I always use is:

Code: Select all

cutechess-cli \
-recover \
-concurrency 60 \
-ratinginterval 100 \
-games 2 -rounds 2500 \ 
-openings file=./Blitz_Testing_4moves.pgn order=random -repeat 2 \
-each tc=20+0.5 option.Hash=64 proto=uci dir=./ \
-engine cmd=./NewEngine\
-engine cmd=./OldEngine

You will probably need to adjust some things. I don't remember where I got the opening book. Probably from here.

From my experience the following methods are enough to get to 2700 CCRL:
Evaluation:

• - king square contextual piece square tables
  - isolated pawns
  - pawn with two neighbors
  - passed pawns
  - mobility
  - sliding pieces attacking area around king
  - rook on open file
  - both bishops
  - knight attacking bishop, rook, or queen
  - tapered parameters
  - optimized using gradient descent

search:

• - principle variation search
  - quiescence search
  - transposition table
  - move ordering: hash move first, tactical moves sorted using SEE, killer moves, relative history heuristic
  - nullmove reduction
  - late move reductions
  - check extensions
  - delta pruning
  - fail-high delta pruning
  - futility reductions
  - hash result futility pruning

You can also look at the READMEs of many other engines to see what they have implemented.

The thing about eval vs search is, that for example late move pruning with history heuristic depends on a good evaluation function to work best. Though it is entirely possible to get to 2800 CCRL with only PSQTs (IIRC someone built an engine that focused only on search and they got to 2800).

[Chan Rasjid]

I don't see how changing your qsearch can cause your engine to miss mates since qsearch isn't involved in mate finding.

I prune all nodes with SEE < 0 in qsearch.

I also reduce moves by one ply in my main alphabeta search if they have SEE < 0.

I think bad to reduce any moves based on SEE unless you have really tested it. You should already have dismissed qs moves with delta pruning.

SEE is only tentative as it is restricted to captures at one squares; no rigorous reason to prune it. My weak test seems to suggest best not to prune.

SEE should only be used for sorting moves to the back; even applied for internal nodes non-capture moves.

[niel5946]

1) I had an idea of skipping any move with a negative SEE value in qsearch. According to my tests, this approach is faster but leads to missed mates. Has anyone tried this, and is it worth it?

Do you recognize checkmates in qsearch? The reason I'm asking is that usually, this shouldn't happen. The only reason quiescence search is used is to limit the horizon effect. An example of the horizon effect could be that if captures aren't resolved, engines will tend to just delay big material losses such that they happen later. If they can extend this postponing of material loss so far down the tree, that they can't see it due to depth-limitations, the loss "doesn't happen".
I don't resolve checkmates in quiescence since I believe it should be left for the main search function. I would suggest testing for elo instead of mate-finding capability.

2) Where exactly should I use SEE in my engine? I already have a working implementation that returns the SEE value relative to the side whose turn it is.

I use SEE in three places:

1. Pruning bad captures in quiescence search. I got around 56 elo points from this IIRC.
2. Move ordering for captures (mix of SEE and MVV/LVA).
3. Depth reductions for bad captures in main search.

3) How should I go about testing the strength (and elo gains) of my engine? I’m using a mac and currently just running tournaments against other engines on ScidvsMac.

I would strongly advice you to run SPRT tournaments whenever you add a feature (then play a match between the version without the feature and the one with the feature). The good thing about SPRT is that it stops the test automatically, whenever there is enough statistical significance in the results.
OpenBench, written by Andrew Grant, is a great framework for testing your engine during development. It has support for multiple clients (machines) testing the same engine and you can also stop/restart your tests whenever you want to.

4) Would anyone be willing to have a look at my code and give me feedback? (DM me

Just share your Github repo in this thread and I can take a look at it.

5) I’ve been experimenting with different move ordering schemes. which one has worked best for you, and what are the top engines using?

The most simple, and probably the most rewarding is the following (ordered by best to worst moves):

• Best move from the transposition table.
• MVV/LVA for captures. Promotions should be scored as highly as captures.
• Killer moves.
• History heuristic

The last two only being applied to quiet moves.
SEE is also good for move ordering (better at predicting captures's values than static MVV/LVA), but comes at a speed cost; therefore, I use a mix of the two.
The top engines use a lot of other, less important methods, so I wouldn't relly worry about that until your engine is above 2900 elo.

6) Delta pruning: my implementation is slightly different than the CPW implementation. Does this make sense?

Code: Select all

best_case = see(move) + (MOVE_IS_PROMOTION(move) ? 900 : 0);
if (eval + best_case < alpha) return alpha;

You shouldn't return from the function unless you have a beta cutoff. You should do this instead:

Code: Select all

best_case = see(move) + (MOVE_IS_PROMOTION(move) ? 900 : 0);
if (eval + best_case <= alpha) continue; /* Note less than or equal instead of less than */

This is better since you don't skip all the remaining, potentially good moves when you encounter a bad one early.

7) Should I be focusing more on pruning or on improving evaluation? Out of curiosity, which do you think (on the more advanced level) provides more of an improvement?

This is a hard question, and I'm not sure if it even has an answer. As others have said, they are very dependent on each other. If you have a bad evaluation, late move reductions should be limited since you would otherwise risk not seeing very good/bad moves (this is also true for insufficient move ordering). The point is that if you have a really good, well-tuned search, it wont really matter if your evaluation function is sloppy and can't guide the former to good positions, but it will still be way better than plain alpha-beta.

8) What kinds of advanced evaluation improvements should I add? I'm currently using tapered evaluation, bishop pair, doubled/isolated/passed pawns, semi/fully open rook files, piece mobility, and king safety.

If your engine's rating is still just 2350 (if you're not running long tournaments when testing, you can't be certain on this by the way. 1000 games should be played at least), I would advice you to remove all evaluation terms, including tapering, except material and piece-square tables. Then, starting with tapered evaluation, re-add all of them one by one, thoroughly testing each term. This will take some time, but it will be worth it. I'm suggesting you do this since I would expect the rating of your engine to be significantly higher with said features.
After having made sure that none of the terms lose elo, you can implement texel tuning (see texel's tuning method on CPW).

Actually, I would suggest you do this to your search as well if you have more than null move pruning and simple move ordering. Material, PSQT, NMP and said simple move ordering can oftentimes get an engine into the 2200-range.

9) What should be the next steps for the development of my engine? I’d estimate its current playing strength at 2350 elo.

Even though it might be slow testing a lot (and feeling like you're back at the starting line), I really think you should do what I suggested in point 8. Also, the SPRT testing method in part 3 is nearly a must for efficient engine development.

[niel5946]

I think bad to reduce any moves based on SEE unless you have really tested it. You should already have dismissed qs moves with delta pruning.

I don't agree with this at all. There is a difference between delta pruning and SEE pruning in quiescence search:

• Delta pruning also has the potential to prune good moves. A move gets pruned if it is likely that it won't raise alpha (eval + score(move) <= alpha).
• SEE pruning only prune moves that loose material.

SEE is only tentative as it is restricted to captures at one squares; no rigorous reason to prune it. My weak test seems to suggest best not to prune.

SEE gives a very good indication about the material outcome of a move. Therefore, since quiescence search is only about resolving captures, it doesn't make sense to begin searching a bad one. Additionally, a move with negative SEE in main search is very likely to be bad, therefore LMR can be increased for SEE < 0.
I got around 56 elo from pruning moves with SEE < 0 in quiescence search and around 20 from increasing LMR with the same condition.

SEE should only be used for sorting moves to the back; even applied for internal nodes non-capture moves.

SEE would be way too slow to compute for captures as well as quiets. It should only be used for captures, and even then one should be conservative with using it.

[Chan Rasjid]

SEE gives a very good indication about the material outcome of a move. Therefore, since quiescence search is only about resolving captures, it doesn't make sense to begin searching a bad one. Additionally, a move with negative SEE in main search is very likely to be bad, therefore LMR can be increased for SEE < 0.
I got around 56 elo from pruning moves with SEE < 0 in quiescence search and around 20 from increasing LMR with the same condition.

I have never properly tested pruning losing SEE. Computer chess is ultimately about testing. So I accept your testing.