Proper Engine writing ,and guidlines ?

[MahmoudUthman]

I wrote my first engine in C++ implementing several techniques in the following order :
1-Legal move generation (extensively checked for errors, I'm sure it is completely correct ).
2-basic search (Alpha beta with quiescence ) and evaluation(material & piece agnostic mobility).
3-killers & history.
*-PV search before implementing history -ELO ,reverted back to normal AB
*-Check extension (no gain & possibly -ELO ,removed).
4-TT (with legality checking of TTMove).
so far every thing was going great with the engine strength rising all the time , until I started implementing the following:
6-Enhance evaluation with (PSTs, per piece mobility weights, "isolated ,passed , double" pawn ,open/semi files for rooks ),some resulted in +ELO , others -ELO or +-0
5-Null-Move pruning (no ELO gain & possibly no lose)
7-LMR(-ELO)

--------------------------------------
*is there a specific/ recommended for the implementation of these techniques (and any other technique I didn't implement yet)?
*should I write the engine taking parallelism into account from the begging or should I write a serial one first implementing all the desired techniques and parallelize it's search later ? and what Parallel Search algorithm should I use ?
*I remember reading about this somewhere in this forum in the past but I cannot find it anymore : is DTS still the best search algorithm ?
*any other guidelines are appreciated .

[matthewlai]

I wrote my first engine in C++ implementing several techniques in the following order :
1-Legal move generation (extensively checked for errors, I'm sure it is completely correct ).
2-basic search (Alpha beta with quiescence ) and evaluation(material & piece agnostic mobility).
3-killers & history.
*-PV search before implementing history -ELO ,reverted back to normal AB
*-Check extension (no gain & possibly -ELO ,removed).
4-TT (with legality checking of TTMove).
so far every thing was going great with the engine strength rising all the time , until I started implementing the following:
6-Enhance evaluation with (PSTs, per piece mobility weights, "isolated ,passed , double" pawn ,open/semi files for rooks ),some resulted in +ELO , others -ELO or +-0
5-Null-Move pruning (no ELO gain & possibly no lose)
7-LMR(-ELO)

--------------------------------------
*is there a specific/ recommended for the implementation of these techniques (and any other technique I didn't implement yet)?
*should I write the engine taking parallelism into account from the begging or should I write a serial one first implementing all the desired techniques and parallelize it's search later ? and what Parallel Search algorithm should I use ?
*I remember reading about this somewhere in this forum in the past but I cannot find it anymore : is DTS still the best search algorithm ?
*any other guidelines are appreciated .

A bit strange that you get no gain from check extension. It's a huge gain for most basic engines implementing depth-limited search.

[bob]

I wrote my first engine in C++ implementing several techniques in the following order :
1-Legal move generation (extensively checked for errors, I'm sure it is completely correct ).
2-basic search (Alpha beta with quiescence ) and evaluation(material & piece agnostic mobility).
3-killers & history.
*-PV search before implementing history -ELO ,reverted back to normal AB
*-Check extension (no gain & possibly -ELO ,removed).
4-TT (with legality checking of TTMove).
so far every thing was going great with the engine strength rising all the time , until I started implementing the following:
6-Enhance evaluation with (PSTs, per piece mobility weights, "isolated ,passed , double" pawn ,open/semi files for rooks ),some resulted in +ELO , others -ELO or +-0
5-Null-Move pruning (no ELO gain & possibly no lose)
7-LMR(-ELO)

--------------------------------------
*is there a specific/ recommended for the implementation of these techniques (and any other technique I didn't implement yet)?
*should I write the engine taking parallelism into account from the begging or should I write a serial one first implementing all the desired techniques and parallelize it's search later ? and what Parallel Search algorithm should I use ?
*I remember reading about this somewhere in this forum in the past but I cannot find it anymore : is DTS still the best search algorithm ?
*any other guidelines are appreciated .

A bit strange that you get no gain from check extension. It's a huge gain for most basic engines implementing depth-limited search.

It is not a "huge gain" in Crafty. It is a measurable gain, but that is about all. Probably due to LMR where you LMR many moves, but not safe checks, which is similar to extending those...

[jdart]

A bit strange that you get no gain from check extension.

Even stranger is no gain from null move. IMO if this is not helping you, you have probably implemented it in some faulty way.

--Jon

[cdani]

A bit strange that you get no gain from check extension.

Even stranger is no gain from null move. IMO if this is not helping you, you have probably implemented it in some faulty way.

--Jon

Was probably more than 100 elo worth for my reworking of Andscacs. Of course I used a very optimized formula of Andscacs, but you should win something notorious probably with a basic one.

[Sven]

I wrote my first engine in C++ implementing several techniques in the following order :
1-Legal move generation (extensively checked for errors, I'm sure it is completely correct ).
2-basic search (Alpha beta with quiescence ) and evaluation(material & piece agnostic mobility).
3-killers & history.
*-PV search before implementing history -ELO ,reverted back to normal AB
*-Check extension (no gain & possibly -ELO ,removed).
4-TT (with legality checking of TTMove).
so far every thing was going great with the engine strength rising all the time , until I started implementing the following:
6-Enhance evaluation with (PSTs, per piece mobility weights, "isolated ,passed , double" pawn ,open/semi files for rooks ),some resulted in +ELO , others -ELO or +-0
5-Null-Move pruning (no ELO gain & possibly no lose)
7-LMR(-ELO)

--------------------------------------
*is there a specific/ recommended for the implementation of these techniques (and any other technique I didn't implement yet)?
*should I write the engine taking parallelism into account from the begging or should I write a serial one first implementing all the desired techniques and parallelize it's search later ? and what Parallel Search algorithm should I use ?
*I remember reading about this somewhere in this forum in the past but I cannot find it anymore : is DTS still the best search algorithm ?
*any other guidelines are appreciated .

The main reason for this type of observation is a bug (often more than one). Considering your results at no. 3, 5, 6 and 7 I am really very sure that there are unsolved problems in no. 2 (basic AB search and basic evaluation). My reason is that it is very unlikely that these are correctly implemented but for some magic reason all of the stages 3, 5, 6 and 7 fail to improve your engine significantly.

Therefore my proposal is as follows:

- Go back to stage 2 by deactivating all other features from higher stages listed above. (Not removing, just deactivating.) Even TT should be deactivated here.

- Now deactivate "piece agnostic mobility" evaluation as well. Your engine now has basic AB search with QS and material-only evaluation. It should be pretty fast due to lack of any time-consuming parts in evaluation. Its playing strength will be far below the average club player, though, no need to explain why.

- Run your standard test to measure the playing strength and obtain an "initial rating" (I assume you have such a standard test, otherwise any further steps are nothing but guesswork).

- Now only add PST evaluation. Be careful to choose conservative scores that are "obviously ok" but not too large.

- Measure playing strength again with exactly the same standard test. PST should improve the engine considerably at this stage. If this is not the case, or if the improvement is only marginal, then either your scores can be improved, or there is some bug in the basic search (or the main evaluation function itself).

- Go on the same way after finding and fixing the defects of earlier stages. But maybe keep your fingers off the evaluation for a while (including mobility), and only improve the search step by step. The reason is that you can almost be 100% sure to get an improvement if you implement a search feature correctly, but you can really fail miserably when adding an evaluation feature and choose some parameters that will toss everything around and let your engine play horrible chess. Bad scoring can even have a really negative impact on tree size and overall performance. A reasonable order of adding search features could be PVS, TT, killers, history, check extension, null-move pruning and finally LMR but this is certainly a matter of taste, as well as possibly adding some other search features (there are a lot). Of course I assume that your basic AB search has standard move ordering, iterative deepening, some kind of time control and also basic stuff like repetition detection.

- If you find that adding a standard search feature, like null-move pruning, does not improve your engine, then do not "give up", instead find out the reason (in most cases some nasty bug). Do not continue until you know why it failed, otherwise you will very likely build upon wrong assumptions and invalidate some of your further test results. It is still possible that you find a problem in an earlier stage that prevents later stages from delivering the expected improvement.

- Just do not add more than one feature at a time. Reason: If you don't get the expected improvement then you don't know which of the two is the bad one, and so you have to go back. If, on the other hand, you get a somehow satisfying improvement (maybe a bit less than expected but you say "o.k. for me") then it may still be coming from only one feature while the other does not help you, but this will go without noticing so you continue with a sleeping bug in your engine.

- If you passed all of this with the expected result then you have a strong search with a very fast, dumb and minimalistic evaluation. Now you can start to improve the evaluation. Again, step by step and with a lot of testing. A basic rule of thumb is that it takes only few minutes to ruin your program and lose hundreds of ELO points with one careless change, but it can take weeks or months to actually obtain a considerable improvement.

Regarding your question about parallel search: yes, I would spend some thoughts at least about data structures and their suitability for parallel search. E.g. think about "static" variables which would often break thread safety so you'd better think about whether you really need them to be "static".

But testing the early stages as mentioned above is done best with a sequential search due to its reproducability. You'll also get a bunch of additional complexity when doing the parallel stuff, and at that point you will actually see (not just "think") whether your data structures and your basic infrastructure matches the requirements of parallel search. So I'd better not spend *too much* time in designing something specific for parallel search if you do not actually test it yet.

Regarding what's the "best" parallel search algorithm, just ask three of our experts here and expect four different answers at least

[matthewlai]

I wrote my first engine in C++ implementing several techniques in the following order :
1-Legal move generation (extensively checked for errors, I'm sure it is completely correct ).
2-basic search (Alpha beta with quiescence ) and evaluation(material & piece agnostic mobility).
3-killers & history.
*-PV search before implementing history -ELO ,reverted back to normal AB
*-Check extension (no gain & possibly -ELO ,removed).
4-TT (with legality checking of TTMove).
so far every thing was going great with the engine strength rising all the time , until I started implementing the following:
6-Enhance evaluation with (PSTs, per piece mobility weights, "isolated ,passed , double" pawn ,open/semi files for rooks ),some resulted in +ELO , others -ELO or +-0
5-Null-Move pruning (no ELO gain & possibly no lose)
7-LMR(-ELO)

--------------------------------------
*is there a specific/ recommended for the implementation of these techniques (and any other technique I didn't implement yet)?
*should I write the engine taking parallelism into account from the begging or should I write a serial one first implementing all the desired techniques and parallelize it's search later ? and what Parallel Search algorithm should I use ?
*I remember reading about this somewhere in this forum in the past but I cannot find it anymore : is DTS still the best search algorithm ?
*any other guidelines are appreciated .

A bit strange that you get no gain from check extension. It's a huge gain for most basic engines implementing depth-limited search.

It is not a "huge gain" in Crafty. It is a measurable gain, but that is about all. Probably due to LMR where you LMR many moves, but not safe checks, which is similar to extending those...

Yeah that's what I meant by "basic engines". Usually people implement check extension before LMR (as is the case here).

[hgm]

A bit strange that you get no gain from check extension. It's a huge gain for most basic engines implementing depth-limited search.

Micro-Max did not gain anything from check extension untill I switched it off in the end-game.

[hgm]

I am not sure what 'piece-agnostic mobility' means, but it sounds like something bad. Beware that when there really is something grossly wrong in the evaluation, (like wrong piece values), better search can actually hurt you, because it makes the engine smarter and smarter in spotting and achieving wrong goals (which the opponent will be all too glad to help achieving them). E.g. when you set the Queen value to 7, the engine will seek trading Q for R+B, (and then lose because of it), but the opportunity to do so will not occur all that often. If you then improve the search the engine will be able to see more opportunities to do it, and lose more games after Q-RB trading because of its better search.

[Dann Corbit]

I wrote my first engine in C++ implementing several techniques in the following order :
1-Legal move generation (extensively checked for errors, I'm sure it is completely correct ).
2-basic search (Alpha beta with quiescence ) and evaluation(material & piece agnostic mobility).
3-killers & history.
*-PV search before implementing history -ELO ,reverted back to normal AB
*-Check extension (no gain & possibly -ELO ,removed).
4-TT (with legality checking of TTMove).
so far every thing was going great with the engine strength rising all the time , until I started implementing the following:
6-Enhance evaluation with (PSTs, per piece mobility weights, "isolated ,passed , double" pawn ,open/semi files for rooks ),some resulted in +ELO , others -ELO or +-0
5-Null-Move pruning (no ELO gain & possibly no lose)
7-LMR(-ELO)

--------------------------------------
*is there a specific/ recommended for the implementation of these techniques (and any other technique I didn't implement yet)?

Look at well written implementations like those found in Fruit. Pay considerable attention to Fabain's use of assert() to demonstrate correctness.

*should I write the engine taking parallelism into account from the begging or should I write a serial one first implementing all the desired techniques and parallelize it's search later ?

In general, use of public symbols like globals and statics should be reduced to the bare minimum possible. This is not just for chess programming but for all programming. Even at that, if you have lots of globals and statics you can use processes instead of threads and then the only things shared (typically hash tables) are those things that you programatically share. This can be done in a very good way. See Gull on Sourceforge for an example.

and what Parallel Search algorithm should I use ?

They all perform about the same, and Lazy SMP is by far the easiest. But it would be instructive to try to write an implementation of each type.

*I remember reading about this somewhere in this forum in the past but I cannot find it anymore : is DTS still the best search algorithm ?
*any other guidelines are appreciated .

As to which parallel algorithm is best, the jury is out. I guess that it comes down to this:
The parallel algorithm written by the best programmer will look better than the other methods. But that won't mean that it really is better.