Partially re-create Risk-like game based on incomplete log files

Question

I'm trying to re-create this conquerclub (Risk-like) game:

http://conquerclub.barrycarter.info/ONEOFF/7460216.html

In other words, I want to know who owned each territory at each point in time, and how many troops they had on that territory. My primary source of information is the Game Log. Notes:

% It's not in the Game Log, but all territories start w/ 3 troops.

% Since we know the territory owners at the end of the game, and the Game Log mentions all owner changes, determining territory owners at any point in time is easy.

% The challenge is to find the number of troops on a territory at a given time.

% The Game Log gives information on troop deployment, reinforcement, and conquest.

% However, the Game Log is incomplete. Suppose territory X attacks territory Y unsuccessfully, but both territories lose troops in the process. The Game Log will not mention this.

% It's probably not possible (in general) to find the exact number of troops on a territory at a given time, so I'm looking for a range.

% I tried feeding the data to Mathematica as a series of inequalities, but as the manual warns, the computation time increases exponentially with the number of inequalities. Even with a fairly small number of inequalities, it hangs. Plus, I'm not convinced Mathematica is the right tool here.

% Any thoughts? Another example is: http://conquerclub.barrycarter.info/ONEOFF/7562013.html

% I know about http://userscripts.org/scripts/show/83035 but that only tracks \ owners, not number of troops.

Answer 1

You could make use of Prolog's constraint programming (specifically, CLP/FD). It would require you to encode all rules in Prolog, which might be a non-trivial task. However Prolog would be able then to show you all possible valid (legal in terms of encoded rules) ways of playing such game, or just show ranges of possible values.

Also, while CLP/FD in Prolog sometimes is quite fast, it might be difficult to use it to make solving your problem quickly. Most free solvers have many quirks.

Again, I think this is a nontrivial task, and even greater if you haven't programmed in Prolog earlier. But I am pretty sure this would give you answers you seek.