first off any variables your storing you have to set to null or blank.
then take them back to the first frame or wherever it starts
Since we dont know the structure of your game or how you programmed it specifics are hard to pin down, however a good idea would be to have a frame at the beginning of your movie that actually handles all the re-setting of variables, clips, etc. Then when you want to re-set your game you can just shoot them to that frame.
(the frame can really be at the end or the beginning, as long as when its done it sends the playhead to the appropriate starting frame) Also you can label the frame something like "reset" and then just go