Wednesday, November 4, 2009

Why Programming AI is Hard - Part 3

Hopefully you read (or at least glanced) through parts 1 and 2 that talk about how the min-max algorithm can be used to simulate an AI opponent. This article describes some of the problems when using min-max.

In theory min-max can only be used for games that don't have any "hidden information" and in Magic, the cards in your hand and deck are "hidden information". I have no problem with the idea of allowing the min-max algorithm to see all of the cards in you hand and deck. The only possible "problem" that I see is that this might create an AI that is "too good". I seriously doubt this situation would occur because of the complexities of the actual programming.

(Programming is very hard in case you forgot, ha, but you probably didn't forget because you might be a programmer yourself. Programmers have to interface directly with the computer, so technically, programmers aren't human.)

p.s.
In order to use the min-max algorithm you have to be able to generate all possible moves for both players. I could have also said, "In order to use the min-max algorithm you have to generate all possible game states." I didn't use the term "game state" because I didn't want people to geek out and quit reading my blog. :--)

p.p.s.
On a side note, according to Wikipedia there is a variation of min-max that can use probabilities. You could use probabilities instead of taking my suggestion of revealing the hidden information; there is a 20% probability that your opponent is holding Wrath of God in his hand.

27 comments:

Forge said...

Maybe one day a Magic AI will be "too hard" to beat. By "too hard" I mean that you (the human) would only win if the cards that you drew were better than the cards that the AI drew and you played all of your cards 100% effectively. And if the AI could mulligan well, it could even teach pro-tournament winners a thing or two.

Forge said...

If MTG Forge ever uses min-max, if you upgraded your PC, the AI would improve. (Once of the easiest upgrades is installing more memory.)

Anonymous said...

I have to say I'm rather disappointed by the latest AI articles. I'm very interested in AI programming in general, and Magic AI specifically, and so I was very curious about this series of AI articles. However, after three articles now, I'd like to ask "Where is the meat?"

You've spent three articles now mentioning extremely basic concepts that can be gleaned from a single paragraph in Wikipedia. And the first time when you address a non-trivial problem (how to work with hidden information), your answer is "well, let's cheat, let's just reveal the information to the AI so that we don't have a problem."

Where are interesting problems and solutions? Where's a description of the problems in programming an AI algorithm for attacker/blocker assignment, and some thoughts on gow to solve it? Where's a description of targeting problems and approaches for how to solve them?

This is very disappointing. Instead of interesting solutions you're offering the most simple workaround, let's just cheat.

Unfortunately this line of thinking doesn't seem to be new for MTGForge. When you wrote about not implementing Mulligan, your "solution" was to cheat as well, by giving the AI a guaranteed land supply. Which is a shame really because the Mulligan decision is one that can be programmed much easier than many others, even a mathematically trivial approach like calculating the chance of drawing a hand with a better land/spell ratio goes a long way. (The land cheat was the reason why I stopped playing MTGForge and switched to a different program btw. I want to be challenged by a GOOD AI, not by a blatantly cheating one.)

I have to say that I'm growing increasingly skeptical about your approach to AI development. I think you're switching between totally unrealistic approaches (like the article about using neural networks, how would you actually construct an input vector for one, let alone design an evaluation function and train the network?) and a very simplistic "let's cheat if it gets difficult" attitude. You dream about an "AI that's too hard to beat" but offer no concrete ideas whatsoever for getting even half-way there. As I said, it's thoroughly disappointing, imho. :(

Sorry for the rant. I know how much you did for the Magic community, and I appreciate that a lot. But the recent AI articles really disappointed me so much that I had to get this out of my system.

P.S.: And what is the idea behind improving the performance of a minmax algorithm by adding more memory? Since when is memory that important for min-max? You can program a decent min-max algorithm as soon as you have enough memory to store just two game states. It's the exponentially increasing processing time that makes min-max unusable for complex situations.

Anonymous said...

@ Forge: Using probabilities is a non cheating way to deal with the hidden information. Because you don't offer all the 'secret' information, instead you just let the cpu do what they can do best.. calculating with all the information that is available. This advantage for the cpu is still big enough I would say, because no human will constantly calculate the probabilites of his opponent drawing the killer-cards in his deck... or having them in hand, already.

@ Anonymous: You are quite hard with your critisism. Don't want to say you are wrong in content, just quite hard. I think Forge is at the very beginning with all of that but still wants to write about it. But I think as well that some "cheats" like the mulligan-trick should be changed to something more appropriate. Perhaps Forge can start little projects covering this tasks. So the community (I assume that there are enough people with Java know-how) can make suggestions and there can be found a better solution in teamwork.

Perhaps this would be a decent way for even more general development-tasks of MTGForge, once we see that this works.

Anonymous said...

Can you do an article for the top 10 most difficult Magic cards to program?

DennisBergkamp said...

@Anonymous (post #3) :

So the land cheat was the reason you quit playing MTGForge?
You know, you can just turn it off.

If you would've said "the reason I quit playing MTGForge was its numerous bugs", you would actually have a point :)

Anonymous said...

From Anonymous #1 to Anonymous #2: ;)

Thanks for the fair evaluation of my post. I realize that my criticism was quite harsh. I hope that it wasn't _too_ harsh, but it honestly reflects how I felt after reading the article. In any case I'll be available to elaborate or suggest alternative approaches, should Forge be interested.

I guess what got (and still gets) me worked up is that Forge assumes the attitude of a tutor in his articles, but then doesn't really have much to say about the subject. There's absolutely nothing wrong about "just starting out" with a subject like AI algorithms - on the contrary, I admire people who tackle such complicated subjects in their spare time instead of, say, watching soap operas for endless hours. Forge could have written these articles from a perspective of "Hey guys, I want to talk about AI for a while. While MTGForge's AI sort of 'works', it has also been hacked together without a real professional background in AI programming. Taking this into account, I think the AI performs decently, but to improve it, I really want to read up on the professional side of the subject. I'll report my progress here, feel free to join me in this journey." Had he done so, I don't think I would've been disappointed enough to write my previous comment, because then I would have read the articles with very different expectations.

The second thing responsible for the harshness of my criticism is that I'm really very interested in developing Magic AI algorithms, and I think that Forge's willingness to embrace cheats as solutions is detrimental to that cause. An example to illustrate that: I'm always interested in discussing AI algorithms, so I might have contributed some thoughts about how the AI can make a decent Mulligan decision - if Forge had shown an interest in that. But his article "The AI doesn't Mulligan, and why it doesn't matter" didn't give me the feeling that he was really interested in such a discussion. Implementing a cheat that gives the AI a guaranteed land supply is not a solution to the problem of developing a good Magic AI, it's a cop-out to get *around* the problem. Yet Forge touts it as a good solution and even occasionally remarks that he is proud about the AI. So I didn't feel inclined to start any discussion about the subject, instead I just found myself a community (and developer) that has a strong interest in developing a non-cheating Magic AI. I'd be surprised if I'm the only one thinking that way, so I wanted Forge to know that his willingness of presenting cop-outs as solutions might be actively discouraging people from suggesting and discussing improvements. Developing good AI algorithms is hard work, where's the point in doing it when the program's developer is content with cheats?

I think your idea of community-developed algorithms, with active participation and encouragement by the developer(s), would yield much better results. And finally, to show that I'm not only criticizing, here are three ideas that I'd throw into such a discussion if it existed:

(see next post)

Anonymous said...

(post continued)

1. "Duplicate guessing". The AI starts the game with no knowledge of the player's deck, but keeps track of the cards being played. It then assumes that for each card that it has seen being played, there's a higher chance for another instance of that card of being in the player's library, than there is for other cards. This is a non-cheating approach that is similar to the guesses that human players make during play.

2. "AI combo library". Give the AI information about common card combos. A simple way to generate such a library is to run a heuristical analysis over the several hundred decks available to the program and determine which cards have a high chance of appearing together. Again, this is a non-cheating approach that is very similar to the way human players try to guess their opponent's cards. For example, if you see your opponent playing forests, mountains, and several goblin cards including goblin kings, then the chance that he also has Boggart Ram-Gangs in his deck is *very* high.

3. "AI memory". In a match that runs over several games against the same AI deck, let the AI remember each card that it sees. Again, this is a non-cheating approach very similar to the way human players "learn" their opponent's deck during such matches. If you've seen the opponent play 4x Wrath of God and 4x Day of Judgment in the first game of the match, then chances are that these cards will be present in his library for the next game as well (even if he has a sideboard).

I think there are a lot of ways how the problem of hidden information can be tackled. They just need an atmosphere that encourages AI algorithm discussion to be brought forward, and developers that actively participate in the search for the best algorithms, instead of eagerly accepting cheap cheats as solutions.

@DennisBergkamp: Well, I have to admit that I kind of hoped that you, as one of the major MTGForge developers, would be a bit more encouraging with regard to AI development. Ah well ... it's fair enough if you're more concerned about bugs. Just understand that you're giving me very little reason to contribute thoughts about AI development. I wouldn't have written down the ideas listed above if I had read your reply earlier - as I said, there's little point in doing so if the devs themselves aren't encouraging participating in such discussions.

Also, as I pointed out in my previous post, it wasn't alone the land cheat that drove me away (and I know that I can turn it off, although the fact that it's on by default, and misleadingly labeled, did probably contribute). No, what turned me away was the attitude of presenting this cheat as a good solution to AI development, instead of at least admitting that it was a cop-out, and perhaps encouraging the discussion of better alternatives.

wololo said...

Wagic's AI uses a kind of memory mechanism to remember which cards in a given deck are direct threats to it. The more you play with a given deck, the more the AI will be likely to react to it correctly.
You killed it many times with a mortivore? Get ready for your mortivore to be the target of destruction spells next time you play...
Unfortunately this system's been broken in Wagic 0.8.1 and 0.9.1, and I just put it back. It makes a huge difference in how stupid/clever the AI feels. People who want to compile the SVN version can test it of course.

telengard said...

As far as memory, it isn't the amount more so than the actual use of it (IOW CPU time). I had to implement a bunch of "memory pools" due to the performance hit from allocating/deallocating hundreds of thousands of times per second. It made a HUGE difference.

It's also the reason I backed out all of my multithreaded support, the locking for allocations/de-allocations was killing me performance-wise (and stuff like the Horde allocator wouldn't work on all platforms).

If I have a bug though, the memory gets used up VERY fast, but even at pretty high depths my app only uses a few megs of memory. It scales exponentially though, for each increase in depth the memory footprint goes up a large factor.

I managed to use up 4G of memory at a high depth once in a very short amount of time (like seconds). :)

min-max *itself* in my opinion is not that hard. It's a pretty simple algorithm. That said, you have to make sure your engine can always generate all possible moves and be able to back out changes atomically. It helps to have done this from the start but it can be done. So it's all the stuff you need to support min-max that is difficult IMO.

Huggybaby said...

Anonymous, you're a blowhard.

First, Forge obviously didn't aim these articles at you. But he didn't live up to your expectations and you get emotional.

Second, you're "anonymous", so you can spout off.

Third, MTGForge is open source. You could help out all you want with some code, not theories that, like you said, anybody could read anywhere, and of which Forge is already aware.

Fourth, you choose to support some unnamed program. I'm sure we are all suffering from your withdrawn support. Oh yeah, you never provided any.

Forge assumes the attitude of a tutor? What attitude do you have? Oh yeah, someone superior to the tutor. Gee, maybe you should SHOW us how it's done.

Most importantly, what have you programmed? Where is your implementation of a "mathematically trivial approach"? That should be easy for you, it's trivial you know. Where is your blog discussing AI at a level someone like you could appreciate?

Geez, I could go on and on.

Forge has humbly admitted a million times the shortcomings of his program. He's given credit to those who have helped. He's earned the right to express some satisfaction with his accomplishments, although they don't meet your standards.

MTGForge "cheats" to make the game enjoyable. ALL games "cheat", they can't freaking think.

You should know that the programming of MTGForge is an iterative process. What Forge is writing about, thinking out loud about, is replacing cheats with a more genuine AI. I'm sorry he has not yet advanced it far enough to please you. Try back in a year.

In the meantime, take your skepticism elsewhere. I'm sure your attitude will be welcomed with open arms by your new community and developer. Maybe when you've come up with something you can be proud of, you will no longer be anonymous, and we can all tell you what a hell of a job you've done.

Anonymous said...

Huggybaby, I think you misunderstood my post. Please let me clarify.

| Anonymous, you're a blowhard.

Actually I have nowhere claimed that I could code anything better than Forge, so I don't really understand where you see me boasting? And in case you think I'm trying to diminish Forge's achievement, let me assure you that I'm not. Having programmed MTGForge is an impressive feat, especially considering that it was the first free rule-enforcing Magic engine that really succeeded. Nevertheless I still think that his current approach to AI development is detrimental to developing a good AI, and I believe that it should be possible to raise this criticism without being called a blowhard.

To reiterate: The last four AI-related suggestions in this blog are:
- apply a cheat to give the AI a guaranteed supply of land
- apply a cheat to give the AI spells that suit the mana curve
- implement a self-learning neural network as a Magic AI
- apply a cheat to let the AI know what's in the player's hand or library

My point is that this approach is detrimental to the development of a good AI because it (a) circumvents problems rather than solving them, and (b) may discourage people from suggesting and discussing AI improvements for MTGForge, since the main developer seems to be content using cheats. I think that's a valid criticism.

| First, Forge obviously didn't aim
| these articles at you.

Maybe, but I don't see how this invalidates the things I criticized.

| Second, you're "anonymous", so you
| can spout off.

I don't see how my criticism would be any more or less valid if there was a name to attach it to. I'd also be surprised if my IP wasn't logged. However, the front page specifically states that anonymous comments are possible, so I figured that Forge would indeed be more interested in _what_ was being said as opposed to _who_'s saying it.

| Third, MTGForge is open source. You
| could help out all you want with
| some code, not theories that, like
| you said, anybody could read
| anywhere, and of which Forge is
| already aware.

Well, imagine you are a coder to whom it's really important that programs have a sleek user interface. You follow two projects, one of which has a developer that repeatedly touts quick and ugly hacks to address interface issues, and the other one has a developer who repeatedly states his interest in producing a sleek interface, who's always willing to discuss suggestions and who implements some of these suggestions very quickly. In which project would you invest your time?

I'm in just this situation, only that it's the AI that's most important to me. Therefore, it's very unlikely that I'll do any coding for MTGForge. This is not me going emotional and wanting to somehow "punish" MTGForge for not choosing the AI approach I'd like (I'm really not that childish), it's simply a matter of wanting to invest one's meager skills where they are appreciated most - which, imho, is quite natural, don't you think?

Of course, you're absolutely free to disregard criticism if it comes from someone who isn't willing or able to code for the project. I don't see how that invalidates my criticism, but it's your prerogative, definitely.

(continued below)

Anonymous said...

| I'm sure we are
| all suffering from your withdrawn
| support. Oh yeah, you never
| provided any.

Well, I didn't (and honestly still don't) have the feeling that my "support" is even wanted. There's no need in developing a decent AI Mulligan algorithm if you're content with a cheating AI. As Forge self said, "Truthfully I think I could program the computer to mulligan but I didn't think that it would greatly improve the AI." So why should I offer my suggestions for something that he regards as unnecessary?

When I said that I went to another community at this point, I didn't say this as some sort of childish "punishment". I said that to make Forge the aware that IF he wants MTGForge to have a good AI, he's shooting himself in the foot by discouraging people from contributing who might otherwise be interested in helping.

Personally, I think that this is a valid observation. Of course, you can tell me "That's easy for you to say, you never helped this particular project." Which is true. I don't think it invalidates my criticism though.

| Forge assumes the attitude of a
| tutor? What attitude do you have?
| Oh yeah, someone superior to the
| tutor. Gee, maybe you should SHOW
| us how it's done.

I certainly don't think I'm in any way superior to Forge. Frankly I don't think in these categories. I do think he's currently choosing a bad approach to AI development. That's of no relevance to what I think of him as a person and it definitely doesn't make me feel "superior" in any way.

| Most importantly, what have you
| programmed? Where is your
| implementation of a "mathematically
| trivial approach"? That should be
| easy for you, it's trivial you
| know.

I said "even a mathematically trivial approach like calculating the chance of drawing a hand with a better land/spell ratio goes a long way." I stand by that remark.

The most simple algorithm would be:
- Mulligan if you have less than two or more than (currentHandsize-2) lands

That obviously break down for decks that are designed to have very few or very many lands, so an improved algorithm could be:
- Mulligan if you have less than two or more than 5 lands, and the chance of getting between 2 and (currentHandsize-2) lands is | 50%. This way the AI won't mulligan itself to death if you give it a oneäland charbelcher deck, or a Terravore deck with tons of lands. The chance can be calculated by simple probabilistics, the formulas are easy to look up even if one isn't very mathematically inclined.

However, this algorithm doesn't take into account that the reduced handsize is a punishment for having a better number of lands, so you may want to be even more certain that you actually get a better land situation in your next draw, so raising the 50% to 60% or more might be appropriate.

Also, the algorithm would be better if it took non-land manasources into account as well. How hard this is to implement depends on how the cards are coded, but I wouldn't expect a problem at this level.

So far, the algorithm realls isn't that complicated mathematically, all you need is to look up a single probabilistics formula for the situation "You have 60 cards. M of these cards are mana sources. You draw N cards. Determine the chance that X mana sources are among them." And despite this, the algorithm would already cover a lot of Mulligan situations with decent results.

(continued below)

Anonymous said...

You can then further improve the algorithm by looking more closely at the non-land cards. For example, you can determine "Can I play at least two non-land cards in the first three turns with this hand?" Since the hand size is small, you can check the different possible card playing orders (at the worst you'd have to check 7! = 5040 cases, but you'd need every card to be a spell _and_ a mana source _and_ hardly compatible with the other cards to get into a situation where you actually had to check all these cases. It's probably possible to optimize the algorithm if necessary - actually the Mulligan decision might be a good training grounds for implementing a minimax algorithm with alpha/beta-pruning since all cards are known and the number of permutations is small. Anyway, this check would help the AI in cases where it has a "good" ratio of lands and spells, but the colors don't match, e.g. 4 mountains and only spells that require green mana.

Finally, it would also be good to determine (or guess) the chance of being able to play at least 2 spells in 3 turns IF the AI draws a new at hand. At this point, the mathematics are definitely not trivial anymore, so this is where discussion among developers hopefully kicks in, and perhaps someone is mathematically inclined enough to come up with a good solution. Even if this problem doesn't get solved, the algorithm should perform decently in the vast majority of Mulligan situations.

So, this is the kind of algorithm that I'd like to discuss. However, where's the point of doing it when the dev in question already said that he could implement a Mulligan algorithm, but is content with simply implementing a land cheat?

| Forge has humbly admitted a million
| times the shortcomings of his
| program. He's given credit to those
| who have helped. He's earned the
| right to express some satisfaction
| with his accomplishments,

I absolutely agree with every single word. But I also think that he isn't infallible and that, if he's using a flawed or detrimental approach to a problem, it's okay to call him on that.

| MTGForge "cheats" to make the game
| enjoyable. ALL games "cheat", they
| can't freaking think.

The existence of cheats makes the game a lot less enjoyable for many players, so this argument kind of defeats itself, at least itÄs not universally true. It's _definitely_ wrong that all games cheat, although many indeed do.

| You should know that the
| programming of MTGForge is an
| iterative process. What Forge is
| writing about, thinking out loud
| about, is replacing cheats with a
| more genuine AI.

Frankly I don't see that. Perhaps it's a misunderstanding on my part, but what I'm seeing is someone saying that he _could_ write a Mulligan algorithm but decides not to in favor of a crude cheat, and then goes on to suggest to give the AI a guaranteed mana-curve-friendly supply of spells, and then goes on to saying that it doesn't bother him to reveal hidden information to the AI. I'd be glad if he'd see this a just an intermediary step, but please tell me where he actually says that in the articles I referred to.

And again, please, I don't want to diminish Forge's accomplishments in any way (this is the third time now I'm saying it, it really is important to me). But I think that his approach to AI programming as presented in the last 4 blog articles that referred to it is flawed, and detrimental to programming a good AI, and that's what I wanted to make him aware of, in order to hopefully convince him to be a little less eager to use cheats. I'm sorry that this has turned into such a beast of a discussion.

(finish)

Anonymous said...

Trackback from Anonymous #2 to Anonymous #1:

I don't want to say anything else to the main discussion.. I think you made very clear what was your intention throuhout the last 4 comments and I personally think that you are right.

Your 3 ideas for better approaches in AI development are very interesting. Let me throw in something in addition:

Think of some data-mining analysis.. let's imagine that after each game of MTGForge the program transfers the deck-list and some kind of action-list, containing the spells the human player casted.

1. After a while the database will be big enough for 'association rule learning'. So the computer will be able to determine cards that offen appear together. Let's say human player plays a Millstone, so it's very likely that cards like "Altar of Dementia" (or other cards forcing the opponent to put cards from the library into the graveyard) will follow later in this game. With the constant flow of game-information, of games and decks played, this would bring up very popular cards with higher confidence than very old and only seldom used cards. There would be a great variety of other things you could analyze with data-mining algorithms. And it could also be a chance to let the cpu determine which card to play using decision trees.

--> Most of all personal comupters have a permanent connection to the internet these days and the more games are played in MTGForge, the better the AI will act. So it will get better by the time and it will find continuously better answers to very popular decks (actually used by a lot of people)

Addition to the community idea: I know MTGForge is Open Source. But I think lots of people just don't have the time to get round with a big project another person has started. In my oppinion it would be a better way to start certain tasks... cpu mulligan for example.. and then declare the month of novemeber as the task-month addressing this problem. (2 or more month for more complicated things)

You can briefly just publish the current solution and specify the input and output parameters for the target sub-routine so that people can just focus on this task and do not have to understand the entire source code. BECAUSE you (Forge) understand it and that's enough. After a good solution is found and developed far enough you can just insert this function as a "module" replacing the old one, because the input / output parameters guarantee that it works perfectly together with the other parts.

Simple example:
There is a handy-object containing all the information about the cpu's hand... it offers the following propertes: .count --> int, ..... and methods: xyz --> in / out

!!! Here we have to make the new non-cheating sub-routine deciding wether or not to mulligan !!!

And here is the function cpuPlayer.Mulligan(n) where n is the number of new cards being drawed.

I hope you got the idea.

I think this could get a lot more people involved, because they don't have to spend the time to look up your code, understand how the hole thing works and _what_ needs _where_ to be done to implement a better mulligan-decision. They can just focus on the sub-routine. In fact this is similar to a "black-box" behaviour, because they don't know (and don't need to) what the program will do next.

Hope I was able to make myself comprehensible.

nantuko84 said...

Anonymous #1:
what other game and community did you talk about? as I can see you have some experience with ai programming.
could you mail me to nantuko84@gmail.com, I have some questions to you regarding mtg ai development
thank you in advance

DennisBergkamp said...

Wow, this is turning into quite the discussion :)

@Anonymous:

In no way did I mean to discourage you bringing up points about AI development. But you're right, currently I (personally) am way more concerned with fixing some of the major bugs in MTGForge. If the game crashes, it's bound to piss off a lot more people than the AI "cheating" and grabbing a few extra lands.

HOWEVER, I do agree with you these are not great ways of programming a good AI. But for now, they'll just have to do... this is purely a matter of priorities, and currently the bottom line is: there's bigger fish to fry.

Having said that, I did make a bunch of improvements to the AI here and there... and I will continue to do so. But a big AI overhaul will have to wait till the program as a whole is more stable.

Anonymous said...

Understood and agreed, crash bugs definitely _should_ have higher priority than AI issues.

I also have to apologize for reading too much in your first reply. When you said "... then you had a point", I read that as "Your criticism is pointless, the AI is good as it is and there's no problem in adding cheats to it." Your follow-up now made me aware that this is not what you meant. If you're seeing the land cheat (and similar ideas) as a crutch to help the AI along until a (planned) AI overhaul takes place, then we're really not that far apart. I'm still not especially fond of the land cheat even in that context (imho it would have made more sense to implement a non-cheating simplistic Mulligan algorithm instead, I think such an algorithm would have yielded decent results without actually being harder to implement than the land cheat), but the prospect that such cheats are "crutches awaiting improvement" instead of "preferred and intended solutions" makes them a lot easier to swallow. :)

rising fruition said...

Anonymous, I think you are (were, after 11:48 AM post) overly focused on something you call a ‘cheat’. You seem to want your Magic experience to be pure and fair and by the rules. That's fine; we all have our preferences. However, that’s not where Forge (the person) is coming from. He’s more interested in a game that’s FUN. AND, since he had to program it, he’s interested in a game that doesn’t take forever to code. At the time he made it, the Mulligan ‘cheat’ was a quick way to make a program that worked and was fun to play. That was the intent.

*I* also want things to be pure and fair and by the rules. However, that often means doing things the hard way. As time goes by, I am realizing the great value of doing things ‘well enough’. I think it shows great creativity to think of a way to quickly code the program to work, even if it isn’t ‘legal Magic’. Think about ‘bang for the buck’ here. I applaud Forge’s non-mulligan solution.

I have to agree with Forge that it would not ‘greatly improve the AI’ (Aug 26, 2009) if he were to program the computer to mulligan. It *would* make the AI more pure, as in ‘following the rules’. But would that ‘greatly improve the AI’? Think of the most awesome mulligan algorithm you can possibly imagine. Now pretend that there are 2 versions of Forge (the program); one has the currently coded algorithm and the other has the ‘most awesome’ algorithm. I believe the difference in FUN of playing against these 2 would not be significant.

On the other hand, regarding the way Forge (the program) mulligans (or doesn’t as the case may be): who cares? It’s a MODULE. And if it’s not, it can be refactored into one. It can be replaced with another MODULE, perhaps one that actually mulligans, and does it by the book, following the rules.

If a min-max algorithm is implemented in Forge, for the main part of the game, and it takes advantage of hidden information, I feel it will only be done that way because 1) it takes significantly less time to program, and/or 2) it is much more fun to play. My guess is that neither one of those will apply, and therefore, the AI won’t use hidden information. I guess we’ll see some day. I hope we’ll see some day.

But, if it does use hidden information, who cares? It's a MODULE. And if it's not... (see above). Someone can make a new one that doesn't use hidden information.

Konstantin Vernikovskiy said...

I personally don't think that the AI should strive to limit its knowledge of a player's deck pending a bunch of plays. After all, any player playing against a deck can, if they wish, know instantly the entire deck-list of that deck. Forcing ignorance upon the computer would in my mind be cheating in favor of the player, something the player does not at this point need. Furthermore, it would make a sort of 'grind mechanic' where the player has to play a given deck a number of times before the AI feels it has permission to play it intelligently. Finally, allowing the computer to know the deck-list and make decisions accordingly is much easier, programming-wise. Now, a 'learning' approach (like in Wagic, I suppose, though I haven't played that enough to observe such a mechanic) that actually /improves/ the AI I can get behind - just not artificial crippling via imposed ignorance.

Huggybaby said...

Anon #1,

I don't know how you disagree that the development of Forge has been an iterative process. It has and continues to undergo constant refinement.

As for the rest, your points are well taken, kudos.

Silly Freak said...

besides that whole discussion, i want to bring one point back, a few days after the article came out: i like reading forge's articles, but this one seems a little broken. when the "PS" came, i thought, "where's the whole article gone? that was just an intro!"

and i'd like to note that seeing modules in forge is sometimes not easy. i think forge himself said (not in that words) that the core that was originally well planned is so small you could just call the whole program a hack. there are some people who can see the structure of forge; i myself can't and stay at the surface with my submissions.
doing major changes (and I don't know at what size to start "major" - for sure something as M2010 rules) is forge is very hard, that's why i'm trying to implement my own version - not playable, but with some success already

Guillermo said...

Sorry, but I'm little bit more interested in a new version of the Forge... sorry again about my sincerity..
Thanks anyway for the material it has been released and for your spended time to make a lot of people have fun.

Forge said...

Probably the most number of comments ever (for better or worse).

The articles were a little bit simplistic. Some of this is me just "thinking out loud" since I don't have anyone to bounce ideas off of.

Frankly the min-max algorithm scares me to death because it is so complicated but I really want to use it. (It is hard to do something when you think you'll fail at it.)

I'll try to talk more about MTG Forge and how great it is. :)

Forge said...

rising fruition,

"As time goes by, I am realizing the great value of doing things ‘well enough’."

Thanks.

telengard said...

Forge you won't fail at it. Feel free to come onto #incantus on efnet anytime and I can try to help. As I mentioned the hard part isn't min-max itself, it's all the support code needed (undo, querying for all available actions, etc). I don't mind sharing what I've done with you as far as code etc.

If I can do it, anyone can. :)

Forge said...

Thanks telengard