Java geeks in the house?

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!

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

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

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;
    }
}

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]";
    }
}

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,BonusTestsPerDay,HumanWinProbability,AverageHumansLeftAlive,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;
        }
    }
}

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,BonusTestsPerDay,HumanWinProbability,AverageHumansLeftAlive,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