@Alvaro: I think I have fixed up the bug.
Now the point is it takes a long time to complete the test upto 6 plys.
The Perft suite from website, contains about 126 positions in FEN and my program takes about 3 hours to evaluate most of the positions at 6th ply.
I tested a few of them, do you think that keeping my computer on for this purpose for days is of any worth?
Do you have some short listed positions which can help me track bugs, so the time required to run the suite is less than the original.
What should be my next step?
Programing basic Chess AI
How many positions per second does your Perft test go through? If the number is too low, you should see where the time is going. I expect a fast engine on modern hardware can go through several million positions per seconds. If you get something like a hundred thousand, you are probably still OK and shouldn't obsess about it. But if your speed is much lower than that, you are probably doing something wrong (copying tons of boards around, or allocating memory...).
Author
@Alvaro: Thanks for the reply.
I donot copy the board any time.
this is my perft method.
I purposely kept captures and non captures separate as it will help me in quiscent search.
The value of nodes per second is dependent on the position.
For the starting position its like
Solving position number 1
Number of moves : 20 in 16 msecs at depth of 1
Number of moves : 400 in 51 msecs at depth of 2
Number of moves : 8902 in 847 msecs at depth of 3
Number of moves : 197281 in 18591 msecs at depth of 4
Number of moves : 4865609 in 465042 msecs at depth of 5
I donot copy the board any time.
this is my perft method.
I purposely kept captures and non captures separate as it will help me in quiscent search.
Move noCaps_moves[];
Move Caps_moves[];
Move total_moves[] = new Move[200];
Move[] total_final_moves;
public long Perft(int depth, boolean turn) {
long nodes = 0, nods = 0;
//
noCaps_moves = g.nonCaps(turn);
Caps_moves = g.Caps(turn);
//total_moves = new Move[200];
int l = 0;
for (int i = 0; i < noCaps_moves.length; i++) {
total_moves[l++] = noCaps_moves;
}
for (int j = 0; j < Caps_moves.length; j++) {
total_moves[l++] = Caps_moves[j];
}
total_final_moves = g.filterMoves(total_moves, turn);
// System.out.println(total_final_moves.length);
if (depth == 0) {
return 1;
}
for (int x = 0; x < total_final_moves.length; x++) {
if (total_final_moves[x] != null) {
nods = nodes;
g.makeMove(total_final_moves[x]);
// Algebraic(total_final_moves[x]);
// g.Print(boardArray);
nodes += divide(depth - 1, !turn);
// System.out.println("\tnodes : "+(nodes - nods));
g.unMakeMove(total_final_moves[x]);
}
}
return nodes;
}The value of nodes per second is dependent on the position.
For the starting position its like
Solving position number 1
Number of moves : 20 in 16 msecs at depth of 1
Number of moves : 400 in 51 msecs at depth of 2
Number of moves : 8902 in 847 msecs at depth of 3
Number of moves : 197281 in 18591 msecs at depth of 4
Number of moves : 4865609 in 465042 msecs at depth of 5
if (depth == 0) {
return 1;
}Why is that code after all the move generation and filtering of valid moves? You can move it to the beginning of the function and you'll probably get a huge speedup.
Author
I went through that, and placing that code before the move generation and filtering, made absolutely no difference to the timing whatsoever. Logically it should have done, but it doesnt.
I also think that the move-generation speed depends upon the board structure used.
I have used 0x88 system an array of 128 elements.
I get maximum of 10,000 nodes per second using my code.
Now what do you suggest me to do?
I also think that the move-generation speed depends upon the board structure used.
I have used 0x88 system an array of 128 elements.
I get maximum of 10,000 nodes per second using my code.
Now what do you suggest me to do?
[font=arial, verdana, tahoma, sans-serif][size=2]I suggest you learn how to use a profiler, which is a program that let's you explore where in your code is time being spent.[/font][font=arial, verdana, tahoma, sans-serif][size=2]
[/font][font=arial, verdana, tahoma, sans-serif][size=2]From your code, the only thing that I can see that might be slowing you down a lot is using variable-length arrays for moves. If you can somehow avoid all dynamic memory allocation, it might be a big win.[/font]
[/font][font=arial, verdana, tahoma, sans-serif][size=2]From your code, the only thing that I can see that might be slowing you down a lot is using variable-length arrays for moves. If you can somehow avoid all dynamic memory allocation, it might be a big win.[/font]
Author
@Alvaro: I agree with you, and the results too showed that avoiding dynamic memory allocation was a speed up.However I was caught by surprise, I restarted my laptop and then the things further speed up after restarting, I dont really know why.
I am getting around 2,00,000 nodes per second.
Is this around the expected value?
what should I do next now?
kindly help.
Thank you.
I am getting around 2,00,000 nodes per second.
Is this around the expected value?
what should I do next now?
kindly help.
Thank you.
If you are satisfied that your move generator is working and you have a recursive function to iterate through some fixed-depth tree, I think the next step is to put together a simple evaluation function and a simple minimax search function. The program will probably play horribly at this point. Implement quiescence search next, and then alpha-beta pruning. The list gets quite long: Iterative deepening, move ordering, hash tables, null-move pruning, extensions of certain moves, end-game databases, late-move reductions... And of course, you can always improve your evaluation function.
There are other forums that are much more appropriate for chess programming, like talkchess.com. You should also use the Chess Programming Wiki.
There are other forums that are much more appropriate for chess programming, like talkchess.com. You should also use the Chess Programming Wiki.
Author
@Alvaro:Thanks for replying.
I have programed the basic chess, which can find checks. Did the search part with negamax+alphabeta pruning, works quiet well.
I have also noticed that my program is faster if I check for captures first(Sorted the captures), after a thought, I think this is because the material difference gives the cutoff.
I further want to improve the move ordering, so I tried for the Killer moves, but I am not finding any killer till depth of 6 here is a snippet of what I have done.
Please let me know, Is my code correct for killer Moves?
Another question I am having is, Do I have to wait for some more plys to get a killer move?
Its surprising that even if I am getting a cut-off(beta), there is no killer move generated.
Thank you.
PS: Since this is not a total chess related question, I have posted it here.
I have programed the basic chess, which can find checks. Did the search part with negamax+alphabeta pruning, works quiet well.
I have also noticed that my program is faster if I check for captures first(Sorted the captures), after a thought, I think this is because the material difference gives the cutoff.
I further want to improve the move ordering, so I tried for the Killer moves, but I am not finding any killer till depth of 6 here is a snippet of what I have done.
if (total_final_moves == killers[depth]) {
Move temp1;
temp1 = total_final_moves[0];
total_final_moves[0] = total_final_moves;
total_final_moves = temp1;
System.out.println("KILLER found");
}
}
for (int i = 0; i < total_final_moves.length; i++) {
Move coor = total_final_moves;
g_e.makeMove(coor, board);
eval = -NegaMax_ab(board, !turn, depth - 1, -beta, -alpha);
g_e.unMakeMove(coor, board);
if (eval >= beta) {
killers[depth] = total_final_moves;
return beta; // beta-cutoff
}
if (eval > alpha) {
killers[depth] = total_final_moves;
alpha = eval; // alpha acts like max in MiniMax
}Please let me know, Is my code correct for killer Moves?
Another question I am having is, Do I have to wait for some more plys to get a killer move?
Its surprising that even if I am getting a cut-off(beta), there is no killer move generated.
Thank you.
PS: Since this is not a total chess related question, I have posted it here.
Your killer-move code seems correct, and I find it very surprising that you don't find any killer moves before depth 6. Perhaps there is a bug elsewhere...
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
