summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorJannis Harder <harder@informatik.uni-luebeck.de>2011-06-20 23:36:26 +0200
committerJannis Harder <harder@informatik.uni-luebeck.de>2011-06-20 23:36:26 +0200
commita33b0a22acf13a79aba9c205ec320f671b426958 (patch)
tree0c8aa96d701a19f9a90fe8219101347e831ea095 /src
parent2d08646187f514032d3d7eba7aed3767e1505d6f (diff)
downloadJRummikub-a33b0a22acf13a79aba9c205ec320f671b426958.tar
JRummikub-a33b0a22acf13a79aba9c205ec320f671b426958.zip
Improved AI
git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@514 72836036-5685-4462-b002-a69064685172
Diffstat (limited to 'src')
-rw-r--r--src/jrummikub/ai/TurnLogic.java264
1 files changed, 207 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<Integer> leftLeftGroup = new HashSet<Integer>(left.leftGroup);
- HashSet<Integer> leftLeftRun = new HashSet<Integer>(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<Integer> 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 <T extends Comparable<T>> boolean lessThan(T a, T b) {
@@ -265,14 +258,85 @@ public class TurnLogic {
public boolean update(HashSet<Integer> 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<Integer> 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<Integer> 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<HashSet<Integer>> sets = Arrays.<HashSet<Integer>> asList(leftGroup,
- rightGroup, leftRun, rightRun, leftGroup, rightGroup, leftRun);
+ List<HashSet<Integer>> sets = Arrays.<HashSet<Integer>> 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<Integer> 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<Integer> 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<Stone> tableStones,
Collection<Stone> handStones) {
@@ -541,26 +665,33 @@ public class TurnLogic {
@Override
public int compare(Pair<Stone, Boolean> o1, Pair<Stone, Boolean> 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<Stone> handStones2 = new ArrayList<Stone>();
int i = 0;
for (Pair<Stone, Boolean> 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<Stone> setStones = new ArrayList<Stone>();
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<Integer> indices = new ArrayList<Integer>();
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<Integer>() {
+ @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);
}