Improved AI decision making process with situation scoring

All about getting the AI less baka...
mnguyen
Posts: 229
Joined: Thu Apr 29, 2010 4:13 pm

Re: Improved AI decision making process with situation scoring

Post by mnguyen »

lozanogo wrote:
wololo wrote:Yep, just for the record as I'm reading this, the PSP doesn't have enough horsepower for an acceptable minmax. As an anecdote, I've been told that the AI on the Xbox360 (duels of the planeswalkers), which does use minmax, is not as good as the one in Wagic. That being said, I haven't tried myself.
some other freeware games such as deckbot use minmax. When I tried Deckbot (it was a long time ago, I'm sure it has changed since then), it was very slow on my core 2 2gHz/2GB Ram, but very good (the AI pretty much made no strategical mistake).
Of course, waiting 1 minute for one move on a PC, would mean something like 10mins on the PSP...not mentioning the amount of Ram required.

But I'd of course love to stand corrected, I'm convinced the AI can be updated/rewritten, it's just a matter of "somebody" doing it :mrgreen:
Hi wololo, I have Duels of the Planeswalkers (actually through some DoP forums I disovered wagic!!) and its AI reacts clearly better than Wagic's AI in real situations. Note I mentioned 'in real' because maybe the anecdote you know (wagic AI > DoP AI) is something more technical, though clearly is not translated into a real match.

Just my two cents.
can you provide an example of a "real situation"? I'm curious, not debating you.
Zethfox
Posts: 3029
Joined: Thu Jun 10, 2010 11:28 pm

Re: Improved AI decision making process with situation scoring

Post by Zethfox »

try it mike, the game is like 10 bucks on steam and is sorta worth it. youll understand what he means by "real" situations once youve played it.
mnguyen
Posts: 229
Joined: Thu Apr 29, 2010 4:13 pm

Re: Improved AI decision making process with situation scoring

Post by mnguyen »

Zethfox wrote:try it mike, the game is like 10 bucks on steam and is sorta worth it. youll understand what he means by "real" situations once youve played it.
Looks more like $40-$50 to get all the packs.
Zethfox
Posts: 3029
Joined: Thu Jun 10, 2010 11:28 pm

Re: Improved AI decision making process with situation scoring

Post by Zethfox »

youre looking at the expansions
the first base game is like 10 bucks possibly less.

hopefully since its steam powered they will eventually toss up an SDK for it.
rawsugar
Posts: 228
Joined: Wed Aug 11, 2010 11:05 am

Re: Improved AI decision making process with situation scoring

Post by rawsugar »

this sounds really good if it could be implemented!

If i could add a few laymans observations:
first getting the AI to understand or find a work around the abilities trample and first strike is essential! (ie for a decent workaround trample block only if blocker-toughness>attacker-power, and first strike treat as having 1 more power (wouldnt solve creatures with power higher than toughness tho...), something like if attacker-P>defender-T: treat T as infinite (or 1000) would tho) Especially first strike is way too efficient atm. Understanding "blockable only by" is a lesser but also pressing issue.
second calculating CURRENT power and toughness + casting cost with a minimum of casting cost *3 would be a fairly accurate estimate of a cards value? possibly supplemented by a +/- factor in the card coding but that would be a lot more work not to mention debatable.
And treat players life as 1 (or 2) points: ie a 1/1 cost 1 creature is worth 3 lifepoints. last life value of 10000 ofc.
third atm the AI will usually block by getting creatures in your way in the same order they came into the game. Randomizing this order would make it slightly less predictable but coding in a sequence of checks would be better; as in biggest blocker (highest T) blocks biggest attacker, if attacker-P>defender-T, second biggest attacker. Repeat with second biggest blocker. Leftovers check for multiple block, leftovers for blocking high without trample.

hope im not wasting time here, no idea if any of this is even vaguely useful. I want to hlp but lack the skillz:(
Last edited by rawsugar on Tue Nov 30, 2010 2:14 pm, edited 2 times in total.
wololo
Site Admin
Posts: 3728
Joined: Wed Oct 15, 2008 12:42 am
Location: Japan

Re: Improved AI decision making process with situation scoring

Post by wololo »

mnguyen wrote:
Zethfox wrote:try it mike, the game is like 10 bucks on steam and is sorta worth it. youll understand what he means by "real" situations once youve played it.
Looks more like $40-$50 to get all the packs.
dang, That's what we should do guys, sell every 300 new cards as a 10 bucks expansion for Wagic...
The day Duels of the planeswalkers has as much cards as Wagic, it will cost, what, 1000$ to get the full game? :mrgreen:
whismer
Posts: 55
Joined: Thu Aug 06, 2009 2:47 am

Re: Improved AI decision making process with situation scoring

Post by whismer »

DOTP is not perfect but some user have add a lot of card...over 600 for now... it's moddable. The main prob is the small community. I play both of them and both have strength and weakness... AI is better in DOTP because he can use new card we create like mana producing artifact or land... take much time but he can use it... He make some dumb move like other AI. Wagic has more card, a larger community who work hard and well to make user happy (like me). I'm here since version 6 and it's incredible to see what wagic has become
Zethfox
Posts: 3029
Joined: Thu Jun 10, 2010 11:28 pm

Re: Improved AI decision making process with situation scoring

Post by Zethfox »

rawsugar wrote:this sounds really good if it could be implemented!

If i could add a few laymans observations:
first getting the AI to understand or find a work around the abilities trample and first strike is essential! (ie for a decent workaround trample block only if blocker-toughness>attacker-power, and first strike treat as having 1 more power (wouldnt solve creatures with power higher than toughness tho...), something like if attacker-P>defender-T: treat T as infinite (or 1000) would tho) Especially first strike is way too efficient atm. Understanding "blockable only by" is a lesser but also pressing issue.
second calculating CURRENT power and toughness + casting cost with a minimum of casting cost *3 would be a fairly accurate estimate of a cards value? possibly supplemented by a +/- factor in the card coding but that would be a lot more work not to mention debatable.
And treat players life as 1 (or 2) points: ie a 1/1 cost 1 creature is worth 3 lifepoints. last life value of 10000 ofc.
third atm the AI will usually block by getting creatures in your way in the same order they came into the game. Randomizing this order would make it slightly less predictable but coding in a sequence of checks would be better; as in biggest blocker (highest T) blocks biggest attacker, if attacker-P>defender-T, second biggest attacker. Repeat with second biggest blocker. Leftovers check for multiple block, leftovers for blocking high without trample.

hope im not wasting time here, no idea if any of this is even vaguely useful. I want to hlp but lack the skillz:(

please split this into sections and bulletpoint the seperate items, i would really i to understand what exactly youre suggesting but this is like a long run on sentence.

im working on some Ai improvements and ideas are always welcome.
rawsugar
Posts: 228
Joined: Wed Aug 11, 2010 11:05 am

Re: Improved AI decision making process with situation scoring

Post by rawsugar »

hum i suppose i could try.
SCORING OF CARDS:First: point values for the cards for situation scoring could be current power+toughness+casting cost with a minimum of casting cost *3 ie
savannah lion is worth 4, a wellwisher is worth 6 points, moat 12, a sliver that with buffs has 6/4 and costs 2 is worth 12, a black knight with unholy strength is worth 9 while the unholy strength itself is worth 3. etc
Also players life should be worth 1 point, so if AI has 2 2/2 cost 2 creatures and you have a 3/3 creature, attacking will cause 2 point damage but lose a creature worth 6 points so it wont attack. (unless attacking will reduce to 0 or less, since the last life is worth 1000points).

FIRST STRIKE: atm w no situation scoring, the biggest issue with AI is first strike. AI will continually throw away creatures to this. early game it will let attacking creatures through if they are bigger than its blockers but block if they are the same size, so a 2/2 first strike is disproportionally effective in curtailing its buildup.
If there was some way to have AI treat attacking creatures with first strike as having +1/1 for purposes of deciding whether to block this would be less of an issue, and if the AI acted as if first strike creatures had "can be blocked by only 1 creature" the issue of killing off half the AI army w a big first strike creature would be solved (example AI blocks your 5/5 creature with 3*2/2, only 2 of which have first strike).
another issue not covered by the above is if creature has higher power than toughness, fx a elven arhcer with rancor, atm AI will gladly block this with 1/1, 2/2, 3/3 and 4/4, thinking it can kill the archer. A rule for first strike creatures like if attacker Power is higher than blocker Toughness, treat attacker Power and toughness as being 100 for attacking and blocking would solve this. But like I said no idea how complex the rules for AI actions can be atm, I just know that first strike is far too effective atm.

TRAMPLE: Also AI will always block creatures with 5+, first i think this should be set to 8 or even 10 (or better yet a function of blockerstats) , second it should be disabled when the attacking creature has trample to prevent AI from throwing away creatures. A rule like if attacking creature has trample block only if blocker toughness is higher than attacker power.

BLOCK ORDER RANDOM:third atm the AI will usually block by getting creatures in your way in the same order they came into the game. Randomizing this order would make it slightly less predictable but coding in a sequence of checks would be better; as in biggest blocker (highest T) blocks biggest attacker, if attacker-P>defender-T, second biggest attacker. Repeat with second biggest blocker. Leftovers check for multiple block, leftovers for blocking high without trample.

example player attacks with 5/5 trample 5/5 4/4 2/2 and 1/1, AI has 4/5, 3/3,3/3, 1/1, 1/1, 1/1
Ai check for the 4/5 skips the 5/5's (P>T) and blocks the 4/4
for the 3/3 AI checks through 5/5 and 4/4 and blocks the 2/2
the other 3/3 blocks the 1/1
the 3 1/1 check for multiple block as 3/3 finding no creatures to block
they check for single blocking finding a trample creature that they skip and then a 5/5 that they block, the last 2 1/1 skip the block phase.

if this takes too much programming/computer power its not very important, but it seems to me that the protocol that a human player runs through semi consciously can be easily codified.
if not viable then simply make the order random. atm the AI will often block creatures in the order it got them down regardless of stats unless some other rule overrides this (fx its hellbent on killing lords). This allows a player to skip creatures he could attack with in order to get the blocker he wants, if fx theres a deathtouch creature he wants to kill with one of his smaller creatures.

example Ai has 5/2 and 2/2 first strike, player has 2/2 first strike and 4/4, since the AI blocks in this order the human loses nothing and AI both, if human creatures were in reverse order he would know he would lose both (and therefore wait for the AI to attack) but if randomized it would be 50/50 what would happen forcing the human to make a risk assesment trying to gauge whether his hand is likely to give him the advantage in coming rounds or he should take the chance now.
Yorien
Posts: 33
Joined: Tue Feb 02, 2010 10:59 pm

Re: Improved AI decision making process with situation scoring

Post by Yorien »

Yorien says:

About min/maxing, this would make a "basic" AI improvement, but Wagic isn't like a chess game where you can "predict" moves and keep only the "good" offense/defense lines. With this approach, AI should spend too much time "thinking" every phase (while chess only has a white/black move phase, Wagic IA should think what to play in EVERY game phase - in both IA's turn and oponnent's) without doing things like wasting mana in own card "stupid" abilities. That "movement prediction" should probably be used only in combat phases as explained by rawsugar.

I believe "card scoring" is the way to go to keep a decent AI with as less "thinking" as possible; not to build the IA around it since it could be extremely easy to artificially inflate/deflate a card score to divert IA's resources while the action is elsewhere, but mainly to create a "threat table" that helps the IA undertand the decks it fights again. This was actually discussed in a previous topic:

viewtopic.php?f=32&t=1289&start=0

First of all, Wagic is heavily "deck build" based. While in chess all pieces keep the same scoring no matter the game (pawn=1, Knight=3, Bishop=3.5, Tower=5 and Queen=10) the same Magic card may behave in a completely different way on different decks. For example, Llanowar Elves could behave mainly as mana generators in a red/green direct damage deck, while can also be heavily used as attackers in an pure green Elf Deck. This should give different scorings for the elves, each score dependant on the deck they are included and how they are played.

As you say, cards can be given a score based on their current power/thoughnes, generic and codeable abilities (I'd skip mana cost and rarity, expensive doesn't mean "better" in many decks - just take a look at ye olde Suicide Black deck, a cheap-as-heck-to-build deck that could beat the heck out and humiliate way more rare and expensive decks twelve years ago in many official tournaments) but that should only be a BASE score and it should dynamically be adjusted based on card's behaviour in-game so once the game ends, IA knows which cards were the most threatening in that particular game AND in that particular deck.

Since I.A. decks are saved as plain text , I believe those files could also be used to write the IA's "thoughts" about that deck and the cards it contains. This way, the first time IA fights a particular deck it will create the base score from scratch and probably will fail finding the real deck's menaces, but the 15th time the AI is beaten by a particular card with an "initial score" of 3 that ends with a "final score" of 32, a big target should be painted on that card for that deck; the more it plays against that deck, the more it knows about the real threats that deck possesses.

For example against Deck17.txt, first time IA plays there's no IA data, so IA only creates a base scoring and starts modifying it; once battle finishes IA writes to Deck17.txt a threat table in a per card basis, contaning that final score, keeping the score of the last X battles and a rounded "average" value.

Card 1: 6,7,5,6,6,6
Card 2: 18,16,11,15,22,16
Card 3: 11,13,13,,,12
Card 4: ...

(take note, this example keeps track of the last 5 battles, but, card 3 is a "new card" - it was added to the deck recently maybe to a player's deck to test it - so IA has no full data available).

Next time IA battles against deck17.txt, since there's IA data writen, IA not only generates the "base score" (that will be changed as the game proggresses and writen once the game ends) but also loads the AVERAGE it already has and makes decisions not only based on the "current game score" but also takes into account the "historical score". Cards as enchants and instants keep their own score (if a creature with an enchant hits the IA, score is added to BOTH the creature AND enchant, taking into account how much damage did the creature and how much was granted by the enchant itself; also if you play around a combo deck as an old "Living Dead" deck, ALL threat generated by the creatures raised should also be added to the living dead card ) so IA "catches" your play style and knows what to destroy or counter if it has the means.

To even enhance this further, IA could also write how creature type cards are used in a deck so it knows if a creature is mainly used as an attacker, as a blocker, if its a mana or creature generator, if it's played for it's ability only and almost never enters combat...

Finally, IA could write tags to the deck, to define a "deck playstile" depending on how IA "thinks" it is played. For example a typical suicide black could be tagged by the IA once enough games are played as "full attack", "mono" [olor #], "creature", "fast [average # of turns]", while a Living Dead deck could be tagged as "combo [card ID#], "rainbow" (or multi [color #] [color #]), etc... so specific IA behaviors can be written depending on the existent tags.
Locked