final List<Move> moves = scene.getMoveList(side);
...
final Move currentMove = moves.get(index);
I'm not familiar with Java lists, but accessing the n-th element of a linked list is typically O(n). I would recommend using an iterator to traverse the list.
getMoveList returns an 'ArrayList'-object which sould have O(1) speed.
flok wrote:The move-generator and such has played almost 100.000 games on fics now with 0 crashes and 0 illegal moves.
You have ensured your perft numbers are correct, right?
flok wrote:It is oo-code so it allocates a new object for each move etc. which is slow. The only solution is better algorithms.
When I switched from move objects to integers in my C# engine, I saw a 5% increase in perft speed, which suggests object allocation probably isn't a bottleneck. Your site says you have some sort of experimental evaluation. If it doesn't show up as 99% in profiling, you have the fun opportunity to make tons of optimizations. ^^
Codesquid wrote:I'm not familiar with Java lists, but accessing the n-th element of a linked list is typically O(n). I would recommend using an iterator to traverse the list.
Java has LinkedList and ArrayList (c++'s vector). He's probably using the latter.
Ran it through a profiler (http://yourkit.com/) and the current implementation can't be made faster.
Would you wager on that?
Without an algorithm change, I sincerely doubt it.
Forget about "making it faster" as long as it is not clear whether your search algorithm is even implemented correctly. Here I mean "correct" in the sense of correctly using alphaBeta, not in the sense of not playing illegal moves in the game.
Now my next questions:
a) What is your typical value for "maxExtension"? May I guess "-1" or "-2"?
if (score == -Integer.MAX_VALUE || score == Integer.MAX_VALUE)
continue;
i.e. in which case does your evaluation function (getShannonValue()) return MAX_VALUE (positive or negative), and how does getShannonValue() know when to return the positive or the negative MAX_VALUE?
c) You still have the same "suspicious" call of validateMoves() after making a move. Last time in January 2012 you tried to explain what that function does but that blew my mind. So has anything changed substantially since then in that area, or do you still do it the same way?
1) Always listen to Sven
2) Never allocate, just reuse objects - gain is around 3x, if you have a lot of allocations currently.
3) Make sure you have at least an ok eval (if Shannon is the original Shannon formula, maybe you could at least add a piece square table to it).
4) If you want to cut, you must focus on move ordering first (MVV/LVA, killers, TT, etc). If you don't have a good move ordering, you won't be able to cut efficiently without doubt.
Folkert,
I guess it should be easy to debug your engine with the following.
I played
1. f3, e5
2. g4, ....
Then let DeepBrutePos think for 180 seconds on my Nexus. It reports 5 deep, about 86KNs and then still plays a5? Assuming you don't have ID, and start at depth 5 right away, I find it very surprising you are not able to go over all the moves and find the mate in one. If your engine really needs so much time going over all the moves, perhaps it is a good idea to start with a much lower depth (or even better, implement ID).
Aart
abik wrote:Folkert,
I guess it should be easy to debug your engine with the following.
I played
1. f3, e5
2. g4, ....
Then let DeepBrutePos think for 180 seconds on my Nexus. It reports 5 deep, about 86KNs and then still plays a5? Assuming you don't have ID, and start at depth 5 right away, I find it very surprising you are not able to go over all the moves and find the mate in one. If your engine really needs so much time going over all the moves, perhaps it is a good idea to start with a much lower depth (or even better, implement ID).
Aart
Maybe, it should be also noted that if you implement a vanilla alpha-beta/negamax your engine will do everything to dodge a mate in 1 when winning At least that happened to me - was funny to see 6 queens on the board with a clueless king. Described here: http://home.hccnet.nl/h.g.muller/delay.html
please check out the code below (resp. pseudocode for my tiny addition "SearchControl"). It's negamax, and I put in a regular legality + mate dectection + timeout handling + check extension code using mostly your method names. I also added a very simple iterative deepening in findBestMove() which returns the best move (not the best score). Would be interesting to see how that works.
int alphaBeta(final Scene scene, final PlayerColor side, int depth, int height, final IO io, int alpha, int beta, final SearchControl control)
{
// keep track of the number of processed nodes
nodeCount.addAndGet(1);
if (control.isTimeOut(Statics.getTimestamp())) {
// note: should not happen at root
control.abortSearch();
io.progressCallback("Abort search due to time limit");
return +INFINITY;
}
final PlayerColor otherSide = Statics.opponentColor(side);
bool isInCheck = scene.isKingUnderAttack(side, otherSide);
if (isInCheck) {
depth++;
}
if (depth <= 0) {
return getShannonValue(scene, side); // score
}
scene.validateMoves(side); // should only generate moves for "side" and possibly order them appropriately;
// if also legality is tested for each move then the other legality testing code
// can be removed from the loop body, and mate/stalemate detection can be moved
// to the line below this comment
final List<Move> moves = scene.getMoveList(side);
int movesListSize = moves.size();
totalNMoves.addAndGet(movesListSize);
totalNodes.addAndGet(1);
int nLegalMoves = 0;
for(int index=0; index<movesListSize; index++) {
// "do a move", 'afterMove' is the "situation" after 'currentMove' was executed
Scene sceneAfterMove = null;
final Move currentMove = moves.get(index);
try {
sceneAfterMove = currentMove.getScene();
if (sceneAfterMove == null) {
sceneAfterMove = scene.Move(currentMove);
} else {
currentMove.setScene(null); // help GC, link is not required
}
}
catch(Exception e) {
System.out.println(" side: " + side + " alpha " + alpha + " beta " + beta);
System.out.println(" " + (depth + 1) + " " + currentMove);
Statics.displayBoard(afterMove.getBoard());
System.out.println("" + e);
e.printStackTrace();
System.exit(1);
}
if (sceneAfterMove.isKingUnderAttack(side, otherSide)) {
// illegal move
continue;
}
nLegalMoves++;
final int score = -alphaBeta(sceneAfterMove, otherSide, depth - 1, height + 1, -beta, -alpha);
sceneAfterMove.shrink();
if (control.wasSearchAborted()) {
return +INFINITY; // will be ignored by parent who negates the score and never finds -INFINITY
// to be better than his best move so far
}
if (score >= beta) {
return beta;
}
if (score > alpha) {
alpha = score;
if (height == 0) {
control.setBestMove(currentMove);
}
}
}
if (nLegalMoves == 0) {
if (isInCheck) {
// mated
return -(INFINITY - height);
} else {
// stalemate
return 0;
}
}
return alpha;
}
Move findBestMove(final Scene scene, final PlayerColor side, final double finishBefore, int depth, final IO io)
{
SearchControl control = new SearchControl(finishBefore);
for (int d = 1; d <= depth && !control.isSearchAborted(); d++) {
int bestValue = alphaBeta(scene, side, d, 0, io, -INFINITY, +INFINITY, control);
}
return control.bestMove();
}
public class SearchControl ...
// abstraction for timeout checking, aborting search, and best root move
// provides methods:
// SearchControl(finishBefore) => sets abort flag to false and best root move to null, stores "finishBefore"
// abortSearch() => sets abort flag to true
// wasSearchAborted() => queries abort flag
// bestMove() => returns best root move
// setBestMove(move) => stores new best root move
// isTimeOut(timeStamp) => returns true if (finishBefore > 0 && finishBefore <= timeStamp)
bpfliegel wrote:1) Always listen to Sven
Never allocate, just reuse objects - gain is around 3x, if you have a lot of allocations currently.
I'm not so sure about that. My C# engine used to allocate Lists, Moves, and everything else in accordance with OOP principles, and speed wasn't really a problem. However, the memory use was troubling, as it seemed like the GC gave up on it.
Sven's code looks great, but I think I know why the original implementation doesn't work too well.
abik wrote:Folkert,
I guess it should be easy to debug your engine with the following.
I played
1. f3, e5
2. g4, ....
Then let DeepBrutePos think for 180 seconds on my Nexus. It reports 5 deep, about 86KNs and then still plays a5? Assuming you don't have ID, and start at depth 5 right away, I find it very surprising you are not able to go over all the moves and find the mate in one. If your engine really needs so much time going over all the moves, perhaps it is a good idea to start with a much lower depth (or even better, implement ID).
Aart
Maybe, it should be also noted that if you implement a vanilla alpha-beta/negamax your engine will do everything to dodge a mate in 1 when winning At least that happened to me - was funny to see 6 queens on the board with a clueless king. Described here: http://home.hccnet.nl/h.g.muller/delay.html
Balint
This might explain why several of the lower rated engines, such as the new micro engine Iota, can not finish off an opponent when they are way ahead in material
bpfliegel wrote:Maybe, it should be also noted that if you implement a vanilla alpha-beta/negamax your engine will do everything to dodge a mate in 1 when winning At least that happened to me - was funny to see 6 queens on the board with a clueless king. Described here: http://home.hccnet.nl/h.g.muller/delay.html
Balint
That anomaly of looping around in won-situations may indeed occur while forced mate possibilities remain after the selected not-directly-mating-move, and adding delay penalties will fix that. However, in my simple example, many responses from white on a black move resolve the mate thread altogether, and not finding that even with vanilla alpha-beta seems a bug to me.
