Below is taken from a private forum about a private Magic program that uses min-max for the computer AI. The AI easily out performs MTG Forge's AI and can play instants and abilities during combat. The author's idea was to use an object with different "layers" for the evaluation function instead just number. (I'm sorry for keeping the name of this program private, but that is the author's wishes, not mine.) Below is copy and pasted from a private discussion. I did not write it. I'm still working on my own version of min-max and Magic.
I got a lot of requests asking me the AI evaluation function in (private Magic program). I will try to explain a little bit of the function here. You may need to have a basic understanding of how Minimax algorithm works first before you can totally understanding how to apply this to your program.
In the very first engine I have created, my evaluation function is very simple. Basically it counts how many cards in-play for the player and combine that with the player's life. Since life is more important than how many cards a player has put in-play, the life total is multiplied. The result is what I called a score and each area contributing to this score is a component. This calculation is also done for the other player and is subtracted. So for example:
Player 1 - 3 in-play cards - 20 life -> 3 + 20 * 100 = 2003
Player 2 - 10 in-play cards - 18 life -> 10 + 18 * 100 = 1810
Score for player 1 at this stage is 2003 - 1810 = 193 (score for player 2 will be -193)
You will be surprised by how Minimax can perform some amazing things with such a simple evaluation function. There are some special cases in the equation I am not mentioning here. These cases are used to handle losing conditions besides a zero or negative life, e.g. draw with no cards in library, losing condition set by a card, etc. In those cases a lowest possible negative number is used for the player's score regardless of other components.
As a side note, if my computer is infinitely fast and can evaluate the whole game from start to finish in a reasonable time, the evaluation function can be as simple as using just players' life total (plus the win/lose special score.) This is because A.I. can foresee all the consequences of each move and number of in-play cards is not needed to make a sensible decision.
Since our computer can only do a limited amount of calculation and MTG is not a simple game like tic-tac-toe, we need to guide the Minimax/alpha-beta algorithm to an approximated score when an end-game state cannot be achieved. The in-play card scoring part in the above example is one of the approximation. Now you can find many example of winning a game without a single card in-play (e.g. using red.) However in a more general sense the player life part of the equation is kind of balancing this out. So either you are putting cards out or reducing your opponent's life. If you are not doing both, you are not in a good position.
After the first version of the evaluation function, I quickly found out that not all cards are equal and I shouldn't give them equal scores. Ideally, if a card's purpose is to reduce an opponent's life and is effective about it (directly or indirectly), the opponent's life decrease should reflect in the evaluation function and so the merit of one card will be obvious against another card which cannot achieve the same thing. However, when there are too many possibilities and time is limited, Minimax may not be able to reach such a conclusion.
At first I tried to give a card more points when it has more abilities and in case of creatures considering their power and toughness. Later I changed to a more generic 'base' score by just looking at a card's casting cost. The calculation is simple, 150 points for colored cost and 100 points for generic cost. This simple calculation can usually account for how powerful a cards is. However if a card has an unreasonable cost, e.g. Black Lotus, this calculation will not give Minimax a good representation of the card. Hopefully in those case the power of the card (or the lack of) will be reflected in other evaluated parts. Besides the base score, a few bonus points will be added for creatures' power and toughness points.
Besides in-play cards, there are points given to cards in hand and library.
I want to get back to the multiplier given to the life component in the above example. When I add more and more components to the score, it becomes easier for components' scores to 'overlap.' In the above example, using a multipier of 100 will not be enough if all the in-play cards' score total is exceeding 100. Once that is happening, Minimax will behave weird and no longer to preserve a player's life but to put more cards on the table!
To create a solution which is once and for all, I have created a separate score class to deal with scores rather than just use a single integer number. Basically the class has multiple layers of sub-scores. Sub-scores in the upper layer are more important than sub-scores in the lower layers. Each sub-score value is by itself an integer which will allow me to have more precision in tinkering. These are the current list of all the sub-scores:
Limits - represents boundary situations, highest significance
Wins - represents win/lose situations
Creatures - a special sub-score to allow a less conservative play in early game situations
Life - represents play life
Library - represents cards in libraries
InPlay - sub-score for in-play cards
InHand - sub-score for hand cards
Misc - minor scores to prevent indecisive situations, lowest significance
Comparisons of two scores is performed by comparing the highest significant sub-scores against each other first. If they are the same, the next lower significant sub-scores are compared and so on.
Interesting read, I'm curious now what "private MTG program" this is :)
ReplyDeleteThe first example seemed a little bit funky though, I'm probably missing something here, but is one point of life really worth 100 cards? If this were the case, Ancestral Recall would be worth a lot less than Healing Salve :D
"I promise to write a normal article about MTG Forge next time." >:|
ReplyDeleteAbout life, yes: under such evaluation, painlands will never be used, all spells requiring payment of life(that don't damage the opponent for more) will sit dead in hand, all burn will be targeted directly at opponent, etc. Since the algorithm probably doesn't calculate with trustworthy accuracy something as complicated as next turn's combat results, I think more worth should be given to creatures, esp in the most common case of one player having more of them (and thus the ability to get ~∑^(∆№Creats)(LowestCreats_k.pow) damage through during combat).
I basically agree with previous comments.
ReplyDeleteAlso, if the layer system has proven more simple (thus also maybe more effective at this stage), it's obvious that a "ideal" AI shouldn't decide moves solely on a "manual lexicographic order" between different variables, but actually have a formule to mix and match them globally. Although the "perfect" Magic formula is only a dream, it looks like there is a "good compromise" in between. Like, keeping the most extremes "layers", and have an evaluation function for other variables.
Concerning life/cards in a particular, a better representation of life's value could be with a sqrt or ln function, which would help represent how a one life point difference is worth more when you're at low life than when you're at high life. ln(max(life,1E-10)) also has the beauty of directly implying that less than 1 life, ie death, is infinitely bad : )
(...and sorry for the accidental publishing of previous unfinished comments)
ReplyDeleteCards in hand could be valued at something like (ncih = number of cards in hand, v is for value)
if ncih<=7
vcih=ncih
else
vcih=7+sqrt(ncih-7)
end
to reflect how the cards in excess of seven are worth less than the first seven (considering 1) diminishing returns (same thing as for life, the difference between 10 and 11 cards in hand is not the same as compared to 2 and 3 cards), and 2) you'll eventually have to discard to 7 anyway)
Then the composite evaluation function could be something like
5*ln(max(life,1E-10))+alpha*vcih +your current formula to evaluate on board position (as long as a card on board is worth more than a card in hand)
Where alpha is a coefficient around 1 could be used in front of vcih to reflect capability of playing spells. Something simple like
alpha=sqrt(1+(number of lands you control - mcmc)/mcmc)
where mcmc is the mean of your deck's cards' cmc. (just make sure it doesn't grow big enough to make cards in hand worth more than cards in play).
Thus, at around 5 life or less, one point of life starts to be more important than a "normal" (ie pre 7 cards) card in hand. Maybe it shouldn't be exactly 5 life, but the "general" answer is surely in between 5 and 8.
Hey Rares,
ReplyDeleteIt's good you got permission to repost this article from the author, but you should make clear which part is reproduced from the other post (everything after the first paragraph). Otherwise it seems like you wrote it all.
If you are really interested in learning AI, the way you evolve your eval function is by having random weights assigned to your different variables (number of cards, life totals, etc), then having computer play games against itself. After each game weights become adjusted based on the winner and back propogated through previous turns. After enough games played your weights should be much more accurate then trying to set them by hand. Also it gives your AI an opportunity to learn different decks and even assign weight value for each card in the deck if you want to go that far.
ReplyDelete