Chess player/Search and evaluation

From Rosetta Code

{{draft task|Search and Evaluation}} This is a sub-task of the Chess player task.

Create a function or software component which will search the tree of moves from a given chess position up to a maximum depth and determine the best move for the computer. Use a previously written Chess player/Move generation component for enumerating the moves. This is where a lot of effort has been spent to improve chess-playing programs, so you can create a basic version or implement some of the features mentioned below to get a faster or cleverer version.

Basic implementation:

  1. min-max search
  2. static evaluation based on material (numbers and types of pieces)

Advanced implementation:

  1. Alpha-beta, nega-scout or MTD-f
  2. improved static evaluation using pawn structure and piece locations
  3. Iterative deepening and move ordering
  4. Quiescence searching extensions
  5. Null move heuristic
  6. Endgame database
  7. (very advanced) Optimizing board evaluation functions via genetic algorithms