Home » Stars! 2.6/7 » The Academy » Player assistant "AI"
| |
Re: Player assistant "AI" |
Wed, 08 March 2006 04:17 |
|
m.a@stars | | Commander | Messages: 2765
Registered: October 2004 Location: Third star to the left | |
|
Kotk wrote on Tue, 07 March 2006 20:08 |
m.a@stars wrote on Tue, 07 March 2006 11:44 | Seriously, though, I've always wondered why Stars! (or an Stars!-like clone) is not swamped by AI researchers doing moddings and such.
|
Some of the Jeff-made AI-s in game play at newbie level, lot of games made significally later have far worse AIs. But still i doubt there is any reason to be interesting for some AI researcher.
Almost all games have "AI players" and "Non-player characters". These parts of software are far from "Artfical Inteligence".
They have no goals. Getting to goals has no choices of strategies. Strategies do not raise subgoals. Getting to subgoals have no choices of tactics. No generated decision trees, no logics, no heuristics. Vegetables not AI-s.
|
Yeah, I know. If only modern games had at least some semblance of Jeff-style AI... My current goal is not any true AI, mind, but just a set of "automaton scripts" which one day a "smart script" can use to emulate what the current Stars! "AIs" do now.
The interesting part is Stars! (or a Stars!-like clone) offers a nice simple/complex playground for anyone interested in game-AI to test his/her skills/ideas.
Once the interface hurdles are solved, anyway.
[Updated on: Wed, 08 March 2006 04:19]
So many Stars, so few Missiles!
In space no one can hear you scheme! Report message to a moderator
|
|
| | | | |
Re: Player assistant "AI" |
Wed, 08 March 2006 09:41 |
|
m.a@stars | | Commander | Messages: 2765
Registered: October 2004 Location: Third star to the left | |
|
Kotk wrote on Wed, 08 March 2006 14:49 |
m.a@stars wrote on Wed, 08 March 2006 11:17 | The interesting part is Stars! (or a Stars!-like clone) offers a nice simple/complex playground for anyone interested in game-AI to test his/her skills/ideas.
|
I have tested my simple amateur AI ideas on lot simpler playgrounds. For example i did windows minesweeper AI.
Optimized the code until it sweeped expert level below 1 seconds in debug mode (unless it hit mine) on 900MHz Athlon, and then a thief stole my computer.
|
Ouch! You didn't have a backup?
Quote: |
Quote: | Such a graph has indeed been in my mind often, when considering how most ppl do actually scout their space. Could you please tell me how you generated it? I know the general idea, but I'm too lazy/busy to research the actual algorithm/code.
|
What you mean? How i generated? Silently. Wrote in C++ (2003). Reading xy file algorithm i already had, star map display i already had. Used boost::graph template for graph (but current problem needs none of its features). Algorithm to fill graph is 10-liner that selects all pairs of two different planets, uses Pythagoras for calculating distance between them and if distance fits to conditions then add edge to graph. Most code/time went to displaying that graph on star map later.
|
I'm afraid I wouldn't know how to use any proper "graph" lib if it bit me in the I. But, from what you explain, I gather I'm only lacking the "conditions" to add the edge to the graph, plus perhaps a proper structure for storing such graph.
Quote: |
Quote: | I wonder if you have any other cool ideas for penscans?
|
For one example to think about:
1) Draw scanner radius circle around all unscouted planets.
2) measure sweetness of each spot within 81 ly radius to your scout (by how many circles overlap there). Its ~20K spots.
3) choose some sweetest spot and go there.
4) remove the circles for scouted places and back to 2)
|
Yeah, I tried that one long ago. Phase 2 turned out to be the hardest. But I think if I used some kind of graph to weed out most faraway "sweet-spots" things would improve significantly.
Or else try a completely different tack. *sigh*
...
So many Stars, so few Missiles!
In space no one can hear you scheme! Report message to a moderator
|
|
|
Re: Player assistant "AI" |
Wed, 08 March 2006 13:37 |
|
Kotk | | Commander | Messages: 1227
Registered: May 2003 | |
|
m.a@stars wrote on Wed, 08 March 2006 16:41 | Ouch! You didn't have a backup?
|
Nay, but then again ... minesweeper was too simple problem even for AI amateur like me. There are 16x30 unknowns that can be "mine"/"no mine". Gradually during playing these turn into knowns, and all known "no mine"s give knowledge about 8 unknowns around them. So profiling did show that most of the time AI was busy "looking" at the board and clicking it, there was no much to think about.
Quote: | But, from what you explain, I gather I'm only lacking the "conditions" to add the edge to the graph, plus perhaps a proper structure for storing such graph.
| Conditions i gave already? distance < 50 => cyan edge,otherwise distance < 82 => green edge, otherwise no edge.
Graph is nothing special. Directed edge is pair of integers (source vertex id, destination vertex id) so you need vector of pairs of integers to store all edges. Bidirectional edge is one edge there and one back. If you know all your graph has only bidirectional edges anyway (like on our case) then you may use only one pair for each edge. If you want attributes like colors or weights or distances add same size vector for attributes too. Like i say i used boost template but only for it makes needed storages, iterators and all such crap for me. Actually its real powers were not used.
Quote: | Yeah, I tried that one long ago. Phase 2 turned out to be the hardest. But I think if I used some kind of graph to weed out most faraway "sweet-spots" things would improve significantly.
|
Oh ... I joked about that phase 2 thing and need to calculate 20000 times. I think that pen-scanning scouting is geometry problem rather than graph problem. If you have 2 circles they overlap or they dont. Now ... if you have 3 circles that all overlap with each other then there may be (and may not be) region where all 3 overlap. Now if there was such 3- way region and there is 4th circle that has also such 3-way region with each pairs of above 3 then there also exists 4-way region. And ... so on. At some moment you have list of all possible regions. If there are no 5 way regions then there are also no 6 way regions to consider.
Then you take that BOSS 81 ly circle around your JOAT scout, for what you have to analyse these regions. If nothing overlaps with it you take 162 ly circle and so on. Also to simplify your task and have less various regions to consider ... you can limit with say 20 closest unscouted planets to your scout.
Report message to a moderator
|
|
| |
Re: Player assistant "AI" |
Thu, 09 March 2006 04:07 |
|
m.a@stars | | Commander | Messages: 2765
Registered: October 2004 Location: Third star to the left | |
|
Kotk wrote on Wed, 08 March 2006 19:37 | Nay, but then again ... minesweeper was too simple problem even for AI amateur like me. There are 16x30 unknowns that can be "mine"/"no mine". Gradually during playing these turn into knowns, and all known "no mine"s give knowledge about 8 unknowns around them. So profiling did show that most of the time AI was busy "looking" at the board and clicking it, there was no much to think about.
|
Doh. Not exactly my kind of "strategic AI" either.
Quote: | Conditions i gave already? distance < 50 => cyan edge,otherwise distance < 82 => green edge, otherwise no edge.
|
Sorry, I surely wasn't paying enough attention.
Quote: | Graph is nothing special. Directed edge is pair of integers (source vertex id, destination vertex id) so you need vector of pairs of integers to store all edges. Bidirectional edge is one edge there and one back. If you know all your graph has only bidirectional edges anyway (like on our case) then you may use only one pair for each edge. If you want attributes like colors or weights or distances add same size vector for attributes too.
|
Looks somewhat similar to what I've already done. I need to put just a bit more work into the matter, it seems.
Quote: | I joked about that phase 2 thing and need to calculate 20000 times. I think that pen-scanning scouting is geometry problem rather than graph problem. If you have 2 circles they overlap or they dont.
|
Phew. U got me allright with those 20000 times.
I agree about penscan looking more like geometry problem. Trouble is, those circle overlaps take CPU power to calculate...
Quote: | If there are no 5 way regions then there are also no 6 way regions to consider.
|
Nice. I hadn't considered that one.
Thanks for the explanations. Definitely, I will have to put a bit more effort into the whole matter.
So many Stars, so few Missiles!
In space no one can hear you scheme! Report message to a moderator
|
|
|
Re: Player assistant "AI" |
Thu, 09 March 2006 04:16 |
|
m.a@stars | | Commander | Messages: 2765
Registered: October 2004 Location: Third star to the left | |
|
joseph wrote on Wed, 08 March 2006 22:54 | Scouts
No - you misunderstand.
While an algorithum that calculated max stars scouted in min time with specific scout and took that route would be sweet.
What I wanted was a "go to this star" + "Try to scout a planet each turn on way" + "do not go more than X (originally 20)degrees out of direction of travel to find a planet"
Also - show leaps that use large ammounts of fuel.
|
No worries. I consider the "higher" algorithm as the goal. But I'd start with the "smaller" scouting all right. In fact, I think I would consider fuel consumption more important than original direction of travel when deciding about taking a detour or not.
I already got a script which breaks down long trips into cheapest/fastest possible components. Perhaps I'll tweak it to include some "scenic detours" for scouting purposes.
Quote: | I am aware that this will miss some planets and that I may want to tweak flight path to optimise.
But as regards removing MM it would equate to click on target planet, choose "Scout" orders, (set degree -optional), look at route to see if it has done something stupid (also optional I guess.
|
That would be my goal, indeed.
Quote: | From what I know of the Traveling Salesman, it would take considerable computer time to calculate the optimum routes and then some sod would shoot down one of your scouts and ruin it all.
|
Yeah. That's why I'd go with "sub-optimal" calculations, anyway. Having to recalculate often is a pain...
So many Stars, so few Missiles!
In space no one can hear you scheme! Report message to a moderator
|
|
| | | | | | | |
Re: Player assistant "AI" |
Thu, 16 March 2006 19:26 |
|
NingunOtro | | Master Chief Petty Officer | Messages: 105
Registered: September 2005 Location: Brussels, Belgium | |
|
I think that even if the fact that Stars! logic talks about moving ships from one place to another makes it handy to approach the possible solution with the travelling salesman analogy, the far increased complexity of stars and the strategic background much more compares to AI based on the game of chess: multiple differently valued pieces, positional value of pieces, the need to reevaluate the situation after the slightest move, etc. And to our advantage, a lot of investigation has already been done and proyected at production level, even as Open Source software we could have a look at.
If we were esteemed intelligent 'enough', they would have contacted us.
If we can not find them, either we are not smart enough, or they are smarter at hiding.Report message to a moderator
|
|
|
Goto Forum:
Current Time: Mon Jun 03 18:19:17 EDT 2024
|