question about move ordering

[Carbec]

Hi,

I noticed that in Faile, one consider both the "hash move" and the "pv move". Until now, but I am very inexperimented, I thought that once you have the hashtable, you don't use anymore the pv table.
Did I forget something ??

Code: Select all

    /* fill the move ordering array: */

    /* if searching the pv, give it the highest move ordering, and if not, rely
     on the other heuristics: */
    if (searching_pv) {
        searching_pv = FALSE;
        for (i = 0; i < num_moves; i++) {
            from = moves[i].from;
            target = moves[i].target;
            promoted = moves[i].promoted;
            captured = moves[i].captured;

            /* give captures precedence in move ordering, and order captures by
     material gain */
            if (captured != npiece)
                move_ordering[i] = cap_values[captured]-cap_values[board[from]]+1000;
            else
                move_ordering[i] = 0;

            /* make sure the suggested hash move gets ordered high: */
            if (from == h_move->from && target == h_move->target
                    && promoted == h_move->promoted) {
                move_ordering[i] += INF-10000;
            }

            /* make the pv have highest move ordering: */
            if (from == pv[1][ply].from && target == pv[1][ply].target
                    && promoted == pv[1][ply].promoted) {
                searching_pv = TRUE;
                move_ordering[i] += INF;
            }

            /* heuristics other than pv (no need to use them on the pv move - it is
     already ordered highest) */
            else {
                /* add the history heuristic bonus: */
                move_ordering[i] += (history_h[from][target]>>i_depth);

                /* add the killer move heuristic bonuses: */
                if (from == killer1[ply].from && target == killer1[ply].target
                        && promoted == killer1[ply].promoted)
                    move_ordering[i] += 1000;
                else if (from == killer2[ply].from && target == killer2[ply].target
                         && promoted == killer2[ply].promoted)
                    move_ordering[i] += 500;
                else if (from == killer3[ply].from && target == killer3[ply].target
                         && promoted == killer3[ply].promoted)
                    move_ordering[i] += 250;
            }
        }
    }

    /* if not searching the pv: */
    else {
        for (i = 0; i < num_moves; i++) {
            from = moves[i].from;
            target = moves[i].target;
            promoted = moves[i].promoted;
            captured = moves[i].captured;

            /* give captures precedence in move ordering, and order captures by
     material gain */
            if (captured != npiece)
                move_ordering[i] = cap_values[captured]-cap_values[board[from]]+1000;
            else
                move_ordering[i] = 0;

            /* make sure the suggested hash move gets ordered first: */
            if (from == h_move->from && target == h_move->target
                    && promoted == h_move->promoted) {
                move_ordering[i] += INF+1000;
            }

            /* heuristics other than pv */

            /* add the history heuristic bonus: */
            move_ordering[i] += (history_h[from][target]>>i_depth);

            /* add the killer move heuristic bonuses: */
            if (from == killer1[ply].from && target == killer1[ply].target
                    && promoted == killer1[ply].promoted)
                move_ordering[i] += 1000;
            else if (from == killer2[ply].from && target == killer2[ply].target
                     && promoted == killer2[ply].promoted)
                move_ordering[i] += 500;
            else if (from == killer3[ply].from && target == killer3[ply].target
                     && promoted == killer3[ply].promoted)
                move_ordering[i] += 250;
        }
    }

Thanks

Philippe

[mvanthoor]

...

There have been some discussions about that in the last year or so.

The gist of it is that the PV move is also a hash move. So, if you have hash move sorting, you don't need the PV-move sorting anymore. However, there is one caveat: if your hash table is small, the PV move can be overwritten and you lose that move to sort on. There are several solutions:

- Put the PV moves in their own hash table.
- At the end of an iteration, create another hash entry with the PV move (so you stuff all the data back into the TT); this makes sure the move will be available in the next iteration
- Still have PV-move ordering implemented and use this as a fallback if you have no hash move to order on.

At the moment my engine has none of those, but I may try the first or second option to see if this makes any difference.

[pedrojdm2021]

For PV scoring in my engine i use the PV table that i use for extracting the principal variation. (Triangular PV table)

Inside the negamax function i have:

Code: Select all

// enable principal variation scoring
if (follow_pv)
	enable_pv_scoring(target_move_index);

	for (sbyte moveIndex = 0; moveIndex <= target_move_index; moveIndex++)
	{
		OrderMoves(moveIndex, target_move_index);
		......

That function looks like this:

Code: Select all

private static void enable_pv_scoring(int targetMoveIndex)
{
	// disbale follow pv flag
	follow_pv = false;
	// check if we are actually following the pv
	for (int moveIndex = 0; moveIndex <= targetMoveIndex; moveIndex++)
	{
		if (pv_table[0][ply] == move_list[ply][moveIndex])
		{
			// enable pv scoring
			follow_pv = true;
			// enable following pv
			score_pv = true;
			break;
		}
	}
}

And the score_move function looks like this:

Code: Select all

private static int GuessMoveScore(ushort _move)
		{
		        // Score principal variation if we're following it
			if (score_pv && pv_table[0][ply] == _move)
			{
				score_pv = false;
				return 20000;
			}

			MoveFlag flag = MoveUtility.Get_flag(_move);
			byte sq_from = MoveUtility.Get_square_from(_move);
			byte sq_to = MoveUtility.Get_square_to(_move);

			if (flag.Is_Capture())
			{
				byte attacker = board.boardPieces[sq_from];
				byte victim = board.boardPieces[sq_to];
				// apply lookup to the MVV/LVA Table   
				return mvv_lva[attacker][victim] + 10000;
			}
			else
			{
				if (killer_moves[0][ply] == _move)
					return 9000;
				else if (killer_moves[1][ply] == _move)
					return 8000;
				else
					return history_moves[board.sideToMove][sq_from][sq_to];
			}
		}

Also, in the Iterative deeping function i always set the
follow_pv flag to true in every iteration.

i hope it helps.