Positions with 64 pieces cause overflows

[thomas-maeder]

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.

[JoshuaGreen]

Yep.  I already identified and eliminated this limitation in PR #441.  I’m currently reviewing a new version of that branch that is built off the most recent develop branch and will let everyone know when it’s ready. Sent from the all new AOL app for iOS On Sunday, May 19, 2024, 12:44 PM, Thomas Maeder ***@***.***> wrote: 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. — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[thomas-maeder]

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.

[JoshuaGreen]

Ah, interesting.  Any idea what a safe MaxPieceId value would be? Sent from the all new AOL app for iOS On Sunday, May 19, 2024, 2:30 PM, Thomas Maeder ***@***.***> wrote: 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. — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you commented.Message ID: ***@***.***>

[thomas-maeder]

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

[thomas-maeder]

Unless we do a significant redesign, we only have 6 bits for piece ids.

Hmm.
#define PieceIdWidth 7u

[thomas-maeder]

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.

[JoshuaGreen]

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+1 pieces 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.

[thomas-maeder]

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).

[thomas-maeder]

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.

[JoshuaGreen]

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.