AI Improvement

All about getting the AI less baka...
wololo
Site Admin
Posts: 3727
Joined: Wed Oct 15, 2008 12:42 am
Location: Japan

Re: AI Improvment.

Post by wololo » Sat Sep 26, 2009 11:21 am

Psyringe wrote:8. When the AI has an attacker with trample, it (sometimes? always?) assigns all the damage to the blocker/s, even if there's enough damage that could spill over to the opponent. Suggestion: Add a check for "Trample" ability to the code that assigns damage, and have the AI assign only the minimum necessary damage to the blockers if its attacker has Trample.
I believe this one is now fixed. Since the AI currently uses default damages, and the default damages for trample now do the "right" thing


Edit: psyringe, can you add your suggestions to the list of issues on google code ?
http://code.google.com/p/wagic/issues/list

It will help me track them more easily than on the forum

Psyringe
Posts: 1163
Joined: Mon Aug 31, 2009 10:53 am

Re: AI Improvment.

Post by Psyringe » Sat Sep 26, 2009 11:36 am

wololo wrote:Edit: psyringe, can you add your suggestions to the list of issues on google code ?
Will do. Not today (too little time to do anything systematically), but tomorrow should work.

Psyringe
Posts: 1163
Joined: Mon Aug 31, 2009 10:53 am

Re: AI Improvment.

Post by Psyringe » Mon Sep 28, 2009 6:53 am

Okay, I added the following suggestions to the list:

- AI too quick to cast spells with variable mana cost ("X")
- AI does not use mana from mana-producing spells
- AI plays Legends without checking whether they already exist on the battlefield
- AI too willing to sacrifice its creatures
- AI casts "Howl from Beyond" on opponent creatures
- AI taps card for mana to pay for the same card's ability (and then can't activate the ability any more)
- AI casts "Torture" (SHM) on own creatures (from "Bugs" thread)
- AI doesn't use fetchlands efficiently
- AI kills own creatures with a "may destroy" rule, instead of killing its opponent's creatures

Please inform me if I did anything wrong or if I can improve these suggestions in any other way. :)

The following issues have *not* been added to the list because they have been mentioned as "fixed" in either the "Bugs 0.8.1" thread or the SVN comments. I list them here to make it easy to double-check whether one of these should still be included - if so, just drop me a note:

- AI doesn't assign Trample damage to the player (reportedly fixed)
- AI casts Bravado on opponents (while checking the card's code, I thought of a potential fix that I want to try first)

Btw, is there a way for me to assign priorities to issues when adding them in Google? Some of the issues are clearly of low priority and wouldn't even qualify as "Defect", but I saw no way to specify other values.

wololo
Site Admin
Posts: 3727
Joined: Wed Oct 15, 2008 12:42 am
Location: Japan

Re: AI Improvment.

Post by wololo » Mon Sep 28, 2009 7:57 am

It seems that if you are not a member of the project you cannot change the priority of issues unfortunately. I'll seriously consider adding you as a project member, it will allow you to add AI decks and fix your existing ones without having to wait for a dev to report your updates.

Psyringe
Posts: 1163
Joined: Mon Aug 31, 2009 10:53 am

Re: AI Improvment.

Post by Psyringe » Thu Oct 22, 2009 11:50 am

Replying here to a post in the AI deck comparison thread:
John Rohan wrote:I did notice one thing with enchantments like Control Magic or Pacifism. If I have two creatures on the battlefield, one very large and one small, very often the AI will cast these enchantments on the small creature. I guess it chooses randomly. But I think by default, it should always automatically choose the larger one - either by casting cost or by Power.
The current AI doesn't (usually) know what a spell does when it casts it. It only knows that some spells do something "bad" to their targets, and tries to choose the most dangerous enemy creature as a target for those. IIRC "danger" is estimated by checking how much damage the creature has done to you, but there's also a random factor involved.

I haven't checked the code, but if the AI indeed keeps track of the damage caused by an enemy creature, then it might be an improvement if it kept track of "damage caused per turn" instead, so that it doesn't overvalue weak creatures because they've been longer in play, and had more opportunities to do a bit of damage.

Of course, an even better fix would be to make the AI understand the effects of the cards better, but that's apparently more complicated. ;)

Psyringe
Posts: 1163
Joined: Mon Aug 31, 2009 10:53 am

Re: AI Improvement

Post by Psyringe » Sat Nov 28, 2009 6:14 am

After watching lots of AI-vs-AI games for the AI Deck Competition, I think there are three main areas where the current AI has problems. I'm noting these down here partly as a "note to self" and partly to encourage discussion and suggestions.

1. Attacker/Blocker assignent. The AI often misses opportunities for riskless attacking (e.g. when it has flyers or shadow creatures that can't be blocked), on the other hand it often sacrifices it creatures unnecessarily in ill-advised attacks and blocks. Improving this will be difficult since an algorithm that actually deals with all (or even just some) of these variables is bound to become pretty complex.

2. Inability to use dual lands, fetchlands, or mana filters efficiently (or at all). As some of the participants in the AI deck competition remarked, this severely cripples the AI's ability to play non-monocolor decks, up to the point where deck creators consider staying away from creating such decks for future competitions due to their reduced competitivity. Finding an algorithm that improves this doesn't seem too hard, the problem is that such an algorithm would also need to be very efficient (due to the high number of things to check and the weak hardware it's running on), which *does* make it hard to find one, and that the AI currently cannot analyze alternative mana producing abilities of the same card at all.

3. Targeting efficiency. This has improved with the recent fix to AI memory (the AI now has a better idea of which creatures are the most dangerous), but the AI still wastes damage spells on creatures that don't get killed by them, and )apparently, I'll have to check that) doesn't understand the importance of lord cards very well. Unfortunately this kind of AI behavior gets immediately noticed by the player.

furiousone
Posts: 61
Joined: Sat Oct 31, 2009 10:30 pm

Re: AI Improvement

Post by furiousone » Sat Nov 28, 2009 7:10 am

I'm agree that the main issues with the current AI are the attacker/blocker issue and the targeting issue.
As far as I know the AI has the "memory" that tells him how much damage a particular creature has caused him, but I think that may not be enough. Again, I've only started looking into Wagic and dont really know how AI works, but I'll just throw in some ideas of what it should do and let's see if this is already in place or easy to implement.

For blocking:
I guess there are two main things to consider: who to block with and which creature to block.

First, let's focus on which creature is the most dangerous one. I think previous damage in this case is not a great indicator, because you could have had a 1/1 creature deal you 5 damage in 5 turns and now you have a 7/7 creature that is attacking for the first time. So I think the "dangerousness" coefficient should be based on a number of multiple indicators. Here are some suggestions of what to use:

a: Power - The stronger the creature, the more damage it will do to the AI.
b: Rarity - Most of the time rare and uncommon creatures are more valuable to the human player, so if we have a chance to destroy those - let's go for it. I think the value difference should be exponential when counting this component. Just like the difference in price between common, uncommon, and rare cards.
c: Previously dealt damage - I think this is already counted in the current AI algorithm. An important value in case the creature is damaging AI "indirectly" with something like {T}:deal 3 damage to the target opponent
d: Previously dealt damage/per turn - This way it will be a good indicator of how much damage the creature deals to the AI each turn, so the weaker creatures wont be as dangerous
e: Combined cost - Player has worked hard to put this guy out on the table and if we can destroy it that's great
f: Previously dealt damage to human - some creatures (black mostly) deal damage to its controller and I think the more damage it has dealt to its own controller, the less "dangerous" it is to us.
g: AI creatures killed by the creature - some cards that have "tap to destroy target non-black creature" dont have to attack to kill a creature.
h: Special abilities can be counted in as well. Abilities could be divided into "good" and "bad" abilites. For example, "tap to destroy target non-black creature" could have a rating of +10, and something like "each turn controller loses 2 life" could be counted as -10.

D = a*a_coeff+b*b_coeff+c*c_coeff+d*d_coeff+e*e_coeff-f*f_coeff+g*g_coeff+h*h_coeff

Where D is the "dangerousness" coefficient for a particular creature.
That's what I came up with so far. I know its something pretty simplistic but I tried to think of all of the possible factors that I usually consider when making a decision on which creature I dont like the most. This could also be used to determine the target for a "terror"-like spell.

Now, deciding on which creature to block with is another issue...

Psyringe
Posts: 1163
Joined: Mon Aug 31, 2009 10:53 am

Re: AI Improvement

Post by Psyringe » Sat Nov 28, 2009 7:39 am

Thanks, that's an impressive list, and not at all as "simplistic" as you think. ;)

Some info about the AI memory: If I understood wololo correctly, then this is a memory between games, not within a given game. Example: You play a game with your deck 5 against the AI. The AI notes down how much damage each of your creatures does and at the end of the game writes that information to the disk. Next time you play with deck 5 against the AI, the AI loads that information and uses it to assess your creatures' "dangerousness". I don't know whether the AI actually tracks the damage from a given creature within a given game - it probably does, but the information will have little weight if it's added to the accumulated data of 100 previous games against your deck. I also suspect (but can't be sure) that the AI stores this information as "damage per card id", not as "damage per individual card on the battlefield", which means that it can't distinguish between a War Mammoth that has Pacifism cast on it and that never attacked in the whole game, and a War Mammoth that attacked in each of the last 5 turns and caused 15 points of accumulated damage. If I'm guessing right, then both will have the same "dangerousness" rating in the AI memory.

I misunderstood the "long-term" aspect of the AI memory at first (and I think I wrote a couple of posts which might spread this misunderstanding to others, so I thought I'd better clarify it here).

I'll write a more complete reply to your post later (I need a bit of time to fully digest it :) ), but perhaps someone else jumps in with comments/ideas as well. :)

Szei
Posts: 218
Joined: Sat Nov 15, 2008 8:14 pm
Location: USA

Re: AI Improvment.

Post by Szei » Sat Nov 28, 2009 10:10 pm

Psyringe wrote: - AI kills own creatures with a "may destroy" rule, instead of killing its opponent's creatures
It also taps its own creatures with a 'may tap' rule (as with Deathbringer Liege). It's actually quite comical seeing the AI use Deathbringer Liege to tap and destroy itself (but comedy isn't what we're after =P)
Image

furiousone
Posts: 61
Joined: Sat Oct 31, 2009 10:30 pm

Re: AI Improvement

Post by furiousone » Sun Nov 29, 2009 2:26 am

Im playing a game right now against a deck which is a white deck with all the flying creatures and I have had like 12 creatures of mine on the table, basically killing the opponent's creatures with midnight banshee, but I could not attack!! I only have a couple of flying creatures, at the moment only one actually - Vampire Nighthawk. Now, AI has had a few times when it played "removed target creature from the game, its controller gains life equal to power" and it has played it on my 1/1 or 2/2 creatures. I think this example shows that having a statistic of the current game to determine the most dangerous creature would have killed this guy a long time ago and I would have been stuck with my 12/13 creatures not being able to do any damage. I guess eventually I would have won the game anyway, cause my deck is bigger, but I think at least I would have been furious with the AI when it killed my Vamp :)
Attachments

[The extension png has been deactivated and can no longer be displayed.]


Post Reply