for the upcoming basic bots
Laosh'Ra
Join Date: 2011-12-09 Member: 137232Members
Join Date: 2011-12-09 Member: 137232Members
<div class="IPBDescription">consider involving machine learning</div>twitter on the homepage says:
<!--quoteo--><div class='quotetop'>QUOTE </div><div class='quotemain'><!--quotec-->Are there any @NS2 community members interested in working with us to create an official shipping bot ? charlie@unknownworlds.com #fb<!--QuoteEnd--></div><!--QuoteEEnd-->
<!--quoteo--><div class='quotetop'>QUOTE </div><div class='quotemain'><!--quotec-->Oh, and by "bot", I mean: one that can play every role (including every alien and both commanders), in an extremely basic way (1st game)<!--QuoteEnd--></div><!--QuoteEEnd-->
i myself have neither the time nor enough experience to help out with this, but i stilll want to present you a concept which might come in handy somewhere:
the idea of machine learning is that you train a function which will give decisions for new, yet unknown input.
<b>the process usually goes as follows: </b>
1. you create example data (one array per example, the arrays need to have the same dimension) where you (as a human) know wether it should lead to decision A or decision B (you can also introduce more than just 2 categories)
2. you train a fancy algorithm with that data (several exist, i point out some of them below)
3. when fed with new data (while the game is running), the trained algorithm will give you results similar to the example data (the result can be binary or a tradeof)
please note that steps 1 and 2 are usually done offline as they can take quite some time. evaluating the new data (step 3) is usually a lot faster.
as a side note, you can predict wether your algorithm will actually perform nicely or not. this is usually done with cross-validation:
you take 90% of your example data for training and then test it on the last 10% without telling the algorithm the correct decisions it should make on those 10%. this step is done 10 times whereas the 10% are shifted every time.
<b>does this actually work well?</b>
yes it does. but you have to choose descriminative data (data which actually represents the facts the decision should be based on).
as example for a commander-bot, this data could involve the tech-situation, ressources, the amounts and positions of buildings and marines/kharaa.
<b>example</b>
i myself use this technique for object detection/recognition. an example for this is a guitar-hero-bot we built (quite useless but goddamn cool):
<a href="http://www.youtube.com/watch?v=2Rhm1ihoGpg" target="_blank">guitar hero bot</a>
a webcam films the screen and a previously trained classifier decides what kind of objects are seen in each frame. the servos move accordingly. our record was actually 99% hits (easy mode though). most common source of error were the special effects.
<b>so how could this actually be applied to bots?</b>
a simple approach is to put decision A as "this is how you should behave" or "ultimately, the bot won the game" and decision B as "this is how you should not behave" or "ultimately, the bot lost the game". making it based on winning/losing seems a bit too general but could still be used for commanders to evolve good global strategies.
a simple example: with a current game situation X given, training-experience has shown that researching shotguns is more likely give the best benefits than saving for advanced armory.
using it on a smaller scale: for specific tasks, this could help to optimise those tasks.
a simple example: with a current game situation X given, training-experience has shown that waiting for the nearby teammate is more likely to save the attacked ressource tower than attacking alone right away.
essentially, the machine learning could take place whenever decisions would otherwise be based on random or heuristics.
<b>is it worth the effort to be implemented for bots?</b>
if you want good bots, i think it is. since you want only basic bots so far, i'm actually not sure. either way this could still be implemented on top of an already implemented bot-system later on.
please note: you can simply use already implemented open source algorithms and basically all you have to do is feed it with data which should result in decision A and data which should result in decision B, no need to worry about the actual details going on. the quality will mostly depend on the data you feed the algorithm with.
<b>example algorithms for machine learning:</b>
naive bayes (runs fast, easy to implement, returns scores which is useful for tradeoffs)
random forest (runs very fast (we used this method for the example i've shown you above, it took 4 ms to evaluate all 25000 trees for a frame), allows you to detect the most contributing variables of the data)
support vector machine (very popular method, can take its time to evaluate though)
neural network (have never used this yet myself, but it seems the most similar to a human brain)
boosting (have never used this yet myself, but it seems to evaluate quite fast)
<!--quoteo--><div class='quotetop'>QUOTE </div><div class='quotemain'><!--quotec-->Are there any @NS2 community members interested in working with us to create an official shipping bot ? charlie@unknownworlds.com #fb<!--QuoteEnd--></div><!--QuoteEEnd-->
<!--quoteo--><div class='quotetop'>QUOTE </div><div class='quotemain'><!--quotec-->Oh, and by "bot", I mean: one that can play every role (including every alien and both commanders), in an extremely basic way (1st game)<!--QuoteEnd--></div><!--QuoteEEnd-->
i myself have neither the time nor enough experience to help out with this, but i stilll want to present you a concept which might come in handy somewhere:
the idea of machine learning is that you train a function which will give decisions for new, yet unknown input.
<b>the process usually goes as follows: </b>
1. you create example data (one array per example, the arrays need to have the same dimension) where you (as a human) know wether it should lead to decision A or decision B (you can also introduce more than just 2 categories)
2. you train a fancy algorithm with that data (several exist, i point out some of them below)
3. when fed with new data (while the game is running), the trained algorithm will give you results similar to the example data (the result can be binary or a tradeof)
please note that steps 1 and 2 are usually done offline as they can take quite some time. evaluating the new data (step 3) is usually a lot faster.
as a side note, you can predict wether your algorithm will actually perform nicely or not. this is usually done with cross-validation:
you take 90% of your example data for training and then test it on the last 10% without telling the algorithm the correct decisions it should make on those 10%. this step is done 10 times whereas the 10% are shifted every time.
<b>does this actually work well?</b>
yes it does. but you have to choose descriminative data (data which actually represents the facts the decision should be based on).
as example for a commander-bot, this data could involve the tech-situation, ressources, the amounts and positions of buildings and marines/kharaa.
<b>example</b>
i myself use this technique for object detection/recognition. an example for this is a guitar-hero-bot we built (quite useless but goddamn cool):
<a href="http://www.youtube.com/watch?v=2Rhm1ihoGpg" target="_blank">guitar hero bot</a>
a webcam films the screen and a previously trained classifier decides what kind of objects are seen in each frame. the servos move accordingly. our record was actually 99% hits (easy mode though). most common source of error were the special effects.
<b>so how could this actually be applied to bots?</b>
a simple approach is to put decision A as "this is how you should behave" or "ultimately, the bot won the game" and decision B as "this is how you should not behave" or "ultimately, the bot lost the game". making it based on winning/losing seems a bit too general but could still be used for commanders to evolve good global strategies.
a simple example: with a current game situation X given, training-experience has shown that researching shotguns is more likely give the best benefits than saving for advanced armory.
using it on a smaller scale: for specific tasks, this could help to optimise those tasks.
a simple example: with a current game situation X given, training-experience has shown that waiting for the nearby teammate is more likely to save the attacked ressource tower than attacking alone right away.
essentially, the machine learning could take place whenever decisions would otherwise be based on random or heuristics.
<b>is it worth the effort to be implemented for bots?</b>
if you want good bots, i think it is. since you want only basic bots so far, i'm actually not sure. either way this could still be implemented on top of an already implemented bot-system later on.
please note: you can simply use already implemented open source algorithms and basically all you have to do is feed it with data which should result in decision A and data which should result in decision B, no need to worry about the actual details going on. the quality will mostly depend on the data you feed the algorithm with.
<b>example algorithms for machine learning:</b>
naive bayes (runs fast, easy to implement, returns scores which is useful for tradeoffs)
random forest (runs very fast (we used this method for the example i've shown you above, it took 4 ms to evaluate all 25000 trees for a frame), allows you to detect the most contributing variables of the data)
support vector machine (very popular method, can take its time to evaluate though)
neural network (have never used this yet myself, but it seems the most similar to a human brain)
boosting (have never used this yet myself, but it seems to evaluate quite fast)
Comments
but it can work real-time as you can see in the example i've shown (here, training took ~15 minutes): it processes 5 subimages (400 dimensions each) in merely 4 milliseconds. of course one could also chose to use less than 25000 trees for this.
what one usually does to reduce the data is clustering in order to compute a "bag of words". this method is used for .gif images for example: you reduce the palette to a desired number of colors, those colors are picked to represent the image as good as possible.
in this case, map-locations could be clustered.
other methods to reduce the dimension of the input data, are PCA and LDA but this is really going into too much detail now.
i figure my posts are getting way too abstract by now, here's a picture to <b>sum up the basic concept</b>:
<a href="http://imageshack.us/photo/my-images/687/21028086.jpg/" target="_blank"><img src="http://img687.imageshack.us/img687/9382/21028086.jpg" border="0" class="linked-image" /></a>
the images with white backround represent the example data. for NS2: instead of image-pixels, it's a bunch of useful variables given by the game situation. the same variables are used for every example, the amount of used variables is called d here.
in this example, the human decides wether the images are suns or moons (in case of NS2, this can be win and loss, or anything else to represent the consequences of a decision).
you do this by setting y_1 to either 1 or -1 for the image x_1, same goes for x_2 and y_2 and so forth.
the classifier algorithm will learn whats characteristic for those two categories, and will then be able to tell for the new image (the blue sun) wether it is rather a sun or rather a moon, based on the trained experience.
<!--quoteo--><div class='quotetop'>QUOTE </div><div class='quotemain'><!--quotec-->I will now train a bot to detect 13 years old (mentally, not necessarily physically) trolls.<!--QuoteEnd--></div><!--QuoteEEnd-->
i agree his post was quite redundant. fun fact: spam filters are usually done with machine learning as well...
All you would have to do is program in a lot of tracked variables, and then tell the game what counts as 'good' for each variable.
So a 'good' sentry would be one that gets lots of kills, a 'good' tech point is one that stays captured for longest, a 'good' resource extractor is one that gets the most income, that sort of thing, and then tell the game to pick 'good' options. You can also try global results such as any option that happens before the game is won gets a certain amount of good points added to it.
For sentries you could just tell the game to track how many kills every sentry gets, pick the top five, then place them every game. Obviously it is somewhat dictated by the overall strategic state of the game, but to an extent an important choke point is still an important choke point and it is also still statistically probable that the sentry will be effective, so it is the absolute best way to guarantee effective sentry placement without programming in an actual understanding of sentries.
Every one of those variables you program in will increase the bot's effectiveness, the bot doesn't have to simulate a human's behaviour, it just has to win games.
With that said, though, a bot that could map out a tree of potential builds/strategies in the game and track their utility would be *very* cool in an RTS setting, and it would be neat to see how trustworthy might become of having such a bot lead the battle. Now there's an interesting thought.
as for taking the sentry guns which give you the most kills, sure that is an approach that might work. but the effectiveness of a sentry will not only depend on the location you place it, it will depend on a lot of other factors as well.
as i pointed out before, i am not sure wether this approach is worth implementing or not, i just wanted to bring up the possibilty. <b>it's not a must have!</b> wether they make use of it now or later or never is up to them. it also depends on the kind of bots they want to have.
to be honest, i personally dont like bots at all. but if we're going to have them in the long run, also as commanders, i'd prefer them to be decently good, even if that requires some effort.
I imagine Max could do it, but his time is better spent elsewhere. A basic bot, will be a static one. Which is why Flayra is asking the community for help, which I think means "can someone do it for us?" or "can you help give us a starting point, and/or what are the things/process the bot will use?".
So if I wanted to help, and I didn't really know anything about programming, and especially AI, I'd just try and imagine how conceptually the bot will work. The basic conditions, the specific ones, the special situations, and how the bot may be able to transition between them all. Stuff like that.
I sat down and had a think about it while at work.
Just the navigation turns out to be problematic.
If you go with a waypointed system, then that would work ok for marines, you could use the pathing that's used for Macs/drifters.
However for aliens it would be different, you will have trouble getting them to use walls/ceilings.
Then how do you get gorges to place buildings in appropriate locations?
The lerk/skulk/fades have very different combat styles and will be difficult to program in a convincing manner.
But I found the biggest problems would be with the commanders.
You could hard code a set of strategies that could be random, or procedural.
But how do you get commanders to respond to a change in strategy?
Placement of sentries, forward armories, phase gates etc?
The concepts of your typical RTS AI player spring to mind. But I wouldn't know where to begin.
I fear that the behaviour would be quite rigid if going with a waypointed system.
If a custom waypointed system is required then it is prone to problems caused by map changes and new waypoints would need to be created for new maps.
A totally organic system would be a nightmare to develop. But the last thing you want is a predictable AI player.
Why state that?
<!--quoteo(post=1890836:date=Dec 19 2011, 04:30 PM:name=WombatLOL)--><div class='quotetop'>QUOTE (WombatLOL @ Dec 19 2011, 04:30 PM) <a href="index.php?act=findpost&pid=1890836"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->Hinting he should make one for a Wombat to be able to sit down and read for less then 30 seconds.. Kthx<!--QuoteEnd--></div><!--QuoteEEnd-->
If that's what you wanted, then antagonising the person isn't going to work (I'm speaking from experience, here), but asking them nicely and in certain terms might (theoretically, anyway).
I didn't see where the irony in your post was, but if we're talking about irony, then that describes my post, in at least two ways:
- I'm antagonistic and rarely nice.
- Because it was too long, I actually didn't read the OP fully either.
On-topic:
Interesting thread. Has anyone started doing anything bot/AI-related for NS2?
Interesting thread. Has anyone started doing anything bot/AI-related for NS2?<!--QuoteEnd--></div><!--QuoteEEnd-->
AI ? no ... just basics like RTS units with move, follow the target, build or place cysts... to be able build on them hierarchical bottom-> top classic AI.
I think something so sophisticated as neural network, it's not possible without basic building blocks, and will take little longer to be able reach this milestone :)
ZycaR
I think something so sophisticated as neural network, it's not possible without basic building blocks, and will take little longer to be able reach this milestone :)
ZycaR<!--QuoteEnd--></div><!--QuoteEEnd-->
Main thing I'm hoping to see in the future is mainly bots for commander for offline practice.
Hopefully you're working on that ZycaR :3