Hotfix for unsoundness issue with MoveGen (55)

[terrorfisch]

See #55

I solved this by ignoring moves that do not fit in the list. The performance impact of this solution should be minimal because the branch predictor should be able to guess right and it should only introduce an additional conditional jump instruction. I did not measure anything though.

A clean fix would either require a SmallVec (probably best with a specialized happy path that does the same as above) or a ExpectedBoard or ValidBoard like type that upholds certain invariants.

[jordanbray]

This one is a bit tricky for me. This evil code-path is only possible if there are more pieces on the chess board than can exist on a chess board (or more than 2 e.p. captures possible at a time). Perhaps an assert on the number of pieces is cleaner? IE, don't use this if there are more than 16 pieces on the board.

Perhaps the assertion should be done in Board to keep the board "sane" at all times? Maybe in set_piece and friends? I'm not sure yet, let me think on this.

As far as I can tell, if that evil path is hit, something has already gone horribly wrong, and a panic may be in order.

Alternatively, there may be a cheap way to handle any number of pieces that I haven't thought of yet.

[terrorfisch]

I choose not to panic because I wanted to do a minimal change and panicking also increases the function size.

I'm not sure yet, let me think on this.

I also think that a final fix requires a few design choices on how to handle "custom" boards. I suggest merging this change for now because this is a potential security risk for instance if you have a server that allows loading custom boards.

[jordanbray]

I believe the following would resolve the unsoundness as well, but again I'd need to check more deeply:

If all the following is done in Board, I believe there would be no performance impact for chess engines, and minimal performance impact for other chess programs. I also believe this would ensure that no Board could exist in an invalid state. It's a tough invariant to hold in theory, but I do think this would about do it.

• confirm Board::xor safe
• add check in Board::is_sane

  if self.color_combined(Color::White) > 16 || self.color_combined(Color::Black) > 16 { // Edit: Changed to > 16, lol
      return false;
  }

• add check for result.is_sane() in set_piece
• add check for result.is_sane() in clear_square?
• FENs already call is_sane, so the unit test created will fail already.
• Add documentation to declare that more than 16 pieces is invalid.
• Declare that is_sane should always return true for any user program, and any user program that causes is_sane to return false indicates a bug in the ~program~ chess library.

This upholds the same safety guarantees (as far as I can tell), but reduces the merge request down to 6-7 lines. It also completely removes the performance impact where it matters most.

[terrorfisch]

So your plan is to make it an safety relevant invariant that an object of type Board is always "sane"? One has to be very careful that it is impossible to break this invariant in safe code. This would require that Board::xor always does a runtime check or is marked as unsafe.

What are the invariants that you plan to guarantee? I would only choose a subset of the extended "sane" to keep upholding it easier an allow invalid pinned and checkers states:

• No square with multiple pieces:
  • x & y == 0 for all x, y in pieces
  • color_combined[0] & color_combined[1] == 0
• Consistency of pieces, color_combined and combined
  • union(pieces) == combined
  • union(color_combined) == combined
• Limit number of pieces:
  • color_combined[0].popcnt() <= 16 && color_combined[1].popcnt() <= 16

Maybe we could factor out pieces, color_combined and combined into a seperate struct that always upholds these?

Note: One could replace piece_on with this

if self.combined() & opp == EMPTY {
    None
} else {
    let result: u8 = self.pieces.iter().enumerate().skip(1)
        .map(|(idx, bb)| (idx as u8) * ((opp & bb != EMPTY) as u8)).sum();

    Some(match result {
            0 => Piece::Pawn,
            1 => Piece::Knight,
            2 => Piece::Bishop,
            3 => Piece::Rook,
            4 => Piece::Queen,
            5 => Piece::King,
            _ => unreachable!()
    })
}

Or this completely branchless version

let result_plus_one: u8 = self.pieces.iter().enumerate()
  .map(|(idx, bb)| (idx as u8 + 1) * ((opp & bb != EMPTY) as u8)).sum();

Some(match result_plus_one.wrapping_sub(1) {
        0 => Piece::Pawn,
        1 => Piece::Knight,
        2 => Piece::Bishop,
        3 => Piece::Rook,
        4 => Piece::Queen,
        5 => Piece::King,
        _ => return None
})

[jordanbray]

• So, on the is_sane function, I think it's safe to assume already that no Board should be constructable using the public API that causes is_sane to return false. The test provided here basically invalidates that invariant (although technically is_sane doesn't check this particular invariant), so that's my first target (in my mind). There are certainly other ways to look at this problem, but that's the way that seems to have the most positive benefits in my twisted corridor of a brain.

• Xor probably is unsafe by that logic right now. It's a private function, but that doesn't really matter for safety, other than the key point that we can change it to unsafe without breaking existing code.

  • Is it writable in a safe way?
  • Would an assert on piece count fix that? Would that be too expensive as measured by chess_perft?
  • Is there some other tricky logic that can be pulled?
  • Maybe never add a piece that doesn't already exist? Only remove pieces? Can some fancy and and ors do that?
  • Maybe two functions? One to move a piece, on to remove a piece?)

• Moving this guarantee into is_sane gives me a warm, fuzzy feeling. I believe I should be able to set a fuzzer loose on any publicly documented API and have is_sane never return false. I have experience with quickcheck on the rust side, but there may be a better option.

• You made the argument that pinners and checkers probably don't need to uphold this invariant and they're more complicated anyways. For safety purposes I can maybe agree, but that feels like a semantic argument because it still likely indicates a bug. As to whether or not the area of effect of that bug reaches into the "safety" category, I'm honestly not sure I care. I should fix it anyways, lol.

• On piece_on, That's pretty clever. I'd be curious about benchmarks. I did (a long, long time ago) write a branchless version, but the branched version was faster in practice (as measured by perft). Mine didn't look as nice though.

[terrorfisch]

I am currently hacking together a solution that works via a destinct type which represents the "physical" board and handles to pieces and squares to avoid duplicate checks.

For safety purposes I can maybe agree, but that feels like a semantic argument because it still likely indicates a bug

Definitely but this is IMO a completely different category. If one has a safety relevant invariant there should go more effort into proving it.

On piece_on, That's pretty clever. I'd be curious about benchmarks. I did (a long, long time ago) write a branchless version, but the branched version was faster in practice (as measured by perft). Mine didn't look as nice though.

Thanks. I expect that the benchmark result depends heavily on the work load, the CPU architecture and the compiler (version).

[jordanbray]

Thanks. I expect that the benchmark result depends heavily on the work load, the CPU architecture and the compiler (version).

Yeah, benchmarks are very tricky. You gotta be very careful in order to get numbers. That said, I think I could probably get some numbers on that tonight.