Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Chess - Programming - Introduction ======

To create a strong chess program:

  * Have fast move generators.
  * Use data structures that allow fast makemove and unmakemove algorithms.
  * Search a relatively small number of moves only (using aggressive forward pruning rules, allowing them to search deeper).
  * Have extensive evaluation functions that capture a significant amount of chess knowledge.

----

Goals:

  * The **Evaluation** and **Search** functions are the heart & soul of a chess engine.
  * Improve Evaluation, Search and Move sorting in particular.
  * Consider using **BitBoards**.


Chess programs determine the best move by traversing down a tree of possible moves and opponent moves, up to a certain depth, and then evaluate the resulting positions at the tree tips (leafs, at the end of the search branches) to see which move will lead to the best result, assuming that the opponent will also play the best moves.

The chess search tree is very wide (on average there are 35 legal moves for a chess position), and very deep (the average chess game is 40 moves, or 80 half moves or plies).

  * Not all possible variations can be evaluated (note that 3580 is approximately 10123 ;  by comparison, the estimated number of atoms in the universe is 1080).
  * The search function is implemented as a recursive function (a function that makes a call to itself);
    * at every chess position (node), the move generator returns a list of moves to make (and unmake, when the search traverses back up to the root of the tree to pass the result of the search to the calling function).

The evaluation of chess positions is done by considering many static aspects, starting of course with the material balance, and considering pawn structure, king safety, piece mobility, and many other aspects of the position.  

  * The score is usually expressed in centipawns (a pawn equals 100).  

Speed is important, and there are many techniques to improve the search speed of a chess program (including using bitboards and hash tables).

  * Some chess engines will display their search speed in knods/s (1000 nodes per second).  


Search Algorithm optimization.

  * The main objective here is to minimize the number of moves to search, by skipping moves that are proven to be, or seem to be, 'unattractive'.
  * Techniques to improve and speed up the search include the alpha-beta algorithm, pvs (principal variation search), move ordering, null-move, search extensions, and aspiration windows.  
  * There is of course an intrinsic danger in omitting moves that seem unattractive (at small search depths), because some of them could lead to a decisive advantage as the game progresses (at greater search depths).
  * Alpha-beta, pvs and move ordering increase the search speed without affecting accuracy. 
  * Other techniques can severely deteriorate accuracy, if not implemented correctly, or when using too aggressive pruning parameters. 


Evaluation function

  * By far the best investment you can make to produce a strong program is to improve the evaluation function.
  * Speed is still important in the evaluation function.
  * However, if you can improve the evaluation function, at the cost of adding more code lines and hence making your program somewhat slower, go for it!
  * Same is valid for the search algorithm, adding more code lines will make the code slower, but can make the search faster (by visiting less nodes).