General roadmap for learning/development of a chess engine?

[abulmo2]

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

3.5 Move ordering using MVV-LVA
7. PVS/negascout in place of alphabeta
8. nullmove pruning
9. late move reduction
10. Mover oredering with killer moves, history, SEE, etc.
11. other pruning / reduction / extension.

Before 2. I will also add a simple evaluation function to evaluate the leaves.

It is also important to avoid bugs as much as possible.

[rdhoffmann]

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

Agreed, from my experience, the above techniques are extremely robust and always seem to work (also for chess variants). Quite a few chess programming techniques are rather error-prone to implement and depend on precise conditions that are hard to figure out on your own, as a hobbyist. Also some may not gain any ELO points in your particular engine.

Regarding the transposition table, the implemenation here is also somewhat error-prone from my experience, I would use it only for move ordering initially and later extend it to other purposes.

[smatovic]

[...]

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%

[...]

Nice comparison.

--
Srdja

[smatovic]

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

3.5 Move ordering using MVV-LVA
[....]

Agree, makes sense.

--
Srdja

[smatovic]

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

Agreed, from my experience, the above techniques are extremely robust and always seem to work (also for chess variants). Quite a few chess programming techniques are rather error-prone to implement and depend on precise conditions that are hard to figure out on your own, as a hobbyist. Also some may not gain any ELO points in your particular engine.

Regarding the transposition table, the implemenation here is also somewhat error-prone from my experience, I would use it only for move ordering initially and later extend it to other purposes.

Yes, there are mathematically sound and unsound methods, as soon as you add selective search heuristics you leave safe water and it depends then on your implementation with certain parameters.

--
Srdja

[smatovic]

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

Indeed, w/o UCI first you will probably have to rewrite the engine's root structure/main function later.

--
Srdja

[rdhoffmann]

Here's a post from many years ago, it helped me tremendously to get started:

https://stackoverflow.com/questions/165 ... ing-factor

Quote:

Here's an overview of techniques that I found to be most effective. Note that some components are complements and others are substitutes, so the results I give are general guidelines. The great gains at the end of the list are not possible if you don't have a strong foundation.

Just negamax with alpha-beta pruning: depth 4 within 3 seconds.

Add iterative deepening and null move heuristic: depth 5. Iterative deepening does not really help at this point, but it is easy to implement. The null move consists of skipping your turn and seeing if you can still get a beta cutoff with a shallow search. If you can, then it's probably safe to prune the tree since it's almost always advantageous to move.

Killer heuristic: depth 6. This involves storing moves that cause beta cutoffs and trying them first if they are legal next time you are at the same depth. You seem to be doing something similar already.

MVV/LVA ordering: depth 8. Basically, you want to put captures that have lots of potential material net gain at the top of the move list. So if a pawn captures a queen, you should obviously search it first.

Bitboard representation: depth 10. This doesn't improve branching factor, but this is what I did when I reached this point. Ditch the arrays, use UInt64s instead, and use make/unmake instead of copy-make. You don't need to use magic bitboards if you find it difficult; there are simpler methods that are still very fast. Bitboards greatly improve performance and make it easy to write evaluation components. I went from perft(6) taking minutes to taking 3 seconds. (By the way, writing a perft function is a great way to ensure move generation correctness)

Transposition table: depth 13. This offers great gains but is also very difficult to get right. Be absolutely certain that your position hashing is correct before implementing the table. Most of the benefit comes from the amazing move ordering the table gives you. Always store the best move into the table and whenever you get a matching position, try it first.

Late move reductions: depth 16. This greatly inflates your search depth but the strength gain is more artificial than with other techniques. Basically your move ordering is so good now that you only need to fully search the first few moves in a node, and you can just check the others with shallow searches.

Futility pruning: depth 17. Leaf nodes are trimmed by skipping moves that have a low chance of improving the value of the node when looking at potential material gain. If the the net potential gain of the move + static evaluation of the position is below the current value of the position, skip the evaluation for the move.

[abulmo2]

I did some experiment in Dumb to see how much Elo each heuristic gives to my engine. It may help to rank which algorithm to prioritize in a chess engine. In the search module, I removed one feature at a time and run a robin tournament between all programs. I got:

Code: Select all

# PLAYER                           : RATING  ERROR   POINTS  PLAYED    (%)
   1 dumb-2.3                        :    0.0   ----   1264.0    2000   63.2%
   2 dumb-2.3-no-futility            :  -11.3   14.2   1232.0    2000   61.6%
   3 dumb-2.3-alphabeta              :  -27.4   16.1   1186.0    2000   59.3%
   4 dumb-2.3-no-probcut             :  -29.3   11.9   1180.5    2000   59.0%
   5 dumb-2.3-no-late-move-pruning   :  -38.0   14.8   1155.5    2000   57.8%
   6 dumb-2.3-no-razoring            :  -39.4   13.3   1151.5    2000   57.6%
   7 dumb-2.3-no-aspiration          : -101.2   12.4    970.0    2000   48.5%
   8 dumb-2.3-no-nullmove            : -115.8   13.3    927.0    2000   46.4%
   9 dumb-2.3-no-quiescence-search   : -145.3   12.0    841.5    2000   42.1%
  10 dumb-2.3-no-late-move-reduction : -229.3   15.1    611.0    2000   30.6%
  11 dumb-2.3-no-hash-table          : -282.6   13.4    481.0    2000   24.1%

I did the same for move ordering and got:

Code: Select all

  # PLAYER                     : RATING  ERROR   POINTS  PLAYED    (%)
   1 dumb-2.3                  :    0.0   ----   1184.5    1800   65.8%
   2 dumb-2.3-no-hashmove      :  -12.2   15.1   1156.5    1800   64.2%
   3 dumb-2.3-no-refutation    :  -15.3   18.5   1149.5    1800   63.9%
   4 dumb-2.3-no-killer        :  -22.2   14.1   1133.5    1800   63.0%
   5 dumb-2.3-no-see           :  -39.2   16.3   1094.0    1800   60.8%
   6 dumb-2.3-no-push7         :  -73.6   19.4   1014.0    1800   56.3%
   7 dumb-2.3-no-history       :  -94.1   18.9    966.5    1800   53.7%
   8 dumb-2.3-no-mvv-lva       : -495.4   24.1    312.0    1800   17.3%

So, it is quite obvious that the hashtable, the move ordering with mvv-lva, the quiescence search, the nullmove heuristics and using aspiration windows should be high in the todo list of a new program made from scratch. Although late move reduction adds a bunch of Elo, I will add it later because it depends on the quality of move ordering and need history, killer, etc.

[rdhoffmann]

Cool, thank you for posting this, I always wondered about the ELO effects of particular features.

About the hash move, I start with that first (since it is easiest to code), it makes a huge difference for me. If it is only a few points for you, I suppose either your move ordering is incredibly good, or you use some other way to calculate the PV than I do (i.e. not the hash).

[abulmo2]

Cool, thank you for posting this, I always wondered about the ELO effects of particular features.

About the hash move, I start with that first (since it is easiest to code), it makes a huge difference for me. If it is only a few points for you, I suppose either your move ordering is incredibly good, or you use some other way to calculate the PV than I do (i.e. not the hash).

I did my computation by removing one feature at a time. So when I remove the hash move from move ordering, all the other features (mvv_lva, killers, history, bad captures, etc.) are still there. If you do it the other way, by adding one feature at a time, the importance of each feature may change, because of the correlations they share.
In Dumb, I indeed compute the PV from the search tree, not from the hash table. Basically, on a PV node, I do:

Code: Select all

PV[ply] = best_move + PV[ply + 1]; 

When computing the PV from the hash table, if you have collisions in your hash table, you may get a wrong PV. Or if you lose an entry in your hash table, you may get a truncated PV. On the other hand, you can extract a PV at almost no cost. Note that in my Othello engine Edax, I do extract the PV from the hash table without getting neither wrong PVs (collision are not possible in this hash table implementation) nor truncated PVs (the missing part is recomputed).