Improved AI decision making process with situation scoring

All about getting the AI less baka...
spades09
Posts: 4
Joined: Tue Nov 16, 2010 10:16 pm

Improved AI decision making process with situation scoring

Post by spades09 »

So I've been trying to figure out a good way for the AI to judge/score given situations. Since every different sequence of actions results in a different situation, it could test many different sequences and choose the best one based on which sequence results in the best situation. For example, if it were to decide whether or not to play a Day of Judgment (assuming that it's the only thing it can possibly do this turn), it would simply score the two possible resulting situations, and then compare the scores.

A function to score a given situation might use parameters like life totals of all players, poison counters on all players, total power and toughness of each player's creatures (hopefully, not including effects that wear off at the end of the turn), whether there will be enough untapped creatures to defend against an attack, and other stuff like that. It could also rate the quality of the cards on the field based on converted mana cost, rareness, power, toughness, and the presence of extra abilities. These things would probably carry different weights which would probably be decided arbitrarily. (More on situation scoring later.)

As far as different possible sequences of actions, a full recursive back-tracking algorithm from Main Phase 1 to Declare Attackers Phase may be difficult, impractical, or even impossible under the PSP's specs. The easiest way to get different effective sequences would probably be to use its current semi-random method of deciding on actions (but possibly with a bit more randomization) several times. It would go through a certain number of these semi-random sequences before deciding on the one that results in the highest scored situation. The decision process might go something like this:

1. Start by storing a default SequenceOfActions (which would probably be just playing a land), and a default HighestScore (the score of the situation that would result after the default sequence of actions).
2. Use the AI's current method of deciding on actions (maybe with a bit more randomization) to generate a sequence of actions up through the Declare Attackers phase.
3. Attempt to predict which of the player's creatures will block, possibly by using its own method of deciding which creatures will block.
4. Determine the situation that would result after uninterrupted combat damage.
5. Score the situation and compare it to the current HighestScore. If higher, store the situation's score as the new HighestScore, and store the sequence of actions as the new SequenceOfActions.
6. Loop though steps 2-5 a preset number times.
7. Implement the sequence in SequenceOfActions. If interrupted by the opponent, start the process all over again after the interruption resolves.

Any thoughts?
Zethfox
Posts: 3029
Joined: Thu Jun 10, 2010 11:28 pm

Re: Improved AI decision making process with situation scoring

Post by Zethfox »

Ai doesnt randomly(per se) use card, yes it plays what it can, but it does hold wight to what would be a good choice, however limited it might be now, such as "damagers" , "lords" ect...and it plays the most expensive cards first, lucky us the better a card is in MTG the more mana it cost. so this worked out in our favor i guess.
A function to score a given situation might use parameters like life totals of all players, poison counters on all players, total power and toughness of each player's creatures (hopefully, not including effects that wear off at the end of the turn), whether there will be enough untapped creatures to defend against an attack, and other stuff like that. It could also rate the quality of the cards on the field based on converted mana cost, rareness, power, toughness, and the presence of extra abilities. These things would probably carry different weights which would probably be decided arbitrarily. (More on situation scoring later.)
i have already started implementing a rough draft of something like this. it factors all the above mention varibles into a "rating" for a given card, its in the early stages but i hope to make it wider spread in choice making for Ai, the reason im taking it easy on going all out with teach Ai all these new methods is because we've discussed(amongst the devs) switching Ai to use a Min/max method to decide its actions.

which is exactly what youre talking about here.
So I've been trying to figure out a good way for the AI to judge/score given situations. Since every different sequence of actions results in a different situation, it could test many different sequences and choose the best one based on which sequence results in the best situation. For example, if it were to decide whether or not to play a Day of Judgment (assuming that it's the only thing it can possibly do this turn), it would simply score the two possible resulting situations, and then compare the scores.
personally i would like Ai to be completely redone, i started coding 3 different tactics for combat that Ai would use but decided not to commit it, because all i was doing was slapping a bandage on Ai.


altho the 3 functions i coded "All in", "let them all through", "hold back blockers"..DRAMATICALLY improved Ai combat, like i said, it was just slapping bandages on Ai.the 3 functions were basically coded so they would evaluate the battlefield NOW and what it would be NEXT combat based on the creatures on the field now, some more controversial changes it would have implemented was letting Ai know what the player had in thier hand. and help it make the combat choices based on if player hand a pump, removal, or creature it would be able to afford next combat. This i KNEW wouldnt settle well with most the dev team. these functions were overrides for Ai choice making, they had to be force over ride, which is what i didnt personally like.

infact im amazed(tho im sure it simply went unnoticed) that the dev team didnt chew my head off for stacking Favors in Ai openning hand if the deck youre fighting was listed as "easy" to make it a more challanging fight. I also set it to forcebest ability uses. which is an option currently reserved for momir.

in short, Ai needs to be redone, not added too :)
spades09
Posts: 4
Joined: Tue Nov 16, 2010 10:16 pm

Re: Improved AI decision making process with situation scoring

Post by spades09 »

It does need to be redone, but I figured that this may be a quicker solution. I mentioned it as an alternative to minmaxing because I've noticed that minmaxing has been mentioned before in these forums, but hasn't been implemented yet. Not to mention that, for a true minmax method, you would have to use recursive back-tracking to store, test, and compare every possible sequence of actions. That could take a lot of processing power, memory, and waiting time.

The method I mentioned above is similar to the minmax method, only instead of testing every possible sequence, it would create many semi-random sequences, and compare each one to the previously created one. Each randomly generated sequence would have to be sensible enough by current AI standards, but random enough to make it different from the other generated sequences.
i have already started implementing a rough draft of something like this. it factors all the above mention varibles into a "rating" for a given card, its in the early stages but i hope to make it wider spread in choice making for Ai
Are you referring to the sequence scoring function, or the card rating function?
Zethfox
Posts: 3029
Joined: Thu Jun 10, 2010 11:28 pm

Re: Improved AI decision making process with situation scoring

Post by Zethfox »

card rating based on manacost, power, toughness, abilities.....
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 »

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:
Djardin
Posts: 129
Joined: Sat Sep 04, 2010 11:40 am

Re: Improved AI decision making process with situation scoring

Post by Djardin »

I read the article linked by Zethfox about the AI implementation in duels of the planeswalkers on xbox 360 and it only performs min-max in the current turn. Consequently if the AI has got a 0/1 with flying and regenerate and the opponent has got a 12/12 without flying, this AI will always attack ... which is ****. They however have a very nice way to not make the user waif for 10 minutes, they actually put the AI in another thread, which makes some nice use of the other CPU of the xbox, and they compute while the player is thinking on its turn. Doing that, would be a nice way to do on the PSP... hum ... can you pop a thread on PSP ? =)
Zethfox
Posts: 3029
Joined: Thu Jun 10, 2010 11:28 pm

Re: Improved AI decision making process with situation scoring

Post by Zethfox »

wololo i agree with you that PSP cant handle a full blown max/min to *some* extent....i say some because of a few reason....there are chess games on psp.

these chess games can simulate the next 100 moves, this is full blown max min. tho for wagic it would be too complex due to the nature of cards, but we *could* do a maxmin that would only do a tree of like 10 branches, and have it pick the best out of 10, that alone would improve our Ai dramatically without taking on such a massive preformence hit.

we dont need to give it duel of planewalkers level of maxmin with its 1000s of branches...even just 10 would be nice :)
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 »

Maybe you're right, we could give it a try. But you know that means implementing an undo function before that ;)
lozanogo
Posts: 81
Joined: Wed Aug 25, 2010 6:48 am

Re: Improved AI decision making process with situation scoring

Post by lozanogo »

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.
spades09
Posts: 4
Joined: Tue Nov 16, 2010 10:16 pm

Re: Improved AI decision making process with situation scoring

Post by spades09 »

wololo i agree with you that PSP cant handle a full blown max/min to *some* extent....i say some because of a few reason....there are chess games on psp.

these chess games can simulate the next 100 moves, this is full blown max min. tho for wagic it would be too complex due to the nature of cards, but we *could* do a maxmin that would only do a tree of like 10 branches, and have it pick the best out of 10, that alone would improve our Ai dramatically without taking on such a massive preformence hit.

we dont need to give it duel of planewalkers level of maxmin with its 1000s of branches...even just 10 would be nice :)
See, this is basically what I'm talking about, only the ~10 branches are semi-random ones.
Locked