That is perfect, why on earth did that never come to me?
Without knowing more about the game it's hard to suggest something.
Maybe a system like the one in Battle Masters
Assign the pieces from one player with the numbers 1-4, the pieces from the other player with the numbers 5-8.
Take one of these decks and draw the top card to see which piece may move. If you draw the 9, simply draw another card. Repeat until the deck is empty.