Ideas for a masters research paper on SpringRTS AIs?

[hughperkins]

Hi,

You may remember for the various projects I've made that nobody uses C# AI interface, C# AI, MapDesigner, a Java AI (HughAI), and SpringGrid / SpringAIGrid.

I finally got around to signing up for a research masters, and I just started my first year, and it's really fun.

I have to select a topic for my thesis project, by May this year, something to do with machine learning.

Given I've spent so much time doing Spring AI related work in the past, I'm thinking it could be fun to do something spring-related for my masters thesis.

On the other hand:
- I don't know what the current cutting edge in this area is
- I need to be able to convince my supervisor
- ideally I'd like to be able to publish a paper about it

What topics might be possible that might make good research paper material at the moment, and that might involve springrts ais?

[AF]

You may remember for the various projects I've made that nobody uses C# AI interface, C# AI, MapDesigner, a Java AI (HughAI), and SpringGrid / SpringAIGrid.

New AI interface obsoleted most of those and they're no longer maintained, and SpringAIGrid showed promise but never did what it said on the tin!

Anyways we have our nice new Java OO API for AIs, and a C based API for ABI compatibility.

I would suggest pathfinding? There's also the matter of lua game rules and potentially figuring out how to use different capabilities automatically, e.g. tell the AI there is something called jumpjets in ZK, and the kind of parameters it expects, and let the AI decide the mechanics of when it should be used, how, how using it relates to the cooldowns etc

Also so far nobody has investigated AI human cooperation, and most RTS seem to be happy to just have a 'ping' to indicate attention is wanted here or there, maybe an attack here now order, all very primitive.

I assume what new work will either be in C++ or Java?

[hughperkins]

I assume what new work will either be in C++ or Java?

Fair assumption

I would suggest pathfinding?

Pathfinding would be interesting. It looks like there is already a fair bit of research in this area? http://springrts.com/phpbb/viewtopic.php?f=15&t=2752

[Zyre]

I strongly suggest to you: make something more smart, not a finite state machine, something like a learning AI that change it's decisions itself in-game not after, like "this was no good then i will change to this" the main problem is to define what is "the problem" to be solved by a learning algorithm and what really is a good and bad result.

[hughperkins]

I strongly suggest to you: make something more smart, not a finite state machine, something like a learning AI that change it's decisions itself in-game not after

Yes, I agree, there should be a learning algorithm.

Whether that algorithm kicks in during the game or between games is an open question.

Personally, I always found playing against a computer that changed according to what I did between games a bit annoying. Half the point of playing against a computer opponent, as a human, is that the computer is very repeatable, so you can see yourself improve. If the computer improves at least as fast as you, then you will never be able to beat it more often, no matter how many times you play!

Which would support an in-game learning algorithm. But in-game learning is very hard: there is insufficient information, and not much time to use it. On the one hand, for a human player to learn to play takes many hours - maybe hundreds of hours - of play, and on the other hand, running things like a support vector machine needs a fair wodge of cpu.

The other question is, is it really worth using springrts for doing research, or is it better to pick some very small well-defined problem, and solve that? springrts is so very complicated that lots of effort might go into doing all sorts of stuff that might not really change the final conclusion of the corresponding paper, but which would take lots of time to implement and deal with.

[hughperkins]

(If I remember rightly, the last time I was doing AIs, I was basically heading in the direction of making the ais play against each other repeatedly, and using that as the basis of a learning algorithm. Hence springgrid et al.)

[hoijui]

wow.. nice to see you again here!
welcome!
also nice you got away form that other.. ugly thing you did, and do something nice now. :D

of course it would be easier to use some small, well defined thing and code for that. if you want to see it used in practice though, spring is a good way to go.
it being used in practice also has advantages in the pure research sense, as it allows for you to also test performance against real humans.

if you decide to use spring, use Java again
it is much faster now, with the pureint changes in the release, plus it is the most advanced and best maintained interface.
worst decision ever would be "i go for C++ because of speed".

and yeah... your AI grid stuff would be great for getting together training data, also the only realistic way to go, and i guess it would not take too much work to get it running again.

you forgot to mention your most successful contribution to spring though, which is of course spring-headless!
it is an integral part now, built for every commit by the buildbot, maintained by all the devs, and used for validation tests, running AI vs AI battles after each change to the source, automatically.

[PicassoCT]

you could do a team up with a neuro-scientist, he tells you how to exploit human behaviour patterns, and you write the learning ai that actually exploits them, training humans up.

For example, if you use a strategy successfully (even if it was just one big lightshow) the weaker players will try to copycat that, and run into any countermeasures your ai prepared.

Or you could make a AI that actually balances games, but not for a even-ness of powers...

Or you make a hydra, two or more AIs playing for one team, and the AI Head most succesfull is slowly overwritting the AI_strategy of the competeting heads, until there is a monoculture, and madness is allowed into the responses to the events to evolve into even more crazyness.

Or you make a distributed AI System that is connected over the "cloud" (fency buzzwords always catch them) and distributes its knowledge to battles on similar maps against diffrent players, even copying players succesfull moves (like comando Operations).

You can write a tactics equivalent to_gameOfLife, that creates new patterns, storing the succesfull ones, until your AI is a freaking Napoleon, winning by sheer brilliance alone against vastly superior numbers.

Or you write a learning mutliple Game AI that adapts to no_matter_what Game(Spring, Starcraft) its trhown in and masters it.

You started it, you wanted to know.. its not my job to evaluate those options for master_thesis qualities.

PS: You are welcome to write the GAIA LUAAI for journeywars Zombies. But im afraid a threeliner: Spring.Echo("Brains")
Spot.Enemy (walk in the direction)
GetStuck(Create Bump_Kin) Walk along the borders of Bumpkin, until you can walk into last_seen_enemy_direction again

wont be good enough for a master_thesis

[hoijui]

ouh btw.. you should never worry about an AI playing too good.
we have enough AIs that do not improve, and believe me.. the potential user-base for an ever improving AI is MUCH larger then for a so-so playing, static AI.
with improve i mean, in game style of course, not just by cheating in more resources or using LOS hack or the like.

it is also very easy to let the user artificially trim down a good AI.

[hughperkins]

you forgot to mention your most successful contribution to spring though, which is of course spring-headless!
it is an integral part now, built for every commit by the buildbot, maintained by all the devs, and used for validation tests, running AI vs AI battles after each change to the source, automatically.

Oh wow, cool! Funny how sometimes the things that took the least time are the most useful, and the things that I put months into are pretty much never used!

also nice you got away form that other.. ugly thing you did, and do something nice now. :D

haha By the way, after re-reading this, it occurred to me that this could be misinterpreted by other people, so just to be clear, what hoijui means is I was working for an investment bank for a bit.

[SpliFF]

For a thesis you should be focusing on the AI strategy and learning, not gameplay / enjoyment. Gameplay is only relevant to spring games and "enjoyment" definitely goes into the realm of psychology which is usually beyond the scope of a CS masters. If your AI beats humans every time that just means you got the "I" part of "AI" right.

I think your biggest issue will be finding an avenue of AI research that hasn't been done to death. My understanding of masters thesis requirements (learnt second-hand as I haven't actually done one) is that it's preferred for a thesis to explore new areas of research.

That's not to say there aren't original approaches available to you. You'll just have to come up with novel solutions.

BTW, are lisp and prolog still taught in AI courses? These languages have some unique features which make them ideal for many classes of AI problem solving.

[Nemo]

Hi hugh!
Evolutionary computing seems to be questionable in terms of 'machine learning', but it certainly counts as AI, and there aren't all that many papers on it. Rather, there are only a few examples of "I did this thing with EC and game AI"; there are lots of "hey, somebody should do something with EC and game AI." Direct applications to strategy game AI in various forms: one, two, three.

Genetic algorithms in particular are something I think could produce very interesting/effective and potentially unexpected approaches to a game. The downside, of course, is the time they take to run (finding a fitness function that doesn't take ages and ages), and defining the problem for the GA to solve. One thing I've always thought would be cool would be 'seeding' a GA for some part of RTS gameplay with cases culled from top-level human play (injecting human 'cases' into the population, that is).

The approach in the third paper there is basically getting an AI to figure out when to apply a set of pre-defined tactics/plans. I tried something along those lines with the Tron game last year (unsuccessfully - pretty sure the differences between outcomes from different behavior choices were often too small, and that there was insufficient information to really lock particular board setups into particular strategies).

While that is really, really cool, a fairly unexplored direction with GAs and RTS AI would be tactic generation - this makes sense, because actually generating behaviors is a much bigger problem space than just picking one given some circumstances, but it is also a problem better suited to a GA approach (imo, of course). Check out classic success stories of GAs with antennae design - GAs stumbling on effective things that human cognitive biases prevented people from coming up with.

TL;DR:
<_< genetic algos are cool, yo. only a few papers, gogo gadget spring + some GA research.

[AF]

A group already did a study using NTai task lists and a java based program to evolve a better task list over time.

[Nemo]

Would be neat to see that paper, searches are turning up empty - got a link?

[Anarchid]

Would be neat to see that paper, searches are turning up empty - got a link?

Maybe this (also googly-cachy-quick-preview here)?

Doesn't sound too similar though, that's about KBAI, not NTAI + learning.

[AF]

It may have been an end of year assignment, Sander Bachs students were involved

[Cheesecan]

Don't get too bogged down in coding for a master's thesis, grading is based on engineering approach as well as implementation.

[Beherith]

Hit me up if you need obscene amounts of computing power

[Licho]

Make AI that learns from the real players, thats certainly unique area.

ZK team has infrastructure in place to allow that (all games stored including various details, user tracking, real time autohost communication http://zero-k.info/Battles )
And if you pick C# you would get direct coding help as well.

Or make a team balancing algorithm that works better for teams than ELO.

[CarRepairer]

Hi,

You may remember...

I just remember you as the person who was offended by the use of the term BUGGEROFF in the code.

Anyhow, welcome back.

NOW BUGGER OFF!!