thomas-maeder/popeye

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:

  1. Do you think we're hitting some sort of loop in the solving, causing us to infinitely recurse?
  2. Alternatively, are we simply hitting an internal Popeye limit? en_passant_multistep_over has dimension maxply+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:

  1. If we can rigorously bound the number of needed steps then we should update the dimension(s) accordingly.
  2. 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 and exit 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. 😛