More Thoughts on AI

[Malban]

More thoughts on AI.

What I am doing right now ... I am trying to implement a new, better AI.
This is needed IMHO since JPortal is moving towards supporting new card types and more variaties of cards.

Up until now, it has been sorceries and creaturs which could be handled with some optimization within a relative simple "allround AI".
In the future with magic cards and with more different kinds of cards and actions more must be considered.

Since in general a computer AI is not intuitve and has "good" ideas created out of thin air... an AI will (most of the time) be based upon
computations.
Computations in the means of ...
- I try a lot of variations of my current possibilites, weight them in some way and chose one that in my weighting process wins.

As of now in JPortal there are two such processes.
1) Computations of creature battles
2) Computations of sorcery cards

Which at the moment are independend of each other.

My goal for the future "enhanced AI" is that the AI will "think" in terms of one Round, meaning the collection of all phases and substeps of one round.
The AI will plan one round starting in the UNTAP phase and will lay it´s path out till the ending phase.

Upon each step on it´s way AI should evaluate the situation anew and thus will be able to react to the doings the other player did.

I am not there yet.
One of the main hinderences on the ways is the sheer multitude of choices available to the AI.
My first goal therefor is to build a "simulation" (or actually many) which the AI will use to judge the current situation.

A brute force method here is virtually not possible to realize.
You will see why, while I keep on explaining what I am up to right now.

I started of with making a "better" combat simulation (all the while I found some mistakes in the old one - which will probably NOT be corrected).

Let´s assume combat situations.
Player 1 has three creatures and Player 2 has 3 creatures with whih he may block.

The effective combinations the attacker may chose to attack with are
A
B
C
AB
AC
BC
ABC

Order of attackers do not matter!

The effective combinations the blocker may block with are:
A
B
C
AB
BA
AC
CA
BC
CB
ABC
ACB
BAC
BCA
CAB
CBA
Order of blockers do matter!

All different variations put together give the amount of 105 different combat situations,
which an AI may use doing a brute force attack.
105 doesn´t sound like much, but just advancing to a battle of 7 attackers and 7 blockers
result in 127 differnet attacker possibilities and 13699 different blocker variations.
To do a calculation how many differents combat situations that give (building classes for comencing battles)
gives with my computer an "out of memory error".

The old AI gives up on that stage. It just says - the largest battle I do is 4 versus 4. If any greater battle is in
order I divide the attackers and blockers to equal sized chunks smaller that 5 and handle the situations by divide and conquer.
Which gives acceptable results, but not the optimum.

Right now I try to figure out sensible reduction schemes which will generate acceptable small variations which might be simulationable.

Example.
Right now I am experimenting with 5 attackers and 5 blockers.
Attacker 31 variations, Blockers 325 variations -> which results in 25945 uniquly different possible combat situations.

To be able to visualize the doings I created a battle simulations screen, in which I can try different settings.
I can list the permutations of attackers, blockers and all combat variations.

Right now I have found 5 noteworty elemination strategies.

a) Only use full blockerlist
(Meaning I only test battle situations where all blockers are used - "unused" blockers can be elemintated later on)
This is a good one since it reduces the combinations of blockers, BEFORE I create all battle combinations.
The Blocker variation with that is reduced to 120 and all combat permutaions are reduced to 6960

b) Blocker in defensive order
In most situations it is clever to only use blocker combinations with descending order of toughness value, meaning the toughest
one does the first blocking...
This (in the special case of my attack list) reduces the blocker permutaions to 31 and results in combat permutations of 7775.
This is also a good one since it reduces the combinations of blockers, BEFORE I create all battle combinations.

c) Remove unblockable attackers
If there are attackers which are unblockable by all blockers, than these can be removed from the evaluation,
the attackers will be added later manually, we can´t do anything about them anyway
This is also a good one since it reduces the combinations, BEFORE I create all battle combinations.

d) Remove unblockable blockers
Remove blockers which can not block at all
This is also a good one since it reduces the combinations of blockers, BEFORE I create all battle combinations.

c) + d)
Find combinations of attacker / blockers, which are not possible (flying / non flying... eg)
This "bad-combination"-list can be built beforehand.
While building the permutations of combat formations this can be checked and the combinations and all subsequent branches can be removed.

e) Remove non effective blockers
This must be done during the building of all battle permutations and do a "first step" simulations of a battle on the fly.
If a blocker is not effective
(Meaning:
- Attacker can not be killed by blockers, than only at MOST one blocker should be used
- if the first n blockers killed the attacker, than all n+1 blockers are useless
) the combat combination will be removed (and all subsequent "branches")

Doing all of the above, results in my test 5 versus 5 in VALID battle permutaions of
" only " 24!
Meaning this is only 1/1000 of the original battles to simulate!


I am still looking for further optmizations.

Right now I am thinking about:
- Attacker evaluation
If simulating a "blocker" situation, find a prioratized Attacker combintaion to block.
e.g.
* Block power descending, meaning block most powerfull creatures first
* Block preffered 1:1 kill creatures, meaning try to kill an attacker by one single blocker
etc

After finding an sufficient enough algorithm (certainly configurable) I will move on, by adding instants and abilities to the
simulation.

Than do an round based AI.

Than implement further magic cards.

Further Ideas:
- Tighten the relation of cards / AI / Hint system
meaning:
- define concrete and fixed rules for the hint system
- build a gui where these hints are forced
- if hints are "fixed" - two more things might be possible
a) by evaluating card text, hints may be automatically built (not all - but a great deal, there will allways be special cases in a game like magic)
b) built java-script - code from hints (this will also not allways be possible, but if only 60% - 80% is possible, card implementaion will be
very very much less painfull!)
c) base the AI - simulation code on hints

With all these in place, a majority of cards will be peanuts to implement!

Oh well, I have a whole life for implementation - don´t I?

Regards

Malban

[Huggybaby]

Doing all of the above, results in my test 5 versus 5 in VALID battle permutaions of
" only " 24!
Meaning this is only 1/1000 of the original battles to simulate!

Yes! That's awesome Malban. (I was playing JPortal just last night BTW.)

[Malban]

Thinking further - actually these are facts.

Next AI will be an "internal AI".
Meaning it will not be scripted.
The old scripting system will still be used and useable.

Nonetheless, development of an AI is easier (debugging) while not scripting, and the AI will be a bit faster.

I could do the new AI by scripting - but I won´t.

I will provide an Java-Interface for AI (in general), and the internal AI will be loaded "on the fly" (more or less a plugin mechansism).

The new AI will probably not support different "intelligence" settings. For more dumb AI one can still use the already implemented "allround AI".

A more restrictive "Hint System" will defenitly be done.

AI should not access hints directly anymore. Rather I will use some kind of proxy that will answer AI questions.
like:
- what kind of targets does that card have
- what type of card is it (damage, buff, heal...)
- ...

The whole collections amounts to quite a few open ends I have right now:

- Mana class
- new AI
- new Hint system
- new card types
- new battle simulation

I hope I won´t lose any of the open ends I am generating right now - this could be fatal for JPortal.



...

Malban

[Huggybaby]

The adjustable AI (doesn't matter if it's scripted or how it's implemented) is perhaps the most unique thing about JPortal, I'm glad it's not disappearing (yet).

[jeffwadsworth]

The following is a attacking and blocking combination generator. The capital letters are attackers and the numbers are blockers.
It also counts the number of combinations generated. I do not suggest going above 4 on 4. Gets nuts.

Code: Select all

import java.util.*;

public class CombinationGenerator {
    private Map<String, List<List<Integer>>> memo;
    private List<Character> attackers;
    private List<Integer> blockers;
    private int combinationCount;  // Counter for the number of combinations

    public CombinationGenerator(List<Character> attackers, List<Integer> blockers) {
        this.memo = new HashMap<>();
        this.attackers = attackers;
        this.blockers = blockers;
        this.combinationCount = 0;  // Initialize the counter
    }

    public void generateAndPrintCombinations() {
        List<List<Integer>> blockerSubsets = generateBlockerSubsets();
        generateAndPrintCombinations(attackers, blockerSubsets, 0, new ArrayList<>(), new HashSet<>());
    }

    private List<List<Integer>> generateBlockerSubsets() {
        List<List<Integer>> subsets = new ArrayList<>();
        generateBlockerSubsets(0, new ArrayList<>(), subsets);
        return subsets;
    }

    private void generateBlockerSubsets(int idx, List<Integer> currentSubset, List<List<Integer>> subsets) {
        if (idx == blockers.size()) {
            subsets.add(new ArrayList<>(currentSubset));
            return;
        }
        generateBlockerSubsets(idx + 1, currentSubset, subsets);

        currentSubset.add(blockers.get(idx));
        generateBlockerSubsets(idx + 1, currentSubset, subsets);
        currentSubset.remove(currentSubset.size() - 1);
    }

    private void generateAndPrintCombinations(List<Character> attackers, List<List<Integer>> blockerSubsets, int current, List<List<Integer>> result, Set<Integer> usedBlockers) {
        if (current == attackers.size()) {
            printResult(attackers, result);
            return;
        }

        for (List<Integer> subset : blockerSubsets) {
            if (Collections.disjoint(subset, usedBlockers)) {
                String key = generateKey(current, subset);
                if (!memo.containsKey(key)) {
                    List<List<Integer>> permutations = generatePermutations(new ArrayList<>(subset));
                    memo.put(key, permutations);
                }

                for (List<Integer> permutation : memo.get(key)) {
                    result.add(permutation);
                    usedBlockers.addAll(permutation);
                    generateAndPrintCombinations(attackers, blockerSubsets, current + 1, result, usedBlockers);
                    usedBlockers.removeAll(permutation);
                    result.remove(result.size() - 1);
                }
            }
        }
    }

    private List<List<Integer>> generatePermutations(List<Integer> subset) {
        List<List<Integer>> permutations = new ArrayList<>();
        generatePermutations(subset, 0, permutations);
        return permutations;
    }

    private void generatePermutations(List<Integer> arr, int index, List<List<Integer>> result) {
        if (index >= arr.size() - 1) {
            result.add(new ArrayList<>(arr));
            return;
        }

        for (int i = index; i < arr.size(); i++) {
            Collections.swap(arr, index, i);
            generatePermutations(arr, index + 1, result);
            Collections.swap(arr, index, i);
        }
    }

    private String generateKey(int current, List<Integer> subset) {
        return current + "-" + subset.toString();
    }

    private void printResult(List<Character> attackers, List<List<Integer>> result) {
        for (int i = 0; i < attackers.size(); i++) {
            System.out.print(attackers.get(i) + "->" + (result.get(i).isEmpty() ? "no blocker, " : result.get(i) + ", "));
        }
        System.out.println();
        combinationCount++;  // Increment the counter for each combination
    }
   
    public int getCombinationCount() {
        return combinationCount;
    }

    public static void main(String[] args) {
        List<Character> attackers = Arrays.asList('A', 'B', 'C');
        List<Integer> blockers = Arrays.asList(1, 2, 3);

        CombinationGenerator generator = new CombinationGenerator(attackers, blockers);
        generator.generateAndPrintCombinations();
        System.out.println("Total number of combat combinations: " + generator.getCombinationCount());
    }
}

[jeffwadsworth]

Here is a more "advanced" attacker and blocker combat combination code in Java. This one let's you limit the attackers and blockers in each combat group.

Code: Select all

import java.util.*;

public class CombinationGenerator {
    private Map<String, List<List<Integer>>> memo;
    private List<Character> attackers;
    private List<Integer> blockers;
    private int combinationCount;  // Counter for the number of combinations

    public CombinationGenerator(List<Character> attackers, List<Integer> blockers) {
        this.memo = new HashMap<>();
        this.attackers = attackers;
        this.blockers = blockers;
        this.combinationCount = 0;  // Initialize the counter
    }

    public void generateAndPrintCombinations() {
        List<List<Integer>> blockerSubsets = generateSubsets(blockers);
        List<List<Character>> attackerSubsets = generateSubsets(attackers);
        for (List<Character> attackerSubset : attackerSubsets) {
            generateAndPrintCombinations(attackerSubset, blockerSubsets, 0, new ArrayList<>(), new HashSet<>());
        }
    }

    private <T> List<List<T>> generateSubsets(List<T> items) {
        List<List<T>> subsets = new ArrayList<>();
        generateSubsetsRecursive(0, new ArrayList<>(), subsets, items);
        return subsets;
    }

    private <T> void generateSubsetsRecursive(int idx, List<T> currentSubset, List<List<T>> subsets, List<T> items) {
    if (idx == items.size()) {
        if (currentSubset.size() <= 2) { // Limit the subset size to 2 or fewer for both attackers and blockers
            subsets.add(new ArrayList<>(currentSubset));
        }
        return;
    }
    generateSubsetsRecursive(idx + 1, currentSubset, subsets, items);

    currentSubset.add(items.get(idx));
    generateSubsetsRecursive(idx + 1, currentSubset, subsets, items);
    currentSubset.remove(currentSubset.size() - 1);
}

    private void generateAndPrintCombinations(List<Character> attackerSubset, List<List<Integer>> blockerSubsets, int current, List<List<Integer>> result, Set<Integer> usedBlockers) {
        if (current == attackerSubset.size()) {
            printResult(attackerSubset, result);
            return;
        }

        for (List<Integer> subset : blockerSubsets) {
                String key = generateKey(current, subset);
                if (!memo.containsKey(key)) {
                    List<List<Integer>> permutations = generatePermutations(subset);
                    memo.put(key, permutations);
                }
                for (List<Integer> permutation : memo.get(key)) {
                    if (Collections.disjoint(permutation, usedBlockers)) {
                        result.add(permutation);
                        usedBlockers.addAll(permutation);
                        generateAndPrintCombinations(attackerSubset, blockerSubsets, current + 1, result, usedBlockers);
                        usedBlockers.removeAll(permutation);
                        result.remove(result.size() - 1);
                    }
                }
        }
    }

        private List<List<Integer>> generatePermutations(List<Integer> subset) {
        List<List<Integer>> permutations = new ArrayList<>();
        generatePermutations(subset, 0, permutations);
        return permutations;
    }

    private void generatePermutations(List<Integer> arr, int index, List<List<Integer>> result) {
        if (index >= arr.size() - 1) {
            result.add(new ArrayList<>(arr));
            return;
        }

        for (int i = index; i < arr.size(); i++) {
            Collections.swap(arr, index, i);
            generatePermutations(arr, index + 1, result);
            Collections.swap(arr, index, i);
        }
    }

    private String generateKey(int current, List<Integer> subset) {
        return current + "-" + subset.toString();
    }

    private void printResult(List<Character> attackerSubset, List<List<Integer>> result) {
        for (int i = 0; i < attackerSubset.size(); i++) {
            System.out.print(attackerSubset.get(i) + "->" + (result.get(i).isEmpty() ? "no blocker, " : result.get(i) + ", "));
        }
        System.out.println();
        combinationCount++;  // Increment the counter for each combination
    }

    public int getCombinationCount() {
        return combinationCount;
    }

    public static void main(String[] args) {
        List<Character> attackers = Arrays.asList('A', 'B', 'C', 'D', 'E');
        List<Integer> blockers = Arrays.asList(1, 2, 3, 4, 5);

        CombinationGenerator generator = new CombinationGenerator(attackers, blockers);
        generator.generateAndPrintCombinations();
        System.out.println("Total number of combat combinations: " + generator.getCombinationCount());
    }
}


Lastly, here is code that allows you to set a limit on just the blockers while allowing all attacker combinations to be considered.

Code: Select all

import java.util.*;

public class CombinationGenerator {
    private Map<String, List<List<Integer>>> memo;
    private List<Character> attackers;
    private List<Integer> blockers;
    private int combinationCount;  // Counter for the number of combinations

    public CombinationGenerator(List<Character> attackers, List<Integer> blockers) {
        this.memo = new HashMap<>();
        this.attackers = attackers;
        this.blockers = blockers;
        this.combinationCount = 0;  // Initialize the counter
    }

    public void generateAndPrintCombinations() {
        List<List<Integer>> blockerSubsets = generateSubsets(blockers);
        List<List<Character>> attackerSubsets = generateSubsets(attackers);
        for (List<Character> attackerSubset : attackerSubsets) {
            generateAndPrintCombinations(attackerSubset, blockerSubsets, 0, new ArrayList<>(), new HashSet<>());
        }
    }

    private <T> List<List<T>> generateSubsets(List<T> items) {
        List<List<T>> subsets = new ArrayList<>();
        generateSubsetsRecursive(0, new ArrayList<>(), subsets, items);
        return subsets;
    }

    // Modified to limit blocker size to 2 or fewer
    private <T> void generateSubsetsRecursive(int idx, List<T> currentSubset, List<List<T>> subsets, List<T> items) {
        if (idx == items.size()) {
            if (currentSubset.size() <= 2) { // Ensure the blocker size is 2 or fewer
                subsets.add(new ArrayList<>(currentSubset));
            }
            return;
        }
        generateSubsetsRecursive(idx + 1, currentSubset, subsets, items);

        currentSubset.add(items.get(idx));
        generateSubsetsRecursive(idx + 1, currentSubset, subsets, items);
        currentSubset.remove(currentSubset.size() - 1);
    }

    private void generateAndPrintCombinations(List<Character> attackerSubset, List<List<Integer>> blockerSubsets, int current, List<List<Integer>> result, Set<Integer> usedBlockers) {
        if (current == attackerSubset.size()) {
            printResult(attackerSubset, result);
            return;
        }

        for (List<Integer> subset : blockerSubsets) {
                String key = generateKey(current, subset);
                if (!memo.containsKey(key)) {
                    List<List<Integer>> permutations = generatePermutations(subset);
                    memo.put(key, permutations);
                }
                for (List<Integer> permutation : memo.get(key)) {
                    if (Collections.disjoint(permutation, usedBlockers)) {
                        result.add(permutation);
                        usedBlockers.addAll(permutation);
                        generateAndPrintCombinations(attackerSubset, blockerSubsets, current + 1, result, usedBlockers);
                        usedBlockers.removeAll(permutation);
                        result.remove(result.size() - 1);
                    }
                }
        }
    }

        private List<List<Integer>> generatePermutations(List<Integer> subset) {
        List<List<Integer>> permutations = new ArrayList<>();
        generatePermutations(subset, 0, permutations);
        return permutations;
    }

    private void generatePermutations(List<Integer> arr, int index, List<List<Integer>> result) {
        if (index >= arr.size() - 1) {
            result.add(new ArrayList<>(arr));
            return;
        }

        for (int i = index; i < arr.size(); i++) {
            Collections.swap(arr, index, i);
            generatePermutations(arr, index + 1, result);
            Collections.swap(arr, index, i);
        }
    }

    private String generateKey(int current, List<Integer> subset) {
        return current + "-" + subset.toString();
    }

    private void printResult(List<Character> attackerSubset, List<List<Integer>> result) {
        for (int i = 0; i < attackerSubset.size(); i++) {
            System.out.print(attackerSubset.get(i) + "->" + (result.get(i).isEmpty() ? "no blocker, " : result.get(i) + ", "));
        }
        System.out.println();
        combinationCount++;  // Increment the counter for each combination
    }

    public int getCombinationCount() {
        return combinationCount;
    }

    public static void main(String[] args) {
        List<Character> attackers = Arrays.asList('A', 'B', 'C', 'D', 'E');
        List<Integer> blockers = Arrays.asList(1, 2, 3, 4, 5);

        CombinationGenerator generator = new CombinationGenerator(attackers, blockers);
        generator.generateAndPrintCombinations();
        System.out.println("Total number of combat combinations: " + generator.getCombinationCount());
    }
}


And lastly, a version that let's you set each attacker and blocker maximum amount per combat group separately.

Code: Select all

import java.util.*;

public class CombinationGenerator {
    private Map<String, List<List<Integer>>> memo;
    private List<Character> attackers;
    private List<Integer> blockers;
    private int maxAttackerSize = 2;
    private int maxBlockSize = 2;
    private int combinationCount;  // Counter for the number of combinations

    public CombinationGenerator(List<Character> attackers, List<Integer> blockers) {
        this.memo = new HashMap<>();
        this.attackers = attackers;
        this.blockers = blockers;
        this.combinationCount = 0;  // Initialize the counter
    }

    public void generateAndPrintCombinations() {
        List<List<Integer>> blockerSubsets = generateSubsets(blockers, maxBlockSize);
List<List<Character>> attackerSubsets = generateSubsets(attackers, maxAttackerSize);

        for (List<Character> attackerSubset : attackerSubsets) {
            generateAndPrintCombinations(attackerSubset, blockerSubsets, 0, new ArrayList<>(), new HashSet<>());
        }
    }

    // This method now includes a maxSubsetSize parameter to control the subset size.
private <T> void generateSubsetsRecursive(int idx, List<T> currentSubset, List<List<T>> subsets, List<T> items, int maxSubsetSize) {
    if (idx == items.size()) {
        if (currentSubset.size() <= maxSubsetSize) {
            subsets.add(new ArrayList<>(currentSubset));
        }
        return;
    }
    generateSubsetsRecursive(idx + 1, currentSubset, subsets, items, maxSubsetSize);

    currentSubset.add(items.get(idx));
    generateSubsetsRecursive(idx + 1, currentSubset, subsets, items, maxSubsetSize);
    currentSubset.remove(currentSubset.size() - 1);
}

// Modify the generateSubsets method to accept the maxSubsetSize and pass it to the recursive method.
private <T> List<List<T>> generateSubsets(List<T> items, int maxSubsetSize) {
    List<List<T>> subsets = new ArrayList<>();
    generateSubsetsRecursive(0, new ArrayList<>(), subsets, items, maxSubsetSize);
    return subsets;
}

    private void generateAndPrintCombinations(List<Character> attackerSubset, List<List<Integer>> blockerSubsets, int current, List<List<Integer>> result, Set<Integer> usedBlockers) {
        if (current == attackerSubset.size()) {
            printResult(attackerSubset, result);
            return;
        }

        for (List<Integer> subset : blockerSubsets) {
                String key = generateKey(current, subset);
                if (!memo.containsKey(key)) {
                    List<List<Integer>> permutations = generatePermutations(subset);
                    memo.put(key, permutations);
                }
                for (List<Integer> permutation : memo.get(key)) {
                    if (Collections.disjoint(permutation, usedBlockers)) {
                        result.add(permutation);
                        usedBlockers.addAll(permutation);
                        generateAndPrintCombinations(attackerSubset, blockerSubsets, current + 1, result, usedBlockers);
                        usedBlockers.removeAll(permutation);
                        result.remove(result.size() - 1);
                    }
                }
        }
    }

        private List<List<Integer>> generatePermutations(List<Integer> subset) {
        List<List<Integer>> permutations = new ArrayList<>();
        generatePermutations(subset, 0, permutations);
        return permutations;
    }

    private void generatePermutations(List<Integer> arr, int index, List<List<Integer>> result) {
        if (index >= arr.size() - 1) {
            result.add(new ArrayList<>(arr));
            return;
        }

        for (int i = index; i < arr.size(); i++) {
            Collections.swap(arr, index, i);
            generatePermutations(arr, index + 1, result);
            Collections.swap(arr, index, i);
        }
    }

    private String generateKey(int current, List<Integer> subset) {
        return current + "-" + subset.toString();
    }

    private void printResult(List<Character> attackerSubset, List<List<Integer>> result) {
        for (int i = 0; i < attackerSubset.size(); i++) {
            System.out.print(attackerSubset.get(i) + "->" + (result.get(i).isEmpty() ? "no blocker, " : result.get(i) + ", "));
        }
        System.out.println();
        combinationCount++;  // Increment the counter for each combination
    }

    public int getCombinationCount() {
        return combinationCount;
    }

    public static void main(String[] args) {
        List<Character> attackers = Arrays.asList('A', 'B');
        List<Integer> blockers = Arrays.asList(1, 2);

        CombinationGenerator generator = new CombinationGenerator(attackers, blockers);
        generator.generateAndPrintCombinations();
        System.out.println("Total number of combat combinations: " + generator.getCombinationCount());
    }
}