some questions about mailbox

[tcusr]

after gaining interest in mailbox engines i decided i wanted to start from solid foundations and already implement some well known tricks/techniques,
one of which is the neighbor table by hgm. while for move gen it may be relatively useful for the generation of captures/in check detection i thought that the most use could be found in evaluation.
for example it can be used to find rooks on open files, passed pawns, doubled pawns etc very quickly, just a single 'if'.
so my (very naive) question is, what improvements do bitboards give in evaluation?
please provide some real examples because while reading other engine's eval code i could come up with something similar in mailbox easily
thanks

[emadsen]

for example [bitboards] can be used to find rooks on open files, passed pawns, doubled pawns etc very quickly, just a single 'if'.
so my (very naive) question is, what improvements do bitboards give in evaluation?
please provide some real examples because while reading other engine's eval code i could come up with something similar in mailbox easily
thanks

Not sure what you're asking because you seem to have answered your own question. Yes, bitboards speed up static evaluation. For example, like you suggest, you can determine if a pawn is passed via bitmasks.

Code: Select all

private static bool IsPassedPawn(Position position, Square square, Color color)
{
    Debug.Assert(PieceHelper.GetColorlessPiece(position.GetPiece(square)) == ColorlessPiece.Pawn);
    Debug.Assert(PieceHelper.GetColor(position.GetPiece(square)) == color);
    var enemyColor = 1 - color;
    // Determine if pawn can be blocked or attacked by enemy pawns as it advances to promotion square.
    return (Board.PassedPawnMasks[(int)color][(int)square] & position.GetPawns(enemyColor)) == 0;
}

In a mailbox engine, you must loop through many squares in two (board edge) or three files to determine if an enemy pawn is in front of your own pawn. This is very slow.

[tcusr]

for example [bitboards] can be used to find rooks on open files, passed pawns, doubled pawns etc very quickly, just a single 'if'.
so my (very naive) question is, what improvements do bitboards give in evaluation?
please provide some real examples because while reading other engine's eval code i could come up with something similar in mailbox easily
thanks

Not sure what you're asking because you seem to have answered your own question. Yes, bitboards speed up static evaluation. For example, like you suggest, you can determine if a pawn is passed via bitmasks.

Code: Select all

private static bool IsPassedPawn(Position position, Square square, Color color)
{
    Debug.Assert(PieceHelper.GetColorlessPiece(position.GetPiece(square)) == ColorlessPiece.Pawn);
    Debug.Assert(PieceHelper.GetColor(position.GetPiece(square)) == color);
    var enemyColor = 1 - color;
    // Determine if pawn can be blocked or attacked by enemy pawns as it advances to promotion square.
    return (Board.PassedPawnMasks[(int)color][(int)square] & position.GetPawns(enemyColor)) == 0;
}

In a mailbox engine, you must loop through many squares in two (board edge) or three files to determine if an enemy pawn is in front of your own pawn. This is very slow.

sorry, i didn't express myself correctly, i was talking about the neighbor table when describing the examples
this is what they would look like

Code: Select all

bool pawn_is_passed(int square, int color)
{
    return neighbor[square][relative_north(color)] == GUARD;
}
bool rook_on_open_file(int square)
{
    return neighbor[square][north] == GUARD && neighbor[square][south] == GUARD;
}

bool is_doubled_pawn(int square, int color)
{
    return neighbor[square][relative_north(color)] == PAWN + color;
}

you get the idea, as you can see they are very similar to your implementation

[hgm]

In a mailbox engine, you must loop through many squares in two (board edge) or three files to determine if an enemy pawn is in front of your own pawn. This is very slow.

There are more efficient ways for doing that. I like the TSCP method, which first loops through all pawns to determine the most backward one in each file. Then, to determine whether a given pawn is a passer, you just have to compare its rank with the backward-most opponent in two or three files, rather than looping through the squares of the files themselves. The work of looping through the pawns might seem a lot, but all tests for the individual passers then uses the result. So per pawn it is in fact just taking the minimum/maximum of its rank and the best-so-far for that file. You have to initialize this 'stopping power' for each file to the promotion rank, but if these are byte values you can do that in a single memory store of a uint64_t.

But the most important point is that it doesn't matter how slow it is. Because typically you find the result of this entire calculation in the pawn hash table, and would only have to calculate it from scratch on a miss. Which should be very rarely. For this reason it doesn't pay to make the calculation of the stopping power incremental (which could be easily done, and would greatly increase its speed): you would have to do that on every MakeMove. Doing it from scratch on the rare miss is faster. So you only update the pawn key incrementally.

[JohnWoe]

FRC code from Mayhem: https://github.com/SamuraiDangyo/mayhem ... .hpp#L1464

This is pretty much the fastest way to check bishops on corners.
In Stockfish 100% the same way.

Code: Select all

// Trapped bishop penalty in FRC
// Bishop on a1/h1/a8/h8 blocked by own pawn
int FixFRC() {
  // No bishop in corner -> Speedup
  constexpr std::uint64_t corners = Bit(0) | Bit(7) | Bit(56) | Bit(63);
  if (!((g_board->white[2] | g_board->black[2]) & corners))
    return 0;

  auto s = 0;
  if (g_board->pieces[0]  == +3 && g_board->pieces[9]  == +1) s -= FRC_PENALTY;
  if (g_board->pieces[7]  == +3 && g_board->pieces[14] == +1) s -= FRC_PENALTY;
  if (g_board->pieces[56] == -3 && g_board->pieces[49] == -1) s += FRC_PENALTY;
  if (g_board->pieces[63] == -3 && g_board->pieces[54] == -1) s += FRC_PENALTY;
  return s;
}

[hgm]

That is basically a mailbox test, except that you use a bitboard 'filter' to decide whether it should be done. (Which is of course almost never.) A faster way, which doesn't require bitboards, is to exploit some otherwise unused bits in the hash key: make sure these bits are always zero in the piece-square keys, except for the bishops in corners, where each corner then has its own bit. (So this uses 4 bits of the key.) You then just have to test whether any of the bits is non-zero as the primary filter.

[tcusr]

another question, is it better to use a piece list of a fixed size of 16 for each color or 12 piece lists for each piece type/color?
in 'New Architectures in Computer Chess' fritz reul suggests to use the second option to be able to optimize every aspect of each piece but this is not a problem since i use C++ (he uses C) and i can use templates to write much less but equally faster code.
the only problem is when i have to update these lists and to a series of if else to choose the right one, is this cost negligible?

[hgm]

One doesn't exclude the other. You can have one list, which is a concatenation of the lists for each piece type. You just have to keep track of the first and last piece of every type, when this is not fixed during the game. E.g. because you compact the list in the root. But it doesn't often happen you want to loop through all pieces, and do the same to all.

[tcusr]

One doesn't exclude the other. You can have one list, which is a concatenation of the lists for each piece type. You just have to keep track of the first and last piece of every type, when this is not fixed during the game. E.g. because you compact the list in the root. But it doesn't often happen you want to loop through all pieces, and do the same to all.

this is what you do in qperft right? i guess i'll do this instead
the only problem is that i am basically using all your ideas

[hgm]

FRC code from Mayhem: https://github.com/SamuraiDangyo/mayhem ... .hpp#L1464

This is pretty much the fastest way to check bishops on corners.
In Stockfish 100% the same way.

Code: Select all

// Trapped bishop penalty in FRC
// Bishop on a1/h1/a8/h8 blocked by own pawn
int FixFRC() {
  // No bishop in corner -> Speedup
  constexpr std::uint64_t corners = Bit(0) | Bit(7) | Bit(56) | Bit(63);
  if (!((g_board->white[2] | g_board->black[2]) & corners))
    return 0;

  auto s = 0;
  if (g_board->pieces[0]  == +3 && g_board->pieces[9]  == +1) s -= FRC_PENALTY;
  if (g_board->pieces[7]  == +3 && g_board->pieces[14] == +1) s -= FRC_PENALTY;
  if (g_board->pieces[56] == -3 && g_board->pieces[49] == -1) s += FRC_PENALTY;
  if (g_board->pieces[63] == -3 && g_board->pieces[54] == -1) s += FRC_PENALTY;
  return s;
}

It occurred to me that this could be done infinitely faster, as a completely free side effect of evaluating the castling rights: next to the 4 flags that indicate which castling rights exist, you add 4 flags for indicating which bishops are still trapped in a corner. The spoilers for the squares where bishops and the pawns that block those start would clear those bits when they move or get captured, just as moving king or rook clear castling rights. The flag word is than used to index a 256-entry table in which you can look up the applicable eval bonus (for castling rights) plus penalty (for the bishop trapping).