General roadmap for learning/development of a chess engine?

[imnoumni]

Hi all,

I'm interested in writing a chess engine. So far, I've got a working move generator, verified by comparing perfts of many positions with Stockfish. This part of chess programming I found analytical, black-and-white (pun). As long as you are able to find all your mistakes in calculating legal moves, you eventually "got it right".

From here, I find many of the concepts in much more of a gray area. Techniques exist in search and evaluation, but there isn't "the one right way", and everyone does it differently. It's hard looking at chess engine implementations, even didactic ones, because techniques are interwoven and if one doesn't understand the technique, reviewing implementations isn't very useful. I'm unsure how to proceed and in what order. Any general guidance would be appreciated.

In general, I've found a basket of techniques that all have to be woven together to get something working:

• negamax
• iterative deepending
• alpha/beta pruning
• zobrist hashing
• transposition trables
• aspiration windows
• principal variation search
• quiescence search
• null move
• static exchange evaluation
• mvv-lva move ordering
• killer moves
• piece/square evaluation
• mobility
• various piece patterns for evaluation, double-bishop, etc.
• so many more ...

How do I wrap my head around this dizzying array of techniques? What should I focus on first to get something working?

Can this list be ordered in a way so that I can iteratively understand/implement the techniques and get an engine that improves with each technique? Do I have anything that is in the above list that shouldn't be in a beginner's list, or isn't in the list that should?

Is there some sort of a road map that can be put together to learn this stuff one-by-one, each building on the last?

[tttony]

Hi,

I had the same question when I decided to base my engine on VICE

As you say "there is no right way" you are free to use or create your own features for your engine

The way I started was to create a very very basic engine, using ony vanilla alphabeta search without any search or eval feature, only a basic PST based eval, this reached ~1500 on CCRL, for now there has no been any bug found... yet

And since then I've been "improving it" slowly but at least improving, every now and then I do some refactor and add features, recently I separated the make_move in two stages, first make the move in the bitboard then check for legality, if legal update the array piece list and the hash key, etc... if not legal then just revert the bitboard, but this method proved to be slow

Now my engine is almost 2000 and I'm happy with it, of course there will be times that adding new features will be a waste of time but that's part of the development

Choose whatever way and test it, every change to your engine need to be tested and the stronger it gets the more games will need to test it

[ZirconiumX]

In general, I've found a basket of techniques that all have to be woven together to get something working:

• negamax
• iterative deepending
• alpha/beta pruning
• zobrist hashing
• transposition trables
• aspiration windows
• principal variation search
• quiescence search
• null move
• static exchange evaluation
• mvv-lva move ordering
• killer moves
• piece/square evaluation
• mobility
• various piece patterns for evaluation, double-bishop, etc.
• so many more ...

How do I wrap my head around this dizzying array of techniques? What should I focus on first to get something working?

Can this list be ordered in a way so that I can iteratively understand/implement the techniques and get an engine that improves with each technique? Do I have anything that is in the above list that shouldn't be in a beginner's list, or isn't in the list that should?

Is there some sort of a road map that can be put together to learn this stuff one-by-one, each building on the last?

That list is ordered in exactly the way you're asking. Every step there builds on the last. So, start at the top and work your way down.

[smatovic]

My suggestion for the beginning would be:

1. negamax
2. alphabeta pruning
3. quiscence search
4. iterative deepening

with very basic evaluation, then you can add step by step advanced techniques, selective search methods and evaluation features.

--
Srdja

[smatovic]

My suggestion for the beginning would be:

1. negamax
2. alphabeta pruning
3. quiscence search
4. iterative deepening

with very basic evaluation, then you can add step by step advanced techniques, selective search methods and evaluation features.

--
Srdja

Too late for an edit:

1. negamax
2. alphabeta pruning
3. quiscence search
4. zobrist hashes
5. transposition table
6. iterative deepening

makes more sense.

Question is to implement minimal working protocol, XBoard or UCI, first or later.

--
Srdja

[chrisw]

My suggestion for the beginning would be:

1. negamax
2. alphabeta pruning
3. quiscence search
4. iterative deepening

with very basic evaluation, then you can add step by step advanced techniques, selective search methods and evaluation features.

--
Srdja

Too late for an edit:

1. negamax
2. alphabeta pruning
3. quiscence search
4. zobrist hashes
5. transposition table
6. iterative deepening

makes more sense.

Question is to implement minimal working protocol, XBoard or UCI, first or later.

--
Srdja

Start with basic UCI plus some test commands. Start your engine in another thread.

[phhnguyen]

IMHO, it looks like you are going to select a hard/long roadmap to go

You may know that in software engineering, implementation and testing should go together at almost every step. It is not a good idea to implement multiple things/steps at once, then come back to test them.

I think you didn’t have any significant trouble when implementing your first move generator because you immediately tested it with the Perft function. You also had a bonus of good feelings for your work done.

Now, your plan looks hard and may take a very long time and labour to complete since you have a long list to learn and implement at once. Understanding and implementing chess algorithms correctly, such as Alpha-Beta search, qsearch, and evaluation function are very hard job for newcomers. Understanding and implementing their enhancements, such as sorting move list, alphabeta pruning, null moves, hash table and so on, are very hard jobs too. If you combine them all, you may have a very long time working hard in a dark tunnel without any light of success. It may be a depressive situation!

I suggest all newcomers should divide their chess programming work into multiple small steps, which they can implement in short periods, then can test them and know clearly and enjoy if a step is successful.

I suggest a few first steps as follows:
1. Select and implement chessboard representation (you completed). Typically, it can test by displaying diagrams, read/export FEN strings
2. Implement move generators. Test via Perft algorithm (you completed)
3. Implement a very basic/simple evaluation function. I suggest it is just a very short function to count materials only
4. Implement a very basic/simple Alpha-Beta search function

After all the above steps, your program can start playing whole chess games (via keyboard and show the chessboard as text diagrams). Of course, it may play very slowly and at low levels but you can test it yourself and enjoy it, and become its first ever rival.

(3) and (4) are actually simple jobs; you may implement them in a few hours to a day. You may look at my program called FirstChess to see how to implement those functions in a very simple way.

5. Add a loop/thread for processing UCI commands.

Once you complete UCI, you can start using chess GUIs (as well as multi tools) as the front end for your chess program, play against it via mouse and the graphics screen. Those chess GUIs typically capture and show/save all logs, interpreting data (such as PVs, scores, depths) in much easier to watch and follow (tabulars, charts…). Moreover, they can manage tournaments for your program vs other chess engines. Watching our babies playing chess is highly enjoyable!

At that moment you have an understanding/overview of a chess program, knowing what is hard, which points you should focus on. All make you plan better and ask for help with better questions.

After all, you can start improving your search and evaluation functions as well as others. Just add/modify by small steps and test ASAP (by letting it play in chess tournaments).

Good luck and enjoy!

[imnoumni]

with very basic evaluation, then you can add step by step advanced techniques, selective search methods and evaluation features.

What are the highest value/lowest effort evaluation techniques to start with?

[smatovic]

I started with "Simplified Evaluation Function" by Tomasz Michniewski:

https://www.chessprogramming.org/Simpli ... n_Function

Meanwhile people use piece square tables, like in PeSTO:

https://www.chessprogramming.org/PeSTO

Side note, it was said that during development search and eval co-depend, they both advance together.

--
Srdja

[abulmo2]

I started with "Simplified Evaluation Function" by Tomasz Michniewski:

https://www.chessprogramming.org/Simpli ... n_Function

Meanwhile people use piece square tables, like in PeSTO:

https://www.chessprogramming.org/PeSTO

Side note, it was said that during development search and eval co-depend, they both advance together.

Something interesting is to tune yourself your own tables. In Dumb, I got a better result than the PeSTO evaluation function and obviously than Michniewski's simplified evaluation function (SEF):

Code: Select all

   # PLAYER              : RATING  ERROR   POINTS  PLAYED    (%)
   1 dumb-2.3            :    0.0   ----   1443.5    2000   72.2%
   2 dumb-2.3-PeSTO      :  -47.4   13.3   1279.5    2000   64.0%
   3 dumb-2.3-SEF        : -346.3   15.2    277.0    2000   13.8%

One reason, is that my search is of course optimized for Dumb's evaluation function, and the evaluation function is tuned against game played by a previous version of Dumb against opponents of similar strength, ie somewhat optimized for its own search. As you wrote, search and evaluation function both advanced together.
Michniewski's evaluation function is obviously much weaker than the other two. It is somewhat a proof than we humans are very bad at guessing the right evaluation weights. PeSTO's weigths and Dumb's weights look pretty random, but are much more accurate. That say, it is a good start to have a working chess engine. I also started with something similar before tuning the weights of the evaluation function.