package jrummikub.ai; import java.util.ArrayList; import java.util.Arrays; 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; import jrummikub.model.Stone; 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; private List inputStones; private StoneColor maxColor; private StoneColor minColor; private ArrayList stoneColors; private volatile State bestState; private ArrayList stack = new ArrayList(); private State top; private volatile boolean abort = false; private volatile boolean autoAbort = false; private int neededPoints = 0; private double neededScore = 0; @SuppressWarnings("serial") private static class Contradiction extends Throwable { } private class State { ArrayList stones = new ArrayList(); HashSet changedStones = new HashSet(); ArrayList jokerIDs = new ArrayList(); public State() { } public State(State state) { for (StoneState stone : state.stones) { stones.add(new StoneState(stone)); } jokerIDs = state.jokerIDs; } public void add(StoneState stone) { stones.add(stone); changedStones.add(stones.size() - 1); if (stone.joker) { jokerIDs.add(stone.id); } } public void updateStones() throws Contradiction { checkJokerCount(); for (int i : changedStones) { stones.get(i).checkState(); } checkScoreAndPoints(); while (!changedStones.isEmpty()) { while (!changedStones.isEmpty()) { updateStonesStep(); checkScoreAndPoints(); } checkJokerCount(); checkScoreAndPoints(); } } public void updateStonesStep() throws Contradiction { HashSet newChangedStones = new HashSet(); for (int i = 0; i < stoneCount; i++) { StoneState stone = stones.get(i); if (stone.isInterested(changedStones)) { if (stone.update(changedStones)) { newChangedStones.add(i); } } } changedStones = newChangedStones; } public boolean isSolved() { for (StoneState stone : stones) { if (!stone.isSolved()) { return false; } } return true; } 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 (stone.needsJoker(false)) { jokersRight--; if (jokersRight < 0) { throw new Contradiction(); } } } } public void checkScoreAndPoints() throws Contradiction { if (getPoints() < neededPoints) { throw new Contradiction(); } if (getScore() <= neededScore) { throw new Contradiction(); } } public int getPoints() { int sum = 0; for (StoneState stone : stones) { if (stone.onTable != Boolean.FALSE) { sum += stone.getPoints(); } } return sum; } public double getScore() { double sum = 0; for (StoneState stone : stones) { if (stone.onTable != Boolean.FALSE) { sum += stone.getScore(); } } return sum; } } private class StoneState { int id; boolean joker; Integer value; StoneColor color; Boolean onTable; boolean fromTable; HashSet leftRun; HashSet rightRun; HashSet leftGroup; HashSet rightGroup; public StoneState(int id, Stone stone, boolean table) { this.id = id; joker = stone.isJoker(); if (!joker) { this.value = stone.getValue(); this.color = stone.getColor(); } onTable = table ? true : null; fromTable = table; leftRun = makeFullSet(); rightRun = makeFullSet(); leftGroup = makeFullSet(); rightGroup = makeFullSet(); } public StoneState(StoneState stone) { this.id = stone.id; this.joker = stone.joker; this.value = stone.value; this.color = stone.color; this.onTable = stone.onTable; this.fromTable = stone.fromTable; this.leftRun = new HashSet(stone.leftRun); this.rightRun = new HashSet(stone.rightRun); this.leftGroup = new HashSet(stone.leftGroup); this.rightGroup = new HashSet(stone.rightGroup); } private HashSet makeFullSet() { HashSet set = new HashSet(); for (int i = 0; i < stoneCount; i++) { if (i != id) { set.add(i); } } set.add(null); return set; } public boolean isInterested(HashSet changes) { return !(Collections.disjoint(changes, leftRun) && Collections.disjoint(changes, rightRun) && Collections.disjoint(changes, leftGroup) && Collections .disjoint(changes, rightGroup)); } public > boolean lessThan(T a, T b) { return a == null || b == null || a.compareTo(b) < 0; } public boolean same(T a, T b) { return a == null || b == null || a.equals(b); } public boolean step(Integer a, Integer b) { return a == null || b == null || (int) a == b - 1; } public 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) { if (isNullSet(leftGroup) && isNullSet(other.rightGroup)) { return false; } if (other.color == minColor || color == maxColor) { return false; } return lessThan(color, other.color) && same(value, other.value); } public boolean runNeighbor(StoneState other) { if (isNullSet(leftRun) && isNullSet(other.rightRun)) { return false; } if (!same(color, other.color)) { return false; } if (settings.isNoLimits()) { return cycleStep(value, other.value); } else { if (((Integer) 1).equals(other.value) || ((Integer) settings.getHighestValue()).equals(value)) { return false; } return step(value, other.value); } } 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; HashSet relevantChanges = new HashSet(leftRun); relevantChanges.retainAll(changes); for (int i : relevantChanges) { StoneState other = top.stones.get(i); if (!other.runNeighbor(this) || !other.rightRun.contains(id)) { leftRun.remove(i); changed = true; } else if (other.rightRun.size() == 1 && other.onTable == Boolean.TRUE) { changed |= leftRun.retainAll(Arrays.asList(i)); changed |= onTable != Boolean.TRUE; onTable = true; break; } } 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); if (!this.runNeighbor(other) || !other.leftRun.contains(id)) { rightRun.remove(i); changed = true; } else if (other.leftRun.size() == 1 && other.onTable == Boolean.TRUE) { changed |= rightRun.retainAll(Arrays.asList(i)); changed |= onTable != Boolean.TRUE; onTable = true; break; } } return changed; } public 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)) { leftGroup.remove(i); changed = true; } else if (other.rightGroup.size() == 1 && other.onTable == Boolean.TRUE) { changed |= leftGroup.retainAll(Arrays.asList(i)); changed |= onTable != Boolean.TRUE; onTable = true; 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) { StoneState other = top.stones.get(i); if (!this.groupNeighbor(other) || !other.leftGroup.contains(id)) { rightGroup.remove(i); changed = true; } else if (other.leftGroup.size() == 1 && other.onTable == Boolean.TRUE) { changed |= rightGroup.retainAll(Arrays.asList(i)); changed |= onTable != Boolean.TRUE; onTable = true; break; } } return changed; } public boolean checkState() throws Contradiction { boolean changed = false; if (onTable == Boolean.FALSE) { if (leftRun.size() + rightRun.size() + leftGroup.size() + rightGroup.size() != 0) { leftRun.clear(); rightRun.clear(); leftGroup.clear(); rightGroup.clear(); return true; } 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)); } if (!(leftRun.contains(null) || rightRun.contains(null))) { 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, rightGroup, leftRun); for (int i = 0; i < 4; i++) { if (isNullSet(sets.get(i)) && isNullSet(sets.get(i + 1)) && isNullSet(sets.get(i + 2))) { 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); } if (isSingleNonNullSet(rightRun) && isNullSet(top.stones.get(rightRun.iterator().next()).rightRun)) { changed |= leftRun.remove(null); } if (isSingleNonNullSet(leftGroup) && isNullSet(top.stones.get(leftGroup.iterator().next()).leftGroup)) { changed |= rightGroup.remove(null); } if (isSingleNonNullSet(rightGroup) && 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) { throw new Contradiction(); } if (onTable == null) { onTable = false; leftRun.clear(); rightRun.clear(); leftGroup.clear(); rightGroup.clear(); changed = true; } } return changed; } private void checkGroupRunExclusive() throws Contradiction { if ((isSingleNonNullSet(leftGroup) || isSingleNonNullSet(rightGroup)) && (isSingleNonNullSet(leftRun) || isSingleNonNullSet(rightRun))) { throw new Contradiction(); } } private boolean checkJoker() { 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() { if (onTable == Boolean.FALSE) { return true; } if (onTable == null || color == null || value == null) { return false; } if (leftRun.size() > 1 || rightRun.size() > 1 || leftGroup.size() > 1 || rightGroup.size() > 1) { return false; } return true; } public double getScore() { if (fromTable) { return 0; } return 1; } public double getPoints() { if (fromTable) { return 0; } if (value == null) return (double) settings.getHighestValue(); 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) { return i.size() == 1 && i.contains(null); } private static boolean isSingleNonNullSet(HashSet i) { 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; stoneCount = tableStones.size() + handStones.size(); maxColor = Collections.max(settings.getStoneColors()); minColor = Collections.min(settings.getStoneColors()); stoneColors = new ArrayList(settings.getStoneColors()); Collections.sort(stoneColors); top = new State(); stack.add(top); ArrayList> sortedStones = new ArrayList>(); inputStones = new ArrayList(); for (Stone stone : tableStones) { sortedStones.add(new Pair(stone, true)); } for (Stone stone : handStones) { sortedStones.add(new Pair(stone, false)); } Collections.sort(sortedStones, new Comparator>() { @Override public int compare(Pair o1, Pair o2) { int cmp; cmp = ((Boolean) o1.getFirst().isJoker()).compareTo(o2 .getFirst().isJoker()); if (cmp != 0) { return -cmp; } cmp = (o1.getFirst().getColor()).compareTo(o2.getFirst() .getColor()); if (cmp != 0) { return cmp; } 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); } /** * Include initial meld threshold into turn logic */ public void needIntialMeldThreshold() { neededPoints = settings.getInitialMeldThreshold(); } private void pop() { stack.remove(stack.size() - 1); if (!stack.isEmpty()) { top = stack.get(stack.size() - 1); } } private void replace() { stack.remove(stack.size() - 1); } private void pushes(State... states) { for (State state : states) { stack.add(state); } } private void done() { 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; if (result == null) { return null; } ArrayList outputSets = new ArrayList(); for (int i = 0; i < stoneCount; i++) { StoneState stone = result.stones.get(i); if (isNullSet(stone.leftRun) && isNullSet(stone.leftGroup)) { ArrayList setStones = new ArrayList(); while (true) { setStones.add(inputStones.get(stone.id)); if (isNullSet(stone.rightRun) && isNullSet(stone.rightGroup)) { break; } Integer rightRunID = stone.rightRun.iterator().next(); Integer rightGroupID = stone.rightGroup.iterator().next(); stone = result.stones.get(rightRunID == null ? rightGroupID : rightRunID); } outputSets.add(new StoneSet(setStones)); } } return outputSets; } /** * Solves next state on stack while not aborted * * @return solved */ public boolean solve() { if (top.isSolved()) { pop(); } while (stack.size() != 0) { if (abort) { return false; } try { top.updateStones(); if (top.isSolved()) { bestState = top; return true; } branch(); done(); } catch (Contradiction c) { pop(); } } 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(); System.out.println(neededScore); } return neededScore; } private void branch() throws Contradiction { ArrayList indices = new ArrayList(); for (int i = 0; i < stoneCount; i++) { 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); return; } if (stone.rightRun.size() > 1) { replace(); branchRightRun(i, stone); return; } if (stone.leftGroup.size() > 1) { replace(); branchLeftGroup(i, stone); return; } if (stone.rightGroup.size() > 1) { replace(); 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); return; } if (stone.value == null) { replace(); branchValue(i); return; } } // This should never happen 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 = true; newState.changedStones.add(i); State altState = new State(top); altState.stones.get(i).onTable = false; 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; } }