Comment by GolfyMcG

If it wasn't so late I might get into it but I think this could be dramatically improved by just detecting whether a piece is currently underneath another piece. Assuming you can eliminate those as possible choices for the random select process, you would avoid the issue of iterating through a bunch of pieces that can't even be moved during the late game!