The Ur-Quan Masters Discussion Forum

The AI code is an awful, awful mess. It manages to describe a decent AI, as AIs go, but with this base, it would be far less worthwhile to build on the current code than to start over completely froms scratch.

Currently, much of the code is generalized in a way that only really works for about half the ships in the game. It also only works against about half the ships in the game, as it's terrible against Orz, Chmmr, Utwig, Thraddash, Mycon, Syreen, Spathi, and Androsynth. (Yeah, there's others, but those are the ones that can mainly destroy the AI with complete impunity.)

So, where to begin? Clearly there's _some_ things that generalize across more than one ship (how to maneuver for a gravity whip, for instance) so it'd make sense to have a lot of utility functions that all the AIs draw on - but unlike the current system, to have them only for specific uses, desigining the main intelligence completely on a per-ship basis.

There are also some things that there seems to be no sane way for the AI code to find out - like the size of the ship it's flying. Maybe it'd be better to rework much of the current non-AI code before even starting to try to write an AI.

(There's also the possibility of writing a learning AI and running it for a while for each individual ship, but that approach has all its own issues...)

The more I think about it, the more I realize how huge a project this is. I did write an AI for tw-light, but that was mainly a wimpy AI to try to replace the even wimpier AI that was already in place. And IIRC, tw-light has better code than UQM anyway.

Hypothetically, who here both has programming skills and would be willing to help a new AI project if it got off the ground?

I've been considering doing myself essentially what you've proposed (I think I have enough AI experience to get it done), but there's quite a lot of work there for one man. Although it's unclear where I'm supposed to get the time from, I do have an interest in participating.

I've got no experience in coding, but I do know that there are 25*25=625 different match-ups (A vs B and B vs A being taken into account separately) to code if you go this way. Assuming that you do one per day, you'll need two years to finish! Two per day, and still you have to work for an entire year.
I presume you want to do scripts for more than one match-up, right? For example, no matter what ship you have, you MUST avoid crashing into a Thraddash afterburner flame!
I repeat, I am not a programmer...

PART I: if we were to do a learning AI.


We could set up a Boinc project...
;)

More seriously, we could have it be of a form where it reports the results of battles, then makes learning decisions.

Start off with a quick seris of, say, 25 one-on-one matches for each pair, at first against the Awesome AI, then against itself. That wouldn't take too long if we let it go on turbo.

Then send out that AI to volunteers. I don't think we'd have trouble gathering those. Each plays the AI and sends in the AI reports. Those are gathered and the resulting modified AI sent out for future waves.

The problem, of course, is what sort of learning algorithm would we use? Genetic algorithms on logic flows? Neural net weighting of actions using Newton's method to maximize results?

I would favor the former, but it would probably take longer to converge. You'd need a virtual machine, and of course there's the overhead for running the genetic algorithm. But it's always fun to see two computer programs 'getting it on', as it were. Funky stuff happens.

PART II:

I get C-like languages, but my only AI experience is when I scoured the SC2 AI to root out bizarre behavior bugs that became most obvious in AI vs AI matches. Also, not too much time.

Hey,

For a long time now I've been working on evolving AIs for games.  I am looking for a way now to plug my stuff into UQM.
I've got the source but its a little overwhelming since I don't have much C experience, all of my stuff is in Java.  After reading a lot about JNI and NLink I'm pretty sure I know how to call C from Java and vice versa, however I can't seem to find where I'm supposed to plug it in.
Are there any central APIs for selecting the next ship, and for controlling the ship and reading the environment?
I am willing to dig into the C code to do this because watching supermelee evolution would be very interesting.


Cheers,
Alex Ostrovsky.

instead of being a graphic geek, I wish I was a C++ geek ! or better yet a c++ graphic designer geek [!]

I know I probably should not dignify this thread with a responce, but here we go.

I recomend against this for the following reasons: (1)your initial post is asking for help, (2) the scope of the problem is too big any way you slice it, and (3) this discussion may be appropiate for TimeWarp, I don't forsee the UQM community as a whole thanking you for making the sylandro more difficult to beat.

Academicly it's an interesting discussion, you know, "what would it take to make a good AI in this game?" but practacally I think anyones time would be better served on other activities like making waffles from scratch.

Mmmmm, waffles.

I'm told that good AI is the hardest thing in gaming to code. That said, the best place to start would be to give the AI some sort of script that recognizes Thraddash afterburner jets as extremely dangerous.

You could apply similar logic against the Spathi, except I wouldn't want the story game Ur-Quan and Kohr-Ah to be able to mop the floor with Fwiffo. Newbies need to be able enjoy UQM too.

I think reviewing the AI is a great idea. It doesn't have to be part of UQM, it could be its own "mod" for those that want to be able to play on their own (for example, on a laptop while taking a bus from home to university) but what a bit more of a challange.

Good luck defeating the 4 Ur-Quan and 4 Kohr-Ah leading up to the Sa-Matra, too... ;)

(Yeah, I'd leave the "awesome" AI or whatever in the main game ^_^)

Regarding...
I recomend against this for the following reasons: (1)your initial post is asking for help, (2) the scope of the problem is too big any way you slice it, and (3) this discussion may be appropiate for TimeWarp.

All very good points, but luckily summer is here and I have no more school, so i'll be trying some code hacking to get this working.  I'll obviously open source all my stuff, i think UQM could be the ultimate AI testbed.


@Shiver
Totally agreed, it would also be cool if it learned its own scripts to see what it comes up with.  We'll have to see this coming summer if i get this working.

@countchocula86
Yes for sure it should be an external "mod".  I was thinking maybe making it a netplay client that controlled a ship as if over TCP, this way the C code is not touched at all.


Cheers all! Thanks for the great replays,
Alex Ostrovsky.

I must have missed that post. Actually, those points are not good at all:
It is not.
Improving the AI would be a daunting task, yes, but not that infeasible.
...with the small problem that TimeWarp melee isn't much like that of UQM, so there's no sense comparing them.

I am personally very interested in AI that learns, but connecting your code to UQM is going to be tough, because the UQM code is not very clean.
I suggest you log in on the IRC channel #sc2 on irc.freenode.org sometime; I can give you some pointers interactively then.

Incidentally, I rewrote a bit of the AI code the other day, and thereby made the AI quite a bit more sensible about when to shoot. Also, I was able to make the AI Utwig a _lot_ harder to fake out (and probably better at shielding, at the same time.)

Oooooh thats awesome EP!

Yeah, keep up the good work. Don't mind the people requesting Kzorz-Za Nemeses on the Cafe - don't mind me either requesting them, which I surely will. In fact, don't even POST anymore ideas like that one. AI is a better project.

Honestly?

If you guys are serious about improving the AI in the game, then you need to make it easier for people to do the work.

What you need is a single mod that you don't need grand C++ experience in order to get in there and adjust. And the best way I can think of to do that is to invoke a scripting language. My recommendation would be Lua (http://www.lua.org).

The idea would be that the code would call a Lua script for each frame, and the Lua script would be able to ask questions (where is the ship, are there any space objects in this region of space, how fast am I going, etc) of the game and give their own ship commands (turn, fire, etc). The way I'd design it is such that there could be a single Lua script for every matchup, but if a script for a particular matchup isn't found, then the game goes to the standard ship script, and if that isn't found, it goes to a generic one that can work for all ships (but shouldn't work very well).

Lua as a language is a lot more fogiving than C++, and because it's executed at runtime, you can even change scripts in the middle of battle without needing to recompile them. This makes it much faster in terms of development of a good AI, since you don't have to stop the program, make your change, recompile, run, start Super Melee, select the fleets, and start the battle. The biggest difficulty is going to be creating a good script interface. That is, exposing appropriate script functions so that it can ask useful questions (is there a space object that will hit me if I keep going, can I dodge it in time to avoid the damage, etc). Once you work out a decent list of questions (and the best way to do it is to get a bare-bones script working, and then try to make a good AI. When you start needing to test things that there is no API function for, write one), you're pretty much ready to go.

Really you don't need all 625 different pairs in the end. Ship-based generic ones can handle a lot of the variation, but there are going to be certain encounters for certain ships that will require a hand-tuned approach.

I'm not sure how much work it would be to sensibly integrate a scripting language... I suspect it would be a lot, given the game's current code.

I'm just a modder on this game, a coder of petty features. (and for a reason.)

Excellent, I'll need all the help I can get.  I'm gonna be familiarizing myself with the UQM code for the next couple weeks, I'm quite excited as I've never worked on a game, or on an open source project before.

How I'm planning to make this work...
1) clean up the UQM AI code
2) interface with with my Java reinforcement learning code
3) watch crazy AI battles unfold.

About my AI code...
1) Genetic programming based
2) Decomposes environment into useful sub-cases and solves each one separately (this gets around the 25*25 problem, coz we can just run random matchups and it will pick up on the cross-ship patterns itself).
3) Has many adjustable parameters such as reaction time.
4) Makes heavy use of multi-threading.

Are your genetic algorithms going to include 'sexual selection', i.e. nontrivial means of choosing pairs for crossbreeding?

Yep, currently my model supports micro mutation, macro mutation, sexual recombination.  For choosing pairs for cross breading I use tournament selection with tournament size = 4.   This means that four individuals are randomly selected and compared by fitness, then the fitter two replace the two losers.  We will easily be able to pit different selection strategies against each other.
I am currently cleaning up my code, I'll put it up on google code or something when its good to go (currently I'm testing it on a tron-style game).

Though that's good, it's not what I meant.

I meant, do you have these AI's have any features not related to their performance which determine which AI's mate? Sexual selection can be useful to help 'valley-crossers' get where they're going, and can eventually bring about speciation.

Just a thought.

Does.......does that mean the ships are gonna get it on?

No, the AI's which fly the ships.

Yep there are many things that determine which AIs mate.  I use a cluster analysis algorithm to find useful patterns in the environment and then evolve independent niche species for each case.  With UQM, one niche might be "running away", and another might be "bogged down by green blobs".  A good read on this is http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/rosca_thesis.html

That's good, and even better, but it's still not what I meant: you're still basing it off of survival advantage (combat performance).

Real organisms have additional selection criteria. Like, are pretty girls more capable of surviving? No; but they are more likely to reproduce. In the same vein, you are unlikely to attempt to mate with a chimpanzee, no matter how attractive that chimpanzee is to other chimps.

In other words, it may be useful to keep some clusters together by factors other than environmental selection.

I don't see how that would benefit the evolution algorithm. In nature, these things seem to be side effects.
The concept of attractiveness seems to have evolved as an indicator of health and other properties which would make an individual more succesful. Once that mechanism of recognising attractiveness is in place, additional aspects which trigger the "attractiveness" mechanism but aren't beneficial to the survival chance of offspring will be selected.

In this artificial evolution, you can base the selection on the actual success.


Note that I do know that this is how the evolution of attractiveness actually worked, but it does seem to fit with what I would expect from evolution.

They are beneficial, in that your AI's may 'speciate' and form populations which do not mix anymore because they are too different in internal structure.

Also, they may learn not to mate with AI's that are just like themselves (incest taboo).

What's the use of speciation when there are no "niches" to fill?

Overall strategies. If one is trying to dance at the edge of range and the other is trying to slingshot to get on the enemy's 6, crossing them would kill both. There would be certain ways of combining them to make it stronger (make them sort of sub-behaviors within a larger AI), but it wouldn't be the same old mix and mate.

This would give alternate strategies time to grow into their own before being brought back into any hegemonic structure that may emerge... that is at a local optimum.

First I'd like to start by saying that I am by no means an expert on evolution, so take everything I say with a massive brick of salt.

Regarding...
Real organisms have no selection criteria whatsoever, it is their genes that have selection criteria.  Otherwise homosexuality would not be so prevalent in most all species.   Richard Dawkins' "The Selfish Gene" is a good read on this.
All genes undergo the same selection criteria, namely their success at replicating.    So genes that build prettier girls are going to outcompete those that build uglier ones.  And of course --as meep-eep mentioned-- the genes that produce a sense of aesthetics (which discerns "pretty" from "ugly") are also naturally selected.  But I digress.

Regarding...
They are beneficial, in that your AI's may 'speciate' and form populations which do not mix anymore because they are too different in internal structure.

Yep,  my system has that feature.  Read the link I provided in an earlier message for how the species are determined.


Regarding...
Also, they may learn not to mate with AI's that are just like themselves (incest taboo).

Very good suggestion.  It would be interesting to see if the cost of calculating relatedness for the purposes of incest prevention is worth the CPU resources.  Maybe it is better to have the occasional incest if it is much faster to compute.


Thanks for all the great feedback!!

While what you say is true, I think this distinction is irrelevant in this case. The genes are expressed in individuals.

Good, on the speciation front.