Search is the remaining one third of the chess program.
It is also the most difficult part to understand.
Theoretically what search does is that it basically Looks Ahead in the game.
This is what search practically does:
Suppose a position has 'N' legal moves.
Then search makes a legal move, evaluates the position and unmakes the move.
Search will do this for 'N' times (to cover all N legal moves).
Then it will determine and return the best move among all.
The story of two Entities
As discussed before in eval section there are 2 entities:
1. Maximiser
2. Minimiser
These entities are determined by the perspective of eval.
Currently eval returns the advantage of the side to move (Refer eval.c)
/* the score[] array is set, now return the score relative
to the side to move */
if (side == LIGHT)
return score[LIGHT] - score[DARK];
return score[DARK] - score[LIGHT];
But, before we get a clearer understanding, lets code such that eval only returns white's advantage = "score[LIGHT] - score[DARK]" i.e eval's perspective is "white".
This is used to determine who is maximiser and who is minimiser.
If eval always returns score with White's perspective then, white is maximiser and black is minimiser.
So, if we have to define the best move among 'N' legal moves in search.
For white, the best move is the one which has maximum eval value.
For black, the best move is the one which has minimum eval value.
Below are the search loops for both the players.
A search loop would loop for all moves generated for a position (not in code).
int max(move_bytes* best_move)
{
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 = -eval();
takeback();
if(value > score){
score = value;
*best_move = gen_dat[i].m.b;
}
}
return score;
}
int min(move_bytes* best_move)
{
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 = eval();
takeback();
if(value < score){
score = value;
*best_move = gen_dat[i].m.b;
}
}
return score;
}
Notice a few things in the above functions:
1. We have coded such that eval returns with white's perspective ALWAYS.
This is done by multiplying the value returned by eval with '-1' in max function.
2. The makemove function is also a move legality checker. If it returns TRUE, the move is anyways made and if it returns FALSE then we just continue the for loop with the next move.
3. The initial scores are set to +/- INFINITY (a very high number). This is done so that atleast 1 move will be accepted in our search.
4. The evaluate function does not contain checkmate detection or END_OF_GAME_CONDITION. This needs to be implemented in the search function and if such a case arises then this score should over ride the score returned by evaluate.
And then there is the main search function.
2 parameters are desired from search function :
1. Score
2. Best Move
The best_move is fetched by passing a pointer (as of now).
This is because later when we will understand deep searches, it will be seen that the score returned by max or min function will actually play the role of eval function.
Also, best_move will be replaced by a series of principal moves called as principal variation.
void search(){
move_bytes best_move ;
int score;
if (side == LIGHT)
score = max(&best_move);
else
score = min(&best_move);
printf("\n Score is : %d",score);
printf("\n Best Move is : %s",move_str(best_move));
}
Personal note:
In order to understand SEARCH ALGORITHM better, just forget about your Board Representation details and only concentrate on this:
1. All that is needed from board rep implementation are the 4 functions - move generation, move make, move unmake and evaluate.
2. We have to go through search slowly breaking up things before coming to the final algorithm as in TSCP.