From bc835d499f2fe3c8b9c5b6bc9cfca9d9666854e9 Mon Sep 17 00:00:00 2001 From: Ida Massow Date: Sat, 18 Jun 2011 15:01:21 +0200 Subject: Fix many comments, fix tests, fix complexity git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@462 72836036-5685-4462-b002-a69064685172 --- src/jrummikub/ai/TurnLogic.java | 235 +++++++++++++++++++++++++++++----------- 1 file changed, 174 insertions(+), 61 deletions(-) (limited to 'src/jrummikub/ai') diff --git a/src/jrummikub/ai/TurnLogic.java b/src/jrummikub/ai/TurnLogic.java index b9e2a2a..81391a7 100644 --- a/src/jrummikub/ai/TurnLogic.java +++ b/src/jrummikub/ai/TurnLogic.java @@ -14,6 +14,9 @@ import jrummikub.model.StoneColor; import jrummikub.model.StoneSet; import jrummikub.util.Pair; +/** + * Logic behind the ai turns + */ public class TurnLogic { private GameSettings settings; private int stoneCount; @@ -264,13 +267,15 @@ public class TurnLogic { public boolean update(HashSet changes) throws Contradiction { boolean changed = false; - changed |= updateRuns(changes); - changed |= updateGroups(changes); + changed |= updateRightRuns(changes); + changed |= updateLeftRuns(changes); + changed |= updateRightGroups(changes); + changed |= updateLeftGroups(changes); changed |= checkState(); return changed; } - public boolean updateRuns(HashSet changes) + public boolean updateRightRuns(HashSet changes) throws Contradiction { boolean changed = false; HashSet relevantChanges = new HashSet(leftRun); @@ -288,7 +293,13 @@ public class TurnLogic { break; } } - relevantChanges = new HashSet(rightRun); + return changed; + } + + public boolean updateLeftRuns(HashSet changes) + throws Contradiction { + boolean changed = false; + HashSet relevantChanges = new HashSet(rightRun); relevantChanges.retainAll(changes); for (int i : relevantChanges) { StoneState other = top.stones.get(i); @@ -306,7 +317,7 @@ public class TurnLogic { return changed; } - public boolean updateGroups(HashSet changes) + public boolean updateRightGroups(HashSet changes) throws Contradiction { boolean changed = false; HashSet relevantChanges = new HashSet(leftGroup); @@ -325,6 +336,13 @@ public class TurnLogic { break; } } + return changed; + } + + public boolean updateLeftGroups(HashSet changes) + throws Contradiction { + boolean changed = false; + HashSet relevantChanges = new HashSet(leftGroup); relevantChanges = new HashSet(rightGroup); relevantChanges.retainAll(changes); for (int i : relevantChanges) { @@ -345,6 +363,7 @@ public class TurnLogic { public boolean checkState() throws Contradiction { boolean changed = false; + if (onTable == Boolean.FALSE) { if (leftRun.size() + rightRun.size() + leftGroup.size() + rightGroup.size() != 0) { @@ -357,6 +376,23 @@ public class TurnLogic { return false; } + changed |= checkSetTypeKnown(); + + changed |= checkLonelyStone(); + + changed |= checkNeighborStoneNeeded(); + + changed |= checkStoneCanBeOnTable(); + + checkGroupRunExclusive(); + + changed |= checkJoker(); + + return changed; + } + + private boolean checkSetTypeKnown() { + boolean changed = false; if (!(leftGroup.contains(null) || rightGroup.contains(null))) { changed |= leftRun.retainAll(Arrays.asList((Integer) null)) | rightRun.retainAll(Arrays.asList((Integer) null)); @@ -365,7 +401,11 @@ public class TurnLogic { changed |= leftGroup.retainAll(Arrays.asList((Integer) null)) | rightGroup.retainAll(Arrays.asList((Integer) null)); } + return changed; + } + private boolean checkLonelyStone() { + boolean changed = false; @SuppressWarnings("unchecked") List> sets = Arrays.> asList( leftGroup, rightGroup, leftRun, rightRun, leftGroup, @@ -376,7 +416,11 @@ public class TurnLogic { changed |= sets.get(i + 3).remove(null); } } + return changed; + } + private boolean checkNeighborStoneNeeded() { + boolean changed = false; if (isSingleNonNullSet(leftRun) && isNullSet(top.stones.get(leftRun.iterator().next()).leftRun)) { changed |= rightRun.remove(null); @@ -394,7 +438,11 @@ public class TurnLogic { && isNullSet(top.stones.get(rightGroup.iterator().next()).rightGroup)) { changed |= leftGroup.remove(null); } + return changed; + } + private boolean checkStoneCanBeOnTable() throws Contradiction { + boolean changed = false; if (leftGroup.isEmpty() || rightGroup.isEmpty() || leftRun.isEmpty() || rightRun.isEmpty()) { if (onTable == Boolean.TRUE) { @@ -409,15 +457,14 @@ public class TurnLogic { changed = true; } } + return changed; + } + private void checkGroupRunExclusive() throws Contradiction { if ((isSingleNonNullSet(leftGroup) || isSingleNonNullSet(rightGroup)) && (isSingleNonNullSet(leftRun) || isSingleNonNullSet(rightRun))) { throw new Contradiction(); } - - changed |= checkJoker(); - - return changed; } private boolean checkJoker() { @@ -425,16 +472,22 @@ public class TurnLogic { } public boolean isSolved() { + boolean solved = false; if (onTable == Boolean.FALSE) { - return true; + return solved; } if (onTable == null || color == null || value == null) { - return false; + return solved; } if (leftRun.size() > 1 || rightRun.size() > 1 || leftGroup.size() > 1 || rightGroup.size() > 1) { - return false; + return solved; } + solved = bothGoupAndRun(); + return solved; + } + + private boolean bothGoupAndRun() { if (!((isNullSet(leftRun) && isNullSet(rightRun)) || (isNullSet(leftGroup) && isNullSet(rightGroup)))) { return false; } @@ -467,6 +520,16 @@ public class TurnLogic { return i.size() == 1 && !i.contains(null); } + /** + * Creates new turn logic + * + * @param settings + * the game settings + * @param tableStones + * all stones on the table + * @param handStones + * all stones on the hand + */ public TurnLogic(GameSettings settings, Collection tableStones, Collection handStones) { this.settings = settings; @@ -517,6 +580,9 @@ public class TurnLogic { } } + /** + * Include initial meld threshold into turn logic + */ public void needIntialMeldThreshold() { neededPoints = settings.getInitialMeldThreshold(); } @@ -542,10 +608,18 @@ public class TurnLogic { top = stack.get(stack.size() - 1); } + /** + * Aborts currently running solve call + */ public void abort() { abort = true; } + /** + * Get the found stones and create output sets + * + * @return output sets to put on table + */ public List getResult() { State result = bestState; @@ -574,10 +648,14 @@ public class TurnLogic { outputSets.add(new StoneSet(setStones)); } } - return outputSets; } + /** + * Solves next state on stack while not aborted + * + * @return solved + */ public boolean solve() { if (top.isSolved()) { pop(); @@ -601,6 +679,11 @@ public class TurnLogic { return false; } + /** + * Optimizes the solution found as long as stopped from control + * + * @return score of found solution + */ public double optimize() { while (!autoAbort && solve()) { neededScore = top.getScore(); @@ -613,77 +696,37 @@ public class TurnLogic { StoneState stone = top.stones.get(i); if (stone.onTable == null) { replace(); - State newState = new State(top); - newState.stones.get(i).onTable = false; - newState.changedStones.add(i); - State altState = new State(top); - altState.stones.get(i).onTable = true; - altState.changedStones.add(i); - pushes(altState, newState); + branchOnHand(i); return; } if (stone.leftRun.size() > 1) { replace(); - for (Integer id : stone.leftRun) { - State newState = new State(top); - newState.stones.get(i).leftRun.clear(); - newState.stones.get(i).leftRun.add(id); - newState.changedStones.add(i); - pushes(newState); - } + branchLeftRun(i, stone); return; } if (stone.rightRun.size() > 1) { replace(); - for (Integer id : stone.rightRun) { - State newState = new State(top); - newState.stones.get(i).rightRun.clear(); - newState.stones.get(i).rightRun.add(id); - newState.changedStones.add(i); - pushes(newState); - } + branchRightRun(i, stone); return; } if (stone.leftGroup.size() > 1) { replace(); - for (Integer id : stone.leftGroup) { - State newState = new State(top); - newState.stones.get(i).leftGroup.clear(); - newState.stones.get(i).leftGroup.add(id); - newState.changedStones.add(i); - pushes(newState); - } + branchLeftGroup(i, stone); return; } if (stone.rightGroup.size() > 1) { replace(); - for (Integer id : stone.rightGroup) { - State newState = new State(top); - newState.stones.get(i).rightGroup.clear(); - newState.stones.get(i).rightGroup.add(id); - newState.changedStones.add(i); - pushes(newState); - } + branchRightGroup(i, stone); return; } if (stone.color == null) { replace(); - for (StoneColor color : stoneColors) { - State newState = new State(top); - newState.stones.get(i).color = color; - newState.changedStones.add(i); - pushes(newState); - } + branchColor(i); return; } if (stone.value == null) { replace(); - for (int value = 1; value <= settings.getHighestValue(); value++) { - State newState = new State(top); - newState.stones.get(i).value = value; - newState.changedStones.add(i); - pushes(newState); - } + branchValue(i); return; } } @@ -691,11 +734,81 @@ public class TurnLogic { throw new Error("Internal AI error"); } + private void branchValue(int i) { + for (int value = 1; value <= settings.getHighestValue(); value++) { + State newState = new State(top); + newState.stones.get(i).value = value; + newState.changedStones.add(i); + pushes(newState); + } + } + + private void branchColor(int i) { + for (StoneColor color : stoneColors) { + State newState = new State(top); + newState.stones.get(i).color = color; + newState.changedStones.add(i); + pushes(newState); + } + } + + private void branchRightGroup(int i, StoneState stone) { + for (Integer id : stone.rightGroup) { + State newState = new State(top); + newState.stones.get(i).rightGroup.clear(); + newState.stones.get(i).rightGroup.add(id); + newState.changedStones.add(i); + pushes(newState); + } + } + + private void branchLeftGroup(int i, StoneState stone) { + for (Integer id : stone.leftGroup) { + State newState = new State(top); + newState.stones.get(i).leftGroup.clear(); + newState.stones.get(i).leftGroup.add(id); + newState.changedStones.add(i); + pushes(newState); + } + } + + private void branchRightRun(int i, StoneState stone) { + for (Integer id : stone.rightRun) { + State newState = new State(top); + newState.stones.get(i).rightRun.clear(); + newState.stones.get(i).rightRun.add(id); + newState.changedStones.add(i); + pushes(newState); + } + } + + private void branchLeftRun(int i, StoneState stone) { + for (Integer id : stone.leftRun) { + State newState = new State(top); + newState.stones.get(i).leftRun.clear(); + newState.stones.get(i).leftRun.add(id); + newState.changedStones.add(i); + pushes(newState); + } + } + + private void branchOnHand(int i) { + State newState = new State(top); + newState.stones.get(i).onTable = false; + newState.changedStones.add(i); + State altState = new State(top); + altState.stones.get(i).onTable = true; + altState.changedStones.add(i); + pushes(altState, newState); + } + + /** + * Abort as soon as a solution is found + */ public void autoAbort() { if (bestState != null) { abort = true; } autoAbort = true; - } } -- cgit v1.2.3