Move generators

A move generator is responsible for finding the possible move at any step of a game.
By extension, it should maintain an internal representation of the game (for instance, the chess board), play the moves during the game, and allow evaluation functions to access to information about the game state.

A move is an action the player can take (play a card, move a chess piece, etc).

The game ALWAYS ends when a player cannot make any move. This means that doing nothing, should be considered as a move like any other. Typically in Reversi game, when a player can't place any disk, it should pass; Passing is a move!

Sorting moves

Some tree algorithms, like alpha-beta pruning can be greatly optimized by ordering the moves to start evaluation by what seems to be the best moves.

The move generator is responsible for sorting the moves.

Legal, pseudo legal and unsafe moves

This library manages three different kind of moves:

• The legal moves: It is a move guaranteed to be legal. This means it can be played without breaking any of the game rules.
• The pseudo-legal moves: It is a move that seems to be legal. It means the move generator has delayed some validity checks that require an important amount of time. Typically, in chess game, verifying that the move does not leave the king attacked is omitted in pseudo-legal moves. A pseudo-legal move needs extra checks while being played.
  The idea behind the pseudo-legal concept is that, thanks to alpha-beta pruning, there is a good chance that the move will never be played. We therefore have a good chance of saving the time required for an exhaustive validity check.
  Of course, a move generator can decide to perform all validity checks while generating pseudo-legal moves. For instance, if these checks are very fast. In such a case, pseudo-legal moves will all be legal and the move generator will not have to perform any extra checks when playing a pseudo-legal move.
• The unsafe moves: It is a move that has absolutely no warranty of being valid. For instance a move that was typed by a human on a keyboard is unsafe. The move generator should perform a full validity check on these moves.