doing the minimax!

[flok]

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.

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]

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.

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 stack

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).
Also see my other posting.

[Sven]

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.

How many plies deep was that search?

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! Now what is your next step: Negamax? AlphaBeta?

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

[flok]

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.

How many plies deep was that search?

Ehr I'm not sure
I visit 4 levels of the tree, so I guess that's 2 plies?

Do you count temporarily visiting a node just for validating move legality as a node?

No, only the ones I evaluate.

Nice to read that you got your code to work! Now what is your next step: Negamax? AlphaBeta?

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.

Just in case your legality check is a severe performance blocker:

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.).

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,

Wellll, the previous engine on which it was based kept track of the following:
- the other chess objects an object can catch
- the objects that can catch this object
- which objects guard it

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.

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.

[flok]

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;
}

I made an enhancement to this: I also keep track of the depth at which a best score happened.
Then, after the if (side == rootSide) {} else {} I added:

Code: Select all

            if (score == bestScore && score.depth > bestScore.depth) {
                bestMove = move;
                bestScore = score;
            }

Because I think that the later a situation happens (later = further down the tree), the less likely is that it is going to happen.

[Sven]

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;
}

I made an enhancement to this: I also keep track of the depth at which a best score happened.
Then, after the if (side == rootSide) {} else {} I added:

Code: Select all

            if (score == bestScore && score.depth > bestScore.depth) {
                bestMove = move;
                bestScore = score;
            }

Because I think that the later a situation happens (later = further down the tree), the less likely is that it is going to happen.

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.

Sven

[flok]

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),

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.

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.

fair enough!

[Sven]

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),

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.

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.

From your earlier posts:

I visit 4 levels of the tree, so I guess that's 2 plies?

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.

On my todo list is (apart from porting it to the Android platform) is googling if there are any ideas on cutting leaves.

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 things

Sven

[flok]

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.

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.

[flok]

Tonight I won't be replacing minimax (need a clear mind for that)

Ok implemented. Seems to work: behaves the same as the minimax version.

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 

I aborted it after the 18th move as it then starts to repeat. Need to implement some kind of history (well, fix it: the one I have doesn't work: I calculate a hash on the board-setup and store it in a hash tree).

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.

That seems to work!
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!