Page 1 of 1

Obstacles to mana source giving multiple mana? (a code qu.)

PostPosted: 07 Aug 2017, 22:28
by Utterly
So, I'm really interested in the project, but its really frustrating to see large blocks of cards be unavailable.

I took a look at the really basic code involved in mana sources, starting with the card parsing code, which details how the mana source is defined.

Obviously, its not hard to create a more flexible definition of mana sources from a data structure sense, but the issues come later. I understand that its much easier when you have a granularity of one for mana, and changing to a system where you have to look at a list of potential mana permutations is harder than just having sum totals of each potential color (but certainly not that much.) Looking at the forum, it seems that devs are very concerned about the AI being able to use every card... would it be correct to assume we don't multiple mana per source because the AI can't handle it.. yet?

Am I understanding the situation correctly? Is the hold-up on the back end of the engine? or should it be relatively simple, but just not a priority ATM?

Whats the situation with Magarena's AI, code-wise? I did see Monte Carlo mentioned, and I'm aware of the basic premise of monte carlo methods to find the "best" solution.

Is the AI code monolithic, or is it integrated into the general code base?

Any other thoughts would be welcome

(and P.S. my predominant experience is in database development, but I've coded for forever... happy to lend expertise, here.)

---
Utterly

Re: Obstacles to mana source giving multiple mana? (a code q

PostPosted: 08 Aug 2017, 02:52
by melvin
Hey Utterly, thanks for starting a discussion on this. Improving the mana system to support more cards is one of our longer term goals. So far there is one proposal based on mana tokens at https://github.com/magarena/magarena/issues/752

Utterly wrote:would it be correct to assume we don't multiple mana per source because the AI can't handle it.. yet?
That's right.

The whole mana system is built around one mana source generates one mana and each mana cost requires activating some mana abilities. There is no provisions to carry forward any additional mana created, but this information can be added fairly easily.

The more difficult part is creating payment options for the AIs to consider. We separate the generation of options for AIs from the actual AI code itself which is concerned with searching the space of options. So here the issue is how to generate the mana payment options.

The hardest part being that some AIs internally uses a delayed mana payment. Instead of actually paying the cost and tapping mana permanents, it just notes that it owes the system so much mana and continues until the end of the turn. As long as it does not owe more mana than it can generate it can continue to do this (this check is done assuming one mana source = one unit of mana). This allows the AI to defer on the choice of which permanents to tap for mana and allows it to go deeper in its search. Presumably using this system improves the AI's playing strength by allowing it to search deeper, but exactly how much this mechanism improves the AI is not quantified. For example, this system ignores things like pain land and other side effects of tapping for mana as it doesn't actually tap the lands.

With a mana pool, there is the issue of the mana pool emptying at the end of steps and phases. So the logic of delaying payment becomes more complicated.

See https://github.com/magarena/magarena/bl ... hoice.java for the starting points of computing payment options for both player and AI.

Utterly wrote:Am I understanding the situation correctly? Is the hold-up on the back end of the engine? or should it be relatively simple, but just not a priority ATM?
Yes, the hold-up is mostly on the AI's decision making. Another reason is probably due to the complexity of this part of the code. Mana payment has not been significantly changed since it was written by the original developer, who is not longer active on the project.

Utterly wrote:Whats the situation with Magarena's AI, code-wise? I did see Monte Carlo mentioned, and I'm aware of the basic premise of monte carlo methods to find the "best" solution. Is the AI code monolithic, or is it integrated into the general code base?
We have several AI implementations, the classic Minimax and the more recent Monte Carlo Tree Search methods are implemented. You can find them in their own package https://github.com/magarena/magarena/tr ... c/magic/ai

The AI code is separated into its own class, they only have to implement one method, namely "findNextEventChoiceResults". The controller will invoke this method to ask the AI to choose the next mode. Internally, most AIs create a clone of the game model and simulates future moves.

Re: Obstacles to mana source giving multiple mana? (a code q

PostPosted: 14 Aug 2017, 00:02
by Utterly
Initial thoughts on multiple mana sources

1) The running total method of mana is an inappropriate solution to the problem, even now: Mana producing cards often have alternate tapping/sacrificed abilities, thus you have to treat them like they are tapped if they are used, regardless.

2) If your next-action-object holds the tap status (and mana pool) of the current state, and recursively spawns a new (set of) successive next-action-objects including the game state based on the object (plus the action) that spawned them (rather than just being iterative,) it makes no difference whether a card is mana-generating or not. Knowing whether any given card is tappable - or limited in some other way- (and hence usable/unusable) or otherwise matters, and its handled the same way for both mana and other permanents. You've reached the complete solution state, when there are no more potential actions.

A next action shouldn't be planned blind. A solution is the set of single actions among a recursive set of possible actions.

Rather than the AI acting on these directly (because if you are simply testing the outcome, you don't need to store the mana state for every action - the recursion of next-action-object has taken care of the complication of what given set of abilities and actions are available in a turn,) you could generate either a tree structure (each node being a single "action," card action outcomes, and a set of pointers to next potential single actions,) or construct a 2d array with each row holding one unique permutation of potential actions.

Now, considering potential issues, there may be performance issues (finding ALL solutions might produce a gigantic search space, so we'd need to figure out methods to limit that - and problems with deadlocking or infinite loops - aborting based on recursion depth, perhaps) but it would be my first approach in solving this.


3) If you're going to have a mana pool (and you should if you're simulating the game,) you should leverage the game engine, rather than adding next UI elements, just yet. Include a virtual card, with a set of GRUBW, and colorless mana symbols with the current mana pool available in each displayed. Rather than just tapping a land/whatever, you can pre-generate mana, and click one of the symbols to spend mana from your mana pool. Certainly you could do this other ways, but if we're developing the system, better to re-purpose something that's basically already working.

4) Although we mostly care about same turn mana, we're going to have to consider mana in future turns, too. Sacrificing a mana producer for one extra mana may be crucial on earlier turns when it isn't in later turns. Sometimes we can use an ability now to produce extra mana next turn for an ability that we couldn't otherwise produce given our resources. A counter heavy deck is going to want to save mana to operate during the other turn (obviously... but that's irrelevant if you don't have a counter in your hand.)

Extending this idea, more generally, intelligent play incorporates a contextual understanding of your deck and the game situation. Certain actions or expenses have different relative value based on your deck or the game situation. We can set up certain mana strategies given certain conditions (even having any given card contribute a set value to a given mana strategy, perhaps, rather than setting absolute conditions, like slightly favoring reserving mana etc.)

5) Implementation-wise, in determining next-action options, we want to iterate through cards which can produce mana to determine the potential mana pool, but we want to know a couple more things: Does the card have non-mana abilities? Are there other modes (E.G. token for mana, etc.)? This will help with optimization, too; If a non-mana ability (of a card that has other mana abilities) is used (and no new mana abilties were enabled,) the mana availability is the same, minus that cards contribution, for example.

Edit by melvin: I accidentally overwrote this post by clicking "edit" instead of "reply". This version is restored from a copy on my RSS feed. My apologies for not checking before I submit and overwrote the original content.

Re: Obstacles to mana source giving multiple mana? (a code q

PostPosted: 14 Aug 2017, 11:40
by melvin
No issues with representing the mana pool, the problem is in generating the possible mana payment options for a given mana cost. Payment of a mana cost is considered a single move in the game.

Generating the list of valid moves and searching for the best move is independent. The main changes needed to implement mana pool is to represent it in the game model and use it in https://github.com/magarena/magarena/bl ... hoice.java to generate the moves for AI and player. This class decides how the player can pay for mana cost and also determined the options available to the AI when it needs to pay the mana cost.

In principle, we know how it should look like, the devil is in the details to work out the action plan to getting to the end state.

@Utterly do consider looking at the class above to get the details of how the mana system works.