summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorJannis Harder <harder@informatik.uni-luebeck.de>2011-06-14 21:05:15 +0200
committerJannis Harder <harder@informatik.uni-luebeck.de>2011-06-14 21:05:15 +0200
commit3ffad8597290f91d21c2a2ba7657bbbc16ab1582 (patch)
treef2d4847afdebfc3778b70cca751f81ea4678b5e1 /src
parent751d5a3aa98461bf27f2a21a157e72f8da89406a (diff)
downloadJRummikub-3ffad8597290f91d21c2a2ba7657bbbc16ab1582.tar
JRummikub-3ffad8597290f91d21c2a2ba7657bbbc16ab1582.zip
Implemented initial meld test using new AI
git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@441 72836036-5685-4462-b002-a69064685172
Diffstat (limited to 'src')
-rw-r--r--src/jrummikub/ai/TurnLogic.java50
-rw-r--r--src/jrummikub/ai/fdsolver/Constraints.java5
-rw-r--r--src/jrummikub/ai/fdsolver/Var.java3
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/ListSumConstraint.java91
-rw-r--r--src/jrummikub/model/Hand.java37
5 files changed, 162 insertions, 24 deletions
diff --git a/src/jrummikub/ai/TurnLogic.java b/src/jrummikub/ai/TurnLogic.java
index 1ce752c..e736361 100644
--- a/src/jrummikub/ai/TurnLogic.java
+++ b/src/jrummikub/ai/TurnLogic.java
@@ -32,11 +32,15 @@ public class TurnLogic {
private GameSettings settings;
private int stoneCount;
private int maxSetSize;
+ private int maxHandPoints;
private Var<Boolean> trueVar;
+ private Var<Integer> totalPoints;
private List<Var<Boolean>> onTable = new ArrayList<Var<Boolean>>();
+ private List<Var<Integer>> pointsValue = new ArrayList<Var<Integer>>();
+
private List<Var<Integer>> stoneValue = new ArrayList<Var<Integer>>();
private List<Var<Integer>> leftStoneValue = new ArrayList<Var<Integer>>();
private List<Var<Integer>> rightStoneValue = new ArrayList<Var<Integer>>();
@@ -76,6 +80,7 @@ public class TurnLogic {
trueVar = solver.makeVar(true);
+ maxHandPoints = 0;
int i = 0;
for (Stone stone : tableStones) {
addStone(i, true, stone);
@@ -89,6 +94,19 @@ public class TurnLogic {
for (i = 0; i < stoneCount; i++) {
addConstraints(i);
}
+
+ totalPoints = solver.makeRangeVar(settings.getInitialMeldThreshold(),
+ maxHandPoints);
+
+ List<Var<Integer>> points = new ArrayList<Var<Integer>>();
+
+ for (Var<Integer> var : pointsValue) {
+ if (var != null) {
+ points.add(var);
+ }
+ }
+
+ add(sum(totalPoints, points));
}
private void addStone(int i, boolean table, Stone stone) {
@@ -100,9 +118,22 @@ public class TurnLogic {
isJoker.add(stone.isJoker());
if (stone.isJoker()) {
stoneValue.add(solver.makeRangeVar(1, settings.getHighestValue()));
+ if (table) {
+ pointsValue.add(null);
+ } else {
+ pointsValue.add(solver.makeRangeVar(0,
+ settings.getHighestValue()));
+ maxHandPoints += settings.getHighestValue();
+ }
stoneColor.add(solver.makeVar(settings.getStoneColors()));
} else {
stoneValue.add(solver.makeVar(stone.getValue()));
+ if (table) {
+ pointsValue.add(null);
+ } else {
+ pointsValue.add(solver.makeVar(0, stone.getValue()));
+ maxHandPoints += stone.getValue();
+ }
stoneColor.add(solver.makeVar(stone.getColor()));
}
@@ -282,6 +313,13 @@ public class TurnLogic {
add(unless(onTable.get(i),
constant(stoneColor.get(i), StoneColor.RED)));
}
+
+ // initial meld points
+ if (pointsValue.get(i) != null) {
+ add(when(onTable.get(i),
+ same(stoneValue.get(i), pointsValue.get(i))));
+ add(unless(onTable.get(i), constant(pointsValue.get(i), 0)));
+ }
}
public boolean solve() {
@@ -342,10 +380,12 @@ public class TurnLogic {
System.out.print("["
+ stoneColor.get(i).getValue().toString().substring(0, 1)
+ stoneValue.get(i).getValue() + "]");
- // + "," + leftNeighbor.get(i).getValue() +
- // hasLeftNeighbor.get(i).getValue() + lowCount.get(i).getValue() + ","
- // + rightNeighbor.get(i).getValue() +
- // hasRightNeighbor.get(i).getValue() + highCount.get(i).getValue() +
- // "]");
+ /*
+ * + "," + leftNeighbor.get(i).getValue() +
+ * hasLeftNeighbor.get(i).getValue() + lowCount.get(i).getValue() + ","
+ * + rightNeighbor.get(i).getValue() +
+ * hasRightNeighbor.get(i).getValue() + highCount.get(i).getValue() +
+ * "]");
+ */
}
}
diff --git a/src/jrummikub/ai/fdsolver/Constraints.java b/src/jrummikub/ai/fdsolver/Constraints.java
index 0885d2a..caa8cfa 100644
--- a/src/jrummikub/ai/fdsolver/Constraints.java
+++ b/src/jrummikub/ai/fdsolver/Constraints.java
@@ -7,6 +7,7 @@ import jrummikub.ai.fdsolver.constraint.FilterConstraint;
import jrummikub.ai.fdsolver.constraint.IfConstraint;
import jrummikub.ai.fdsolver.constraint.IndexConstraint;
import jrummikub.ai.fdsolver.constraint.LessThan;
+import jrummikub.ai.fdsolver.constraint.ListSumConstraint;
import jrummikub.ai.fdsolver.constraint.OffsetConstraint;
import jrummikub.ai.fdsolver.constraint.SameConstraint;
import jrummikub.ai.fdsolver.constraint.SumConstraint;
@@ -46,6 +47,10 @@ public class Constraints {
return new SumConstraint(x, y, z);
}
+ public static Constraint sum(Var<Integer> sum, List<Var<Integer>> list) {
+ return new ListSumConstraint(sum, list);
+ }
+
public static <T extends Comparable<T>> Constraint lessThan(Var<T> x, Var<T> y) {
return new LessThan<T>(false, x, y);
}
diff --git a/src/jrummikub/ai/fdsolver/Var.java b/src/jrummikub/ai/fdsolver/Var.java
index a454487..e885cef 100644
--- a/src/jrummikub/ai/fdsolver/Var.java
+++ b/src/jrummikub/ai/fdsolver/Var.java
@@ -42,6 +42,9 @@ public class Var<T> implements Comparable<Var<T>> {
range.remove(value);
solver.logInvalidation(this, value);
makeDirty();
+ if (range.size() == 0) {
+ solver.contradiction = true;
+ }
}
HashSet<Constraint> getConstraints() {
diff --git a/src/jrummikub/ai/fdsolver/constraint/ListSumConstraint.java b/src/jrummikub/ai/fdsolver/constraint/ListSumConstraint.java
new file mode 100644
index 0000000..22f480f
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/ListSumConstraint.java
@@ -0,0 +1,91 @@
+package jrummikub.ai.fdsolver.constraint;
+
+import java.util.ArrayList;
+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 java.util.Set;
+
+import jrummikub.ai.fdsolver.Constraint;
+import jrummikub.ai.fdsolver.Propagator;
+import jrummikub.ai.fdsolver.Satisfiability;
+import jrummikub.ai.fdsolver.Var;
+
+public class ListSumConstraint extends Constraint {
+ Var<Integer> sum;
+ List<Var<Integer>> list;
+ List<Var<?>> vars = new ArrayList<Var<?>>();
+
+ public ListSumConstraint(Var<Integer> sum, List<Var<Integer>> list) {
+ this.sum = sum;
+ this.list = list;
+ vars.add(sum);
+ vars.addAll(list);
+ }
+
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return vars;
+ }
+
+ @Override
+ public Collection<Propagator> getPropagators(boolean negate) {
+ return Collections.emptyList();
+ }
+
+ @Override
+ public Satisfiability getSatisfiability() {
+ List<Integer> values = new ArrayList<Integer>();
+ int valueSum = 0;
+ boolean isTaut = sum.getRange().size()==1;
+ for (Var<Integer> var : list) {
+ Iterator<Integer> it = var.getRange().iterator();
+ int value = it.next();
+ if (it.hasNext())
+ isTaut = false;
+ values.add(value);
+ valueSum += value;
+ }
+ if (isTaut) {
+ if (valueSum == sum.getValue()) {
+ return Satisfiability.TAUT;
+ } else {
+ return Satisfiability.UNSAT;
+ }
+ }
+
+ Set<Integer> reachableValues = new HashSet<Integer>();
+ Set<Integer> newValues = new HashSet<Integer>();
+ reachableValues.add(valueSum);
+
+ if (sum.getRange().contains(valueSum)) {
+ return Satisfiability.SAT;
+ }
+
+ for (int i = 0; i < values.size(); i++) {
+ Var<Integer> var = list.get(i);
+ int offset = values.get(i);
+ for (int x : var.getRange()) {
+ if (x == offset)
+ continue;
+ newValues.clear();
+ for (int y : reachableValues) {
+ int newValue = x + y - offset;
+ if (!reachableValues.contains(newValue)) {
+ newValues.add(x + y - offset);
+ }
+ }
+ if (!Collections.disjoint(sum.getRange(), newValues)) {
+ return Satisfiability.SAT;
+ }
+ reachableValues.addAll(newValues);
+ }
+ }
+
+ return Satisfiability.UNSAT;
+ }
+
+}
diff --git a/src/jrummikub/model/Hand.java b/src/jrummikub/model/Hand.java
index 681241a..c656afd 100644
--- a/src/jrummikub/model/Hand.java
+++ b/src/jrummikub/model/Hand.java
@@ -1,12 +1,15 @@
package jrummikub.model;
-import static jrummikub.model.StoneTray.Direction.*;
+import static jrummikub.model.StoneTray.Direction.LEFT;
+import static jrummikub.model.StoneTray.Direction.RIGHT;
import java.util.ArrayList;
+import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.TreeMap;
+import jrummikub.ai.TurnLogic;
import jrummikub.control.AIUtil;
import jrummikub.util.Pair;
@@ -44,8 +47,8 @@ public class Hand extends StoneTray<Stone> implements IHand {
}
@Override
- protected Pair<Position, Direction> fixInvalidDrop(Stone stone, Position pos,
- Direction dir) {
+ protected Pair<Position, Direction> fixInvalidDrop(Stone stone,
+ Position pos, Direction dir) {
double x = pos.getX();
double y = pos.getY();
@@ -56,9 +59,11 @@ public class Hand extends StoneTray<Stone> implements IHand {
return new Pair<Position, Direction>(new Position(0, y), RIGHT);
} else {
if (getFreeRowSpace((int) y) == 0) {
- return new Pair<Position, Direction>(new Position(0, y + 1), RIGHT);
+ return new Pair<Position, Direction>(new Position(0, y + 1),
+ RIGHT);
} else {
- return new Pair<Position, Direction>(new Position(WIDTH - 1, y), LEFT);
+ return new Pair<Position, Direction>(
+ new Position(WIDTH - 1, y), LEFT);
}
}
}
@@ -80,29 +85,23 @@ public class Hand extends StoneTray<Stone> implements IHand {
@Override
public boolean isInitialMeldPossible(GameSettings settings) {
- AIUtil aiUtil = new AIUtil(settings);
+ List<Stone> handStones = new ArrayList<Stone>();
- List<Stone> stones = new ArrayList<Stone>();
-
- for (Iterator<Pair<Stone, Position>> iter = this.iterator(); iter.hasNext();) {
- stones.add(iter.next().getFirst());
+ for (Pair<Stone, Position> entry : this) {
+ handStones.add(entry.getFirst());
}
- Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer> stoneCounts = AIUtil
- .countStones(stones);
-
- Pair<List<StoneSet>, Integer> result = aiUtil.findSetsWithTotalPoints(
- settings.getInitialMeldThreshold(), stoneCounts.getFirst(),
- stoneCounts.getSecond());
-
- return (result.getSecond() >= settings.getInitialMeldThreshold());
+ TurnLogic turnLogic = new TurnLogic(settings,
+ Collections.<Stone> emptyList(), handStones);
+ return turnLogic.solve();
}
@Override
public int getIdenticalStoneCount() {
List<Stone> stones = new ArrayList<Stone>();
- for (Iterator<Pair<Stone, Position>> iter = this.iterator(); iter.hasNext();) {
+ for (Iterator<Pair<Stone, Position>> iter = this.iterator(); iter
+ .hasNext();) {
stones.add(iter.next().getFirst());
}