Genetically programmed Trackmania

General Discussion about Trackmania Nations ESWC.

Moderator: TM-Patrol

Post Reply
User avatar
xai
happy cruiser
happy cruiser
Posts: 162
Joined: 13 Nov 2008 15:46
Owned TM-games: TMU(F),TMN(F)
Manialink(s): xai

Genetically programmed Trackmania

Post by xai » 15 Jul 2011 19:16

I decided to start a little project last week: to genetically program a Trackmania "bot".

What is genetic programming?
If you don't know what genetic programming is: you basically start by generating a population(in my case of 20) of random bots that just bashes the throttle, steer and brake buttons. You let them all drive a track, you pick the best ones and adjust them just slightly(like by 2%), then you let them drive and select the best again, adjust those, and you just repeat that all the time. Theoretically you should be able to get a bot that can drive a track perfectly after some(read: a lot) of time. It's evolution, but then in programming :P.

Wow, what are the results?
I ran the program that "evolves" for 8 hours straight. The best bot drove a track which I can finish in under 6 seconds in 9.23 seconds. It's not a top time, I know, but it's not about top times for me, it's about the technique behind it.

Video video video!
As you want sir:
http://www.tm-tube.com/video/24454/Gene ... +Test+%231

Isn't this cheating? :(
Some might consider this cheating, I say: it's cheating, but it's so impractical(would probably take months to drive a track better than a "good" player) that you could better spend the time training yourself and not the program :).

Can I take a quick peek at the source code?
Nope, sorry, since this program uses some techniques that hackers could exploit I won't make it easier for them to use it. Only one I would release my code to would be Nadeo staff :P.

Any questions, comments, ideas or encouragements?
Weeeeeeeeeeee

tcq
speedy pilot
speedy pilot
Posts: 380
Joined: 05 Apr 2007 08:09
Location: Germany

Re: Genetically programmed Trackmania

Post by tcq » 15 Jul 2011 19:51

Nice idea to find the optimal line due to an genetic algorithm. Used this kind of calculation a lot the last years, but it consumes so much power -_- Which technique did you used for the recombination part?
Did you set a cut off value after finding a local optimum or did you let it simply calculate for 8 hours and the aborted it?

User avatar
xai
happy cruiser
happy cruiser
Posts: 162
Joined: 13 Nov 2008 15:46
Owned TM-games: TMU(F),TMN(F)
Manialink(s): xai

Re: Genetically programmed Trackmania

Post by xai » 15 Jul 2011 20:20

tcq wrote:Nice idea to find the optimal line due to an genetic algorithm. Used this kind of calculation a lot the last years, but it consumes so much power -_- Which technique did you used for the recombination part?
Did you set a cut off value after finding a local optimum or did you let it simply calculate for 8 hours and the aborted it?
I did it simple, just letting it run for 8 hours and aborting. Still thinking about running multiple instances of trackmania in virtual machines so I can distribute each population over them :P
Weeeeeeeeeeee

Queen Jadis
speedy pilot
speedy pilot
Posts: 459
Joined: 18 May 2009 21:37
Owned TM-games: TMUF,TMNF,TMSX,TMN
Manialink(s): jadis
Location: Scotland

Re: Genetically programmed Trackmania

Post by Queen Jadis » 17 Jul 2011 13:06

Nice idea, but, as you said, practically not very efficient. I can imagine that the time and capacity that the program requires depends on the complexity of the specific track (for ESL longer than for LOL :P). I also doubt it would find cuts or tricks on such maps, regardless of the time it takes, and thus it will never rival real players.
Image
______________________________
My manialink: Jadiscolor>
My TM Blog

User avatar
xai
happy cruiser
happy cruiser
Posts: 162
Joined: 13 Nov 2008 15:46
Owned TM-games: TMU(F),TMN(F)
Manialink(s): xai

Re: Genetically programmed Trackmania

Post by xai » 17 Jul 2011 13:31

Queen Jadis wrote:Nice idea, but, as you said, practically not very efficient. I can imagine that the time and capacity that the program requires depends on the complexity of the specific track (for ESL longer than for LOL :P). I also doubt it would find cuts or tricks on such maps, regardless of the time it takes, and thus it will never rival real players.
If I'd have the capacity of the Google Servers it would actually find cuts. Since then after a while it would have tried every possible combination of key pressing.

The biggest problem at the moment is that it has to finish the track first before I can even start calculating how "good" a bot is. For ESL tracks it will indeed take a very long time before even the first finish occurs. I'm thinking about programming the first "generation" in myself, and let the bot just improve that drive.
Weeeeeeeeeeee

Xymph
Pit Crew
Pit Crew
Posts: 5708
Joined: 19 Aug 2007 12:58
Owned TM-games: TMN, TMU, TMF, TM²
Contact:

Re: Genetically programmed Trackmania

Post by Xymph » 17 Jul 2011 13:37

xai wrote:just bashes the throttle, steer and brake buttons.
Interesting project, but how do you 'bash' the buttons? Is that a robot punching the keys on your keyboard (unlikely), or do you feed the game client via DirectInput or something like that?
Developer of XASECO for TMF/TMN ESWC & XASECO2 for TM²: see XAseco.org
Find your way around the Mania community from the TMN ESWC hub, TMF hub, TM² hub, and SM hub

User avatar
xai
happy cruiser
happy cruiser
Posts: 162
Joined: 13 Nov 2008 15:46
Owned TM-games: TMU(F),TMN(F)
Manialink(s): xai

Re: Genetically programmed Trackmania

Post by xai » 17 Jul 2011 16:25

Xymph wrote:
xai wrote:just bashes the throttle, steer and brake buttons.
Interesting project, but how do you 'bash' the buttons? Is that a robot punching the keys on your keyboard (unlikely), or do you feed the game client via DirectInput or something like that?
I simulate a button being pressed. I use the Java(yes, the program is written in Java) class "Robot" for it.
Weeeeeeeeeeee

tcq
speedy pilot
speedy pilot
Posts: 380
Joined: 05 Apr 2007 08:09
Location: Germany

Re: Genetically programmed Trackmania

Post by tcq » 26 Jul 2011 15:07

xai wrote:For ESL tracks it will indeed take a very long time before even the first finish occurs. I'm thinking about programming the first "generation" in myself, and let the bot just improve that drive.
Why not driving a few runs into the finish and record the buttons you pressed with a key logger to create the first chromosomes?

User avatar
xai
happy cruiser
happy cruiser
Posts: 162
Joined: 13 Nov 2008 15:46
Owned TM-games: TMU(F),TMN(F)
Manialink(s): xai

Re: Genetically programmed Trackmania

Post by xai » 31 Jul 2011 18:28

tcq wrote:
xai wrote:For ESL tracks it will indeed take a very long time before even the first finish occurs. I'm thinking about programming the first "generation" in myself, and let the bot just improve that drive.
Why not driving a few runs into the finish and record the buttons you pressed with a key logger to create the first chromosomes?
That's what I mean with that. Only problem I'm facing now: inaccuracy, if I'm off by 50ms at the start it can make a huge difference in the end.
Weeeeeeeeeeee

Post Reply