This is very nerdy so feel free to skip this and watch an episode of The Simpsons or even better The Big Bang Theory. I really do think I'm half-Sheldon and half-Leonard, ha. (I promise to write a normal article about MTG Forge next time.)For my geeky readers, you might want to checkout this article about evolving a good evaluation function. The name of the article is "Bootstrap Learning of Alpha-Beta Evaluation Functions" which refers to the evaluation function that is used for alpha-beta, an optimized version of min-max. (The article uses the Greek symbols alpha and beta.)
I'll try to summarize the article. The min-max algorithm doesn't involve any learning since it uses a static evaluation function and the article proposes the idea that you save the game state tree that is generated and try to evolve a better evaluation function. The idea is to test the evaluation function with the previously generated game tree to see whether the evaluation function made good choices.
(Remember that the goal of the evaluation function is to determine which player is winning and by how much. Usually the evaluation function generates an integer number to represent how much the AI is winning or losing.)
Saving the whole game state tree that alpha-beta creates is difficult. I understand the alpha-beta algorithm but I don't understand it well enough to code it and the alpha-beta code that I have found is recursive, so I don't know how to save the game state tree that is created.
Basically the article is really interesting and has some really good ideas but I'm not sure how to practically use it. (Thinking about AI hurts my brain.)
p.s.
I got my four year bachelor's degree in Information Science but we didn't touch AI. I really need a Master's degree or PhD in order to really understand AI. Anyone willing to foot the bill? :*)
p.p.s.
I found a nice Java implementation of the alpha-beta algorithm in the download section for the book "Algorithms in a Nutshell". You can read more about the book and download the code from here. (To download the Java source code the link is on the left side in small letters, click on "Examples". Now you should see three directories, click on "Releases".)
Or you can download the 10 MB zip file from here.
nice blog. a like the twist you've done combining magic with programming. uniqueness.
ReplyDeleteSo basically, MinMax could be used for the AI, and Genetic Algorithms to improve the evaluation function :)
ReplyDeletehm, I like the idea to generate weights for evaluation function using GA. we can just create descriptions of many game states and run GA to teach program use proper evaluation... \o/
ReplyDelete"Nice blog. a like the twist you've done combining magic with programming. uniqueness."
ReplyDeleteThanks. Combining Magic and programming also limits the number of people who would find my blog interesting but that is OK because I really enjoy writing about Magic and programming it.
Once I get MTG Forge 2.0 working with 10 cards and can support min-max then I can start applying a whole truckload of AI techniques like genetic algorithms, alpha-beta, neural networks, etc... The possibilities are truely endless once you start combining the techniques such as alpha-beta WITH genetic algorithms. Or using alpha-beta that uses a neural network for the evaluation function which could actually learn while it is playing against you.
ReplyDeleteJust optimizing alpha-beta is a whole sub-project all to itself because of the huge number of things that can be tweaked.
Such as the depth that is searched, the evaluation function itself, and the amount of information about Magic that you want to give the algorithm, like a creature can block and also use its activated ability. Giving alpha-beta more info should improves it's performance.
Hypothetically if the code is fast enough, before you play the computer it could play itself a few times using the decks that you have selected so it would know what is the best strategy.
ReplyDeleteIn the future, computers will be as good at Magic as they are now at chess. (I’m not sure if this is a good thing or scary, lol.)
"In the future, computers will be as good at Magic as they are now at chess. (I’m not sure if this is a good thing or scary, lol.)" That might prove problematic, I am sure wizards will make more complicated abilities and fundamental Comp. rulebook changes to stay ahead for a while :P.
ReplyDeleteZerker,
ReplyDeletethe ironic thing is that you might be right. A few rule minor rules changes here and there in order to keep the AI programming behind. Odd historical fact, supposedly the current "Qwerty" keyboard was designed to make typing SLOWER because people were typing too fast when the typewriter was first invented. I've read this fact is a few different places and it seems to be true.