Problem with counter move heuristic

[HemiMG]

Hey guys,
Long time lurker, first time poster, and all that jazz. Normally I can solve any problem I run into, but I'm a bit stumped trying to implement the counter move heuristic as described in the chess programming wiki. I've got it implemented, but it makes my search worse, sometimes much worse, and never even marginally better. I've tested across a number of board positions and at a number of depths. Search time and number of nodes always goes up. I'm clearly doing something wrong, but I don't know what.

I've tested to ensure that it is matching up the correct moves by printing the board at the top of each search and then having the program tell me when it finds a countermove. The countermove is the current move being scored and the previous move it is matching with aligns with the previous printed board position. So the right values are being scored, I would assume. I've also tried giving the counter moves a variety of different scores. Anything but 0 makes things worse.

My evaluation function right now is just the simplified evaluation, also from the chess programming wiki. I'll attach the relevant code below, in the hopes that someone spots an obvious error and can stop me from banging my head against a wall.

First, the move scoring function in its entirety:

Code: Select all

int Board::ScoreMove(Move move, int piece, int target, int ply)
{
    if (move == hash_move1 || move == hash_move2)
        return 25000;

    if (score_pv && pv_line[ply] == move) {
        score_pv = false;
        return 20000;
    }

    if (GetPromotedPiece(move))
        return 19000;

    if (move == killer_move1[ply])
        return 9000;
    if (move == killer_move2[ply])
        return 8000;

    int from = GetFromSquare(previous_move);
    int to = GetToSquare(previous_move);
    if (move == counter_moves[from][to])
        return 7000;
    
    return history_moves[piece][target];
}

Now the relevant portion of the search:

Code: Select all

if (score >= beta)
                {
                    ply--;

                    if (!captured)
                    {
                        board.killer_move2[ply] = board.killer_move1[ply];
                        board.killer_move1[ply] = move;

                        int from = GetFromSquare(old_previous_move);
                        int to = GetToSquare(old_previous_move);
                        board.counter_moves[from][to] = move;
                    }

                    board.UnmakeMove(move);
                    board.game_state = old_game_state;
                    board.previous_move = old_previous_move;

                    return beta;
                }

There isn't much code there, but it should be a fairly simple addition. The only thing missing is when the previous_move is actually set, during the make_move function of the board. old_previous_move is set to that right before the move being tested is made, so it is using the correct move as the previous one.

Any obvious thing I'm missing would be super helpful.

[HemiMG]

Hmm. Whenever I post a question, I always solve it shortly after. This was no exception. If anyone else is wondering why move ordering makes things worse, you may be making the same silly mistake I was. I commented out my late move reduction code and retried the experiment. This time, countermove ordering DID improve the number of nodes searched.

So, while I'm searching more nodes now, presumably that's because nodes that shouldn't be pruned are no longer getting pruned. It should be stronger as a result, I'd imagine. I can't test that tell I have time to boot into Linux again. Arena doesn't work for Mac and I can't find a suitable replacement. Anyhow, mystery solved.

[maksimKorzh]

Hmm. Whenever I post a question, I always solve it shortly after. This was no exception. If anyone else is wondering why move ordering makes things worse, you may be making the same silly mistake I was. I commented out my late move reduction code and retried the experiment. This time, countermove ordering DID improve the number of nodes searched.

So, while I'm searching more nodes now, presumably that's because nodes that shouldn't be pruned are no longer getting pruned. It should be stronger as a result, I'd imagine. I can't test that tell I have time to boot into Linux again. Arena doesn't work for Mac and I can't find a suitable replacement. Anyhow, mystery solved.

I had similar issues with search and I also came up with the same conclusions you did.
Earlier I tried to bundle all search optimization techniques I could find/implement but
then I've realized that even reducing the number of traversed nodes doesn't always
necessarily mean that the search has improved.

Now I'm running lots of tests woth and with out every single optimization I make to make sure
that the new optimization at very least doesn't result in more poor play.

[pedrojdm2021]

So... this don't work with Late Move reductions ??

[No4b]

I've got it implemented, but it makes my search worse, sometimes much worse, and never even marginally better. I've tested across a number of board positions and at a number of depths. Search time and number of nodes always goes up. I'm clearly doing something wrong, but I don't know what.

This is terrible approach to testing if things works, tbh.
I have a ton of examples where tweaking ordering heuristics (history/countermove/etc) would:
1) Increase nodes searched in fixed depth and gain elo
2) Reduce nodes searched in fixed depth and lose elo

So... this don't work with Late Move reductions ??

I introduced originally CounterMoves for ordering only early in developement and it was a huge elo-gainer.
Then after some time, I added a patch to reduce counterMoves less in LMR.

Since than I added CounterMoveHistory. After re-test, seems that CounterMove isnt really useful in ordering anymore, but reducing less still has some value.
So at least in my engine, CounterMoves work ONLY for LMR.

For each their own, so i cannot guarantee it would be same for other engines

[pedrojdm2021]

I've got it implemented, but it makes my search worse, sometimes much worse, and never even marginally better. I've tested across a number of board positions and at a number of depths. Search time and number of nodes always goes up. I'm clearly doing something wrong, but I don't know what.

This is terrible approach to testing if things works, tbh.
I have a ton of examples where tweaking ordering heuristics (history/countermove/etc) would:
1) Increase nodes searched in fixed depth and gain elo
2) Reduce nodes searched in fixed depth and lose elo

So... this don't work with Late Move reductions ??

I introduced originally CounterMoves for ordering only early in developement and it was a huge elo-gainer.
Then after some time, I added a patch to reduce counterMoves less in LMR.

Since than I added CounterMoveHistory. After re-test, seems that CounterMove isnt really useful in ordering anymore, but reducing less still has some value.
So at least in my engine, CounterMoves work ONLY for LMR.

For each their own, so i cannot guarantee it would be same for other engines

I see, i ended up in the conclusion that the more nodes that you prune, the better evaluation you'll need, as you said "Reduce nodes searched in fixed depth and lose elo" in ineed reduces elo.

i was expecting some number of position searched reduced with countermove, but it was the opporiste, the thing that worked for me is making an more agressive LMR, but again, it costs some elo points. I have to compensate that with a more advanced evaluation function