I’m new to GSB and when I first checked it out the first thing that popped into my head was mega programming game potential. If there was a way to automatically run a battle of one deployment against another deployment without having to go through the menus and watch it et cetera it could make for a really really interesting programming game. I saw all the game data is stored in plain text, so you could write a script to implement a genetic algorithm or something of that nature to gradually tweak a deployment towards various goals, testing it’s effectiveness automatically after each incremental change.
I realize it’s not an open source game and this might not be possible, but just wondering if anyone has explored this possibility… I haven’t been able to find any information on it, so it’s probably a resounding “no”, but maybe if the multiplayer matchup server could be run locally? I assume this isn’t available for download though…
Anyways, any thoughts would be appreciated, maybe if enough people are interested we can bug cliffski to scratch the itch he does allude to it in this post after all… viewtopic.php?f=19&t=5275&hilit=automatic&start=15#p35093 although the point wouldn’t be to rack up wins against human picked fleets (as if there’s anything to gain from that except a number anyways), but rather to pit it vs other programmed fleets or to just experiment with different algorithms.
If you can write such an algorithm, PLEASE send it to me! Personally I’d prefer to give it weapon and module sets to work with, then work to beat using a modified version of my fleet. Make it a true AI fleet that’s as hard or harder then a human fleet… I would love such a trainer. Heck, i’d probably try and let it cook up a survival challenge just to see how hard it’d be xD
Yeah, the genetic algorithm part is the easy part, I wrote one for a robocode (http://robocode.sourceforge.net/) robot that was quite effective against fairly strong non-learning opponents (if the opponent learns as well then it adapts to your evolving bot) if trained against the opponent in question for a few hundred thousand matches… The “genome” of the genetic algorithm, or in other words, the set of parameters which were used as the basis of the evolution, was something like the following:
first pixels to move forward/backwards, degrees to turn while doing first movement, second pixels to move forward/backwards, degrees to turn while doing second movement… etc etc with something like 6-12 movement/turning pairs that just looped over and over. So it was simple enough that the algorithm could quickly narrow down to the more effective options, but flexible enough that it could end up with a variety of movement patterns from back and forth zig zags to stars to circles and so forth and so on… Also it had a couple basic types of aiming it chose from, like firing directly at them, firing towards where they’re going, and firing towards where the curvature of their movement is going, which was also part of the “genome”.
For GSB, the genome could be something narrow like starting positions of ships in a predefined fleet, the loadout of a set of ships each in known-as-mostly-optimal predefined locations, order priorities, some combination of the above or even others (again, new to the game). More narrow means it tends to settle on something optimal for the problem space you’ve given it more quickly, but yeah, I could hash something out in ruby in a few days if only I had an interface for setting up battles programmatically and without graphics (for performance reasons, since tens or hundreds of thousands of battles would probably be needed for any kind of interesting problem space)…
for small maps you could do it pretty quickly, but once you get over ~40k credits it takes a while, yeah. If Cliff makes battles deterministic OR gives us the option to not have to watch it, or better yet run it at like x100 speed…
Well, I think it would have to be on the order of max 10 seconds per game and entirely automated, that would give ~172k rounds over the course of 2 days which ought to be enough to come up with a sufficiently settled set of parameters, or long enough to know you’re not going to get anywhere and need to tweak your genetic algorithm settings… It could be hypothetically run in parallel in virtual machines though, the automation is really the key though… I guess it wouldn’t be impossible to make some sort of macro-like mouse controlling script that logs into the game, loads up a battle, loads the currently-to-be-tested deployment, runs the game, and records the outcome, but it might be a little more hackish and cumbersome than I’m willing to endure :\ And doing it by hand would of course be impossible to get enough battles in without losing your mind first, lol.
Yeah, I’m in total awe right now. My programming knowledge is limited to turing. How would this be integrated with the main game, as a mod? or will you contact Cilff to have him release it as a patch? If that is, that this is something that could go into a patch.
Falnar, if you got a v0.1 up on the site, even with the longer battles, i think that could be well worth it. (I’m going to be away for two weeks, so giving it a week w/ the automation to click though the menu’s and watch every fight? that’s an option for me ^^)
It would be infinitely better if I could get a CLI patch from Cliff where I could interact with the executable with something like the following:
GSB.exe --no-video --player1=my_current_deployment_name --player2=name_of_deployment_to_test_against --stats=winner,points,duration (just making these up)
=> {‘winner’: ‘player1’, ‘points’: ‘5000-3002’, ‘duration’: ‘3000 seconds’} (duration in this case would be how long it -would- have taken if run in real time, duration isn’t necessary or anything, just giving an example of useful stats)
I’m not sure I’d have time to figure out mouse control automation, if someone wanted to help with that part of it or had suggestions though…
Well, from what I’ve read it seems like indeed, there is no “perfect deployment” against all other deployments, however… That doesn’t mean there can’t be a perfect deployment against some specific opponent deployment. I’m quite confident I’d be able to write a GA that could (at least partially) optimize a deployment against another deployment if I had a CLI.
As a teaser, here’s an article on someone using a GA to find highly optimized Starcraft II build orders for specific goals (in this example, getting 7 roaches out ASAP) using a build time simulator (which stands in as a similarly behaving programmatically accessible copy of starcraft 2, as far as build orders are concerned): lbrandy.com/blog/2010/11/using-g … ld-orders/
A friend linked me to that like 30 minutes ago xD
Um… I’m not quite sure how i’d go about implimenting the mouse interface. Maybe with Automater on OS X?
Yeah, definitely an option, but one step at a time, I’d probably just start with optimally positioning the fleet against a given fleet as a proof of concept and as something it could probably quickly settle on.
I’d actually go with orders and position (by orders i mean targeting priorities and engagement ranges, as well as who you’re escorting/formationed too)
And if you wrote it so that it had even the most basic UI (ie, i click a button on it that says “learn from this set of stuff” then click the “fight” button) i can probably get Automator to work it
I’d be more interested in seeing the actual algorythm for GSB atm
Well, unfortunately it’s not quite as simple as “learn from this set of stuff”, it would be most effective if one aspect of the game was focused on at first… Like a generally agreed to be flexible and effective positioning and set of ships with loadouts predetermined, and then the GA designed to tweak some subset of their orders. It could then potentially find an -extremely- effective and fine tuned set of orders for that already pretty good deployment. The key is to be creative in how you narrow the problem space while still leaving it flexible enough for it to have room to find an exceptional solution. Think of it like looking for gold, you pinpoint a spot on the map that you think is a promising place to start looking, make it small enough so that your judgement of it as a “good spot” still has meaning (saying a continent is a good place to look for gold probably isn’t very useful), but large enough so that it probably does contain some good nuggets. Also, the narrower the problem space, the more aggressive you can be with your algorithm without introducing too much randomness. And problem spaces with gradually sloping areas of value are much better than ones with sharp unrelated hot spots, since it can’t tell it’s getting “warmer” otherwise.
Plus, I don’t think it would be worth it if the best option is an osx only solution… Probably the best would be a windows solution that could be easily run in virtual machines/on any hardware/in WINE without windows at all… It seems like you could get battle duration down to a few seconds in 4x speed if you used the right types of ships, which would be on the order of 30k or less battles a day… Not great, but possibly could work for a really narrow problem space. I’ll start brainstorming over the next few days of what might be a good problem space…
The problem is, there are three things to optimize. Modules (both placement and kind), orders and placement.
If you set any one or two of those and work on the third, you’ll have to rotate. Which will de-optimize one or both of the things you had constent, then de-optimize your formerly optimized sets! I think the best option would be to just generalize the “best long range” or “best tank” ships, as those are two roles that are reletivly similar in both unit placement and builds across maps. I’d be intersted in testing this for you if you had a working prototype, even if each round took 30 minutes to run. I’m using OS X at the moment, but will be getting a Windows laptop this coming weekend or during the week after it.
It’s mathematically, a huge probklem. I started coding stuff early in the game to mutate ship designs and derive better ones, but it was hell. The problem is, you can change the effectiveness of a single design by just swapping two weapons modules between 2 slots. Given the variety of ships, varierty of positions, orders (and the order sliders) the order-combinations and the variety of the modules themselves, it becomes too vast to really get a grip on.
What you could do, is take a fleet that is doing badly, and let a genetic system optimise it better, but there will always be a far far better solution that is just vastly different because it is based upon a totally different starting point.
It’s fascinating stuff to code though
he does allude to it in this post after all… viewtopic.php?f=19&t=5275&hilit=automatic&start=15#p35093 although the point wouldn’t be to rack up wins against human picked fleets (as if there’s anything to gain from that except a number anyways), but rather to pit it vs other programmed fleets or to just experiment with different algorithms.