Magarena AI

[ubeefx]

The project page now contains a Wiki page with a detailed description of the Magarena AI.
You can discuss it here. Also when you find any strange behavior of the AI, please describe it here.

[telengard]

Nice writeup!

I do a lot of the same things in my application (an undo engine for backing out changes, eval function with tweaks based on phases/etc, multi-threaded AI on copies of game state, minmax w/ smarts for phases etc, memory pool per game state at each depth to allow high depths without running out of memory).

One thing that really intrigued me, and at one point I had considered doing was your "score caching". I've seen this sorta thing done in Chess AIs too (transposition tables). How on earth did you get this to work with the amount of game state data there is for a game like Magic? In my engine I could not come up with a way to have all of the current state data map to a single identifier. I support all pieces/rules/abilities in my game so there is a lot to keep track of (assigned damage/venom, destroyed/disrupted pieces, piece locations, various "pools", sustained effects, engine hooks (for abilities), whether pieces have moved/attacked, etc etc).

I know something like this would REALLY speed up my engine because a lot of the time, the same set of actions done in a different order end up with the same game state/result and I could prune better in those cases.

~telengard

[ubeefx]

Thanks.

About the score caching, what I try to do is create some kind of a hash code of the game state.
Although a lot of the state is used, it does not use everything. Also the more complex the state becomes,
like adding player poison counters, the more different game states will map to the same code.
The code could for instance then become 2 times 64 bits, or even more, but there will always be cases where it does not work correctly.
However I did some testing and this seems to work quite well most of the time.
One thing that is used to calculate the identifier next to the game state is the score at that time, because it also tells a lot about what happened.

[mtgrares]

Your Wiki AI page was very detailed, I won't say that I understood all of it but I enjoyed reading it. Thanks for such a thorough explanation.

I was curious to see if your AI looked at the players hand or library and the answer is no. There isn't a right answer, I was just wondering.

Last night I had a great 39 turn game against the Magarena where I came back to win from AI - 46 life, me - 16 life. Of course drawing Akroma, Angel of Wrath and Venser, Shaper Savant didn't hurt.

[ubeefx]

Putting all the detail into the page actually helped me get a full picture again how the AI works.

The sometimes very close or long games with the AI are indeed fun.
Life gain can be really strong in Magarena in some situations.

[Happy Cat]

Played last evening. AI did well for the most part but it surprised me by destroying unequiped Leonin Scimitar instead of unequiped Sword of Body and Mind using Trygon Predator.

[Huggybaby]

I've noticed also that the AI is not afraid to attack with two guys when it knows one of them is going to get creamed. This is in direct contrast to the new DotP AI, which will never attack unless it's perfectly safe to do so.

[Aswan jaguar]

Is this just my wild imagination or you have implement a mock feature in AI.This is what happened in 2,3 games that AI had superior forces both in numbers and power and I was no threat.It could win me in a strike but instead it attacked only with 1 creature that I blocked and lose mine ,next turn the same again attacked only with 1 creature that I blocked and lose mine as if it was mocking me,and wanted to ridicule me.


*Does AI know what cards I have in my deck?

[ubeefx]

The AI does not know or try to find out what cards are in your library or hand for the moment.
But it does try to win with the highest score.
On level 6 that is the highest score after 3 turns (6 main phases).
So that could be the reason why the AI postpones the victory, to increase the score.

[MageKing17]

The AI does not know or try to find out what cards are in your library or hand for the moment.
But it does try to win with the highest score.
On level 6 that is the highest score after 3 turns (6 main phases).
So that could be the reason why the AI postpones the victory, to increase the score.

Why is a postponed victory worth more? Winning as quickly as possible should be worth the most to it.

[ubeefx]

Actually the scoring does take earlier wins into account.
But maybe in this case the "extra gain" for the AI overshadows it.

[Aswan jaguar]

You say that AI won't make a bluff but I can't explain (especially with Magarena great AI) the reason AI will attack with 2/2 creature into a 3/3 one when it is not obliged to do so (attack each turn) and doesn't have an istant to boost it?Next time I will make a video or photo to back it up.


* Is it possible that bigger card pool and AI changes to have made AI in certain scenarios not to make the best possible moves.

* What is your evaluation of AI in order of difficulty?
DEFAULT
MINIMAX
MONTE CARLO
VEGAS
RANDOM=the weakest I guess.

[ubeefx]

The Monte Carlo AI is the hardest to compare, because it uses the normally hidden information about hand and library of opponent.
So that should make it more challenging in the cases where this is beneficial.
It should be better than Vegas and sometimes MiniMax.

All other AIs do not know about hidden information. They were not explicitly learned to bluff.
- Default or MiniMax at level 6 is currently optimal
- Vegas at level 8 is worse and non deterministic, but has consistent speed and could be fun due to more random play
- Random is as implied just bad, but it will still use some features like the legal target filtering

Now let me be clear about this, the AI will not always make the best move guaranteed.
The scoring system and caching are good but not perfect.

[Aswan jaguar]

Will reports of AI's worse moments or tactics help you improve it further?If it is helpful I will be glad to report such cases,while I have so much fun and challenging games to play.

[ubeefx]

If there would be an option to save a replay for a game, then these could be shared.
I am thinking about making a new Limited Edition with this option.
Then it will be easier for me if I have a number of these replays to find improvements.
Might also add the right mouse click action and some cool cards from New Phyrexia.