SeriesCapture: a sufficiently long series may overflow the memory of pawns capturable en passant
thomas-maeder opened this issue · 6 comments
...
h=1 2 + 62
ProteanChess
SeriesCapture
pieces/walks/pawns/en_passant.c:344:11: runtime error: index 1003 out of bounds for type 'square[1003]' (aka 'int[1003]')
#0 0x5bd9c3f4969c in en_passant_is_capture_possible_to (/home/thomas/workspace/popeye/develop/py+0x1eb69c) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#1 0x5bd9c3f47189 in pawns_generate_ep_capture_move (/home/thomas/workspace/popeye/develop/py+0x1e9189) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#2 0x5bd9c3f46cae in pawn_generate_moves (/home/thomas/workspace/popeye/develop/py+0x1e8cae) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#3 0x5bd9c3e60e4b in dispatch (/home/thomas/workspace/popeye/develop/py+0x102e4b) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#4 0x5bd9c3f15017 in castling_generator_generate_castling (/home/thomas/workspace/popeye/develop/py+0x1b7017) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#5 0x5bd9c3e60e57 in dispatch (/home/thomas/workspace/popeye/develop/py+0x102e57) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#6 0x5bd9c3f133ba in non_king_move_generator_solve (/home/thomas/workspace/popeye/develop/py+0x1b53ba) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#7 0x5bd9c3e60e41 in dispatch (/home/thomas/workspace/popeye/develop/py+0x102e41) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#8 0x5bd9c3e60d06 in dispatch (/home/thomas/workspace/popeye/develop/py+0x102d06) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#9 0x5bd9c3e621c8 in dispatch (/home/thomas/workspace/popeye/develop/py+0x1041c8) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#10 0x5bd9c3f24b42 in defense_adapter_solve (/home/thomas/workspace/popeye/develop/py+0x1c6b42) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#11 0x5bd9c3e60fc5 in dispatch (/home/thomas/workspace/popeye/develop/py+0x102fc5) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#12 0x5bd9c3e60e29 in dispatch (/home/thomas/workspace/popeye/develop/py+0x102e29) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#13 0x5bd9c3f2643d in goal_immobile_reached_tester_solve (/home/thomas/workspace/popeye/develop/py+0x1c843d) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#14 0x5bd9c3e62339 in dispatch (/home/thomas/workspace/popeye/develop/py+0x104339) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#15 0x5bd9c3e6110f in dispatch (/home/thomas/workspace/popeye/develop/py+0x10310f) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#16 0x5bd9c3e60d12 in dispatch (/home/thomas/workspace/popeye/develop/py+0x102d12) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#17 0x5bd9c3f25301 in goal_reached_tester_solve (/home/thomas/workspace/popeye/develop/py+0x1c7301) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#18 0x5bd9c3e610b1 in dispatch (/home/thomas/workspace/popeye/develop/py+0x1030b1) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#19 0x5bd9c3f1cb63 in end_of_branch_goal_solve (/home/thomas/workspace/popeye/develop/py+0x1beb63) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#20 0x5bd9c3e60cd8 in dispatch (/home/thomas/workspace/popeye/develop/py+0x102cd8) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#21 0x5bd9c3e6116e in dispatch (/home/thomas/workspace/popeye/develop/py+0x10316e) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#22 0x5bd9c3f1cea3 in help_move_played_solve (/home/thomas/workspace/popeye/develop/py+0x1beea3) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#23 0x5bd9c3e622a4 in dispatch (/home/thomas/workspace/popeye/develop/py+0x1042a4) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#24 0x5bd9c3eb5777 in series_capture_journal_fixer_solve (/home/thomas/workspace/popeye/develop/py+0x157777) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#25 0x5bd9c3eb5777 in series_capture_journal_fixer_solve (/home/thomas/workspace/popeye/develop/py+0x157777) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#26 0x5bd9c3eb5777 in series_capture_journal_fixer_solve (/home/thomas/workspace/popeye/develop/py+0x157777) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#27 0x5bd9c3eb5777 in series_capture_journal_fixer_solve (/home/thomas/workspace/popeye/develop/py+0x157777) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
...
#54 0x5bd9c3eb5777 in series_capture_journal_fixer_solve (/home/thomas/workspace/popeye/develop/py+0x157777) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
#55 0x5bd9c3e627a3 in dispatch (/home/thomas/workspace/popeye/develop/py+0x1047a3) (BuildId: c5c1ccddfb328eb8c4feac677f527f121723bd5c)
...
Without the full problem it's hard for me to follow along here. My naïve questions:
- Do you think we're hitting some sort of loop in the solving, causing us to infinitely recurse?
- Alternatively, are we simply hitting an internal Popeye limit?
en_passant_multistep_over
has dimensionmaxply+1
, which would probably be OK except that I guess in SeriesCapture we can have multiple steps per ply.
If (1) then we should find a way to detect the loop. If (2) then we have another split:
- If we can rigorously bound the number of needed steps then we should update the dimension(s) accordingly.
- If we can't, or if the bound is too large to be reasonable, then we should just accept this limitation and put in a run-time check (not an
assert
) so that we can notify the user andexit
if this limit is crossed.
(I suppose there's also
3. This is the result of some other type of bug.
)
I couldn't give the example because it is an unpublished problem which I know with almost 100% certainty was correct.
Looks like the answer was (3) and my thoughts could be safely ignored.
Indeed.
If a capture series ended in a pawn double step, Popeye remembered the ep potential by
- increasing en_passant_top for the ply
- storing the possition of the capturable pawn
After the double step, the same pawn's single step was tried, but the en passant potential was not forgotten.
Eventually, en_passant_top would reach a value that caused undefined behavior when it was used as an array index.
It seems that you found a fairly interesting bug, and you showed great foresight in developing a testcase. 😛