Question: Units in wc3 has range of attack damage and it isn't consistent most of the time e.g critical hit and so on. Yet, they managed to make a replay that could even reconstruct bugs scene. I am just curious how they do it. It could be useful for fighting games or perhaps to easily submit evidence of recurring bugs. The best part is it's not even a big of a file and even could be used on a customize games. Come back to the title, how did they do it?

Answer: 
They would include that damage (or the data needed to get to the damage value like the RNG state) in the replay information. Each attack is only a numerical value of the damage value, the id of the attacker and the id of the victim. That is 3 values with a limitation on number of units those IDs could be a single byte each.

Crucial information is often RNG seeds, player input and (most importantly) fully deterministic implementation. Anything not deterministic would otherwise need to be included in the replay stream. A perfect implementation would use the "replay" engine for actual real-time play. Where input is nothing but the RNG seed and player input as it comes in.

For scrubbing efficiency and a failsafe you can include full board snapshots, these would contain the location of all units and their health, position of the buildings and unit building progress, etc.
I found few documents, that describe the replay file, so from those you can figure out what kind of model they are using for commands etc.

They have to use some kind of [command pattern](http://en.wikipedia.org/wiki/Command_pattern). That means, that each command issued is capsuled in instance of command (or ICommand ). Thus, if everything in the game happens with those commands, you could just push them to the engine and see previous actions replayed ( ofcourse, initial position of everything has to be the same ). 

This method is quite like the one that Half life uses for HLTV, it's simple, compact and efficient way to accomplish the streaming, replaying and undoing actions.

I found these documents, that you might be interested:

* [Fan made page about WC3 replay format](http://w3g.deepnode.de/)
* [Replay format description](http://w3g.deepnode.de/files/w3g_format.txt)
* [Replay actions description](http://w3g.deepnode.de/files/w3g_actions.txt)
* [Another format description](https://gist.github.com/dengzhp/1185519)