Yes, it has to do with the garbage collector. If I start the jvm with e.g. -Xmx128m, it "only" uses 83MB of ram.flok wrote:Ok I think I got it work.
It is somewhat slow though and uses 370MB of ram (probably because the garbage collector (it is java) is not kicking in quick enough).
I did e2-e4, then: nodes: 405386, took: 111.07s, nodes/s: 3649.8 and my program came up with e7-e6.
doing the minimax!
Moderator: Ras
Re: doing the minimax!
Re: doing the minimax!
There's no memory leak. Really. In java you don't free objects. The only thing you can do is help the gc a little by explicitly set references to null (especially for chained objects that can be usefull).lucasart wrote:fix your memory leak first. you should not rely on a garbage collector to compensate for the bugs you have. when a node is finished the move list should be deallocated. a C program typically does this w/o any extra work, by allocating it on the stackflok wrote:Ok I think I got it work.
It is somewhat slow though and uses 370MB of ram (probably because the garbage collector (it is java) is not kicking in quick enough).
I did e2-e4, then: nodes: 405386, took: 111.07s, nodes/s: 3649.8 and my program came up with e7-e6.
Also see my other posting.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: doing the minimax!
How many plies deep was that search?flok wrote:Ok I think I got it work.
It is somewhat slow though and uses 370MB of ram (probably because the garbage collector (it is java) is not kicking in quick enough).
I did e2-e4, then: nodes: 405386, took: 111.07s, nodes/s: 3649.8 and my program came up with e7-e6.
Do you count temporarily visiting a node just for validating move legality as a node?
Nice to read that you got your code to work!

Just in case your legality check is a severe performance blocker: a huge amount of work can be saved by classifying moves based on whether it is even possible that they could be illegal. Assuming you are not doing anything extremely unusual in your move generator, you can state the following:
If you know the previous move that led to the current position, and that move was none of:
a) a check evasion (moving out of check),
b) a king move (including castling),
c) an en passant capture (which is rare but always a bit more tricky), or
d) a move of a pinned piece,
then it was not an illegal move so there is no need to make, test for king in check, and unmake such a move. That procedure would only be applied to all the other moves, so you end up testing only very few "suspicious" moves for legality.
Condition a) is immediately given when maintaining some "in check" flag per position which is set after having made the move.
Condition d) can be approximated, i.e. made weaker without losing too much of its speedup effect, by finding out whether a moving piece *could* be pinned. E.g. with Ke1, Nd2 that would apply to each move of Nd2 if the opponent had any diagonal slider on c3/b4/a5. But taking the time to calculate that information is already close to perfectly detecting pins, so the approximation may be less important.
Sven
Re: doing the minimax!
Sven Schüle wrote:How many plies deep was that search?flok wrote:Ok I think I got it work.
It is somewhat slow though and uses 370MB of ram (probably because the garbage collector (it is java) is not kicking in quick enough).
I did e2-e4, then: nodes: 405386, took: 111.07s, nodes/s: 3649.8 and my program came up with e7-e6.
Ehr I'm not sure
I visit 4 levels of the tree, so I guess that's 2 plies?
No, only the ones I evaluate.Do you count temporarily visiting a node just for validating move legality as a node?
Well, I did some profiling (using http://yourkit.com/ ) and I saw that a whole lot of time is spend in copying objects: 30%, that is much more than I want to spend on that. E.g. when I go one move deeper, I recreate the board and scene object (scene objects binds the board, chess objects and move-list objects together) from the white and black objects. First I do then is make a copy of the chess objects-objects in case they change. Hmmm, while typing this I'm thinking maybe I can do copy-on-write! Reduces the load on the garbage collector and is probably faster.Nice to read that you got your code to work!Now what is your next step: Negamax? AlphaBeta?
It indeed is. I estimate that's about 60% of the cpu-time (that is a guesstimate) since for every move I generate, I execute that move (with all that creating those objects and movelists, etc.).Just in case your legality check is a severe performance blocker:
Wellll, the previous engine on which it was based kept track of the following:a huge amount of work can be saved by classifying moves based on whether it is even possible that they could be illegal. Assuming you are not doing anything extremely unusual in your move generator,
- the other chess objects an object can catch
- the objects that can catch this object
- which objects guard it
That's interesting. That's something I will look at. On my todo list is (apart from porting it to the Android platform) is googling if there are any ideas on cutting leaves.you can state the following:
If you know the previous move that led to the current position, and that move was none of:
a) a check evasion (moving out of check),
b) a king move (including castling),
c) an en passant capture (which is rare but always a bit more tricky), or
d) a move of a pinned piece,
then it was not an illegal move so there is no need to make, test for king in check, and unmake such a move. That procedure would only be applied to all the other moves, so you end up testing only very few "suspicious" moves for legality.
Re: doing the minimax!
I made an enhancement to this: I also keep track of the depth at which a best score happened.Code: Select all
int minimax(int side, int rootSide, int depth) { if (depth == 0) return (side == rootSide) ? evaluate() : -evaluate(); int bestScore = (side == rootSide) ? -INF : +INF; for (all moves) { makeMove(move); score = minimax(opponent(side), rootSide, depth - 1); unmakeMove(move); if (side == rootSide) { if (score > bestScore) { bestMove = move; bestScore = score; } } else { if (score < bestScore) { bestMove = move; bestScore = score; } } } return bestScore; }
Then, after the if (side == rootSide) {} else {} I added:
Code: Select all
if (score == bestScore && score.depth > bestScore.depth) {
bestMove = move;
bestScore = score;
}
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: doing the minimax!
I don't understand what you plan to improve by that last piece of code. Apart from details in the given minimax algorithm which make that comparison "score.depth > bestScore.depth" currently useless (for instance, the way I wrote down the algorithm both values are always identical since minimax() searches to a fixed depth so all leaves are at the same level), I see no point in coupling the "best move/best score" idea with any kind of "likelihood for something to happen". At a node N, a move M2 is better than another move M1 if and only if its score is greater (from the maximizer's viewpoint) or lower (from the minimizer's viewpoint) than that of M1. An equal score is never better. It is important to strictly apply this principle, since otherwise algorithmic improvements like alphaBeta would not work.flok wrote:I made an enhancement to this: I also keep track of the depth at which a best score happened.Code: Select all
int minimax(int side, int rootSide, int depth) { if (depth == 0) return (side == rootSide) ? evaluate() : -evaluate(); int bestScore = (side == rootSide) ? -INF : +INF; for (all moves) { makeMove(move); score = minimax(opponent(side), rootSide, depth - 1); unmakeMove(move); if (side == rootSide) { if (score > bestScore) { bestMove = move; bestScore = score; } } else { if (score < bestScore) { bestMove = move; bestScore = score; } } } return bestScore; }
Then, after the if (side == rootSide) {} else {} I added:
Because I think that the later a situation happens (later = further down the tree), the less likely is that it is going to happen.Code: Select all
if (score == bestScore && score.depth > bestScore.depth) { bestMove = move; bestScore = score; }
Sven
Re: doing the minimax!
The idea is that checkmate might happen in a certain position for move a after 3 plies while for move b after 5 plies. Then you want to use the one with 3 plies is my assumption.II don't understand what you plan to improve by that last piece of code. Apart from details in the given minimax algorithm which make that comparison "score.depth > bestScore.depth" currently useless (for instance, the way I wrote down the algorithm both values are always identical since minimax() searches to a fixed depth so all leaves are at the same level),
fair enough!I see no point in coupling the "best move/best score" idea with any kind of "likelihood for something to happen". At a node N, a move M2 is better than another move M1 if and only if its score is greater (from the maximizer's viewpoint) or lower (from the minimizer's viewpoint) than that of M1. An equal score is never better. It is important to strictly apply this principle, since otherwise algorithmic improvements like alphaBeta would not work.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: doing the minimax!
That is correct. But mate scoring is usually done differently. When detecting that the moving side is checkmated, one possible (and frequently used) way of mate scoring is to subtract the distance in plies of the current node to the root node from some fixed constant, e.g. MATE_VALUE, which is clearly greater than all possible static evaluation scores, and to apply the correct sign to the result according to your search algorithm, e.g. in your case the maximizer being checkmated gets a negative score and the minimizer a positive score. That has the property you were looking for: from the maximizer's viewpoint MATE_VALUE-3 is better than MATE_VALUE-5.flok wrote:The idea is that checkmate might happen in a certain position for move a after 3 plies while for move b after 5 plies. Then you want to use the one with 3 plies is my assumption.II don't understand what you plan to improve by that last piece of code. Apart from details in the given minimax algorithm which make that comparison "score.depth > bestScore.depth" currently useless (for instance, the way I wrote down the algorithm both values are always identical since minimax() searches to a fixed depth so all leaves are at the same level),
From your earlier posts:
One ply = one half move. 1.e2e4 e7e6 is two plies. So visiting 4 levels of the tree (not counting the root node) is 4 plies. That is almost exactly matching your node count "405386" which is 1 + the number of leaf nodes of the 4-ply-tree after 1.e4 (i.e. 1 + perft(4)). Many people also include all non-leaves into their node count.flok wrote:I visit 4 levels of the tree, so I guess that's 2 plies?
Porting to Android is surely a good thing. But I propose to work on an alphaBeta-based algorithm first before you starting any porting, to save double work. Regarding "cutting leaves", read the chess programming wiki (I gave one link in an earlier post) and start with alphaBeta. I would leave all that stuff about forward pruning for a later stage of development when your engine is already in a mature state. If you get basic alphaBeta with good move ordering, a simple static eval and an effective quiescence search up and running, maybe also using SEE (static exchange evaluation), then you will already have a medium-strength engine that beats "Pos" 999:1 and can turn to the advanced thingsflok wrote:On my todo list is (apart from porting it to the Android platform) is googling if there are any ideas on cutting leaves.

Sven
Re: doing the minimax!
Tonight I won't be replacing minimax (need a clear mind for that), but suddenly I realised: I keep track of which object protects what (an object that protects would be able to catch the object it protects if it were a different color, to say it different: the place of the kind would be reachable in 1 move): if an object is not protecting the king, and there are no attackers behind it (I also keep track of that), then I should be able to ignore the move of that object.Sven Schüle wrote:Just in case your legality check is a severe performance blocker: a huge amount of work can be saved by classifying moves based on whether it is even possible that they could be illegal.
Re: doing the minimax!
Ok implemented. Seems to work: behaves the same as the minimax version.flok wrote:Tonight I won't be replacing minimax (need a clear mind for that)
Code: Select all
[Event "BrutePOS v1.21 (Tue Jan 17 21:05:49 2012) versus opponent"]
[Site "?"]
[Date 2012.1.2"]
[Round "1"]
[White "BrutePOS v1.21 (Tue Jan 17 21:05:49 2012)"]
[Black "opponent"]
1.Pa2a3 Pa7a6 2.Pf2f3 Pf7f6 3.Pb2b4 Pb7b5 4.Pg2g4 Pg7g5 5.Pc2c3 Pc7c6 6.Ph2h3 Pd7d6 7.Pc3c4 Pe7e6 8.Pc4c5 Ph7h6 9.Pf3f4 Bc8d7 10.Pd2d3 Pd6d5 11.Pf4f5 Pe6e5 12.Pe2e4 Pd5d4 13.Bf1e2 Bf8g7 14.Ra1a2 Qd8c8 15.Ra2b2 Ke8e7 16.Rb2c2 Ke7e8 17.Rc2b2 Ke8e7 18.Rb2c2 Ke7e8
That seems to work!flok wrote:but suddenly I realised: I keep track of which object protects what (an object that protects would be able to catch the object it protects if it were a different color, to say it different: the place of the kind would be reachable in 1 move): if an object is not protecting the king, and there are no attackers behind it (I also keep track of that), then I should be able to ignore the move of that object.
nodes: 183894, took: 14.104s, nodes/s: 13038.4 -> without it I do 3600 nodes/s
Need to do lots of more tests though to verify that indeed it is correct.
Testing is troublesome: I noticed yesterday that I have a bug in my en passant code which did not get detected in the 97k games played at fics!