doing the minimax!

[flok]

Hi,

After 3 attempts for creating a chess program not doing brute force calculations and still play nice, I gave up. It's not going to work.

Sooo, let's see if I can implement minimax!

I think I implemented it correctly but since I get strange results (really weird moves) if the search depth gets > 1, I want to ask you if you can point me at my mistake.

Code: Select all

int iterate&#40;Move baseMoveIn, SelectedMove selectedMove, List<QueuedMove> queuedMoves, Scene scene, PlayerColor baseColor, PlayerColor currentColor, int depth, IO io&#41; &#123;
        // get list of moves in the current setup
        List<Move> moves = scene.getMoveList&#40;currentColor&#41;;
        // just a difficult way of finding the color of the opponent &#58;_)
        PlayerColor afterMoveColor = Statics.opponentColor&#40;currentColor&#41;;

        // go through list of moves
        for&#40;Move currentMove &#58; moves&#41; &#123;
                // calculate the situation after the move
                Scene afterMove = scene.Move&#40;currentMove&#41;;
                // for the situation after the move, calculate the shannon value
                // seen from the point of view of the opponent
                double value = getShannonValue&#40;afterMove, afterMoveColor&#41;;

                // value bigger than previous calculated value and we're looking at
                // the shannon value for the color that started the whole search?
                // then remember the move that started it all &#40;one of the moves in
                // the first step of the tree&#41; and the value
                Move baseMoveUse = baseMoveIn != null ? baseMoveIn &#58; currentMove;
                if &#40;value > selectedMove.getValue&#40;) && afterMoveColor == baseColor&#41; &#123;
                        selectedMove.setMove&#40;baseMoveUse, value, depth&#41;;
                &#125;

                // queue the node after the move; will check its children
                if &#40;afterMove.isCheckMate&#40;afterMoveColor&#41; == false&#41;
                        queuedMoves.add&#40;new QueuedMove&#40;baseMoveUse, value, afterMove, afterMoveColor, depth + 1&#41;);
        &#125;

        return moves.size&#40;);
&#125;

public SelectedMove calculateMove&#40;int it, List<History> history, double finishBefore, Scene scene, PlayerColor myColor, IO io&#41;
&#123;
        SelectedMove selectedMove = new SelectedMove&#40;null, -25000000.0, -1&#41;;
        List<QueuedMove> queuedMoves = new ArrayList<QueuedMove>();
        int processed = 0;

        // depth = 0
        processed += iterate&#40;null, selectedMove, queuedMoves, scene, myColor, myColor, 1, io&#41;;
        for&#40;;;) &#123;
                int size = queuedMoves.size&#40;);
                if &#40;size == 0 || Statics.getTimestamp&#40;) >= finishBefore&#41;
                        break;

                QueuedMove currentQueuedMove = queuedMoves.remove&#40;size - 1&#41;;
                // other depths
                processed += iterate&#40;currentQueuedMove.getBaseMove&#40;), selectedMove, queuedMoves, currentQueuedMove.getScene&#40;), myColor, currentQueuedMove.getColor&#40;), currentQueuedMove.getDepth&#40;), io&#41;;
        &#125;

        return selectedMove;
&#125;

[Sven]

Hi Folkert,

it seems you are not backing up the best value correctly. In Minimax you need to either take the perspective of the "maximizer" (the moving side at the root node) or of the "minimizer" (its opponent). Usually you have two search functions for that. Have you taken a look at the CPW?
You can also put that into one function but then you have a significant overhead by doing a lot of "if"-s. Avoiding these "if"-s as a next step will almost directly lead you to the Negamax algorithm which is much simpler than Minimax.

But if you insist on Minimax within one function, follow these guidelines:

1) Let your evaluation function always return a value from the "maximizer" viewpoint, not from the side whose turn it is currently.

2) If it is the maximizer's turn BEFORE MAKING A MOVE (i.e., when entering your iterate() function) then compare like "if (score > bestScore)", otherwise "if (score < bestScore)". [You are only doing one of the two, it seems.] Note how the bestScore has to be initialized depending on MAX or MIN viewpoint.

Example pseudocode for recursive minimax in one function (not tested):

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 &#40;score < bestScore&#41; &#123;
                bestMove = move;
                bestScore = score;
            &#125;
        &#125;
    &#125;
    return bestScore;
&#125;

Another point in your code is that it seems you do not perform a recursive search but always terminate after 1 ply, unless I misunderstand the meaning of your function getShannonValue() (I thought it is your static evaluation function, and if it is then you need to call it outside the move loop if "depth == 0").

I have a lot of difficulties in understanding that line:

Code: Select all

Move baseMoveUse = baseMoveIn != null ? baseMoveIn : currentMove;

According to the comment above that line it seems you are referencing some move from a higher level of the tree at this point, which I strongly believe is incorrect. A recursive search started for some node determines the best value and (possibly) best move for that node, then returns to the parent node, and so on.

Minimax and Negamax are of course fully insufficient to play any kind of reasonable chess with acceptable response times, so be prepared to try alphaBeta soon

Sven

[flok]

it seems you are not backing up the best value correctly. In Minimax you need to either take the perspective of the "maximizer" (the moving side at the root node) or of the "minimizer" (its opponent). Usually you have two search functions for that.

Ah indeed. I was ignoring the opponent's value, the newer version compares that value too.

Have you taken a look at the CPW?
You can also put that into one function but then you have a significant overhead by doing a lot of "if"-s. Avoiding these "if"-s as a next step will almost directly lead you to the Negamax algorithm which is much simpler than Minimax.

Will look at that link, thanks. My first attempt will be getting things to work, then later on i'll see if i can speed-up things by such split-ups. Currently the limiting factor is in how I determine if moves are valid: to do so, I calculate the situation after a move and then see if a king is still check, if so then the move is not valid. This greatly affects the performance as you can imagine.

While typing this I'm doing a test-run and something odd is happening: the value of the opponent is always the negative value of the moving side.

Another point in your code is that it seems you do not perform a recursive search but always terminate after 1 ply, unless I misunderstand the meaning of your function getShannonValue() (I thought it is your static evaluation function, and if it is then you need to call it outside the move loop if "depth == 0").

'iterate' processes one scene or situation. it is called by calculateMove. iterate looks at each move possible in a situation, evaluates them using that getShannonValue method and adds the scene-object resulting from the move in a queue. then calculateMove picks a move from that queue and then runs iterate again, until time is up or the queue is empty.

I have a lot of difficulties in understanding that line:

Code: Select all

Move baseMoveUse = baseMoveIn != null ? baseMoveIn : currentMove;

According to the comment above that line it seems you are referencing some move from a higher level of the tree at this point, which I strongly believe is incorrect. A recursive search started for some node determines the best value and (possibly) best move for that node, then returns to the parent node, and so on.

At ply 0, baseMoveIn == null so if eval value is bigger, the current move is selected as a possible result move. scenes/positions/situations deeper down the tree get a baseMoveIn pointer which points to the move-object at the top of that tree. that way i can easily update my "global" SelectedMove object with the move. This trickery is because it is not a recursive implementation but a iterative one.

Minimax and Negamax are of course fully insufficient to play any kind of reasonable chess with acceptable response times, so be prepared to try alphaBeta soon

ok, thanks for the elaborate reply!

[Sven]

Hi Folkert,

since you are working with a queue, it looks like a breadth-first search algorithm to me, correct? I.e. produce all nodes at ply 1, then all at ply 2, then all at ply 3 and so on. That will quickly become inefficient for higher depths, I'm afraid ... One point is the order of processing nodes of the game tree, the other is the amount of memory you need for that approach, since for an N-ply search you will have to store information about ALL frontier nodes (maxDepth-1) which would be around 35^(N-1) (with minimax) and around 2 * 35^((N-1)/2)) (with a very basic alphaBeta-like implementation, assuming that can be done efficiently in a breadth-first framework which is a separate issue ).

But anyway, putting aside the efficiency for a moment, I have not understood yet how you back up values to the parent node and upwards to the root node. Your algorithm currently looks wrong to me, which might of course be caused by not understanding the details. If you find some move being better than the best move found so far then this is a statement valid for one certain node, comparing all moves which are legal there. But it does not necessarily have any impact on what is the best move at nodes higher in the tree, i.e. 2, 4, 6, ... plies closer to the root. But it seems you are always updating the best move of either the root node or (if you are at an odd ply) of the root node's successor on the current move path. And that is wrong, since the opponent's moves that were made inbetween are not necessarily his optimal moves.

Next point, what value is it that you are backing up? You compare the result of "getShannonValue()" (where I still assume that's your static evaluation function) to some "best score" that you found before, but you do that independent from the current depth. What you actually have to do for a correct game tree search (in its simplest form, no quiescence-search, pruning etc.) is to manage that your static evaluation is called at the leaf nodes [only - unless you use static eval also for other purposes], i.e. "depth == maxDepth", and that at each node with depth < maxDepth you determine the best score (and, if needed, the best move that leads to that score) relative to that node, which results from backing up values whose origin is at leaf nodes. I don't see how your algorithm does that, can you explain it?

The approach you have chosen has quite some limitations. It is already a well-known fact that, in order to play reasonable chess, a chess program is forced to take serious measures in cutting down the growing complexity of the game tree. It can PERHAPS be done with a breadth-first-like approach (it certainly has already been done in the past) but then you'll need quite a sophisticated approach to deal with that complexity reduction task and also with the memory requirements - and it needs to be correct, or course.

To understand what is a correct game tree traversal you WILL need to understand first how recursive Minimax, Negamax, and AlphaBeta algorithms work, and only then, in my opinion, it is an option to go a different way, experimentally trying to achieve the same correct results through different algorithms.

Sven

[Sven]

Hi again,

just to clarify one point:

Your algorithm currently looks wrong to me, which might of course be caused by not understanding the details.

What I meant here was "which might of course be caused by the fact that I do not understand all the details of your algorithm".

I found another issue: it is not clear to me how your detection of illegal moves works. "if (afterMove.isCheckMate(afterMoveColor) == false)" does not look right to me. "if (afterMove.isKingInCheck(currentColor) == false)" would look more appropriate. If that is actually what is behind your "isCheckMate()" function then I propose to choose a better naming to avoid further confusion with real checkmate testing code.

Sven

[lucasart]

After 3 attempts for creating a chess program not doing brute force calculations and still play nice, I gave up. It's not going to work.

Don't give up so soon. If you've written all the board playing code and move generation, that's a lot of work, and it would be a shame to throw it away for that. Doing a basic alpha beta search is very simple actually. But you should not begin by the search itself. My advice to you is to proceed as follows:
1/ implement a SEE
2/ create some class that gets instanciated from a position, and has a method like ::next_move() which allows you to pick moves in decreasing SEE order. At this stage equal SEE are still sorted as they come out of the move generation (ie. randomly), and you will improve that later with a history table (but forget that for now).
3/ write an alpha beta quiescent search

And of course, after every step, and before proceeding to the next one, test your functions independantly, and put lots of assert() everywhere... One is never too prudent!

Let me know when you reach that stage. The quiescent is easy to test on sample positions. And you will notice that certain positions lead to a quiescent search tree explosion, so you'll have to add the SEE pruning there.

Once all that works, it's easy to write an alpha beta search that calls itself recursively and the qsearch at depth 0.

[flok]

just to clarify one point:

Your algorithm currently looks wrong to me, which might of course be caused by not understanding the details.

What I meant here was "which might of course be caused by the fact that I do not understand all the details of your algorithm".

Well I also think it is not going to work. I looked at your example code, and saw that you use the evaluation value at the "end" of the tree; the deepest part. My attempt would also look at the values down the line.
Also the memory usage is problem: with only a couple of plies deep the program uses 0,9GB of ram.

I found another issue: it is not clear to me how your detection of illegal moves works. "if (afterMove.isCheckMate(afterMoveColor) == false)" does not look right to me. "if (afterMove.isKingInCheck(currentColor) == false)" would look more appropriate. If that is actually what is behind your "isCheckMate()" function then I propose to choose a better naming to avoid further confusion with real checkmate testing code.

Code: Select all

Scene afterMove = currentMove.getScene();
afterMove.validateMoves(afterMoveColor);

That validateMoves method would throw away all moves that stay in check or move itself to check mate.

Currently I'm looking how I can implement a correct minimax with minimal changes to the core (move generation and such).

[flok]

After 3 attempts for creating a chess program not doing brute force calculations and still play nice, I gave up. It's not going to work.

Don't give up so soon. If you've written all the board playing code and move generation, that's a lot of work, and it would be a shame to throw it away for that.

Oh, no, I'm not going to throw that away. That has been tested for quiet a while (pos played at least a 98.000 games at fics via ficsdrone). It is only the brain, the code that selects a move that I'm going to replace.

Once all that works, it's easy to write an alpha beta search that calls itself recursively and the qsearch at depth 0.

Am looking at it
Well, minimax first. Small steps.

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

[lucasart]

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