Java geeks in the house?

[RepoMan]

Are there any?

I'm running Thing Game 2 based off the calculations of my random-strategy-Thing-game-simulator. It's written in Java. No one but me has checked the code. This obviously means it could be rife with bugs.

Is there anyone out there who
- knows Java 5
- knows the Thing game rules
- is at all interested in checking my code?

It's not much -- three files,
ThingGameCalculator.java (149 lines, incl. comments)
ThingGameState.java (210 lines, incl. comments)
ThingGameRules.java (58 lines, incl. comments)

Please advise. Cheers!

[XPav]

I'll check it. Even though I'm not a java guy, I mean, it's pretty much just logic.

[fire]

Although I pretend I don't know Java I'll be glad to browse it.

[RepoMan]

OK, I'm going to severely abuse the forum and just post the files here, since it's just us nerds.

I commented a bunch, let me know if more's needed.

ThingGameRules.java:
/**
* The game rules.
*/
class ThingGameRules {
public ThingGameRules (int initialHumans, int initialThings, int maxHumanTestsPerDay, int bonusTestsPerDay) {
this.initialHumans = initialHumans;
this.initialThings = initialThings;
this.maxHumanTestsPerDay = maxHumanTestsPerDay;
this.bonusTestsPerDay = bonusTestsPerDay;
}

private int initialHumans;
private int initialThings;

private int maxHumanTestsPerDay;
private int bonusTestsPerDay;

public int getInitialHumans() {
return initialHumans;
}

public int getInitialThings() {
return initialThings;
}

public int getMaxHumanTestsPerDay() {
return maxHumanTestsPerDay;
}

public int getBonusTestsPerDay() {
return bonusTestsPerDay;
}


public boolean isGameOver (ThingGameState state) {
return state.getCurrentThings() == 0 ||
(state.getCurrentHumans() < state.getCurrentThings());
}

public boolean didHumansWin (ThingGameState state) {
assert isGameOver(state);
return state.getCurrentThings() == 0;
}

public boolean isDayOver (ThingGameState state) {
// if we are under our max. humans tested, we're not done
if (state.getHumanTestsPassedSoFarToday() < getMaxHumanTestsPerDay()) {
return false;
}

// if we killed no things, then we get some bonus tests
if (state.getThingsKilledSoFarToday() == 0) {
return state.getHumanTestsPassedSoFarToday() >= maxHumanTestsPerDay + bonusTestsPerDay;
}

return true;
}
}

[RepoMan]

ThingGameState.java:
import java.util.Map;
import java.util.HashMap;

/**
* The game state.
*/
class ThingGameState implements Comparable {
public ThingGameState (ThingGameRules rules, int currentHumans, int currentThings, int humanTestsPassedSoFarToday, int thingsKilledSoFarToday) {
this.rules = rules;
this.currentHumans = currentHumans;
this.currentThings = currentThings;
this.humanTestsPassedSoFarToday = humanTestsPassedSoFarToday;
this.thingsKilledSoFarToday = thingsKilledSoFarToday;
}

private ThingGameRules rules;
private int currentHumans;
private int currentThings;
private int humanTestsPassedSoFarToday;
private int thingsKilledSoFarToday;

public int getCurrentHumans() {
return currentHumans;
}

public int getCurrentThings() {
return currentThings;
}

public int getHumanTestsPassedSoFarToday() {
return humanTestsPassedSoFarToday;
}

public int getThingsKilledSoFarToday() {
return thingsKilledSoFarToday;
}

/**
* Interned instance map.
*/
private static Map<ThingGameState, ThingGameState> internedStates = new HashMap<ThingGameState, ThingGameState>();

/**
* Intern ThingGameState instances. Critical for memoization.
*/
public ThingGameState intern () {
if (internedStates.containsKey(this)) {
return internedStates.get(this);
} else {
internedStates.put(this, this);
return this;
}
}

public int hashCode() {
return getCurrentHumans() * 10000 + getCurrentThings() * 100 + getHumanTestsPassedSoFarToday();
}

public boolean equals (Object o) {
ThingGameState state = (ThingGameState)o;
return state.getCurrentHumans() == getCurrentHumans() &&
state.getCurrentThings() == getCurrentThings() &&
state.getHumanTestsPassedSoFarToday() == getHumanTestsPassedSoFarToday() &&
state.getThingsKilledSoFarToday() == getThingsKilledSoFarToday();
}

public int compareTo(Object o) {
ThingGameState state = (ThingGameState)o;
return !rules.isGameOver(this) && rules.isGameOver(state) ? -1 :
rules.isGameOver(this) && !rules.isGameOver(state) ? 1 :
rules.isGameOver(this) && rules.isGameOver(state) && rules.didHumansWin(this) && !rules.didHumansWin(state) ? -1 :
rules.isGameOver(this) && rules.isGameOver(state) && !rules.didHumansWin(this) && rules.didHumansWin(state) ? 1 :
getCurrentHumans() < state.getCurrentHumans() ? -1 :
getCurrentHumans() > state.getCurrentHumans() ? 1 :
getCurrentThings() < state.getCurrentThings() ? -1 :
getCurrentThings() > state.getCurrentThings() ? 1 :
getHumanTestsPassedSoFarToday() < state.getHumanTestsPassedSoFarToday() ? -1 :
getHumanTestsPassedSoFarToday() > state.getHumanTestsPassedSoFarToday() ? 1 :
getThingsKilledSoFarToday() < state.getThingsKilledSoFarToday() ? -1 :
getThingsKilledSoFarToday() > state.getThingsKilledSoFarToday() ? 1 :
0;
}

/**
* Maps ultimate outcomes -- e.g. end-game states that are transitively reachable from this state --
* into float probabilities (0f to 1f). All probabilities in any game state's outcome map will sum to 1.
*/
private Map<ThingGameState, Float> outcomeMap = null;

/**
* Get the outcome map dependent from this game state. Memoize the result.
*/
public Map<ThingGameState, Float> getOutcomeMap (boolean printTree, int depth) {
// handle actual memoization for states we re-visit
ThingGameState state = intern();
if (state != this) {
return state.getOutcomeMap(printTree, depth);
}

if (outcomeMap != null) {
return outcomeMap;
}

outcomeMap = new HashMap<ThingGameState, Float>();

if (printTree) {
for (int i = 0; i < depth; i++) {
System.out.print(" ");
}
System.out.print("Evaluating " + this + "... ");
}

// Is the game over? If so, then our outcome map is empty. If not, then go on.
if (rules.isGameOver(state)) {

// then this is its own outcome, e.g. endstate.
outcomeMap.put(this, 1f);
if (printTree) System.out.println("it's an end state.");

} else {

// Is the day over? If so, then our outcomes are the same as tomorrow's outcomes.
if (rules.isDayOver(state)) {

// tomorrow: one more thing, and one less human, and no tests taken.

if (printTree) System.out.println("it's the end of a day.");

outcomeMap = new ThingGameState(rules,
getCurrentHumans() - 1,
getCurrentThings() + 1,
0,
0)
.getOutcomeMap(printTree, depth);

} else {

// The odds of a thing test are equal to the number of things divided by (the number of remaining players
// less the number of human tests today, since you never retest a known human from today).
float probabilityOfThingTest = (float)(getCurrentThings()) /
(float)(getCurrentThings() + getCurrentHumans() - getHumanTestsPassedSoFarToday());

if (printTree) System.out.println("there's more testing to be done!");

// The outcomes for us are equal to the sum of the outcomes of the two test possibilities.
// This would be like one line of Haskell.

Map<ThingGameState, Float> thingTestedOutcomes = new ThingGameState(rules,
getCurrentHumans(),
getCurrentThings() - 1,
getHumanTestsPassedSoFarToday(),
getThingsKilledSoFarToday() + 1)
.getOutcomeMap(printTree, depth + 1);

Map<ThingGameState, Float> humanTestedOutcomes = new ThingGameState(rules,
getCurrentHumans(),
getCurrentThings(),
getHumanTestsPassedSoFarToday() + 1,
getThingsKilledSoFarToday())
.getOutcomeMap(printTree, depth + 1);

// now sum the maps appropriately.
addProbabilityInto(thingTestedOutcomes, probabilityOfThingTest, outcomeMap);
addProbabilityInto(humanTestedOutcomes, 1 - probabilityOfThingTest, outcomeMap);

if (printTree) {
for (ThingGameState finalOutcome : outcomeMap.keySet()) {
for (int i = 0; i < depth; i++) {
System.out.print(" ");
}
System.out.println("Ultimate outcome is " + finalOutcome + " with probability " + outcomeMap.get(finalOutcome));
}
}
}
}

return outcomeMap;
}

/**
* Multiply this outcome map into ours.
* Static method to avoid confusion about exactly what is being side-effected.
*/
private static void addProbabilityInto(Map<ThingGameState, Float> outcomeSourceMap,
float sourceProbability,
Map<ThingGameState, Float> outcomeDestMap) {

for (ThingGameState state : outcomeSourceMap.keySet()) {

if (outcomeDestMap.containsKey(state)) {

// this state is now just that much more probable
float totalProbability = sourceProbability * outcomeSourceMap.get(state) + outcomeDestMap.get(state);
outcomeDestMap.put(state, totalProbability);

} else {

// first time we've realized this could happen
outcomeDestMap.put(state, sourceProbability * outcomeSourceMap.get(state));

}
}
}

/**
* Tostring.
*/
public String toString () {
return "[" + getCurrentHumans() + " human" + (getCurrentHumans() == 1 ? "" : "s") + ", " +
getCurrentThings() + " thing" + (getCurrentThings() == 1 ? "" : "s") + ", " +
getHumanTestsPassedSoFarToday() + " human" + (getHumanTestsPassedSoFarToday() == 1 ? "" : "s") + " tested today, " +
getThingsKilledSoFarToday() + " thing" + (getThingsKilledSoFarToday() == 1 ? "" : "s") + " killed today]";
}
}

[RepoMan]

ThingGameCalculator.java:
import java.util.*;

/**
* Calculates the odds of winning a given Thing game.
*
* A Thing game ruleset is described by:
* - Number of initial humans
* - Number of initial Things
* - Maximum number of human-detecting tests per day
*
* A Thing game is described by:
* - Number of current humans
* - Number of current Things
* - Number of tests remaining in current day
*
* This program takes a game ruleset and an initial game state, and iterates through all possible outcomes from
* that initial game state. Each outcome is itself another game state. Each game state gets the probability of
* all its "ultimate outcomes" (e.g. all its game-ending states) cached internally in a hashtable.
*
* This means that whenever a later game state branches to a game state whose ultimate outcomes were already
* calculated, it can just use the cached results to calculate its own ultimate outcomes, multiplying the
* branch's ultimate outcomes by the probabilities of taking that particular branch. This memoization technique
* speeds the program up exponentially.
*
* Game states also define an ordering, for printout.
*
* This is all possible because all moves are random, hence game states have very little actual state! So there
* are not that many of them, and hence they memoize very well.
*
* To run it, put all files in single directory, then:
*
* javac *.java
* java -cp . ThingGameCalculator 4 19 1 10 2 2
*
* to test all possible games with between 4 and 19 humans, and between 1 and 10 things.
*
* Or, change line 55 to "boolean verbose = true" and do:
*
* java -cp . ThingGameCalculator 8 8 2 2 1 2
*
* to see *all* the calculations for a game with (for example) 8 humans, 2 things, 2 human-detecting test, and 2 bonus tests.
*/
public class ThingGameCalculator {


public static void main (String[] argv) {


int minInitialHumans = Integer.parseInt(argv[0]);
int maxInitialHumans = Integer.parseInt(argv[1]);
int minInitialThings = Integer.parseInt(argv[2]);
int maxInitialThings = Integer.parseInt(argv[3]);
int maxHumanTestsPerDay = Integer.parseInt(argv[4]);
int bonusTestsPerDay = Integer.parseInt(argv[5]);
boolean verbose = false;

System.out.println("InitialHumans,InitialThings,HumanTestsPerDay,Bonus TestsPerDay,HumanWinProbability,AverageHumansLeftA live,TotalProbability,NumberOutcomes");

for (int h = minInitialHumans; h <= maxInitialHumans; h++) {
for (int t = minInitialThings; t <= maxInitialThings; t++) {

if (t >= h) {

System.out.println(h + "," + t + "," + maxHumanTestsPerDay + "," + bonusTestsPerDay + ",0,0,100,0");

} else {

GameResults results = runSingleGameOdds(h, t, maxHumanTestsPerDay, bonusTestsPerDay, verbose);
System.out.println(h + "," + t + "," + maxHumanTestsPerDay + "," + bonusTestsPerDay + "," +
results.getHumanWinProbability() + "," +
results.getAverageHumansLeftAlive() + "," +
results.getTotalProbability() + "," +
results.getNumberOutcomes());

}
}
}

}

private static GameResults runSingleGameOdds(int initialHumans,
int initialThings,
int maxHumanTestsPerDay,
int bonusHumanTestsPerDay,
boolean verbose) {
ThingGameRules rules = new ThingGameRules(initialHumans, initialThings, maxHumanTestsPerDay, bonusHumanTestsPerDay);

Map<ThingGameState, Float> outcomeMap =
new ThingGameState(rules, initialHumans, initialThings, 0, 0).getOutcomeMap(verbose, 0);

// Print all the outcomes in sorted order.
List<ThingGameState> outcomes = new ArrayList<ThingGameState>(outcomeMap.keySet());
Collections.sort(outcomes);

float humansWinProbability = 0;
float totalProbability = 0;
float averageHumansLeftAlive = 0;
for (ThingGameState outcome : outcomes) {
assert rules.isGameOver(outcome);
float probability = outcomeMap.get(outcome);

if (verbose) System.out.println("Endgame " + outcome + " (humans " + (rules.didHumansWin(outcome) ? "win!" : "lose!") + ") has probability " + (probability * 100) + "%");

totalProbability += probability;
humansWinProbability += rules.didHumansWin(outcome) ? probability : 0;
averageHumansLeftAlive += rules.didHumansWin(outcome) ? probability * outcome.getCurrentHumans() : 0;
}
averageHumansLeftAlive *= 1 / humansWinProbability;

if (verbose) System.out.print("For game with " + initialHumans + " initial humans, " + initialThings + " initial things, and " + maxHumanTestsPerDay + " human tests per day: ");
if (verbose) System.out.println("humans win with probability " + humansWinProbability * 100 + "% (average humans left alive: " + averageHumansLeftAlive + ")");
if (verbose) System.out.println("(Total probability is " + totalProbability * 100 + "%, number of outcomes " + outcomes.size() + ")");

return new GameResults(humansWinProbability, averageHumansLeftAlive, totalProbability, outcomes.size());
}

private static final class GameResults {
// probability of human win
float humanWinProbability;
float averageHumansLeftAlive;
int numberOutcomes;

public float getHumanWinProbability() {
return humanWinProbability;
}

public float getAverageHumansLeftAlive() {
return averageHumansLeftAlive;
}

public float getTotalProbability() {
return totalProbability;
}
public int getNumberOutcomes () {
return numberOutcomes;
}

float totalProbability;

public GameResults(float humanWinProbability,
float averageHumansLeftAlive,
float totalProbability,
int numberOutcomes) {
this.humanWinProbability = humanWinProbability;
this.averageHumansLeftAlive = averageHumansLeftAlive;
this.totalProbability = totalProbability;
this.numberOutcomes = numberOutcomes;
}
}
}

[RepoMan]

And here's the output from a run with arguments "3 3 2 2 2 1" (3 humans, 2 things, 2 normal human tests, 1 bonus test) and verbose=true:
InitialHumans,InitialThings,HumanTestsPerDay,Bonus TestsPerDay,HumanWinProbability,AverageHumansLeftA live,TotalProbability,NumberOutcomes
Evaluating [3 humans, 2 things, 0 humans tested today, 0 things killed today]... there's more testing to be done!
Evaluating [3 humans, 1 thing, 0 humans tested today, 1 thing killed today]... there's more testing to be done!
Evaluating [3 humans, 0 things, 0 humans tested today, 2 things killed today]... it's an end state.
Evaluating [3 humans, 1 thing, 1 human tested today, 1 thing killed today]... there's more testing to be done!
Evaluating [3 humans, 0 things, 1 human tested today, 2 things killed today]... it's an end state.
Evaluating [3 humans, 1 thing, 2 humans tested today, 1 thing killed today]... it's the end of a day.
Evaluating [2 humans, 2 things, 0 humans tested today, 0 things killed today]... there's more testing to be done!
Evaluating [2 humans, 1 thing, 0 humans tested today, 1 thing killed today]... there's more testing to be done!
Evaluating [2 humans, 0 things, 0 humans tested today, 2 things killed today]... it's an end state.
Evaluating [2 humans, 1 thing, 1 human tested today, 1 thing killed today]... there's more testing to be done!
Evaluating [2 humans, 0 things, 1 human tested today, 2 things killed today]... it's an end state.
Evaluating [2 humans, 1 thing, 2 humans tested today, 1 thing killed today]... it's the end of a day.
Evaluating [1 human, 2 things, 0 humans tested today, 0 things killed today]... it's an end state.
Ultimate outcome is [2 humans, 0 things, 1 human tested today, 2 things killed today] with probability 0.5
Ultimate outcome is [1 human, 2 things, 0 humans tested today, 0 things killed today] with probability 0.5
Ultimate outcome is [2 humans, 0 things, 0 humans tested today, 2 things killed today] with probability 0.33333334
Ultimate outcome is [2 humans, 0 things, 1 human tested today, 2 things killed today] with probability 0.3333333
Ultimate outcome is [1 human, 2 things, 0 humans tested today, 0 things killed today] with probability 0.3333333
Evaluating [2 humans, 2 things, 1 human tested today, 0 things killed today]... there's more testing to be done!
Evaluating [2 humans, 2 things, 2 humans tested today, 0 things killed today]... there's more testing to be done!
Evaluating [2 humans, 2 things, 3 humans tested today, 0 things killed today]... it's the end of a day.
Evaluating [1 human, 3 things, 0 humans tested today, 0 things killed today]... it's an end state.
Ultimate outcome is [1 human, 3 things, 0 humans tested today, 0 things killed today] with probability 0.0
Ultimate outcome is [1 human, 2 things, 0 humans tested today, 0 things killed today] with probability 1.0
Ultimate outcome is [1 human, 3 things, 0 humans tested today, 0 things killed today] with probability 0.0
Ultimate outcome is [2 humans, 0 things, 1 human tested today, 2 things killed today] with probability 0.33333334
Ultimate outcome is [1 human, 2 things, 0 humans tested today, 0 things killed today] with probability 0.6666666
Ultimate outcome is [1 human, 3 things, 0 humans tested today, 0 things killed today] with probability 0.0
Ultimate outcome is [2 humans, 0 things, 0 humans tested today, 2 things killed today] with probability 0.16666667
Ultimate outcome is [2 humans, 0 things, 1 human tested today, 2 things killed today] with probability 0.3333333
Ultimate outcome is [1 human, 2 things, 0 humans tested today, 0 things killed today] with probability 0.49999997
Ultimate outcome is [1 human, 3 things, 0 humans tested today, 0 things killed today] with probability 0.0
Ultimate outcome is [2 humans, 0 things, 0 humans tested today, 2 things killed today] with probability 0.111111104
Ultimate outcome is [2 humans, 0 things, 1 human tested today, 2 things killed today] with probability 0.2222222
Ultimate outcome is [3 humans, 0 things, 1 human tested today, 2 things killed today] with probability 0.33333334
Ultimate outcome is [1 human, 2 things, 0 humans tested today, 0 things killed today] with probability 0.33333328
Ultimate outcome is [1 human, 3 things, 0 humans tested today, 0 things killed today] with probability 0.0
Ultimate outcome is [3 humans, 0 things, 0 humans tested today, 2 things killed today] with probability 0.25
Ultimate outcome is [2 humans, 0 things, 0 humans tested today, 2 things killed today] with probability 0.08333333
Ultimate outcome is [2 humans, 0 things, 1 human tested today, 2 things killed today] with probability 0.16666664
Ultimate outcome is [3 humans, 0 things, 1 human tested today, 2 things killed today] with probability 0.25
Ultimate outcome is [1 human, 2 things, 0 humans tested today, 0 things killed today] with probability 0.24999997
Evaluating [3 humans, 2 things, 1 human tested today, 0 things killed today]... there's more testing to be done!
Evaluating [3 humans, 2 things, 2 humans tested today, 0 things killed today]... there's more testing to be done!
Evaluating [3 humans, 2 things, 3 humans tested today, 0 things killed today]... it's the end of a day.
Evaluating [2 humans, 3 things, 0 humans tested today, 0 things killed today]... it's an end state.
Ultimate outcome is [1 human, 3 things, 0 humans tested today, 0 things killed today] with probability 0.0
Ultimate outcome is [2 humans, 0 things, 0 humans tested today, 2 things killed today] with probability 0.11111112
Ultimate outcome is [2 humans, 0 things, 1 human tested today, 2 things killed today] with probability 0.22222221
Ultimate outcome is [2 humans, 3 things, 0 humans tested today, 0 things killed today] with probability 0.3333333
Ultimate outcome is [1 human, 2 things, 0 humans tested today, 0 things killed today] with probability 0.3333333
Ultimate outcome is [1 human, 3 things, 0 humans tested today, 0 things killed today] with probability 0.0
Ultimate outcome is [2 humans, 0 things, 0 humans tested today, 2 things killed today] with probability 0.11111111
Ultimate outcome is [2 humans, 0 things, 1 human tested today, 2 things killed today] with probability 0.22222221
Ultimate outcome is [3 humans, 0 things, 1 human tested today, 2 things killed today] with probability 0.16666667
Ultimate outcome is [2 humans, 3 things, 0 humans tested today, 0 things killed today] with probability 0.16666666
Ultimate outcome is [1 human, 2 things, 0 humans tested today, 0 things killed today] with probability 0.3333333
Ultimate outcome is [1 human, 3 things, 0 humans tested today, 0 things killed today] with probability 0.0
Ultimate outcome is [3 humans, 0 things, 0 humans tested today, 2 things killed today] with probability 0.1
Ultimate outcome is [2 humans, 0 things, 0 humans tested today, 2 things killed today] with probability 0.1
Ultimate outcome is [2 humans, 0 things, 1 human tested today, 2 things killed today] with probability 0.19999999
Ultimate outcome is [3 humans, 0 things, 1 human tested today, 2 things killed today] with probability 0.20000002
Ultimate outcome is [2 humans, 3 things, 0 humans tested today, 0 things killed today] with probability 0.1
Ultimate outcome is [1 human, 2 things, 0 humans tested today, 0 things killed today] with probability 0.29999998
Endgame [2 humans, 0 things, 0 humans tested today, 2 things killed today] (humans win!) has probability 10.0%
Endgame [2 humans, 0 things, 1 human tested today, 2 things killed today] (humans win!) has probability 19.999998%
Endgame [3 humans, 0 things, 0 humans tested today, 2 things killed today] (humans win!) has probability 10.0%
Endgame [3 humans, 0 things, 1 human tested today, 2 things killed today] (humans win!) has probability 20.000002%
Endgame [1 human, 2 things, 0 humans tested today, 0 things killed today] (humans lose!) has probability 29.999998%
Endgame [1 human, 3 things, 0 humans tested today, 0 things killed today] (humans lose!) has probability 0.0%
Endgame [2 humans, 3 things, 0 humans tested today, 0 things killed today] (humans lose!) has probability 10.0%
For game with 3 initial humans, 2 initial things, and 2 human tests per day: humans win with probability 60.000004% (average humans left alive: 2.5)
(Total probability is 100.0%, number of outcomes 7)
3,2,2,1,0.6,2.5,1.0,7