From 9b5f3648eda004f85c020fc7989c12557d08489a Mon Sep 17 00:00:00 2001 From: Jannis Harder Date: Tue, 21 Jun 2011 03:45:44 +0200 Subject: Completed comments of TurnLogic git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@535 72836036-5685-4462-b002-a69064685172 --- src/jrummikub/ai/TurnLogic.java | 412 ++++++++++++++++++++++++++++++++++------ 1 file changed, 350 insertions(+), 62 deletions(-) (limited to 'src/jrummikub') diff --git a/src/jrummikub/ai/TurnLogic.java b/src/jrummikub/ai/TurnLogic.java index 214288a..26318cf 100644 --- a/src/jrummikub/ai/TurnLogic.java +++ b/src/jrummikub/ai/TurnLogic.java @@ -71,7 +71,7 @@ public class TurnLogic { * Create a copy of a state * * @param state - * the state to copy + * the state to copy */ public State(State state) { for (StoneState stone : state.stones) { @@ -84,7 +84,7 @@ public class TurnLogic { * Adds stones to be considered in the state * * @param stone - * the stone to add + * the stone to add */ public void add(StoneState stone) { stones.add(stone); @@ -98,7 +98,7 @@ public class TurnLogic { * Update the stones to consider the changes of the changed stones * * @throws Contradiction - * Is thrown if the changes contradict each other + * Is thrown if the changes contradict each other */ public void updateStones() throws Contradiction { checkJokerCount(); @@ -121,9 +121,9 @@ public class TurnLogic { * One step in the update process * * @throws Contradiction - * Is thrown if changes contradict each other + * Is thrown if changes contradict each other */ - public void updateStonesStep() throws Contradiction { + private void updateStonesStep() throws Contradiction { HashSet newChangedStones = new HashSet(); for (int i = 0; i < stoneCount; i++) { StoneState stone = stones.get(i); @@ -137,8 +137,8 @@ public class TurnLogic { } /** - * Returns whether the stones have a definite value and the state is thereby - * solved + * Returns whether the stones have a definite value and the state is + * thereby solved * * @return whether the state is solved */ @@ -152,10 +152,10 @@ public class TurnLogic { } /** - * Checks that not too many jokers are trying to be used + * Checks that not more jokers than available are needed * * @throws Contradiction - * Is thrown if too many jokers are trying to be used + * Is thrown if too many jokers are needed */ private void checkJokerCount() throws Contradiction { int jokersLeft = jokerIDs.size(); @@ -177,10 +177,10 @@ public class TurnLogic { } /** - * Checks that enough points and a high enough score are reached + * Checks that enough points and a high enough score can be reached * * @throws Contradiction - * Is thrown if points are too few or score is too low + * Is thrown if points are too few or score is too low */ public void checkScoreAndPoints() throws Contradiction { if (getPoints() < neededPoints) { @@ -224,8 +224,8 @@ public class TurnLogic { } /** - * Contains the remaining possible values, colors, positions, etc. a stone can - * take and its possible neighbors in a group or run + * Contains the remaining possible values, colors, positions, etc. a stone + * can take and its possible neighbors in a group or run */ private class StoneState { int id; @@ -243,11 +243,11 @@ public class TurnLogic { * Creates a new * * @param id - * the stone's identifier + * the stone's identifier * @param stone - * the stone + * the stone * @param table - * whether is on the table + * whether is on the table */ public StoneState(int id, Stone stone, boolean table) { this.id = id; @@ -268,7 +268,7 @@ public class TurnLogic { * Creates a copy * * @param stone - * the state to copy + * the state to copy */ public StoneState(StoneState stone) { this.id = stone.id; @@ -300,37 +300,85 @@ public class TurnLogic { } /** - * Returns whether the recent changes affect the stone + * Returns whether the recent changes could affect the stone * * @param changes - * the changes - * @return whether the stone is affected + * the changes + * @return whether the stone could be affected */ - public boolean isInterested(HashSet changes) { + private boolean isInterested(HashSet changes) { return !(Collections.disjoint(changes, leftRun) && Collections.disjoint(changes, rightRun) - && Collections.disjoint(changes, leftGroup) && Collections.disjoint( - changes, rightGroup)); + && Collections.disjoint(changes, leftGroup) && Collections + .disjoint(changes, rightGroup)); } - public > boolean lessThan(T a, T b) { + /** + * Compare two objects, returning true if either is null + * + * @param + * object's type + * @param a + * first object + * @param b + * second object + * @return whether a is less than b or either is null + */ + private > boolean lessThan(T a, T b) { return a == null || b == null || a.compareTo(b) < 0; } - public boolean same(T a, T b) { + /** + * Compare two objects, returning true if either is null + * + * @param + * object;s type + * @param a + * first object + * @param b + * second object + * @return whether a is less than b or either is null + */ + private boolean same(T a, T b) { return a == null || b == null || a.equals(b); } - public boolean step(Integer a, Integer b) { + /** + * Checks whether a and b are consecutive integers or either is null + * + * @param a + * first integer + * @param b + * next integer + * @return whether a + 1 is b or either is null + */ + private boolean step(Integer a, Integer b) { return a == null || b == null || (int) a == b - 1; } - public boolean cycleStep(Integer a, Integer b) { + /** + * Checks whether a and b are consecutive integers modulo highest value + * or either i snull + * + * @param a + * first integer + * @param b + * second integer + * @return whether a + 1 is b (modulo highest value) or either is null + */ + private boolean cycleStep(Integer a, Integer b) { return a == null || b == null || (int) a == b - 1 || a == settings.getHighestValue() && b == 1; } - public boolean groupNeighbor(StoneState other) { + /** + * Checks whether this stone could be left to other in a group + * + * @param other + * possible right neighbor + * @return whether they can be neighbors + */ + private boolean groupNeighbor(StoneState other) { if (isNullSet(leftGroup) && isNullSet(other.rightGroup)) { return false; } @@ -340,7 +388,14 @@ public class TurnLogic { return lessThan(color, other.color) && same(value, other.value); } - public boolean runNeighbor(StoneState other) { + /** + * Checks whether this stone could be left to other in a run + * + * @param other + * possible right neighbor + * @return whether they can be neighbors + */ + private boolean runNeighbor(StoneState other) { if (isNullSet(leftRun) && isNullSet(other.rightRun)) { return false; } @@ -358,7 +413,16 @@ public class TurnLogic { } } - public boolean update(HashSet changes) throws Contradiction { + /** + * Updates this stone considering the changes of all changed stones + * + * @param changes + * stones that have changed + * @return whether we could be updated + * @throws Contradiction + * Is thrown if the changes contradict each other + */ + private boolean update(HashSet changes) throws Contradiction { boolean changed = false; changed |= updateRightRuns(changes); @@ -372,11 +436,29 @@ public class TurnLogic { return changed; } + /** + * Checks that two objects are equal to each other and not null + * + * @param a + * @param b + * @return whether a equals b and both are not null + */ private boolean nonNullEquals(Object a, Object b) { return a != null && b != null && a.equals(b); } - private void breakSymmetries(HashSet changes) throws Contradiction { + /** + * Try to break symmetries between exchangeable stones to reduce the + * state space + * + * @param changes + * stones that changed + * @throws Contradiction + * Is thrown when there exists another trivial solution by + * symmetry + */ + private void breakSymmetries(HashSet changes) + throws Contradiction { Integer mySym = symmetryBreakerValue(); if (mySym == null) { return; @@ -387,7 +469,8 @@ public class TurnLogic { } StoneState otherStone = top.stones.get(other); if (!(joker && otherStone.joker || nonNullEquals(value, - otherStone.value) && nonNullEquals(color, otherStone.color))) { + otherStone.value) + && nonNullEquals(color, otherStone.color))) { continue; } Integer otherSym = top.stones.get(other).symmetryBreakerValue(); @@ -402,12 +485,18 @@ public class TurnLogic { } } + /** + * Order stones by their neighbors to decide on a solution of a set of + * symmetric solutions + * + * @return the order value or null if it can't be determined yer + */ private Integer symmetryBreakerValue() { if (onTable != Boolean.TRUE) { return -1; } - if (leftRun.size() > 1 || leftGroup.size() > 1 || rightRun.size() > 1 - || rightGroup.size() > 1) { + if (leftRun.size() > 1 || leftGroup.size() > 1 + || rightRun.size() > 1 || rightGroup.size() > 1) { return null; } int mode; @@ -437,7 +526,17 @@ public class TurnLogic { return neighbor + stoneCount * mode; } - public boolean updateRightRuns(HashSet changes) + /** + * Updates this stone's right run neighbors considering the changes of + * all changed stones + * + * @param changes + * stones that have changed + * @return whether we could be updated + * @throws Contradiction + * Is thrown if the changes contradict each other + */ + private boolean updateRightRuns(HashSet changes) throws Contradiction { boolean changed = false; HashSet relevantChanges = new HashSet(leftRun); @@ -447,7 +546,8 @@ public class TurnLogic { if (!other.runNeighbor(this) || !other.rightRun.contains(id)) { leftRun.remove(i); changed = true; - } else if (other.rightRun.size() == 1 && other.onTable == Boolean.TRUE) { + } else if (other.rightRun.size() == 1 + && other.onTable == Boolean.TRUE) { changed |= leftRun.retainAll(Arrays.asList(i)); changed |= onTable != Boolean.TRUE; onTable = true; @@ -457,7 +557,17 @@ public class TurnLogic { return changed; } - public boolean updateLeftRuns(HashSet changes) + /** + * Updates this stone's left run neighbors considering the changes of + * all changed stones + * + * @param changes + * stones that have changed + * @return whether we could be updated + * @throws Contradiction + * Is thrown if the changes contradict each other + */ + private boolean updateLeftRuns(HashSet changes) throws Contradiction { boolean changed = false; HashSet relevantChanges = new HashSet(rightRun); @@ -467,7 +577,8 @@ public class TurnLogic { if (!this.runNeighbor(other) || !other.leftRun.contains(id)) { rightRun.remove(i); changed = true; - } else if (other.leftRun.size() == 1 && other.onTable == Boolean.TRUE) { + } else if (other.leftRun.size() == 1 + && other.onTable == Boolean.TRUE) { changed |= rightRun.retainAll(Arrays.asList(i)); changed |= onTable != Boolean.TRUE; onTable = true; @@ -477,14 +588,25 @@ public class TurnLogic { return changed; } - public boolean updateRightGroups(HashSet changes) + /** + * Updates this stone's right group neighbors considering the changes of + * all changed stones + * + * @param changes + * stones that have changed + * @return whether we could be updated + * @throws Contradiction + * Is thrown if the changes contradict each other + */ + private boolean updateRightGroups(HashSet changes) throws Contradiction { boolean changed = false; HashSet relevantChanges = new HashSet(leftGroup); relevantChanges.retainAll(changes); for (int i : relevantChanges) { StoneState other = top.stones.get(i); - if (!other.groupNeighbor(this) || !other.rightGroup.contains(id)) { + if (!other.groupNeighbor(this) + || !other.rightGroup.contains(id)) { leftGroup.remove(i); changed = true; } else if (other.rightGroup.size() == 1 @@ -498,7 +620,17 @@ public class TurnLogic { return changed; } - public boolean updateLeftGroups(HashSet changes) + /** + * Updates this stone's left group neighbors considering the changes of + * all changed stones + * + * @param changes + * stones that have changed + * @return whether we could be updated + * @throws Contradiction + * Is thrown if the changes contradict each other + */ + private boolean updateLeftGroups(HashSet changes) throws Contradiction { boolean changed = false; HashSet relevantChanges = new HashSet(leftGroup); @@ -509,7 +641,8 @@ public class TurnLogic { if (!this.groupNeighbor(other) || !other.leftGroup.contains(id)) { rightGroup.remove(i); changed = true; - } else if (other.leftGroup.size() == 1 && other.onTable == Boolean.TRUE) { + } else if (other.leftGroup.size() == 1 + && other.onTable == Boolean.TRUE) { changed |= rightGroup.retainAll(Arrays.asList(i)); changed |= onTable != Boolean.TRUE; onTable = true; @@ -519,7 +652,14 @@ public class TurnLogic { return changed; } - public boolean checkState() throws Contradiction { + /** + * Enforce local rule consistency + * + * @return whether this stone changed + * @throws Contradiction + * Is thrown if this stone can't be placed anywhere + */ + private boolean checkState() throws Contradiction { boolean changed = false; if (onTable == Boolean.FALSE) { @@ -550,6 +690,12 @@ public class TurnLogic { return changed; } + /** + * If this stone has to be in a group it can't be part of a run and the + * other way around + * + * @return whether this stone changed + */ private boolean checkSetTypeKnown() { boolean changed = false; if (!(leftGroup.contains(null) || rightGroup.contains(null))) { @@ -563,11 +709,18 @@ public class TurnLogic { return changed; } + /** + * If we have no group/run neighbors and no left/right neighbors but are + * on the table we need to have a neighbor for the remaining case + * + * @return whether this stone changed + */ private boolean checkLonelyStone() { boolean changed = false; @SuppressWarnings("unchecked") - List> sets = Arrays.> asList(leftGroup, - rightGroup, leftRun, rightRun, leftGroup, rightGroup, leftRun); + List> sets = Arrays.> asList( + leftGroup, rightGroup, leftRun, rightRun, leftGroup, + rightGroup, leftRun); for (int i = 0; i < 4; i++) { if (isNullSet(sets.get(i)) && isNullSet(sets.get(i + 1)) && isNullSet(sets.get(i + 2))) { @@ -577,6 +730,12 @@ public class TurnLogic { return changed; } + /** + * If we have a neighbor that is on the end of a set we can't be on the + * end either + * + * @return whether this stone changed + */ private boolean checkNeighborStoneNeeded() { boolean changed = false; if (isSingleNonNullSet(leftRun) @@ -599,10 +758,19 @@ public class TurnLogic { return changed; } + /** + * When we need to have some kind of neighbor but there isn't any + * possible one we're either not on the table or if we have to have a + * contradiction + * + * @return whether this stone changed + * @throws Contradiction + * Is thrown if this stone can't be placed anywhere + */ private boolean checkStoneCanBeOnTable() throws Contradiction { boolean changed = false; - if (leftGroup.isEmpty() || rightGroup.isEmpty() || leftRun.isEmpty() - || rightRun.isEmpty()) { + if (leftGroup.isEmpty() || rightGroup.isEmpty() + || leftRun.isEmpty() || rightRun.isEmpty()) { if (onTable == Boolean.TRUE) { throw new Contradiction(); } @@ -618,6 +786,13 @@ public class TurnLogic { return changed; } + /** + * If we need to be in a group and in a run at the same time we have a + * contradiction + * + * @throws Contradiction + * Is thrown if this stone can't be placed anywhere + */ private void checkGroupRunExclusive() throws Contradiction { if ((isSingleNonNullSet(leftGroup) || isSingleNonNullSet(rightGroup)) && (isSingleNonNullSet(leftRun) || isSingleNonNullSet(rightRun))) { @@ -625,6 +800,11 @@ public class TurnLogic { } } + /** + * Try to derive the value of a joker stone from it's neighbor(s) + * + * @return whether we could derive the value + */ private boolean checkJokerValue() { boolean changed = false; if (this.value == null) { @@ -640,7 +820,8 @@ public class TurnLogic { } else if (isSingleNonNullSet(rightRun)) { Integer value = top.stones.get(rightRun.iterator().next()).value; if (value != null) { - this.value = (value - 2) % settings.getHighestValue() + 1; + this.value = (value - 2) % settings.getHighestValue() + + 1; } } changed |= this.value != null; @@ -648,6 +829,11 @@ public class TurnLogic { return changed; } + /** + * Try to derive the color of a joker stone from it's neighbor(s) + * + * @return whether we could derive the color + */ private boolean checkJokerColor() { boolean changed = false; if (this.color == null) { @@ -661,6 +847,11 @@ public class TurnLogic { return changed; } + /** + * Check whether this stone's position, value and color are known + * + * @return true when this stone is solved + */ public boolean isSolved() { if (onTable == Boolean.FALSE) { return true; @@ -668,13 +859,18 @@ public class TurnLogic { if (onTable == null || color == null || value == null) { return false; } - if (leftRun.size() > 1 || rightRun.size() > 1 || leftGroup.size() > 1 - || rightGroup.size() > 1) { + if (leftRun.size() > 1 || rightRun.size() > 1 + || leftGroup.size() > 1 || rightGroup.size() > 1) { return false; } return true; } + /** + * How badly we want to get rid of this stone + * + * @return this stone's badness score + */ public double getScore() { if (fromTable) { return 0; @@ -682,6 +878,11 @@ public class TurnLogic { return 1; } + /** + * How many points we get for melding this stone + * + * @return amount of points + */ public double getPoints() { if (fromTable) { return 0; @@ -692,13 +893,22 @@ public class TurnLogic { return (double) value; } + /** + * Checks whether we need a joker on the left or right side to place + * this stone + * + * @param side + * which side to check + * @return true when a joker is the only possible neighbor + */ @SuppressWarnings("unchecked") public boolean needsJoker(boolean side) { if (onTable != Boolean.TRUE) { return false; } - for (HashSet set : side ? Arrays.asList(leftGroup, leftRun) - : Arrays.asList(rightGroup, rightRun)) { + for (HashSet set : side ? Arrays + .asList(leftGroup, leftRun) : Arrays.asList(rightGroup, + rightRun)) { cancle: if (!set.contains(null)) { for (int idx : set) { if (!top.stones.get(idx).joker) { @@ -713,10 +923,24 @@ public class TurnLogic { } } + /** + * Check whether a set of Integers only contains null + * + * @param i + * set to check + * @return true when it only contains null + */ private static boolean isNullSet(HashSet i) { return i.size() == 1 && i.contains(null); } + /** + * Check whether a set of Integers only contains a single non null value + * + * @param i + * set to check + * @return true when it only contains a single non null value + */ private static boolean isSingleNonNullSet(HashSet i) { return i.size() == 1 && !i.contains(null); } @@ -725,11 +949,11 @@ public class TurnLogic { * Creates new turn logic * * @param settings - * the game settings + * the game settings * @param tableStones - * all stones on the table + * all stones on the table * @param handStones - * all stones on the hand + * all stones on the hand */ public TurnLogic(GameSettings settings, Collection tableStones, Collection handStones) { @@ -758,17 +982,18 @@ public class TurnLogic { @Override public int compare(Pair o1, Pair o2) { int cmp; - cmp = ((Boolean) o1.getFirst().isJoker()).compareTo(o2.getFirst() - .isJoker()); + cmp = ((Boolean) o1.getFirst().isJoker()).compareTo(o2 + .getFirst().isJoker()); if (cmp != 0) { return -cmp; } - cmp = (o1.getFirst().getColor()).compareTo(o2.getFirst().getColor()); + cmp = (o1.getFirst().getColor()).compareTo(o2.getFirst() + .getColor()); if (cmp != 0) { return cmp; } - cmp = ((Integer) o1.getFirst().getValue()).compareTo(o2.getFirst() - .getValue()); + cmp = ((Integer) o1.getFirst().getValue()).compareTo(o2 + .getFirst().getValue()); return cmp; } }); @@ -787,6 +1012,9 @@ public class TurnLogic { neededPoints = settings.getInitialMeldThreshold(); } + /** + * Remove a contradicted state from the try stack, reset top + */ private void pop() { stack.remove(stack.size() - 1); if (!stack.isEmpty()) { @@ -794,16 +1022,29 @@ public class TurnLogic { } } + /** + * Remove an unsolved state, to be replaced with refined state, from the try + * stack + */ private void replace() { stack.remove(stack.size() - 1); } + /** + * Push multiple new state onto the try stack + * + * @param states + * states to push + */ private void pushes(State... states) { for (State state : states) { stack.add(state); } } + /** + * Done with modifying the try stack, reset top + */ private void done() { top = stack.get(stack.size() - 1); } @@ -835,7 +1076,8 @@ public class TurnLogic { ArrayList setStones = new ArrayList(); while (true) { setStones.add(inputStones.get(stone.id)); - if (isNullSet(stone.rightRun) && isNullSet(stone.rightGroup)) { + if (isNullSet(stone.rightRun) + && isNullSet(stone.rightGroup)) { break; } Integer rightRunID = stone.rightRun.iterator().next(); @@ -890,7 +1132,10 @@ public class TurnLogic { return neededScore; } - private void branch() throws Contradiction { + /** + * Refine the currently unsolved top stack state + */ + private void branch() { for (int i = 0; i < stoneCount; i++) { StoneState stone = top.stones.get(i); if (stone.leftRun.size() > 1) { @@ -929,6 +1174,12 @@ public class TurnLogic { throw new Error("Internal AI error"); } + /** + * Create states for all possible values of stone i + * + * @param i + * stone id to branch on + */ private void branchValue(int i) { replace(); for (int value = 1; value <= settings.getHighestValue(); value++) { @@ -939,6 +1190,12 @@ public class TurnLogic { } } + /** + * Create states for all possible colors of stone i + * + * @param i + * stone id to branch on + */ private void branchColor(int i) { replace(); for (StoneColor color : stoneColors) { @@ -947,8 +1204,15 @@ public class TurnLogic { newState.changedStones.add(i); pushes(newState); } + } + /** + * Create states for all possible right group neighbors of stone i + * + * @param i + * stone id to branch on + */ private void branchRightGroup(int i, StoneState stone) { replace(); for (Integer id : stone.rightGroup) { @@ -960,6 +1224,12 @@ public class TurnLogic { } } + /** + * Create states for all possible left group neighbors of stone i + * + * @param i + * stone id to branch on + */ private void branchLeftGroup(int i, StoneState stone) { replace(); for (Integer id : stone.leftGroup) { @@ -971,6 +1241,12 @@ public class TurnLogic { } } + /** + * Create states for all possible right run neighbors of stone i + * + * @param i + * stone id to branch on + */ private void branchRightRun(int i, StoneState stone) { replace(); for (Integer id : stone.rightRun) { @@ -982,6 +1258,12 @@ public class TurnLogic { } } + /** + * Create states for all possible left run neighbors of stone i + * + * @param i + * stone id to branch on + */ private void branchLeftRun(int i, StoneState stone) { replace(); for (Integer id : stone.leftRun) { @@ -993,6 +1275,12 @@ public class TurnLogic { } } + /** + * Create states with stone i on the table and stone i on the hand + * + * @param i + * stone id to branch on + */ private void branchOnHand(int i) { replace(); State newState = new State(top); -- cgit v1.2.3