AI: First Strike / Deathtouch: computer attacks with big creature even though it will be killed by many smaller defenders (who, in turn, will survive)

allentiak commented 4 years ago

Concerned abilities: first strike, deathtouch. The AI doesn't seem to learn from its first mistake, as the bug happens twice in the same game(!).

Ex. 1:

A big creature attacks and is blocked by many first-striking (albeit smaller) ones. As the sum of the defending creatures' power is equal or greater than the attacking creature's toughness, the attacking creature dies. All defenders survive unscratched.

This attack should not have been ordered by the AI...

Ex. 2:

A big creature attacks and is blocked by many first-striking, deathtouching (albeit smaller) ones. As the sum of the defending creatures' power is equal or greater than the attacking creature's toughness, the attacking creature dies. (Plus, they have deathtouch. Even if only one of them had blocked the bigger creature, the attacker would have died anyways.) All defenders survive unscratched.

This attack should not have been ordered by the AI either...

Relevant log lines

L224:

Attacker:

Matter Reshaper (3/2)

Defenders:

Plated Sliver (1/2, first strike),
Striking Sliver (1/2, first strike)

L385:

Attacker:

Thought-Knot Seer (4/4)

Defenders:

Plated Sliver (1/2, first strike, flying, haste, deathtouch),
Striking Sliver (1/2, first strike, flying, haste, deathtouch),
Cloudshredder Sliver (1/2, first strike, flying, haste, deathtouch),
Venom Sliver (1/2, first strike, flying, haste, deathtouch)

Logfile:

XMage 1.4.43V0 (2020.06.20) 20200621_194001_Two Player Duel_2.txt

LevelX2 commented 4 years ago

The AI doesn't seem to learn from its first mistake, as the bug happens twice in the same game(!).

This AI can't learn anything.

allentiak commented 4 years ago

On Mon, 22 Jun 2020, 10:48 LevelX2, notifications@github.com wrote:

This AI can't learn anything.

Depending on the algorithm, you may be right :-)

But that was not my point.

My point is that I think the AI shouldn't attack you when it has all the needed information available on the board to predict that its attack will be not only useless, but (even more!) counter productive.

And that's why I think it's a bug.

(Of course, you may disagree on my conclusion, but that's another story :-)

jeffwadsworth commented 4 years ago

It is an AI issue that has existed since the Big Bang. Not really a bug; it is just that the AI doesn't have a system in place to check all possible states resulting from attacking/blocking. It is specifically coded to handle certain common cases. If there was a efficient algorithm to quickly generate all attacker/blocker configs, then it could be done. I have code that will check the generated groups, etc.

allentiak commented 4 years ago

@LevelX2, @jeffwadsworth

Not really a bug; it is just that the AI doesn't have a system in place to check all possible states resulting from attacking/blocking. -- jeffwadsworth

Strictly speaking, that means that the algorithm does not correctly address the problem it is intending to solve. In lay terms, that algorithm (or its implementation, thereof) is... ahem... buggy :-)

The good news is that, since XMage is libre software, that's not necessarily a problem. You could check Magarena's MCTS AI implementation. Whereas I am not sure whether it actually solves this particular problem (I haven't used Magarena with the decks I submitted here), you will find there a simpler MCTS implementation that you might want to consider for implementation in XMage. In that case, I would suggest contacting Melvin Zhang, Magarena's main maintainer. (Disclosure: I have contributed some code to Magarena, and I do know MZ. In fact, if there is one thing I can say from him, is that he is very open about contributors to the project: he gave me committer access after only a few minor contributions.)

Just take into account that, as Magarena's License (GPL3) is a copyleft one, if you use that code in any way you will be forced to change the current (non-copyleft) X11-slyle XMage license into (copyleft) GPL3.

Of course, whereas: I personally consider that change would be beneficial for Mage in many aspects*, I am completely aware that making that change is definitely not my call.

*The fact of XMage's non-copyleft X11-style license is one of the reasons why I am reluctant to contributing code to XMage myself. Of course, given enough support from core developers, I could argue for the change in more detail. That being said, the general rationale can be found in Bruce Perens' How many open source licenses do you need?

JayDi85 commented 4 years ago

XMage already have MCTS AI implementation (it's old code but it works as proof of concept). Even more -- current AI implementation uses abilities and targets combination to simulate games and find best decision (works for priority plays only... don't know about attack/defence).

allentiak commented 4 years ago

@JayDi85 Have you considered comparing the performance of both implementations?

JayDi85 commented 4 years ago

MCTS is extremly slow.

allentiak commented 4 years ago

You haven't answered my question. Nor the main point of my earlier comment.

jeffwadsworth commented 4 years ago

All of us are quite familiar with Magarena's implementation. Its structure is quite different from Magefree. Perhaps you could implement it. That would be great and most appreciated. If not, come up with the code for an efficient attacker/blocker group generator. That is much easier and would resolve your issues as well.

allentiak commented 4 years ago

In order to consider your request, I would very much welcome some feedback in order to allowing compiling XMage under OpenJDK (see #6703).

jeffwadsworth commented 4 years ago

I only use 1.8, so I can't assist you in that task. Hopefully, you guys figure that out.

allentiak commented 4 years ago

Related to #6839

jeffwadsworth commented 1 year ago

I was fooling around with that OpenAI chatbot and it generated some interesting code for attacking and blocking creatures. This thing is an amazing tool. Just a bit of the session text in raw text (I am using my phone...) I will clean it up later:

Me: Code an algorithm in Java that generates all the attacker and blocker combat combinations possible in card game called "Magic the Gathering" during the combat phase.

Bot: Here is an example of how you could code an algorithm in Java to generate all the possible attacker and blocker combinations in a game of Magic the Gathering during the combat phase:

import java.util.ArrayList; import java.util.List;

public class CombatCombinations { public static void main(String[] args) { // Create a list of all the attackers on the battlefield List attackers = new ArrayList<>(); attackers.add(new Card("Attacker 1")); attackers.add(new Card("Attacker 2")); attackers.add(new Card("Attacker 3"));

    // Create a list of all the blockers on the battlefield
    List<Card> blockers = new ArrayList<>();
    blockers.add(new Card("Blocker 1"));
    blockers.add(new Card("Blocker 2"));
    blockers.add(new Card("Blocker 3"));

    // Generate all the possible attacker-blocker combinations
    for (Card attacker : attackers) {
        for (Card blocker : blockers) {
            System.out.println(attacker.getName() + " vs " + blocker.getName());
        }
    }
}

}

class Card { private String name;

public Card(String name) {
    this.name = name;
}

public String getName() {
    return this.name;
}

}

In this code, we first create two lists, one for the attackers and one for the blockers on the battlefield. We then use a nested loop to iterate over each attacker and blocker and generate all the possible combinations.

For each combination, we simply print the name of the attacker and blocker to the console. You can modify this code to perform any other actions you want for each combination, such as simulating the combat and determining the outcome.

Me: Run a simulation of that code you produced and show me the print out for 2 attackers and 3 blockers.

Bot: Here is an example of how the output of the code might look like if you run it with 2 attackers and 3 blockers:

Attacker 1 vs Blocker 1 Attacker 1 vs Blocker 2 Attacker 1 vs Blocker 3 Attacker 2 vs Blocker 1 Attacker 2 vs Blocker 2 Attacker 2 vs Blocker 3

As you can see, the algorithm generates all the possible combinations of attackers and blockers and prints them to the console. The number of combinations is equal to the number of attackers multiplied by the number of blockers, in this case 2 * 3 = 6.

Me: In combat, the attacker can be blocked by multiple blockers as well. Your code just has one blocker being used against one attacker, instead of showing combinations involving multiple blockers. Do you understand the issue here?

Bot: Yes, I understand the issue. The code I provided generates all the possible combinations of attackers and blockers, but only allows for one blocker to be assigned to each attacker. In reality, an attacker can be blocked by multiple blockers in Magic the Gathering.

To fix this issue, we can use a different approach to generate the combinations. Instead of using nested loops, we can use a recursive method that generates all the possible combinations of blockers for a given attacker. Here is an example of how this might look like:

import java.util.ArrayList; import java.util.List;

public class CombatCombinations { public static void main(String[] args) { // Create a list of all the attackers on the battlefield List attackers = new ArrayList<>(); attackers.add(new Card("Attacker 1")); attackers.add(new Card("Attacker 2"));

    // Create a list of all the blockers on the battlefield
    List<Card> blockers = new ArrayList<>();
    blockers.add(new Card("Blocker 1"));
    blockers.add(new Card("Blocker 2"));
    blockers.add(new Card("Blocker 3"));

    // Generate all the possible attacker-blocker combinations
    for (Card attacker : attackers) {
        generateCombinations(attacker, blockers, new ArrayList<>());
    }
}

private static void generateCombinations(Card attacker, List<Card> blockers, List<Card> currentBlockers) {
    if (blockers.isEmpty()) {
        // No more blockers to choose from, print the current combination
        System.out.print(attacker.getName() + " vs");
        for (Card blocker : currentBlockers) {
            System.out.print(" " + blocker.getName());
        }
        System.out.println();
        return;
    }

    // Try assigning the first blocker in the list to the current attacker
    Card firstBlocker = blockers.get(0);
    List<Card> remainingBlockers = blockers.subList(1, blockers.size());
    List<Card> newBlockers = new ArrayList<>(currentBlockers);
    newBlockers.add(firstBlocker);

    // Generate combinations with and without the first blocker
    generateCombinations(attacker, remainingBlockers, currentBlockers);
    generateCombinations(attacker, remainingBlockers, newBlockers);
}

}

class Card { private String name;

public Card(String name) {
    this.name = name;
}

public String getName() {
    return this.name;
}

}

In this code, we use a recursive method called generateCombinations to generate all the possible combinations of blockers for a given attacker. The method takes the attacker, the list of available blockers, and the list of blockers currently assigned to the attacker as arguments.

For each combination, the method first checks if there are no more blockers to choose from. If this is the case, it prints the current combination of attacker and blockers to the console.

If there are still blockers to choose from, the method assigns the first blocker in the list to the current attacker and generates all the possible combinations with and without this blocker. This is done by calling the generateCombinations method recursively with the updated lists of

Me: Your response was cut off at the end. What did you write after the line "method recursively with the updated lists of"?

Bot: Here is the rest of the sentence that was cut off in my previous response:

method recursively with the updated lists of blockers and assigned blockers.

This means that the generateCombinations method is called twice, once with the original list of blockers and the current list of assigned blockers, and once with the list of blockers excluding the first blocker and the updated list of assigned blockers that includes the first blocker.

This recursive approach allows us to generate all the possible combinations of attackers and blockers, including cases where an attacker is blocked by multiple blockers.

Here is an example of how the output of the code might look like if you run it with 2 attackers and 3 blockers:

Attacker 1 vs Attacker 1 vs Blocker 1 Attacker 1 vs Blocker 2 Attacker 1 vs Blocker 3 Attacker 1 vs Blocker 1 Blocker 2 Attacker 1 vs Blocker 1 Blocker 3 Attacker 1 vs Blocker 2 Blocker 3 Attacker 2 vs Attacker 2 vs Blocker 1 Attacker 2 vs Blocker 2 Attacker 2 vs Blocker 3 Attacker 2 vs Blocker 1 Blocker 2 Attacker 2 vs Blocker 1 Blocker 3 Attacker 2 vs Blocker 2 Blocker 3

As you can see, the algorithm generates all the possible combinations of attackers and blockers, including cases where an attacker is blocked by multiple blockers. In this example, there are 2 * 7 = 14 different combinations.

magefree / mage