From a33b0a22acf13a79aba9c205ec320f671b426958 Mon Sep 17 00:00:00 2001 From: Jannis Harder Date: Mon, 20 Jun 2011 23:36:26 +0200 Subject: Improved AI git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@514 72836036-5685-4462-b002-a69064685172 --- src/jrummikub/ai/TurnLogic.java | 264 +++++++++++++++++++++++++++++-------- test/jrummikub/model/HandTest.java | 12 ++ 2 files changed, 219 insertions(+), 57 deletions(-) diff --git a/src/jrummikub/ai/TurnLogic.java b/src/jrummikub/ai/TurnLogic.java index 8440425..b3ac3cd 100644 --- a/src/jrummikub/ai/TurnLogic.java +++ b/src/jrummikub/ai/TurnLogic.java @@ -6,6 +6,7 @@ import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.HashSet; +import java.util.Iterator; import java.util.List; import jrummikub.model.GameSettings; @@ -64,14 +65,19 @@ public class TurnLogic { } public void updateStones() throws Contradiction { - checkJokers(); + checkJokerCount(); for (int i : changedStones) { stones.get(i).checkState(); } checkScoreAndPoints(); while (!changedStones.isEmpty()) { - updateStonesStep(); + while (!changedStones.isEmpty()) { + updateStonesStep(); + checkScoreAndPoints(); + } + checkJokerCount(); checkScoreAndPoints(); + } } @@ -97,33 +103,20 @@ public class TurnLogic { return true; } - public void checkJokers() throws Contradiction { - for (int i = 0; i < jokerIDs.size(); i++) { - StoneState left = stones.get(jokerIDs.get(i)); - - HashSet leftLeftGroup = new HashSet(left.leftGroup); - HashSet leftLeftRun = new HashSet(left.leftRun); - leftLeftGroup.remove(null); - leftLeftRun.remove(null); - int runID, groupID; - if (leftLeftGroup.isEmpty()) { - groupID = -1; - } else { - groupID = Collections.min(leftLeftGroup); - } - if (leftLeftRun.isEmpty()) { - runID = -1; - } else { - runID = Collections.min(leftLeftRun); - } - for (int j = i + 1; j < jokerIDs.size(); j++) { - StoneState right = stones.get(jokerIDs.get(j)); - - if (right.leftGroup.remove(groupID)) { - changedStones.add(jokerIDs.get(j)); + private void checkJokerCount() throws Contradiction { + int jokersLeft = jokerIDs.size(); + int jokersRight = jokerIDs.size(); + for (StoneState stone : stones) { + if (stone.needsJoker(true)) { + jokersLeft--; + if (jokersLeft < 0) { + throw new Contradiction(); } - if (right.leftRun.remove(runID)) { - changedStones.add(jokerIDs.get(j)); + } + if (stone.needsJoker(false)) { + jokersRight--; + if (jokersRight < 0) { + throw new Contradiction(); } } } @@ -214,8 +207,8 @@ public class TurnLogic { public 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) { @@ -265,14 +258,85 @@ public class TurnLogic { public boolean update(HashSet changes) throws Contradiction { boolean changed = false; + changed |= updateRightRuns(changes); changed |= updateLeftRuns(changes); changed |= updateRightGroups(changes); changed |= updateLeftGroups(changes); changed |= checkState(); + + breakSymmetries(changes); + return changed; } + private boolean nonNullEquals(Object a, Object b) { + return a != null && b != null && a.equals(b); + } + + private void breakSymmetries(HashSet changes) + throws Contradiction { + Integer mySym = symmetryBreakerValue(); + if (mySym == null) { + return; + } + for (int other : changes) { + if (other == id) { + continue; + } + StoneState otherStone = top.stones.get(other); + if (!(joker && otherStone.joker || nonNullEquals(value, + otherStone.value) + && nonNullEquals(color, otherStone.color))) { + continue; + } + Integer otherSym = top.stones.get(other).symmetryBreakerValue(); + if (otherSym == null) { + continue; + } + + if ((mySym != -1 | otherSym != -1) + & ((id > other) != (mySym < otherSym))) { + throw new Contradiction(); + } + } + } + + private Integer symmetryBreakerValue() { + if (onTable != Boolean.TRUE) { + return -1; + } + if (leftRun.size() > 1 || leftGroup.size() > 1 + || rightRun.size() > 1 || rightGroup.size() > 1) { + return null; + } + int mode; + int neighbor; + if (leftRun.contains(null)) { + if (leftGroup.contains(null)) { + if (rightRun.contains(null)) { + if (rightGroup.contains(null)) { + return -1; + } else { + mode = 0; + neighbor = rightGroup.iterator().next(); + } + } else { + mode = 1; + neighbor = rightRun.iterator().next(); + } + + } else { + mode = 2; + neighbor = leftGroup.iterator().next(); + } + } else { + mode = 3; + neighbor = leftRun.iterator().next(); + } + return neighbor + stoneCount * mode; + } + public boolean updateRightRuns(HashSet changes) throws Contradiction { boolean changed = false; @@ -283,7 +347,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; @@ -303,7 +368,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; @@ -320,7 +386,8 @@ public class TurnLogic { 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 @@ -345,7 +412,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; @@ -401,8 +469,9 @@ public class TurnLogic { 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))) { @@ -436,8 +505,8 @@ public class TurnLogic { 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(); } @@ -461,7 +530,36 @@ public class TurnLogic { } private boolean checkJoker() { - return false; + boolean changed = false; + if (this.value == null) { + if (isSingleNonNullSet(leftGroup)) { + this.value = top.stones.get(leftGroup.iterator().next()).value; + } else if (isSingleNonNullSet(rightGroup)) { + this.value = top.stones.get(rightGroup.iterator().next()).value; + } else if (isSingleNonNullSet(leftRun)) { + Integer value = top.stones.get(leftRun.iterator().next()).value; + if (value != null) { + this.value = value % settings.getHighestValue() + 1; + } + } else if (isSingleNonNullSet(rightRun)) { + Integer value = top.stones.get(rightRun.iterator().next()).value; + if (value != null) { + this.value = (value - 2) % settings.getHighestValue() + + 1; + } + } + changed |= this.value != null; + } + if (this.color == null) { + if (isSingleNonNullSet(leftRun)) { + this.color = top.stones.get(leftRun.iterator().next()).color; + } else if (isSingleNonNullSet(rightRun)) { + this.color = top.stones.get(rightRun.iterator().next()).color; + } + changed |= this.color != null; + } + + return changed; } public boolean isSolved() { @@ -471,8 +569,8 @@ 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; @@ -494,6 +592,32 @@ public class TurnLogic { else return (double) value; } + + public int getSize() { + return leftGroup.size() + rightGroup.size() + leftRun.size() + + rightRun.size(); + } + + @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)) { + cancle: if (!set.contains(null)) { + for (int idx : set) { + if (!top.stones.get(idx).joker) { + break cancle; + } + } + return true; + } + } + + return false; + } } private static boolean isNullSet(HashSet i) { @@ -508,11 +632,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) { @@ -541,26 +665,33 @@ 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; } }); + System.out.println("---"); + ArrayList handStones2 = new ArrayList(); int i = 0; for (Pair pair : sortedStones) { top.add(new StoneState(i++, pair.getFirst(), pair.getSecond())); inputStones.add(pair.getFirst()); + if (!pair.getSecond()) { + handStones2.add(pair.getFirst()); + } } + System.out.println(handStones2); } /** @@ -618,7 +749,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(); @@ -669,18 +801,28 @@ public class TurnLogic { public double optimize() { while (!autoAbort && solve()) { neededScore = top.getScore(); + System.out.println(neededScore); } return neededScore; } private void branch() throws Contradiction { + + ArrayList indices = new ArrayList(); for (int i = 0; i < stoneCount; i++) { - StoneState stone = top.stones.get(i); - if (stone.onTable == null) { - replace(); - branchOnHand(i); - return; + indices.add(i); + } + Collections.sort(indices, new Comparator() { + @Override + public int compare(Integer o1, Integer o2) { + Integer size1 = top.stones.get(o1).getSize(); + Integer size2 = top.stones.get(o2).getSize(); + return size1.compareTo(size2); } + }); + + for (int i = 0; i < stoneCount; i++) { + StoneState stone = top.stones.get(i); if (stone.leftRun.size() > 1) { replace(); branchLeftRun(i, stone); @@ -701,6 +843,14 @@ public class TurnLogic { branchRightGroup(i, stone); return; } + if (stone.onTable == null) { + replace(); + branchOnHand(i); + return; + } + } + for (int i = 0; i < stoneCount; i++) { + StoneState stone = top.stones.get(i); if (stone.color == null) { replace(); branchColor(i); @@ -776,10 +926,10 @@ public class TurnLogic { private void branchOnHand(int i) { State newState = new State(top); - newState.stones.get(i).onTable = false; + newState.stones.get(i).onTable = true; newState.changedStones.add(i); State altState = new State(top); - altState.stones.get(i).onTable = true; + altState.stones.get(i).onTable = false; altState.changedStones.add(i); pushes(altState, newState); } diff --git a/test/jrummikub/model/HandTest.java b/test/jrummikub/model/HandTest.java index f0be046..392dbd8 100644 --- a/test/jrummikub/model/HandTest.java +++ b/test/jrummikub/model/HandTest.java @@ -232,6 +232,18 @@ public class HandTest { stones.add(new Stone(i, BLACK)); } testInitialMeld(true, stones); + + testInitialMeld(true, Arrays.asList(new Stone(1, BLACK), new Stone(1, + BLACK), new Stone(2, BLACK), new Stone(8, BLACK), new Stone(9, + BLACK), new Stone(10, BLACK), new Stone(11, BLACK), new Stone( + 12, BLACK), new Stone(12, BLACK), new Stone(3, ORANGE), + new Stone(3, ORANGE), new Stone(5, ORANGE), + new Stone(7, ORANGE), new Stone(12, ORANGE), new Stone(13, + ORANGE), new Stone(13, ORANGE), new Stone(2, BLUE), + new Stone(2, BLUE), new Stone(3, BLUE), new Stone(3, BLUE), + new Stone(8, BLUE), new Stone(9, BLUE), new Stone(1, RED), + new Stone(3, RED), new Stone(4, RED), new Stone(4, RED), + new Stone(5, RED), new Stone(8, RED))); } /** */ -- cgit v1.2.3