Moderators: hgm, Rebel, chrisw
Then there are two major performance problems. Progressive Deepening with searching the PV first and assuming you haveaberent wrote:I am not using Principle Variation or Iterative Deepening, Just vanilla Alpha Beta.
Code: Select all
Search()
{
if (depth <= 0)
return(Qsearch());
test for 3 fold rep
test for transposition table hit and return
null move test and possible return
moves = generate_moves()
for ( each move)
{
make move
value = -Search(depth -1)
if (value > alpha)
{
alpha = value;
if (value >= beta)
return(beta);
Store PV
}
}
Store best move in transposition tables
return(alpha)
}
Qsearch()
{
// stand Pat score
v = PositionEvaluation();
if (v>alpha)
alpha = v;
if (alpha>=beta)
return(beta);
Generate Captures
for ( each capturing move)
{
make move
v = -Qsearch()
if (v>alpha)
alpha =v;
if (v>beta)
return(beta);
}
return(alpha);
}
Did I reverse the operator <>?nevatre wrote:Adam, this doesn't look correct
"if (alpha > examineBoard.Score)
alpha = examineBoard.Score; "
Harald wrote:I don't know C# and your ode looks like some ideas shuffled and written down
but I will make some notes. May be I don't see your main problems. However.I am sure I found only some obvious problems. When I guessed wrongaberent wrote:In case someone has the time, here is my AlphaBeta. This is the second version that makes one move at a time, maybe you guys can see a bug?
Code: Select all
internal static int AlphaBetaFast(Board examineBoard, byte depth, int alpha, int beta, ChessPieceColor movingSide, ref int nodesSearched, bool quiescence, bool extended) //// May be you copy too much boards. Try to use only one copy per call //// or use a reference to ONE updated board. make_move()/undo_move() { nodesSearched++; if (depth == 0) //// Use a second function for quiescence. Don't mix it with your main alpha-beta search. { //If last move was a capture if (examineBoard.LastMove.TakenPiece.PieceType != ChessPieceType.None && quiescence == false) { //Perform a Quiessence Search //// I don't understand the connection between last-move-capture and qsearch. return AlphaBetaFast(examineBoard, 6, alpha, beta, movingSide, ref nodesSearched, true, true); //// Why is depth 6? Normally depth <= 0 is qsearch indicator and we use //// depth = 0 or depth - 1 in the calls inside qsearch. //// Again: dont mix search and qsearch: for better understanding. } if (extended == false) //// What is this extension? { if ((examineBoard.BlackCheck || examineBoard.WhiteCheck) && examineBoard.EndGamePhase) //// If you want to extend checks then only if you are in check //// (or only when you are giving check) but not both { return AlphaBetaFast(examineBoard, 3, alpha, beta, movingSide, ref nodesSearched, false, true); //// A typical extension would use depth + 1 and not 3. } } //Evaluate Score Evaluation.EvaluateBoardScore(examineBoard); //Invert Score to support Negamax examineBoard.Score = AbsoluteScore(examineBoard.Score, GetOppositeColor(movingSide)); //// AbsoluteScore is misleading. It sounds like abs(). Perhaps you mean //// sideToMoveDependentScore when your evaluate function always //// sees score > 0 as good for white? return examineBoard.Score; } if (examineBoard.FiftyMove >= 50 || examineBoard.RepeatedMove >= 3 || examineBoard.StaleMate) return 0; //// Perhaps move50 and repetition should be done first in every node. //// How do you know about stalemate without building a move list? //// Where do you find out that you are mated and where is the mating score? //Stand Pad //// Stand pat. if (quiescence) { //// Again why quiescence flag instead of depth <= 0? //Evaluate Score Evaluation.EvaluateBoardScore(examineBoard); //Invert Score to support Negamax examineBoard.Score = AbsoluteScore(examineBoard.Score, GetOppositeColor(movingSide)); if (examineBoard.Score >= beta) return beta; if (alpha > examineBoard.Score) alpha = examineBoard.Score; //// Where do you collect the best move so far? } List<Position> positions = EvaluateMoves(movingSide, examineBoard, quiescence); //// Assuming this is the move generator. //// Why a list of positions instead a list of moves? if (positions.Count == 0) { //Evaluate Score Evaluation.EvaluateBoardScore(examineBoard); //Invert Score to support Negamax examineBoard.Score = AbsoluteScore(examineBoard.Score, GetOppositeColor(movingSide)); //// See above. return examineBoard.Score; //// Is this your place to recognise mates or stalemates? } positions.Sort(Sort); depth--; //// The usual approach is not to change depth here but in the call below. foreach (Position move in positions) { //Make a copy Board board = examineBoard.FastCopy(); //// Is this the only board copy or just another one? //// See comment above. //Move Piece Board.MovePiece(board, move.SrcPosition, move.DstPosition); //// Once you do promotion you will need a promotion piece also. //We Generate Valid Moves for Board PieceValidMoves.GenerateValidMoves(board); //// Ups! Why? This is not the typical place for move generation. //// See comment on move generator above. int value = -AlphaBetaFast(board, depth, -beta, -alpha, GetOppositeColor(movingSide), ref nodesSearched, quiescence, extended); //// I would expect depth-1 in the call. if (value >= beta) { return beta; } if (value > alpha) alpha = value; //// Keep track on the best move. } //// Here would be a good place to recognise mate. //// (No best move found and in check). //// Here you can store something in a hash table when you implement one later. return alpha; }
that is an indication for a strange way to do something in your code.
Please try to react to some of my comments and in an improved version
we may find more and more serious errors. Have fun.
Harald
Code: Select all
private static int AbsoluteScore(int Score, ChessPieceColor color)
{
if (color == ChessPieceColor.White)
return -Score;
return Score;
}Code: Select all
Board board = examineBoard.FastCopy(); Code: Select all
PieceValidMoves.GenerateValidMoves(board);Thats a great idea, I just learned something new, thankshgm wrote:If at the 3-ply iteration you find the PV = e2e4 - e7e5 - g1f3, search for the 4-ply iteration first the branch that starts with e2e4 - e7e5 - g1f3. I.e. at ply=0 (root) search e2e4 first, then, in the ply=1 node after e2e4 search e7e5 first, etc. At ply=3 you are beyond the end of your old PV, so you try the best capture first, or the moves in random order. (There is only one more ply to go, and the window is still fully open, so this is good enough.)aberent wrote:Ok this sounds promising but I am not sure what you mean. What do you mean by "search the PV first"
Ok so I seperated the Qsearch from regular Alpha Beta. That gave me a small improvement 2%. Better than nothingCRoberson wrote:Most PC's are running chips based on superscalar architectures. Such machines have performance problems with conditional branching (if statements). So, make your quiesce routine a completely different routine. That will get some speed and make your code much easier to debug.
Second, don't generate the next set of moves just before searching the move you just made.
Notice after making a move you then call search (don't gen moves).Code: Select all
Search() { if (depth <= 0) return(Qsearch()); test for 3 fold rep test for transposition table hit and return null move test and possible return moves = generate_moves() for ( each move) { make move value = -Search(depth -1) if (value > alpha) { alpha = value; if (value >= beta) return(beta); Store PV } } Store best move in transposition tables return(alpha) } Qsearch() { // stand Pat score v = PositionEvaluation(); if (v>alpha) alpha = v; if (alpha>=beta) return(beta); Generate Captures for ( each capturing move) { make move v = -Qsearch() if (v>alpha) alpha =v; if (v>beta) return(beta); } return(alpha); }
In the Qsearch, same concept about move gen.
Now, prove to me you understand that algorithm. How does the stand pat score get returned? Also, explain the efficiency in when I gen moves in the Qsearch vs how you do it. Why is what I typed better?
When you can answer those questions, you have a chance at improving your program.
Iterative deepening. You do a 1 ply search, then a 2 ply search, but on the 2 ply search you search the best move from the one ply search first. Then you do a 3 ply search, and search the best moves at ply=1 and 2 from the two ply search first...aberent wrote:Ok this sounds promising but I am not sure what you mean. What do you mean by "search the PV first"hgm wrote:You can still use vanilla Alpha Beta and search the PV first. Doing depth-first without having any idea what the PV is is quite suicidal, and probably fully explains all your problems.aberent wrote:I am not using Principle Variation or Iterative Deepening, Just vanilla Alpha Beta.
No, you don't get it fully. There is much more to it than that. But, lets go with what you have figured out. Now, what is the impact ofaberent wrote:Ok so I seperated the Qsearch from regular Alpha Beta. That gave me a small improvement 2%. Better than nothingCRoberson wrote:Most PC's are running chips based on superscalar architectures. Such machines have performance problems with conditional branching (if statements). So, make your quiesce routine a completely different routine. That will get some speed and make your code much easier to debug.
Second, don't generate the next set of moves just before searching the move you just made.
.......
Notice after making a move you then call search (don't gen moves).
In the Qsearch, same concept about move gen.
Now, prove to me you understand that algorithm. How does the stand pat score get returned? Also, explain the efficiency in when I gen moves in the Qsearch vs how you do it. Why is what I typed better?
When you can answer those questions, you have a chance at improving your program.
I think I get it (maybe) you don't call Generate Moves before you enter a deeper depth because you might be at depth 0 in the next move? In that case you just evaluate the position and exit without having to Generate Moves?
Secondary hint:CRoberson wrote:No, you don't get it fully. There is much more to it than that. But, lets go with what you have figured out. Now, what is the impact ofaberent wrote:Ok so I seperated the Qsearch from regular Alpha Beta. That gave me a small improvement 2%. Better than nothingCRoberson wrote:Most PC's are running chips based on superscalar architectures. Such machines have performance problems with conditional branching (if statements). So, make your quiesce routine a completely different routine. That will get some speed and make your code much easier to debug.
Second, don't generate the next set of moves just before searching the move you just made.
.......
Notice after making a move you then call search (don't gen moves).
In the Qsearch, same concept about move gen.
Now, prove to me you understand that algorithm. How does the stand pat score get returned? Also, explain the efficiency in when I gen moves in the Qsearch vs how you do it. Why is what I typed better?
When you can answer those questions, you have a chance at improving your program.
I think I get it (maybe) you don't call Generate Moves before you enter a deeper depth because you might be at depth 0 in the next move? In that case you just evaluate the position and exit without having to Generate Moves?
not generating moves on the last ply? Think about the branch factor. How many nodes are in the last ply relative to the rest of the tree? Also, how many nodes are in the last ply relative to the previous ply?