debugging move ordering

[maksimKorzh]

Dear community, please help!

I'm now creating a bitboard chess engine in C youtube series and here's an issue I'm now encountering -
I've just implemented MVV LVA/killer/history move ordering and obviously it reduces the number of traversed nodes significantly
BUT the problem I'm now facing is an UGLY debugging, now please let me explain.

If it wasn't a youtube tutorial I would get satisfied with what I have now, but my goal is to SHOW beginners HOW exactly the moves are GETTING ORDERED along the way.

I'm trying to print all the moves and corresponding scores at ply == 0, literally only ROOT MOVES
and with CAPTURES it works pefectly well BUT when it comes to killers/history moves we need
to print the moves at a ply where either beta cutoff occurs storing killer or alpha increases storing history move

Obviously we need to go deeper in order to get history moves sorted and even deeper to get killer moves,
e.g. I'm getting killer initialized starting at ply 3

Here's how my current debugging output looks like:

Code: Select all

  8  ♜ . . ♛ . ♜ . ♚
  7  ♟︎ ♟︎ ♟︎ . . ♟︎ ♟︎ ♟︎
  6  . . ♞ . ♝ ♞ . .
  5  . . ♝ . ♟︎ . . .
  4  . . . ♘ ♙ . . .
  3  . . . ♙ . ♘ ♙ ♙
  2  ♙ ♙ ♙ . . ♙ ♗ .
  1  ♖ . ♗ ♕ . ♖ ♔ .

     a b c d e f g h

     Side:     black
     Enpassant:   no
     Castling:  ----

     move: e5d4   score: 10205
     move: c6d4   score: 10204
     move: c5d4   score: 10203
     move: d8d4   score: 10201
     move: f6e4   score: 10104
     move: e6h3   score: 10103
     move: e6a2   score: 10103
     move: f8e8   score: 7167
     move: f6g4   score: 7098
     move: a7a5   score: 7055
     move: e6d7   score: 7049
     move: f6d7   score: 7049
     move: d8c8   score: 7015
     move: f6d5   score: 7010
     move: b7b5   score: 7008
     move: g7g6   score: 7004
     move: e6g4   score: 7004
     move: b7b6   score: 7003
     move: c5b4   score: 7003
     move: a7a6   score: 7002
     move: e6b3   score: 7002
     move: c6b4   score: 7002
     move: d8b8   score: 7002
     move: e6c4   score: 7002
     move: d8d7   score: 7002
     move: c5b6   score: 7002
     move: c5e7   score: 7001
     move: e6f5   score: 7001
     move: c5d6   score: 7001
     move: e6c8   score: 7001
     move: d8d6   score: 7001
     move: c6e7   score: 7001
     move: e6d5   score: 7000
     move: f6g8   score: 7000
     move: c6b8   score: 7000
     move: c5a3   score: 7000
     move: a8b8   score: 7000
     move: a8c8   score: 7000
     move: h7h6   score: 7000
     move: f8g8   score: 7000
     move: f6h5   score: 7000
     move: c6a5   score: 7000
     move: d8e8   score: 7000
     move: h7h5   score: 7000
     move: d8e7   score: 7000
     move: g7g5   score: 7000
     move: d8d5   score: 7000
     move: f6e8   score: 7000
     move: h8g8   score: 7000

  8  ♜ . . ♛ . ♜ . ♚
  7  ♟︎ ♟︎ ♟︎ . . ♟︎ ♟︎ ♟︎
  6  . . ♞ . ♝ ♞ . .
  5  . . ♝ . ♟︎ . . .
  4  . . . ♟︎ ♙ . ♙ .
  3  . . . ♙ . ♘ . ♙
  2  ♙ ♙ ♙ . ♘ ♙ ♗ .
  1  ♖ . ♗ ♕ . ♖ ♔ .

     a b c d e f g h

     Side:     black
     Enpassant:   no
     Castling:  ----

     move: f6e4   score: 10104
     move: f6g4   score: 10104
     move: e6g4   score: 10103
     move: e6a2   score: 10103
     move: f8e8   score: 7167
     move: a7a5   score: 7055
     move: e6d7   score: 7049
     move: f6d7   score: 7049
     move: d8c8   score: 7015
     move: f6d5   score: 7010
     move: b7b5   score: 7008
     move: g7g6   score: 7004
     move: b7b6   score: 7003
     move: c5b4   score: 7003
     move: a7a6   score: 7002
     move: c5b6   score: 7002
     move: e6c4   score: 7002
     move: c6b4   score: 7002
     move: d8b8   score: 7002
     move: e6b3   score: 7002
     move: d8d7   score: 7002
     move: e6f5   score: 7001
     move: e6c8   score: 7001
     move: c5e7   score: 7001
     move: c6e7   score: 7001
     move: c5d6   score: 7001
     move: d8d6   score: 7001
     move: c6a5   score: 7000
     move: h7h6   score: 7000
     move: f6e8   score: 7000
     move: e6d5   score: 7000
     move: c5a3   score: 7000
     move: a8b8   score: 7000
     move: a8c8   score: 7000
     move: f6g8   score: 7000
     move: f8g8   score: 7000
     move: h7h5   score: 7000
     move: c6b8   score: 7000
     move: d8e8   score: 7000
     move: f6h5   score: 7000
     move: d8e7   score: 7000
     move: g7g5   score: 7000
     move: d8d5   score: 7000
     move: h8g8   score: 7000

So currently I'm using code like this:

Code: Select all

// debug move ordering
void debug_move_ordering(moves *move_list, int count, int print_ply)
{
    if (ply == print_ply)
    {
        if (count == 0)
            print_board();
        
        // print move
        printf("     move: %s%s%c  score: %d\n", square_to_coordinates[get_move_source(move_list->moves[count])],
                                                 square_to_coordinates[get_move_target(move_list->moves[count])],
                                                 get_move_promoted(move_list->moves[count]) ? promoted_pieces[get_move_promoted(move_list->moves[count])] : ' ',
                                                 score_move(move_list->moves[count]));
    }
}

and put it within my alpha-beta search like this:

Code: Select all

// negamax serach with alpha-beta pruning
int negamax(int alpha, int beta, int depth)
{    
    // escape condition
    if (!depth)
        // evaluate position
        return quiescence(alpha, beta);
        ...
    // move ordering
    sort_moves(move_list);

    // loop over move list
    for (int count = 0; count < move_list->count; count++)
    {                                                             
        // debug move ordering at PLY 2
        debug_move_ordering(move_list, count, 2);

        ply++;
        ...
        ply--;
}

Now my question is:
IS THERE A BETTER WAY OF WHAT I'M TRYING TO DO?
Thanks in advance!

[Mike Sherwin]

As Bob, author of Crafty, says; "never do anything before you have to". I would move your sort into the move loop and make it a single pass sort. As far as scoring the moves the way you are doing it is fine but using internal iterative deepening (IID) when there is no hash move works well.

[maksimKorzh]

As Bob, author of Crafty, says; "never do anything before you have to". I would move your sort into the move loop and make it a single pass sort. As far as scoring the moves the way you are doing it is fine but using internal iterative deepening (IID) when there is no hash move works well.

Thanks Mike. Well actually I'm using common iterative deepening, hence having PV move every next depth to put as the first move.
Regarding my own question I've just realized that I can print the ordered list just right after sorting it and that's it!
So it's the exact case when asking a question helps you to determine actual problem and eventually find the solution.

And regarding putting sort_moves() within a loop:
I'm scoring them on the fly and for the didactic purposes I just want to show move list before sorting and after.
Here's the simple solution I came up with:

1. I've changed debug_move_ordering() function:

Code: Select all

// debug move ordering
void debug_move_ordering(moves *move_list, int depth_current, int user_depth) // depth_current == iterative deepening depth
{
    if (depth_current == user_depth && ply == 0) // print move list/scores at user specified ID depth
    {
        for (int count = 0; count < move_list->count; count++)
        {
            if (count == 0)
                print_board();
            
            // print move
            printf("     move: %s%s%c  score: %d\n", square_to_coordinates[get_move_source(move_list->moves[count])],
                                                     square_to_coordinates[get_move_target(move_list->moves[count])],
                                                     get_move_promoted(move_list->moves[count]) ? promoted_pieces[get_move_promoted(move_list->moves[count])] : ' ',
                                                     score_move(move_list->moves[count]));
        }
    }
}

2. And then simply calling it like this:

Code: Select all

    // create move list
    moves move_list[1];
    
    // generate moves
    generate_moves(move_list);
    
    // debug move ordering
    debug_move_ordering(move_list, depth_current, 5); // print moves when ID goes at depth 5

    // move ordering
    sort_moves(move_list);
    
    // debug move ordering
    debug_move_ordering(move_list, depth_current, 5); // print moves when ID goes at depth 5

3. And now the output would be:

Code: Select all

  8  ♜ . . ♛ . ♜ ♚ .
  7  ♟︎ ♟︎ ♟︎ . . ♟︎ ♟︎ ♟︎
  6  . . ♞ . ♝ ♞ . .
  5  . . ♝ . ♟︎ . . .
  4  . . . ♟︎ ♙ . . .
  3  . . . ♙ . ♘ ♙ ♙
  2  ♙ ♙ ♙ . ♘ ♙ ♗ .
  1  ♖ . ♗ ♕ . ♖ ♔ .

     a b c d e f g h

     Side:     black
     Enpassant:   no
     Castling:  ----

info score cp 45 depth 1 nodes 86 pv f8e8 
info score cp 25 depth 2 nodes 1682 pv f8e8 f1e1 
info score cp 35 depth 3 nodes 7369 pv d8c8 f3g5 e6d7 
info score cp 20 depth 4 nodes 41471 pv d8c8 f3g5 f8e8 g5e6 f7e6 

  8  ♜ . . ♛ . ♜ ♚ .
  7  ♟︎ ♟︎ ♟︎ . . ♟︎ ♟︎ ♟︎
  6  . . ♞ . ♝ ♞ . .
  5  . . ♝ . ♟︎ . . .
  4  . . . ♟︎ ♙ . . .
  3  . . . ♙ . ♘ ♙ ♙
  2  ♙ ♙ ♙ . ♘ ♙ ♗ .
  1  ♖ . ♗ ♕ . ♖ ♔ .

     a b c d e f g h

     Side:     black
     Enpassant:   no
     Castling:  ----

     move: a7a6   score: 7001
     move: a7a5   score: 7000
     move: b7b6   score: 7000
     move: b7b5   score: 7004
     move: g7g6   score: 7000
     move: g7g5   score: 7002
     move: h7h6   score: 7000
     move: h7h5   score: 7000
     move: c6b8   score: 7000
     move: c6e7   score: 7000
     move: c6a5   score: 7000
     move: c6b4   score: 7002
     move: f6e8   score: 7000
     move: f6d7   score: 7000
     move: f6d5   score: 7000
     move: f6h5   score: 7000
     move: f6e4   score: 10104
     move: f6g4   score: 7001
     move: e6c8   score: 7000
     move: e6d7   score: 7033
     move: e6d5   score: 7000
     move: e6f5   score: 7000
     move: e6c4   score: 7000
     move: e6g4   score: 7000
     move: e6b3   score: 7000
     move: e6h3   score: 10103
     move: e6a2   score: 10103
     move: c5e7   score: 7000
     move: c5b6   score: 7000
     move: c5d6   score: 7000
     move: c5b4   score: 7000
     move: c5a3   score: 7000
     move: a8b8   score: 7000
     move: a8c8   score: 7000
     move: f8e8   score: 7019
     move: d8b8   score: 7000
     move: d8c8   score: 20000
     move: d8e8   score: 7000
     move: d8d7   score: 7000
     move: d8e7   score: 7000
     move: d8d6   score: 7000
     move: d8d5   score: 7000
     move: g8h8   score: 7000

  8  ♜ . . ♛ . ♜ ♚ .
  7  ♟︎ ♟︎ ♟︎ . . ♟︎ ♟︎ ♟︎
  6  . . ♞ . ♝ ♞ . .
  5  . . ♝ . ♟︎ . . .
  4  . . . ♟︎ ♙ . . .
  3  . . . ♙ . ♘ ♙ ♙
  2  ♙ ♙ ♙ . ♘ ♙ ♗ .
  1  ♖ . ♗ ♕ . ♖ ♔ .

     a b c d e f g h

     Side:     black
     Enpassant:   no
     Castling:  ----

     move: d8c8   score: 20000
     move: f6e4   score: 10104
     move: e6a2   score: 10103
     move: e6h3   score: 10103
     move: e6d7   score: 7033
     move: f8e8   score: 7019
     move: b7b5   score: 7004
     move: g7g5   score: 7002
     move: c6b4   score: 7002
     move: f6g4   score: 7001
     move: a7a6   score: 7001
     move: a7a5   score: 7000
     move: f6e8   score: 7000
     move: f6d7   score: 7000
     move: f6d5   score: 7000
     move: f6h5   score: 7000
     move: g7g6   score: 7000
     move: b7b6   score: 7000
     move: e6c8   score: 7000
     move: h7h6   score: 7000
     move: e6d5   score: 7000
     move: e6f5   score: 7000
     move: e6c4   score: 7000
     move: e6g4   score: 7000
     move: e6b3   score: 7000
     move: h7h5   score: 7000
     move: c6b8   score: 7000
     move: c5e7   score: 7000
     move: c5b6   score: 7000
     move: c5d6   score: 7000
     move: c5b4   score: 7000
     move: c5a3   score: 7000
     move: a8b8   score: 7000
     move: a8c8   score: 7000
     move: c6e7   score: 7000
     move: d8b8   score: 7000
     move: c6a5   score: 7000
     move: d8e8   score: 7000
     move: d8d7   score: 7000
     move: d8e7   score: 7000
     move: d8d6   score: 7000
     move: d8d5   score: 7000
     move: g8h8   score: 7000
info score cp 20 depth 5 nodes 309726 pv d8c8 g3g4 h7h6 f1e1 f8e8 
bestmove d8c8