Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Reelya]

Genetic algorithms can be set up with varying levels of mutation. You optimize for a specific level of random mutation around the "sweet spot". if the mutation rate is too low you get all your points being too perfect (usually stuck in a local maximum), the same as too-high mutation rates, you get too much random noise instead of optimization. This is a known factor that can be coded in

So what I was actually meaning was that the genetic algorithm tries to optimize things to get the best jump, but it has a fairly high mutation rate which would simulate the player hitting different keys, and against that mutation rate, the physics optimizes for a predefined chance of success.

Mutation rate for the player controls, and success chance for the jump would be the two hard-coded parameters. (EDIT: I'd also want to optimize things such as you're pressing keys as often as possible, e.g. a higher level of engagement is necessary).

[Reelya]

I'm not sure what you're talking about now, because it's given that we have a model of the car and the ravine that we are working with. You just time step the thing in the existing code.

You don't need the machine learning to create a model of that, it just needs to push the buttons and see what happened. Then the physics parameters and the controls being pushed get optimized in convergent genetic algorithms. none of that requires you to have equations for the thing you're optimizing, that's why you are using machine learning, so you don't have to have equations for it.

[Reelya]

The game engine has the model already. You don't need to come up with a "mathematical model" of the underlying equations whatsoever. That's what the genetic algorithm is about.

you have inputs, which are the physics parameters, and the car driving controls. Both are set up according to the genetic algorithm. Then you have the model, which is the physics code of the game itself. You run the physics code with the parameters then you get metrics back, and do the whole genetic algorithm thing until your population of GA's gets the required result the right amount of the time.

[Max™]

Fun metrics are an interesting question.

Controllable character behavior variations.
Tactical depth on a scale from rock-paper-scissors through chess through [some suitably deep tactical game].
Control scheme manipulation options, the vanilla df layout is awful for adventurer mode as far as my taste goes, but it can be altered in numerous ways so I was able to find a fun comfortable useful setup.
Difficulty vs progression, being given everything from the start is boring, working hard for nothing is frustrating, working hard for interesting new [tools/options/abilities/accessible areas/storylines] is not.
Playthrough variations, how many ways can the choices you make influence how the game responds, and does the game offer reasons to explore these options and discover new content.

As some examples of various parts of those scales that stand out to me: Metal Warriors (SNES), Way of the Samurai 2 (PS2), sandbox-era GTA games (various), DF (various), Gran Turismo # (PS#), Star Control (Genesis), X-com (the old PC one), and Armored Core # (only played up to the PS2 versions).

[Reelya]

I think we're using different definitions of the word "model" here.

What I mean is a function f(t) which, for any given value of t with 0<=t<=inf, describes the position of your car, given user inputs under whatever probability distribution we've applied to them.

but that's not how machine learning is applied. You don't need to come up with a theoretical model of the thing you're optimizing, you just need the thing, inputs and outputs, and a metric.

in this case the thing is the game, the inputs are the controls and physics constants, and the output is what happened in the game when you applied those things. The metric is how you rate a specific set of inputs, and you then raise or lower their score, mutate them, then run more trials until you get something close to what you asked for.

[Reelya]

Uh, the game's code does that. We are trying to optimize an existing piece of code btw.

Let's take it to a 2D example. If you were trying to optimize the difficulty of a Super Mario jump you just run the jump inside the game's code, while mutating G.A. code that does the jump with slightly different control pushes. The more forgiving the controls (i.e. the further from optimal the Genetic Algorithm can go and still make the jump) is a direct metric of the difficulty of the jump.

again, you don't need a "mathematcal model" of how jumping works, because you've got the code of the game to run trials in.

[Reelya]

Is it a singular function which determines, given the set of all the user's inputs, whether they make it across the ravine or not, as a function of time?

Or is it just plopping the car on a ramp in whatever physics simulation and seeing whether they can make it or not?

You run the simulation inside the code itself. It's sort of the entire point of machine learning. If you're coming up with a theoretical mathematical model, then that's not machine learning because it's not shaped by the thing you're trying to measure.

[Reelya]

You are making less and less sense now. What is your point?

The thing is, you have the game, you can set up the specific point in time, run the car over the ravine thousands of times and you collect data. You then optimize things in the way I described. it's a statistical process, and you don't need to develop any "theoretical" model because it's all about empirical data. That's the basis of machine learning.

[Reelya]

Uh, I described that in detail already.

it would be optimizing the difficulty of the jump, and by difficulty, I mean you can tune the system in terms of how sensitive it is to the exact controls you hit. Genetic algorithms are statistical, you have mutation and selection pressures, so you can tune the exact amount of variation in a genetic algorithm population. Then you co-evolve the physics constants used in the model so that the average chance of success of the genetic algorithm population is constant.

So, a genetic algorithm for the exact timing of the button presses, with a specific mutation rate gives you a spread of button-pushes around the "ideal" set of button pushes. Meanwhile the physics settings are also being adjusted against that, to maintain a ratio of wins/losses.

[wierd]

Player interaction leverages the game's physic model. Unless the AI is also muddling the physics engine (better to use two different AIs with different design goals for that, that just provide tips to each other if you want full automated evolution) one can perform trials using the physics engine, because it can be treated as a constant, and not a dependent variable.

EG, if your design optimisation is limited to "I want a challenging but fun level layout, using Super Mario Bros engine", the former AI can handle this. If your design optimisation is limited to "Players say the physics are wonky, and not fun to play with--" then the datasets used may include video captures of objects falling/colliding/exploding, along with capture data from its engine, and player interaction.  The former is a very different AI from the latter.

[Reelya]

How long does it take for a single simulation to run?

How many cars can you put in a game at once? How fast could it run if you turn graphics off? If you turn car-car collisions off I imagine you could jump hundreds of cars over the ravine at once. Kind of the whole point of genetic algorithms is that they are a parellel processing operation.

[wierd]

Isn't that a derivation of the halting problem?

It also has shades of travelling salesman.

The AI is an optimisation AI-- It looks for better solutions. If it happens upon the absolute mathematical ideal early on, it will continue to test other cases, until it has exhaustively concluded that it has found the global ideal solution given its dataset and rules constraints.

How "lucky" do you think this AI is?

[Reelya]

Well say it's 5 seconds to do the jump then sequentially you could test another configuration every 5 seconds, that's assuming you don't turn off anything else in the game such as graphics and you don't multi-task it. If you're running the engine anyway you might as well implement the maximum number of cars the engine can support while doing this.

But the bigger question would be "how many generations does a genetic algorithm take to reach stability". to which the answer is "not that many". Genetic algorithms aren't some pie in the sky future tech, they're a widely used technique.

I also think that this idea would be more robust than hand-tuning. After all, someone hand-tuning the controls only has their own input to tune against, rather than tuning for a range of player inputs. And they are usually "winging it" rather than tuning against any sort of objective metric.

[wierd]

Which at best, discovers local maxima, given a set of conditions. (There is no perfectly evolved lifeform, for example-- as this is exactly how natural evolution works too.) There can be several local maxima of equal merit within a given solution space though. 

Do you create additional AIs to systemically exclude tested solution spaces being attempted by other AIs given the same task, then review the data from all those AIs?

How long does that take?

(what I am getting at here, is that this is a rather silly set of questions to ask-- These AIs are not being presented with a time constraint, unless one is artificially imposed, which will then only result in even more "localised" local maxima, because the simulation depth is kept small for expediency. There is only so much low hanging fruit.)

[Reelya]

It'd be a lot less that that as I said, you could run as many trials as you can run cars. Plus you could turn all non-essential things such as graphics to the minimum. Tuning by genetic algorithm is an extremely common situation in games development.

And often genetic algorithms are used for such things as training the AI in an RTS, which obviously takes more than 10 seconds a trial. If they are already successfully applied in training and entire RTS AI, then optimizing a single jump in an arcade game is clearly going to take a shorter time per trial.

Here for example is a case of a guy who trained a genetic algorithm to play tetris:
https://luckytoilet.wordpress.com/2011/05/27/coding-a-tetris-ai-using-a-genetic-algorithm/

And this recent one, some guy used genetic algorithms to beat pros at Super Smash Bros
https://www.newscientist.com/article/2122452-ai-beats-professional-players-at-super-smash-bros-video-game/

You seem bewildered by what I'm suggesting, but it's a lot more tame than what other people are already doing.