Possible improvements for AI combat

[mtgrares]

I think I could improve the AI combat code but it would only value each creature by its power/toughness and getValue(Card) which returns a number. getValue() would return 100 for Royal Assassin and 1 for a generic 1/1. Do you think this would really improve the AI or not?

(The values returned by getValue() would be guesses but it would help the computer differentiate between low value and high value cards that have very good abilities like Royal Assassin.)

Right now the code for when the AI attacks or blocks is very, very simple, no simulations are run. Allowing the AI to run simulations that take a few seconds would simulate when you think ahead and figure out how your opponent may block.

On a side note, the new code would probably take a few seconds to run and some cards like Giant Growth "ask" the AI if a specific creature attacks or not. So the new card may break cards that increase the power/toughness.

I should be able to use a alpha-beta for the AI.

Alpha-Beta - Wikiepdia Entry

Below is useable pseudo-code for alpha-beta.

[mtgrares]

As another side note, if getValue() was created, it could be used for drafts so the AI would pick high value cards.

[Chris H.]

I guess that we could create an SVar:Value:{1 to 100} and then add this additional SVar to the cards in cards.txt.

[Rob Cashwalker]

SVars don't work as we had thought... see my post in the picture and rarity thread.....

Problem with scoring like that is it's entirely subjective.... Ask 100 people to rate Royal Assasin on a scale of 0 to 100, and you'll get a number of different responses..

As I was trying to brainstorm in Sloth's spBounceAll thread, there has to be a way to dynamically score a card. P/T/keywords, CMC, rarity, legendary, length of text. Forge is full of sorting methods based on these metrics, very few of which use any standards....

A big help for AI would be a variant of CombatUtil.getAttackers that is able to take power. toughness and keywords as parameters, such that the evaluation would take into account the bonus that would be applied IF the pump spell was played by the time combat occurred. The AI may not attack in the current state... but after Overrun? Probabaly.

[Chris H.]

I see that I went to bed early last night and I am now trying to get caught up on the brainstorming. A card.getValue() is starting to look very interesting. This method would dynamically score the card and we could add in tests for new keywords as they are added to the code base.

This scoring system could be adjusted via some sort of a modifier, like the quest difficulty setting?

[juzamjedi]

Improving combat AI is a very important topic. I'm happy to kick around some ideas with you folks as I would love to be surprised by Giant Growth, or Lightning Bolt / Doom Blade / Unsummon removing one of my creatures that multiple blocked a big monster.

The getValue() function for each card would be pretty hard to do. Rob is right that people would value those cards very differently. The context of the game state changes the value of a card a lot. Something like the CombatUtil.getAttackers evaluating the entire game state is the spirit of rares' pseudo code and also (in my opinion) the better way to approach the AI.

I am personally OK with the game taking longer if the AI will make better decisions. Maybe you could have a toggle button in the menu bar that can let users decide if they want the easy AI or the (new, hopefully) hard AI.

Rares, I have been meaning to update the draft cube for a while. I'll revive that topic with an update and then we can discuss how to improve the AI draft values in that topic.

[Rob Cashwalker]

juzamjedi - check into the thread about SVars for rarity and pictures. At the moment, the draft files aren't being used. We are intending to use an SVar for it, possibly "DraftRarity". The ReadBoosterPack class is called by the DeckEditor, so every card needs to present a "Rarity" SVar. I'll check how much ReadDraftBoosterPack is used, and if it is only used for generating the draft pools, then I can make it accept something like "Removed".

[juzamjedi]

It is interesting you say that. I still have my Draft folder from ages past and my draft rarity files still work. The only cards that show in my draft pool are the cards in my draft cube.

[DennisBergkamp]

Oh, those changes haven't gone into effect yet, except on the SVN.

[mtgrares]

The getValue(Card) is meant to be viewed as "how good can the AI use this card" which is similar but not the same as "how good can a human player use this card". getValue(Card) is a way for the AI to view Eager Cadet as less valuable as Soul Warden, since they are both 1/1 creatures. This hypothetical, better combat system would not take into account activated or static abilities because the combat system would be built separate from everything else in Forge.

Min-Max:
On a side note I spent a couple of hours implemented min-max but even from the nice pseudo-code, I couldn't get the code working. The book where I got the pseudo-code implements min-max and its optimized cousin alpha-beta in Java. The link to the book is here, the code is under "Examples" on the left of the page, and in the "Releases" directory. There is nothing like 10 MB of zipped source code to swim through.

[mtgrares]

The AI may not attack in the current state... but after Overrun? Probabaly.

One way to code Overrun is have the AI play it, if it has 3 or more creatures. Even 3 creatures with Overrun is very lethal. (No this isn't a "great" solution, just a real-world one.)

[mtgrares]

Rares, I have been meaning to update the draft cube for a while. I'll revive that topic with an update and then we can discuss how to improve the AI draft values in that topic.

No problem, I've sort of been in limbo myself. (I've recently become addicted to the medical show House and can watch half a season in a day. Needless to say that I don't get much programming done AND I'm enjoying the insane racing game Burnout Revenge on my old, but useable, Playstation 2.)

[mtgrares]

As I was trying to brainstorm in Sloth's spBounceAll thread, there has to be a way to dynamically score a card. P/T/keywords, CMC, rarity, legendary, length of text. Forge is full of sorting methods based on these metrics, very few of which use any standards....

Good question

Sometimes Goblin King is worth his weight in gold if you are using a goblin deck, but if you happen to find him in your randomly created deck, he is a lame 2/2 that costs 1RR. Forge does "static guessing" and does not compute any future actions. Since cards can (and do) change value, the only correct way to do dynamic scoring is to use a real algorithm like min-max. The problem of min-max and similar algorithms is that you have to be able to undo everything which is a ton of work.

[Rob Cashwalker]

We don't necessarily need a flat-out score, we just need a good, EXTENSIBLE and DYNAMIC way for the Card object to compare itself to another Card.

Then evaluation simply becomes either

Code: Select all

 if (CardA.isBetterThan(CardB))
or
 if (CardA > CardB) 

The isBetterThan method (or an over-riden comparison operator) would call upon a helper object that can be dynamically created and added to a Card like a SpellAbility. This object would have a method where all the card-specific differences in evaluation would be considered.

Goblin King would have a method that MAY evaluate higher than the other card if there were other goblins controlled by its controller, possibly also consider whether the opponent has mountains in play.... There would be other qualifiers of course, comparing power and toughness and CMC, for example. As a static pump keyword becomes available, the method generated by the keyword code will have to consider whatever types are specified.

[mtgrares]

Yeah cards like Goblin King (and other things like card combos) become more valuable with other certain cards. So the evaluation function could look in the player's hand to see if anything is valuable. Obviously it is hard to make evaluations simple because all of the parts are connected.

DeckArena is really good at evaluations but I'm sure that it took a lot of time.