The practicality of search lies in depth.
Chess players calculate moves like White would think in the starting position - if I play e4, black plays e5 and then I play Nf3.
This is called depth and this is what a computer is actually required to do for us.
A chess engine would be useless if it cannot search deep.
We have to understand how search and depth are connected.
Everytime a move is made, depth increases.
Everytime a move is unmade, depth decreases.
Search at a depth greater than or equal to '1' produces a search tree.
Also at alternate depths there are alternate intentions as each player would play only the best move for himself.
If there is maximiser at depth = 1, then there is minimiser at depth = 2 and then again maximiser at depth = 3 etc.
Depth First Search (DFS):
This is the most common algorithm used in chess engines.
It is used to search at depth greater than 1.
The basic concept of DFS is that the son is checked before the sibling.
What this means is that lets suppose in the starting position there are only 2 moves possible - e4 and d4. And after that black has only 2 moves possible - e5 and d5.
And suppose if we call search with depth = 2.
Then DFS will first pick e4. Then it will not pick d4 by white.
Rather it will pick e5 and d5 by black first.
Evaluate the position based on e4.
Only then it will pick the 2nd move d4.
And again go deep and pick e5 and d5 by Black.
The code for DFS is as follows (not in code):
int max(int depth)
{
if(depth == 0)
return eval();
int score = -100000;
int i , value;
gen();
for (i = first_move[ply]; i < first_move[ply + 1]; ++i) {
if (!makemove(gen_dat[i].m.b))
continue;
value = min (depth - 1);
takeback();
if(value > score){
score = value;
}
}
return score;
}
int min(int depth)
{
if(depth == 0)
return -eval();
int score = 100000;
int i , value;
gen();
for (i = first_move[ply]; i < first_move[ply + 1]; ++i) {
if (!makemove(gen_dat[i].m.b))
continue;
value = max (depth - 1);
takeback();
if(value < score){
score = value;
}
}
return score;
}
And the main search function would be:
void search(){
int score;
int depth = 3;
if (side == LIGHT)
score = max(depth);
else
score = min(depth);
printf("\n Score is : %d",score);
}
Notice a few things in the code:
1. The call to the son is made inside the sibling loop.
Hence, sibling loop is not completed till required depth is reached.
We can see that max calls min inside the for loop.
The for loop would not be completed till the call to min is returned.
2. The call is recursive with depth variable decremented by 1 at every call.
This is well known programming technique. We call functions recursively and the loop counter is passed with change.
The loop breaking condition is depth == 0.
And if that is TRUE, then further search and move generating functions are not called. Straightaway eval function is returned.
3. Previously the minus sign for eval was attached in the max function. Now it is attached in the min function. This is just a mathematical concept (as we want eval to return value with White's perspective always). Think like this - when it is black to move and we call search with depth = 0, then min(0) will be called. Eval will check that it is black to move and return black's advantage. It has to be multiplied by -1 to give white's advantage. If this is true for depth = 0, it is also true for any depth.
4. There is no best move concept now. Because when we are searching deep with depth > 1 then we would be needing a series of best moves.
This is called as principal variation (it is explained further as to how to collect the principal variation)
5. The information about the goodness of a move goes from bottom to up. Depth at 0 is reached and the position is evaluated. The value of position at depth = 1 depends upon the values returned by eval for depth = 0. Same goes above. The deeper we go the correctness of eval gets strengthened.