Proper Engine writing ,and guidlines ?

[Fabio Gobbato]

Killer and history usually works with a good evaluation function, with a very simple one could not improve the engine.

The same thing is for PVS: Alphabeta is better if you have a simple evaluation because the engine change PV very often, with a better eval PVS perform better than Alphabeta.

[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 .

For your last question, if you ONLY consider efficiency, DTS is likely the best there is or will be. But if you include complexity, it is also the most complex algorithm around which is a disadvantage. I designed and wrote DTS. I do NOT use it in Crafty at the moment. Very first requirement is recursive negamax can't be used. Which immediately complicates the code by a significant amount...

[tttony]

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 .

Null move pruning and LMR MUST have a huge elo gain, like 100/150

I think that all depends on how you test your engine and of course you MUST use ASSERT on everything in debug mode

I think (in my opinion) that SMP implementation should be when the engine reach like 2600/2700 on CCRL

And don't only test vs the previous engine but test with opponents with 100- and 100+ ELO using various time controls like Erik does with MadChess here --> http://www.madchess.net/page/Downloads

[jdart]

The same thing is for PVS: Alphabeta is better if you have a simple evaluation because the engine change PV very often, with a better eval PVS perform better than Alphabeta.

I don't think this is so. PVS (with a zero-width window for the non-PV moves) is practically required for good performance, and practically all non-trivial engines use it. It does assume you have a reasonable move ordering but even if you just have a hash table (+ maybe IID) you can achieve that.

[Fabio Gobbato]

In the early stage of development of my engine I have tried many times PVS and I achieved bad results than with alphabeta. The engine had only pst and material value.
Only when I added some more knowledge in the eval the PVS started to perform better than alphabeta.

The same thing happen to me for the killer and the history. They started to work only when the evaluation function has become more accurate.

[hgm]

PVS also was a disaster in micro-Max.

[emadsen]

Any other guidelines are appreciated.

I recommend you write a method that automatically tests move counts against known positions. Like this:



After any move generation code change, call the method to ensure you didn't break anything.

I recommend you implement one feature at a time. I mean one. Not a search feature, and new evaluation terms, and a performance optimization, and a few parameter tweaks. JUST ONE.

Then use cutechess CLI to run a gauntlet tournament against 10 -16 comparable strength opponents (no more than +/- 200 ELO). Run at least 1500 games to get the error margin low. Use BayesElo or Ordo to calculate the ELO of your modified engine. Compare against the unmodified engine. If the ELO gain is greater than the error margin, keep the code change. If not, keep working.

Once you get a stable alpha / beta search working, I recommend you write a method (or use a GUI) to find the best move against known positions. Like this:



After any search or evaluation code change, call the method to ensure the number of solved positions doesn't decrease drastically. This can save you time you otherwise would be wasting waiting for a gauntlet tournament to complete. Fix the problem, verify your engine solves the same number of positions (give or take a few), then run a gauntlet tournament to test the engine's strength.

You can read through code examples on my blog at http://www.madchess.net/category/Code

I started with a working alpha / beta negamax + PVS search engine I had written from scratch (which probably is ahead of where you're at now). Then I added one feature at a time. I documented the code I added and the results of my test gauntlet for 20 code changes from 1489 ELO to 2307 ELO. This will give you an idea of how much ELO to expect from each change.

Though you have to understand the ELO gained from each feature is not absolute or linear in nature. Features interact with each other. Implemented in a different order, features would yield different ELO gains.

Don't let your ambition outpace your coding abilities. I detect you're not being honest with yourself, saying...

So far every thing was going great with the engine strength rising all the time , until I started implementing the following...

... AFTER you'd listed numerous failed attempts to implement standard chess engine features.

Should I write the engine taking parallelism into account from the begging?

An emphatic no. Focus on confirming the correctness of each standard engine feature before you tackle complex algorithms like parallel search or even bitboards in my opinion.

You have to ask yourself what are your goals? If you expect to write a 2600 ELO original engine in your first attempt, you're being way too ambitious.

Anyhow, welcome to the chess programming community. Good luck with your engine!

[Robert Pope]

You can read through code examples on my blog at http://www.madchess.net/category/Code

I started with a working alpha / beta negamax + PVS search engine I had written from scratch (which probably is ahead of where you're at now). Then I added one feature at a time. I documented the code I added and the results of my test gauntlet for 20 code changes from 1489 ELO to 2307 ELO. This will give you an idea of how much ELO to expect from each change.

Though you have to understand the ELO gained from each feature is not absolute or linear in nature. Features interact with each other. Implemented in a different order, features would yield different ELO gains.

Thanks for the detailed post, Erik, especially the link to the version by version gains you made. I don't think I've seen anyone actually lay out the development progress so clearly like that.