Comments on That's a Terrible Idea: Reducing and Translating Games

http://en.wikipedia.org/wiki/Knapsack_problem

2009-12-04T12:30:30.621-05:00

http://en.wikipedia.org/wiki/Knapsack_problem

It might interest you that at the time I quit WoW ...

2009-12-03T15:27:38.669-05:00

It might interest you that at the time I quit WoW I was actively developing an application that mined the WoW Armory for items (given some query) and then used a GA to try to determine an optimal gear set for a class, taking into account gems and enchantments.

Although some people claim that min-maxing characters in WoW is as simple as stacking one or two key stats, I think it's a lot less straight-forward than that. There are a lot of subtleties to the process, and a lot of them aren't extremely obvious. this is further complicated by people's innate desire to get shiny new stuff which often leads to bad (human) gearing decisions.

Anyhow:

My initial model was to be feral druid (my class), which had a few stat plateaus (hit rate, armor pen, and maybe something else) to be optimized around.

The end goal, however, was to be general enough in the implementation to allow the GA to optimize any class. The trick here was to develop a syntax that was useful in expressing fitness functions in terms of WoW stats.

A simple example (in plain english) would be: The best gear for a feral druid will maximize attack power and crit chance, however the hit rate must be sufficient to be capped. Further more, armor penetration is a value stat, but after X armor penetration all extra is meaningless.

My interest in coding this evaporated when I quit WoW, and so it's sitting in an unfinished state.

It's good to see someone else around here with an ...

2009-12-02T17:33:33.777-05:00

It's good to see someone else around here with an interest (and apparently some degree of knowledge) in AI. Unfortunately, this article will probably be lost on most people because the significance of being able to transform games into one another isn't apparent to laymen.

Quite often they can solve them flat out - but yes...

2009-12-02T16:49:18.189-05:00

Quite often they can solve them flat out - but yes, I agree your more precise definition is proper.

GAs in particular can get stuck on local maximums (or minimums) and never actually arrive at the correct/optimal solution to the problem that they are designed to solve. Well-tuned mutation rates help mitigate this, but it can never be entirely avoided.

The only reason I miss school at all is my time in AI courses. So much fun!

A Masters in Computer Science comes in handy somet...

2009-12-02T11:04:14.006-05:00

A Masters in Computer Science comes in handy sometimes. :)

Genetic algorithms and machine learning can approximate (not find exactly) the solutions to NP-complete problems in a reasonable amount of time.

Neat post. The really cool thing with NP-complete...

2009-12-02T06:15:27.610-05:00

Neat post.

The really cool thing with NP-complete problems is that they can usually be solved non-deterministically using some artificial intelligence techniques, like genetic algorithms, in a relatively short amount of time.

If "real" intelligences (i.e. humans) find this sort of problem solving fun, I wonder if computers running their AI code are having a blast too? :P