We see 3 functions for search - max() , min() and the main search() function.
The main search() function basically checks who is to move and calls max() or min() accordingly (Also, it does some house keeping stuff like printing pv etc)
negamax() is used so that we no longer need to code 2 functions - max() and min().
Everything can be done using a single function negamax() itself.
The advantage of doing this is:
Notice that previously when pv update needed to be added, it has to be added in both functions keeping the similarity between them intact.
This is time consuming and often a source for bugs and adds difficulty in testing because 2 different functions get updated etc.
Also if you don't do it, you might catch a cold.
The basic concept used here is mathematical:
min(a,b) = - max(-a , -b)
Based on this principle, we will change the min() function such that it resembles the max() function with just some cleverly placed '-' signs.
max(a,b) = max(a,b)
min(a,b) = - max(-a,-b)
Then there is no need for separate min(a,b) function as the requirement can be fulfilled by max() function itself and some clever placement of '-' signs.
So, first we take the min function:
int min(int depth)
{
pv_length[ply] = ply;
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;
pv[ply][ply] = gen_dat[i].m;
for ( int j = ply + 1; j < pv_length[ply + 1]; ++j)
pv[ply][j] = pv[ply + 1][j];
pv_length[ply] = pv_length[ply + 1];
}
}
return score;
}
Now, the basic difference between min() and max() is that:
max() checks if (value > score)
min() checks if (value < score)
If I reverse the signs of value and score in my min() function, I get the same result with </> sign reversed.
e.g. if (2 < 3) is same as checking if (-2 > -3)
Therefore, in min() function, I'll put initial score as -INFINITY rather than +INFINITY.
Also, I'll add another '-' sign to the number stored in variable 'value'.
So, rather than having value = max(depth - 1), I'll convert it to value = - max(depth - 1).
Also now score is negative, to make it consistent, I'll again have to add a '-' sign in the last return.
Finally, to make my min() function consistent, I'll have to change it like this:
int min(int depth)
{
pv_length[ply] = ply;
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;
pv[ply][ply] = gen_dat[i].m;
for ( int j = ply + 1; j < pv_length[ply + 1]; ++j)
pv[ply][j] = pv[ply + 1][j];
pv_length[ply] = pv_length[ply + 1];
}
}
return -score;
}
I have highlighted the changes in bold.
The change is mathematically consistent and you will get the same result if you use it now.
But there is 1 more thing to notice in the above code-
Both the return values :- eval() and score have a '-' sign in front of them.
This '-' sign can be added in max() function at just 1 place and be removed from min() function at both the places.
The new min() and max() functions will be:
int min(int depth)
{
pv_length[ply] = ply;
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;
pv[ply][ply] = gen_dat[i].m;
for ( int j = ply + 1; j < pv_length[ply + 1]; ++j)
pv[ply][j] = pv[ply + 1][j];
pv_length[ply] = pv_length[ply + 1];
}
}
return score;
}
int max(int depth)
{
pv_length[ply] = ply;
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;
pv[ply][ply] = gen_dat[i].m;
for ( int j = ply + 1; j < pv_length[ply + 1]; ++j)
pv[ply][j] = pv[ply + 1][j];
pv_length[ply] = pv_length[ply + 1];
}
}
return score;
}
The '-' is removed from eval() and score in min and added in max() in the statement value = -min(depth - 1).
Now, if we check - both functions are exactly same but only with different names.
If max() now, rather than calling min() calls max() itself (or min() rather than calling max() calls min() itself) then same result would be obtained.
So we just keep 1 function called negamax() which is:
int negamax(int depth)
{
pv_length[ply] = ply;
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 = -negamax(depth - 1);
takeback();
if(value > score){
score = value;
pv[ply][ply] = gen_dat[i].m;
for ( int j = ply + 1; j < pv_length[ply + 1]; ++j)
pv[ply][j] = pv[ply + 1][j];
pv_length[ply] = pv_length[ply + 1];
}
}
return score;
}
And the main search() function will be:
void search(){
int score;
int depth = 3;
score = negamax(depth);
printf("\nScore is : %d\n",score);
for (int j = 0; j < pv_length[0]; ++j)
printf(" %s", move_str(pv[0][j].b));
}
It need not look for side_to_move now as both functions are same.
Notice that, mathematically, we can also modify the max function to look like min function and then use negamin.
But we will also will have to change eval function.
Currently eval is checking whose side it is to move and returning the advantage of that side.
Hence, all sides just have to maximise it using NegaMax.
If we use NegaMin, then eval eval should check whose side it is to move and return the disadvantage of that side.
And hence, all sides would try to minimise it using NegaMin.
In the code, I have provided all the 4 sets.
The first is search which uses normal min and max function.
Next is search1 which uses modified min and max functions.
min is modified to min1 and max is modified to max1 - just to call min1. There is no other change in max1.
Then there is search2, which calls to modified min2 and max2 functions which are exactly same but just have different names.
The last is search3 which calls negamax.