Agreed with tanoshimi.
By the sound of it, your server should produce the replay, and the players will have a C2 replay viewer (that allow them as well some "programming" of the battles through the interface you'll have determined).
The server will serve the replay either in Json (for arrays
) or even in XML
This way you ensure both clients will replay the very same sequence, having had the randomness calculated on the server side to ensure the same result for both players.
The fact is the clients should merely be replay viewers with an interface to allow each player to determine their next moves (sends the infos to the server).