Min-Max Combat Code

[mtgrares]

I've started working on applying min-max to combat so the AI will attack and block better. The code won't see any of the cards abilities so the AI will only see Royal Assassin as a 1/1 and Cemetery Reaper as a 2/2 with no abilities. This limitation can be offset because min-max's evaluation function lets you assign a number value to each card. Royal Assassin could be evaluated to be a 10 while a generic 1/1 with no abilities could be only 1.

Of course creating a numerical value for all of Forge's 5,000+ cards is going to be challenging. I'll try to create a small helper app that will speed things along. And maybe cards should be evaluated from the player's perspective like the AI can only use cards in a limited fashion, so maybe Cemetery Reaper is a 8 from the human player's perspective and only a 5 from the AIs.

I'm hoping that the min-max combat code will be able use a few combat modifiers like: flying, wither, defender, and fear. More combat modifiers could be added later once everything is working. The code should be able to "see" several turns ahead and the code will not consider future creatures in the AI's hand.

I hope that I'm not stepping on anybody's toes. I haven't coded anything in awhile and I've been meaning to use min-max in some fashion. I would like to say that the code will be done by Christmas but I doubt it. It may be a few days later (although it is hard to guess). It seems like I'm 90% done because I only have to generate the possible combat situations. Of course if I get done and it doesn't work then I'm in big trouble.

I'm using actual commments and javadocs. If you just count the source code comments, any one class (in the new combat code) probably has more documentation that all of Forge's put together. I'm also using packages and so far I have 3.

Download (3.7 kb) This my progress so far.

p.s.
Technically I'm using the alpha-beta algorithm, which is an optimized version of min-max.

And in case I forget Merry Christmas.

[Rob Cashwalker]

There was a thread here in the past few months with ideas for dynamically calculating a score for any given card, based on P/T, CMC, words in the rules text, etc. These aren't numbers that should be static. There is at least one card that forces all cards in play to have no abilities and some particular P/T. That sort of effect would make the AI seem dumber if it weren't dynamic.

[friarsol]

As far as people in that code goes: I know Sloth has been working a lot recently on improvements to the Blocking. I don't think he has started in on the Attacking yet.

Last week, I started merging Combat and pwCombat, allowing players to attack more than just one Planeswalker at a time. I'm pretty sure I have everything nailed down. But I don't have enough time to fully test before the holidays start for me and I don't want to break things near a release. So my changes won't make it in until after presents are unwrapped and closer to when the ball drops.

[Chris H.]

There was a thread here in the past few months with ideas for dynamically calculating a score for any given card, based on P/T, CMC, words in the rules text, etc. These aren't numbers that should be static. There is at least one card that forces all cards in play to have no abilities and some particular P/T. That sort of effect would make the AI seem dumber if it weren't dynamic.

`
I think that Sloth did some initial work in this area. I seem to remember coming across this new code in, hmm, I think that it was CardFactoryUtil. I remember the discussions taking place and I think that we all got so preoccupied with the new AbilityFactory that we have not yet had a chance to take it any further.

[Chris H.]

As far as people in that code goes: I know Sloth has been working a lot recently on improvements to the Blocking. I don't think he has started in on the Attacking yet.

Last week, I started merging Combat and pwCombat, allowing players to attack more than just one Planeswalker at a time. I'm pretty sure I have everything nailed down. But I don't have enough time to fully test before the holidays start for me and I don't want to break things near a release. So my changes won't make it in until after presents are unwrapped and closer to when the ball drops.

`
I would like to release the next beta in a few days as an Xmas gift to our user base. The following release will be sometime in January but it is hard to predict how much free time our dev team will find in the next several weeks.

[nantuko84]

Of course creating a numerical value for all of Forge's 5,000+ cards is going to be challenging. I'll try to create a small helper app that will speed things along. And maybe cards should be evaluated from the player's perspective like the AI can only use cards in a limited fashion, so maybe Cemetery Reaper is a 8 from the human player's perspective and only a 5 from the AIs.

Hi,

You may take a look at Rating cards in Mage. Few weeks ago I implemented application that helps to rate cards. It is described here:
http://mwars.blogspot.com/2010/12/mage-rate-cards.html

The idea is simple: everytime just choose one card of the two you like most of all. I would say that we have only 700 cards (against your +5000), but it took only one day for us to rate all cards with 4 guys involved. And now we have Baneslayer rated as 10, Lightning Bolt as 8 and Wurm's Tooth is 1.

I know you have very big community so you can easily find lots of people who will help you to rate your cards.

~nantuko84

[Sloth]

There was a thread here in the past few months with ideas for dynamically calculating a score for any given card, based on P/T, CMC, words in the rules text, etc. These aren't numbers that should be static. There is at least one card that forces all cards in play to have no abilities and some particular P/T. That sort of effect would make the AI seem dumber if it weren't dynamic.

Since the combat AI should care mostly about creatures, we already have the function evaluateCreature and as Rob said it dynamically checks for buffs. You might also try to use some existing functions like canBlock or canDestroyAttacker, rares. They should take care about mostly all keywords and stuff.

[mtgrares]

Thanks for tell me about evaluateCreature(), canBlock() and canDestroyAttacker(), I'll definitely use them. I have thought about coding this earlier but I have no idea how much it will help the AI. Will it improve combat 50% or only 20%? If the code works at all, that will make me happy and we'll see how much it helps the AI.

nantuko84, thanks for telling me about your application. Great minds think alike

[mtgrares]

I thought I had a clear focus on what the new min-max combat code would do but now I don't. The code in my mind has become "murky" and I don't know how to include planeswalkers or regeneration. Maybe not including planeswalkers and regeneration in version 1.0 would be OK, I just don't know.

I know that Chris, Rob and other guys are working on the combat code already.

I feel a little bit more random that usual but that is how life goes. I had a great Christmas though

[Rob Cashwalker]

Yeah, working on the set integration has become muddy in my head too... I'm losing steam, because there are so many points where the set data needs to be weaved in.

[mtgrares]

Obviously combat isn't "total separate" so it is hard to work on. Just looking at ComputerUtil.canAttack(Card) scared me because it has grown so large. Forge started out to be "small pieces working together" and has grown into "large pieces working together".

Rules 3 and 4 now apply to Forge more than 1 and 2, since Forge is bigger than methods and objects, it is now subsystems like IO, AI, GUI, etc...


5 Programming Rules of Thumb (taken from my blog)

1. The less you know about the internal workings of another method, the fewer assumptions you make about how the method operates. The fewer the assumptions you make, there is less chance that one of them is wrong.

2. The goal for individual methods is to make them like a "black "box". You know what goes in and you know what comes out but you don't know what happens inside.

3. The more independent the subsystems are, the more you reduce the complexity. Carefully defined modules separate concerns so you can focus on one thing at one time.

4. If you have data leaks between the subsystems because of sloppily defined interfaces, you will have a flood of unnecessary complexity.

[Chris H.]

Sloth has spent some time recently trying to improve the blocking and I think the attack code. Sol had started some mods on planeswalker combat but it was not ready for the last beta release.

And yes, we all tend to run out of steam for a variety of reasons. Forge is a "work in progress" after all. Granted, there has been a large amount of work submitted over the last 6 months. And while this work is a step in the right direction we have not been able to finish all of the ongoing projects.

Rares, are you able to access the SVN at this time or are you working on an older version of the source?

[mtgrares]

Yes, I can download the SVN so I'm up to date. I found a random, naked exe file that does it for me. Thanks for asking.

I'm not sure that I'll finish the code or not because I'm not sure it would really improve the AI. I'm on the fence and I hate being on the fence. I like being right or wrong but sometimes there is only gray. (And to boot, Monday I'm going to post an article about the new combat code.)

[mtgrares]

Just to be clear, I've given up on the new code.

I thought I knew what I was doing but it became too complicated. Giant Growth’s AI code checks to see if a creature is attacking and then targets that creature. There is no “wait time” for the computer and the new code definitely will need a few seconds in order to generate future combat situations.

May the old combat code, live long and prosper.