Speed and Board Storing Choices

[BrettVsop]

Code: Select all

         //Set Starting Variables
   iMoveStrength = NEG_INFINITY * 100;


If MinMax sees a forced mate it will return NEG_INFINITY. I wanted to make sure it chooses the forced mate over not moving. I do not want the engine to resign.

2. then write a function that checks whether the enemy king is in check (and call it e.g. in the very beginning of each node, so that AlphaBeta returns +INFINITY for illegal positions) [EDIT: you probably have it already but use it within FindAllLegalMoves()],

At the moment I have a function that checks to see if the king is on the board. So I catch illegal positions in the alpha beta search a move after they happen.

I have a function already that checks to see if a square (in this case the king's square) is under attack, and that is the way that I check for legal moves at the moment.

3. then write a perft function and fix your perft numbers,

Yeah I am making some guesses right now on where it is not working and setting up positions to test it out. It could not be pawn promotion, in 4 ply pawn promotion is impossible. As is castling. That leaves En Passant. Thats what it has to be, otherwise 3 ply would of been wrong too.

Code: Select all

int CMinMax::GetFutureImbalance(CReferee *chessboard, bool check_white, int iTime)
{
   int iValue = Min(chessboard,check_white,iTime);
   return iValue;
}


What is the meaning of "GetFutureImbalance", and what does your "Min()" function do?

Sven

There are two functions that are missing: Min and Max. Min will return the value of the lowest Evaluation result for the each possible move for the position. Max will return the highest. If time is greater then zero, then min will call max with time minus one.

GetFutureImbalance, is just a entry point into minmax. I wanted a generic function name so I could swap MinMax with AlphaBeta, or any other search algorithm by changing one line in one function. So to swap to AlphaBeta I change the line in GetFutureImbalance to say AlphaBeta instead of Min.

[Teemu Pudas]

3. then write a perft function and fix your perft numbers,

Yeah I am making some guesses right now on where it is not working and setting up positions to test it out. It could not be pawn promotion, in 4 ply pawn promotion is impossible. As is castling. That leaves En Passant. Thats what it has to be, otherwise 3 ply would of been wrong too.

No, En Passant is impossible as well. It has to be pins or check evasions, I think.

[Sven Schüle]

2. then write a function that checks whether the enemy king is in check (and call it e.g. in the very beginning of each node, so that AlphaBeta returns +INFINITY for illegal positions) [EDIT: you probably have it already but use it within FindAllLegalMoves()],

At the moment I have a function that checks to see if the king is on the board. So I catch illegal positions in the alpha beta search a move after they happen.

I have a function already that checks to see if a square (in this case the king's square) is under attack, and that is the way that I check for legal moves at the moment.

If you have a "king capture engine" then I think you don't need the extra legality check, just manage to return NEG_INFINITY when the moving side has no king.
If you want legal move generation instead, you don't need to check if the king is on the board because it will never be captured.
So perhaps you only need one of the two functions, regardless whether MinMax or AlphaBeta is used.
The third way, frequently used, is pseudo-legal move generation, already described many times. There you test whether the enemy king is in check, but you never capture the king, too.

3. then write a perft function and fix your perft numbers,

Yeah I am making some guesses right now on where it is not working and setting up positions to test it out. It could not be pawn promotion, in 4 ply pawn promotion is impossible. As is castling. That leaves En Passant. Thats what it has to be, otherwise 3 ply would of been wrong too.

In theory it can be everything. It's just less probable that one of promotion, castling or en passant causes the problem because these moves are not legal within the first 4 plies. But if there is a bug ...

I agree with Teemu Pudas, you should have a look at your handling of variations like: 1.e4 f6 2.Qh5+, or 1.c4 d6 2.Qa4+. Do you count all the illegal moves which leave the king in check? When terminating the search at depth 4 and not knowing whether the current position is illegal, you seem to have no other choice. But this leads to wrong results, not only for "perft" but also for regular game play.
So again, perhaps think about your way of legality checking.

GetFutureImbalance, is just a entry point into minmax.

So GetFutureImbalance() does the search. Now I don't understand why CAI::GenerateMoveList() gets a move list as output parameter to be filled, why not only a "best move" parameter? The method name suggests it is the move generator, but indeed it searches all legal moves of the current position to depth DEPTH (i.e., it does a DEPTH+1 search), so I expect this to be the search function at root. But then, how do you get the best move from the move list?
Your code is not straightforward for me, it is a challenge

Sven

[Sven Schüle]

I wanted a generic function name so I could swap MinMax with AlphaBeta, or any other search algorithm by changing one line in one function. So to swap to AlphaBeta I change the line in GetFutureImbalance to say AlphaBeta instead of Min.

I'm not quite sure if it is that simple. Are you keeping in mind that using MinMax means also returning +INFINITY when one side wins but -INFINITY for the other side? Perhaps you do this already, then I overlooked it.

Using NegaMax instead of MinMax would be much easier instead.

Sven

[BrettVsop]

If you have a "king capture engine" then I think you don't need the extra legality check, just manage to return NEG_INFINITY when the moving side has no king.

Well returning NEG_INFINITY has a problem of stalemate. Stalemate will look the same as a checkmate. Also when a forced mate is near, this may make illegal moves.

If you want legal move generation instead, you don't need to check if the king is on the board because it will never be captured.
So perhaps you only need one of the two functions, regardless whether MinMax or AlphaBeta is used.
The third way, frequently used, is pseudo-legal move generation, already described many times. There you test whether the enemy king is in check, but you never capture the king, too.

You are right. I wrote both functions so that I can change my mind later on which is better. I am only using legal moves at the moment so I do not call the function that checks for a king.

In theory it can be everything. It's just less probable that one of promotion, castling or en passant causes the problem because these moves are not legal within the first 4 plies. But if there is a bug ...

Your right. En Passant, promotion, and castling are still probably bugged though

I agree with Teemu Pudas, you should have a look at your handling of variations like: 1.e4 f6 2.Qh5+, or 1.c4 d6 2.Qa4+. Do you count all the illegal moves which leave the king in check? When terminating the search at depth 4 and not knowing whether the current position is illegal, you seem to have no other choice. But this leads to wrong results, not only for "perft" but also for regular game play.
So again, perhaps think about your way of legality checking.

At the moment I am only checking Legal Moves, so it should not be that. Of course my legality checker may be bugged. So setting up positions where the king is in check is a good place to start.

So GetFutureImbalance() does the search. Now I don't understand why CAI::GenerateMoveList() gets a move list as output parameter to be filled, why not only a "best move" parameter? The method name suggests it is the move generator, but indeed it searches all legal moves of the current position to depth DEPTH (i.e., it does a DEPTH+1 search), so I expect this to be the search function at root. But then, how do you get the best move from the move list?
Your code is not straightforward for me, it is a challenge

Sven

I get the best move by randomly selecting one from the list. So GenerateMoveList generates a list of all of the best moves. I want to make sure the engine varies its play, so returning a list of equal moves is useful.

[BrettVsop]

I wanted a generic function name so I could swap MinMax with AlphaBeta, or any other search algorithm by changing one line in one function. So to swap to AlphaBeta I change the line in GetFutureImbalance to say AlphaBeta instead of Min.

I'm not quite sure if it is that simple. Are you keeping in mind that using MinMax means also returning +INFINITY when one side wins but -INFINITY for the other side? Perhaps you do this already, then I overlooked it.

Using NegaMax instead of MinMax would be much easier instead.

Sven

Yes it is returning -INFINITY for the other side. I recently changed my engine to use NegaMin. Not NegaMax because we are evaluating positions after we move.

[BrettVsop]

And the winner is: Bad Illegal Move Checker.

I tried to optimize that part and made a mistake. It is now good to depth 4.

So I am now good to one more depth. And the results are
4865351 at depth 5. About 250 short. En Passant and Castling I suspect.

[H.G.Muller]

You know about 'divided perft', that allows you to zoom in quickly on the offending moves, by following the branch with the faulty count?

On my website there is a perft that can divide up the count to any depth.

[Sven Schüle]

Stalemate will look the same as a checkmate.

Code: Select all

if (foundZeroLegalMoves()) return isInCheck() ? CHECKMATE_VALUE : STALEMATE_VALUE;

Sven

[BrettVsop]

I think I got it all worked out. So far I am good to a depth of 5. And I tried the second position off of (http://www.albert.nu/programs/sharper/perft.htm), the one that finds alot of bugs and had both depths correct.