[thejeff]

There are no simple non-deterministic pseudorandom generators.
In fact pseudo-random is pretty much equivalent to deterministic.

I believe Dominions does use a pseudo random generator not a pregenerated table.

The simplest implementation that comes to mind for doing the battles in parallel would be for each thread to work with it's own RNG and for the main process to generate the seeds for each battle before spinning off the thread.