3

I'm going to further expand a FEN validation function I have been working on for some time to include illegal pawn formations such that:

... for example white pawns could never be on a2, a3, and b2; there is no way a pawn could be on both a3 and b2. (source)

This particular test doesn't require to take opponent missing material into consideration (it could, but I have that on a separate test to check every column with multiple pawns and determine the minimum missing material the opponent should have, but that test is different, I only want to focus on this other test assuming infinite material can be used to reach those positions).

So far, my approach has been to draw a triangle from any pawn (excluding the ones that sit on the starting rank, which wouldn't allow a triangle to be drawn) all the way to the starting rank, then counting all the pawns that would fit on the base line of the triangle (starting rank). In the case the triangle goes out of bounds, those pawns are not counted:

enter image description here

That amount of pawns on the bottom of the triangle are the upper exclusive limit that pawns could then appear anywhere inside the triangle (because the test is applied to each pawn and each one will draw their own triangles and because the test is a generalized "no invalid pawn structures?", as in, all or nothing, it is safe to give big triangles with cluttered pawns a pass, since later on, the pawns inside will undergo the same test).

Example from the left image with limit of 3, there should be 0-2 to be a legal pawn structure.

Will this solution always work or there are times where this limit will be incorrectly generated? Can this be simplified further using a different reasoning or methods?

Any ideas, feedback, alternative solutions are appreciated.

Improve this question

1 Answer 1

Reset to default
3

There is at least one case where your method will fail: pawns on f2, g3, h2 and h3.

enter image description here

The structure is illegal, but drawing triangles from every pawn will not show this. To catch this, you'd have to draw the triangle from every square of the chessboard (h4 in this case demonstrates the illegality).

So as you said, draw triangles, but instead of starting from pawns, draw them from every square on the board. (For white, it actually suffices to try every square from the 3rd to the 8th rank.)

Improve this answer
3
  • awesome catch, I just need to adjust the rules a bit then, instead of always decreasing the limit by 1 (because it always had an ally pawn on the top square) I just need to take that limit as it is, but then take into consideration the top square to count ally pawns there too.
    – ajax333221
    Commented Aug 3, 2019 at 21:36
  • 1
    worth saying that you don't need to try the squares that would allow a limit of 8 pawns (if you already have validation for that). With this information, you go testing only from triangles that have 7 or lower limits (so for the 8th rank you only need to test the a8 and h8 squares), this reduces the squares in 12 (from 48 to 36)
    – ajax333221
    Commented Aug 3, 2019 at 23:10
  • also for even further optimization, avoid searching inside triangles that have limits greater or equal that the amount of pawns in play for that side (best to have a map of the 36 triangles distributed by their limits)
    – ajax333221
    Commented Aug 4, 2019 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.