Positions with 64 pieces cause overflows
thomas-maeder opened this issue · 10 comments
The main reason seems to be that the 64th piece gets piece id 64 (binary 1000000), which doesn't fit in the space reserved in the piece flags.
I see; cool!
Please note that apart from using that last of the 64 "slots", we should also add a check. Even on a 8x8 board, a user can add more than 64 pieces by adding multiple pieces on the same square.
Unless we do a significant redesign, we only have 6 bits for piece ids.
Currently, 0 is used as null value, and the values 1-63 can be used for pieces.
The only things that we can do in a small change are
- allow 0 as additoinal piece id - I am not sure if this is possible, though - there is a reason why we have the constant NullPieceId, after all
- only accept MaxPieceId-MinPieceId+1 pieces from the input and inform the user trying to exceed this limit
Unless we do a significant redesign, we only have 6 bits for piece ids.
Hmm.
#define PieceIdWidth 7u
After further investigation, I think that that redesign wouldn't be as significant as I was afraifd of.
Currently, Flag is a typedef for unsigned long. I hesitate to change this for now.
We can safely assume that unsigned long is >=32 bit.
Of these, we need 1 bit per piece_flag_type enumerator (currently 18).
That seems to give us no less than 14 bit for piece ids.
Resolving Issue #423 requires MaxPieceId ≥ 64, hence PieceIdWidth ≥ 7. Setting the latter to 7 would allow for MaxPieceId up to 127.
That written, I don't think we should jump so easily to making MaxPieceId too large. Increasing MaxPieceId increases the sizes of the arrays
motivation_type motivation[MaxPieceId+1]decision_levels_type decision_levels[MaxPieceId+1]PIECE target_position[MaxPieceId+1]unsigned int PieceId2index[MaxPieceId+1]square pieceid2pos[MaxPieceId+1]boolean piece_visited[MaxPieceId+1]PiecePositionsInDiagram[MaxPieceId+1]
and hence imposes some penalty. Moreover, once we declare a piece id value legal (by ensuring it's ≤ MaxPieceId) we lose the ability to check for that value in an assert in case it's most likely to be the result of a bug. Thus, I think we'd be better off trying to sensibly bound this value.
only accept
MaxPieceId-MinPieceId+1pieces from the input and inform the user trying to exceed this limit
We should absolutely do this! There's no reason to give the user the impression that we can handle something we can't. If a user hits this limit then they can put in a feature request.
Resolving Issue #423 requires MaxPieceId ≥ 64, hence PieceIdWidth ≥ 7
As I noticed yesterday, PieceIdWidth is already ==7, i.e. >=7
Yesterday, I set MaxPieceId to 127 without any other modification, for testing. All the test and example problems (except those in the 'lengthy' directories) ran through without a difference in the solving result (bar little differences in solving time).
Ok - I added the input check, and some more along the same lines.
Right now, MaxPieceId is 64 in this branch.
As per your comment of 20.5.2024, 01:28:17: i don't really see a problem raising MaxPieceId to 127 now.
I can't tell exactly which comment you're referring to, but in case it's mine I'll clarify that I trust your judgment in determining the most appropriate value for MaxPieceId.