All the moves that are generated need to be pushed on a stack so that they can be referred to during move making. This stack is the Move List. It holds all the generated moves.
In TSCP a single move list is used to hold all the generated moves to avoiding the creation of a move list for every position. This saves time in creating a data structure again and again for every position.
The move list is an array of struct data type called gen_t (refer defs.h)
typedef struct {
move m;
int score;
} gen_t;
The variable int score can be ignored as of now. This will be explained later when the concept of "Move Ordering" is explained.
Now refer file data.c
There is an array called gen_dat which is used as the move list.
gen_t gen_dat[GEN_STACK];
The generated moves are pushed on the move list stack using 2 functions (refer board.c):
1. gen_push
2. gen_promote
The function gen_promote is used because every pawn promotion can lead to 4 different legal moves.
Move Tracking in Move List
As mentioned, only 1 move list is being used to store all the moves of all the positions.
The Move List will contain the moves of not only the current position but also of various positions that will result when a move is made later.
Thus, we need 2 levels of tracking for moves in the Move List.
This is done by using 2 variables (refer data.c):
1. ply - to track moves at a position level (All moves with same ply will be of same position)
2. first_move[ ] - to track moves for a given position
1. ply - ply is the depth at which the current position is, after a single player has made the move. Ply increases after each player makes his move. Thus 1 complete chess move (one - one move by each player - black or white) is actually a depth of 2 ply. Ply can increase only when a move is made and ply can decrease only when a move is taken back. Move generation cannot change the variable 'ply'. Only move-make will increment ply and move-unmake will decrement ply.
2. first_move[ ] - This array is used to get the index of the first move at each ply within the Move List.
Refer the function gen() in board.c.
Whenever the gen() function is called, the latest first_move[ply] is stored as is into first_move[ply + 1].
Then refer function gen_push() in board.c.
Whenever a generated move is pushed on the move list, the array counter is incremented.
g = &gen_dat[first_move[ply + 1]++];
The result of the above 2 processes is that the moves for the current position are stored in the Move List with indexes between first_move[ply] is stored as is into first_move[ply + 1].
Now refer its use in search.c
Check the function search()
The loop that traverses through all the generated moves is
for (i = first_move[ply]; i < first_move[ply + 1]; ++i)
Let me take an example to explain.
For the starting position there are 20 legal moves.
The ply of initial position is 0 and first_move[ply] = 0.
This will always be true because of the initialising function (Refer main.c - the function init_board() is called in main which does this )
When we will initiate move generation for the starting position, the move generator will generate all 20 legal moves + some non-legal moves (lets say 2, thus total = 20+2 = 22)
Then initially when gen() function is called,
first_move[ply+1] = first_move[ply].
Therefore first_move[1] = 0.
Then when all the 22 moves are pushed on the Move List, then the value of first_move[1] will be 22.
These 22 moves will be stored in the Move List gen_dat from index 0 to index 21.
Then after white plays a legal move (say e4), black has 20 legal moves.
Again, when we will initiate move generation for the new position (i.e. starting position with 1 e4 played by white and now black to move - the ply of this position = 1), the move generator will generate all 20 legal moves + some non-legal moves (lets say 2, thus total = 20+2 = 22).
Then we call gen() again.
Then first_move[ply+1] = first_move[ply].
Thus, first_move[2] will be equal to 22.
Then when all the 22 moves are pushed on the Move List, then the value of first_move[2] will be 44.
These 22 moves will be stored in the Move List gen_dat from index 22 to index 43.