Author: Bruce Moreland
Date: 14:25:17 04/08/98
Go up one level in this thread
On April 08, 1998 at 16:20:52, Mats Forsén wrote:
If I try to look at this too hard my brain will explode, but I did embed
some suggestions in the code.
bruce
>int AI::negamax( Move * resulting_move, int playercolor, int depth, int
>alpha,
> int beta )
>{
> MoveList moves;
> int result, curmove, cutoff = 0;
> Move next_move;
>
> nodes_visited[ depth ]++;
>
> if( depth == 0 )
> return board->Evaluate(playercolor);
You need a quiescent search. If you just call evaluate when you run out
of depth, you will evaluate positions where tactics are are in the
middle of happening, which is probably a bad idea.
> board->GenerateMoves( playercolor, moves );
>
> if( moves.num == 0 )
> return board->Evaluate(playercolor); // No moves possible
If someone has no legal moves, they are either stalemated or checkmated.
> nodes_generated[ depth ] += moves.num;
Take this line out when this statistic starts to bore you :-)
>// sort_moves( moves );
It is good that you took this line out. Rather than sorting your move
list, you should do a sequential search through it, and grab the best
one, each time you need a new move.
This seems stupid, but it works, because you often cut off.
If you want to be even trickier, just sort the first 8 or so "picks",
and let the rest come in natural order. If you haven't cut off in the
first few moves, your move ordering obviously doesn't understand this
position, so why let it continue to eat CPU time?
> curmove = moves.num;
>
> while( curmove-- && !cutoff )
> {
> board->ApplyMove( moves.m[curmove] );
Here is where you should have done your sequential search, but you
didn't.
>
> if( board->InCheck( playercolor ) )
> {
> board->UndoMove( moves.m[curmove] );
> continue; // No check moves please
> }
This is worrying, because it implies that you had another problem up
above.
Here is the deal. You generate some moves. You have to deal with the
case where you have no *legal* moves, that's either checkmate or
stalemate.
I see no code for this here. Your move generator either has to return
only legal moves, in which case you can do your stalemate/checkmate
checking up above here, or you have to remember that you didn't find a
legal move when you're looping through stuff, so you know whether or not
you need to do checkmate/stalemate determineation at the end.
Since you are checking for illegality here, it seems that your move
generator doesn't do it.
> // Recurse using nega-max variant of alpha-beta
> result = - negamax( &next_move, ( ~(playercolor & COLOR) & COLOR
>),
> depth-1, -beta, -alpha );
The compiler can handle that weird expression, probably, but
"playercolor ^ 1" is easier to read, assuming that "white" is 0 and
"black" is 1. Or make a macro that does this.
> board->UndoMove( moves.m[curmove] );
>
> if( result > alpha )
> {
> alpha = result;
> *resulting_move = moves.m[curmove];
> }
>
> if( alpha > beta )
> {
> cutoff = 1;
> historydata[ moves.m[curmove].where() ] += ( 1 << depth );
Just return beta here, rather than adding complication in order to avoid
having someone accuse you having more than one way out of a function.
If it's readable, maintainable, and efficient, it's hard to argue with,
but if someone tries, just shake a rattle at them and shout, "Out!
Out!". This usually works.
I love "return". I love "break". I love "continue". I even love
"goto", if it behaves.
Case selector lables that are inside blocks, maybe:
switch (a) {
case 1:
if (b) {
case 2:
c();
} else {
case 3:
d();
}
case 4:
e();
}
Hee hee.
> }
>
> }
>
> path.m[ depth ] = *resulting_move;
This thing with how you keep track of your path stuff is frightening. I
couldn't decipher it. Are you sure that it works?
> return result;
>}
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.