Finally having my first free weekend in a few months I'm almost done with my C implementation. The data structures I've come up with aren't that fancy or complicated but are pretty efficient. Once I got out of the mental dead end of the "deck of cards" actually behaving like a deck of cards with a 'top of deck' and the like I've been able to arrange the cards such that I need very few operations to save the current state and randomise the game state for the Monte Carlo playouts..
As you'd expect it's blazingly fast compared to my Python implementation, on the order of several hundred times speed up, possibly more. Once I'm done with this I'll be interested to go back to the Python code and implement the same data structures in Python - once I'm no longer allocating and freeing memory all over the place I wonder how fast I can get the Python code to run.