Author Topic: Ai Data Structures  (Read 3013 times)

Offline LupusShearhart

  • Newbie
  • *
  • Posts: 13
Ai Data Structures
« on: May 13, 2005, 02:20:53 AM »
Alright - here goes. None of the below will contain code, mainly because the whole idea of having a learning system is purely theoretical right now, and may or may not work. Here's my take on things.

Possibility number 1)
We could create 'scripted' AI just like that of the triggers, only have these scripted systems actually use the AI functions instead of having an arbitrary time give an arbitrary research topic, etc.

Possibility number 2)
We could create a hard-coded AI setup that consists of two sets of loops.

Loop set 1 (named HomeBase for future reference)
Outer loop
{
  Builds population (inner loop 1, includes research towards pop. building sciences.)
  Builds morale     (inner loop 2, includes research towards morale building sciences.)
}

Loop set 2 (named buildAttackDefense for future reference)
Outer loop
{
  Researches weapons (inner loop 1, usually runs simultaneous to inner loop 2 in order to create a weapons base.)
  Builds weapons (inner loop 2, builds a crapload of the best weapons available to the AI... while also building walls and defenses and such)
}

Loop set 3 (named searchAndDestroy for future reference)
Outer loop
{
  Scout seeking (Loop 1, runs until it finds the nearest enemy colony, searching with scouts (just to add insult to injury.))
  Complete and utter destruction (Loop 2, launches full scale attack using all mobile weapon units on that nearest base it just found. Does not cease until base=vaporized.)
}

Of the above three sets of loops, the sub loops all run entangled with eachother. Example: You can have a standard lab researching Environmental Psychology at the same time an Adv. Lab is researching Mobile Weap. Platforms assuming you have enough scientists. (Note: This above AI is NOT linear, meaning different loops can run at different times.) Another example is: Say it finished with the pop. building loop, and someone destroys enough residencies to make the demand go above 100%, the loop runs some more, and it rebuilds the destroyed buildings. (This can apply to any building/researching loop.)

Possibility number 3)
Build all different AI loops as stated above, but rather than hard-coding the links between the loops, have the links dynamic, so if one strategy fails, a new order of links is created and thus a new strategy is attempted. These link setups will differ from game-type to game-type... and until the optimal strategy is obtained, from game-to-game. Use two data structures for handling all of these links between the loops. You can use a hash function to store and retrieve the strategies and their links, and while retrieving the links, line them up in a queue so the computer can then run in a linear mode, following the strategy it's just loaded. How it's going to try different links for different strategies is still up for debate.... and the reason I'm posting.

Would the links be all pre-programmed into the hash table and pulled out at random until the optimal strategy is formed? And say that 'optimal strategy' is beaten... should it be possible to figure out where the strategy failed and modify it accordingly using pattern recognition code? Again - this third possibility is all theoretical and may not even be possible given a relatively small time constraint.

The up-side about this possibility is that, in order to have a working, intelligent AI in your map, you won't have to spend two months developing it. You load a hash table, probably from an encoded *.ini file, and import the AILoops class into your project and according to what type of map you're making, you pass in a certain set of variables into the hashing function, and out pops your links directly into a queue, which then run through grabbing functions out of the AILoops class and running them.

Any comments, questions, answers, or any other type of response at all is appreciated. :)  (thumbsup) I'm dying for input on these ideas.
« Last Edit: May 13, 2005, 10:20:43 AM by Leviathan »
"Wake up, Mr. Freeman. Wake up and...smell the ashes." ~The G-man in Half Life 2

Offline coolzero

  • Full Member
  • ***
  • Posts: 106
    • http://www.trippyac.com
Ai Data Structures
« Reply #1 on: May 13, 2005, 07:46:16 AM »
not a coder but do understand a little of what you are saying :P and first things i wana say is i LOVE that you started working on a ai or something... it was realy  nesesary :D. and posebelity 3 seems to me the most efective relyable way  
becous havning my signature 5720 characters long or so is a little crazy and hacker would prob del my signature again i diseded to make a pic of it ... this is acualy my name in letters highlighted. i just took a ss  :D

Offline zigzagjoe

  • Hero Member
  • *****
  • Posts: 626
Ai Data Structures
« Reply #2 on: May 13, 2005, 08:42:12 AM »
Imo, 2 and 3 are/would be the most effective.

The problem with the original A'I's is that they don't act even close to real(ex. Colony Management), They just use the GoAI so they can never die b/c they get 4096 workers and scis, and no food constraint.

Really, thats the part that needs to be devoloped before everything else. The rest of it could be added later, but it would be a acheivement in itself to get a AI that can properly manage itself.

Lev: Pls don't remove what was initaily there in my (anon by accident) post. Why was the his post edited?
« Last Edit: May 13, 2005, 04:30:27 PM by zigzagjoe »

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4955
Ai Data Structures
« Reply #3 on: May 13, 2005, 09:50:23 AM »
Yes, we have gotten a little something done on colony management, but no nice finished library of functions for this. That seems to be the biggest holdup with developing a fully general AI at the moment.
 

Offline Eddy-B

  • Hero Member
  • *****
  • Posts: 1186
    • http://www.eddy-b.com
Ai Data Structures
« Reply #4 on: May 13, 2005, 12:44:55 PM »
AI is nothing more then a set of rules, or call it functions that will be applied.
"AI" will just check (using IF's) to see if there are any threats, or things that need to have top priority. If there's no special priority at any given moment, the AI should build up forces, its base and research pretty much to a standard algorythm.

A coder will just give the parameters an AI has to follow. After that it's still an ARTIFICIAL intelligence - its suppose to LOOK real, not be real.

You can't build a 100% fool-proof AI. There's always going to be a way to fool the AI, which is good, otherwise it would be nearly unbeatable. An AI like this would be very nice to devellop, in use with colony or multi-player maps, where the computer opponent does not have any specific objectives. As for single-player maps, my AI's always have some objective that would make it very hard to function as descibed.


Building an AI engine is not just a matter of coding, as it is a matter of logival thinking. Setting up a basic AI isn't all that hard i think -seeing other games have it as well-

 
Rule #1:  Eddy is always right
Rule #2: If you think he's wrong, see rule #1
--------------------

Outpost : Renegades - Eddy-B.com - Electronics Pit[/siz

Offline LupusShearhart

  • Newbie
  • *
  • Posts: 13
Ai Data Structures
« Reply #5 on: May 13, 2005, 10:10:14 PM »
Quote
AI is nothing more then a set of rules, or call it functions that will be applied.
"AI" will just check (using IF's) to see if there are any threats, or things that need to have top priority. If there's no special priority at any given moment, the AI should build up forces, its base and research pretty much to a standard algorythm.

A coder will just give the parameters an AI has to follow. After that it's still an ARTIFICIAL intelligence - its suppose to LOOK real, not be real.

You can't build a 100% fool-proof AI. There's always going to be a way to fool the AI, which is good, otherwise it would be nearly unbeatable. An AI like this would be very nice to devellop, in use with colony or multi-player maps, where the computer opponent does not have any specific objectives. As for single-player maps, my AI's always have some objective that would make it very hard to function as descibed.


Building an AI engine is not just a matter of coding, as it is a matter of logival thinking. Setting up a basic AI isn't all that hard i think -seeing other games have it as well-
Well - the above AI (Solution 3) was only going to actually be for colony games or multiplayer. For single player, rather than running the random-gen code to get the links, you could look through the table and select which loops you would like the AI to run and push those loops through the queue.

As for the basic algorithm to build forces and colonies and such, it doesn't necesserily have to follow only one or two basic algorithms. You can essentially build a set of loops to act like LEGOs, essentially building blocks for an AI. The links are as if you're putting the legos together. The coder will then, as you said, apply the set parameters the AI will follow... be it a specific strategy, or a range of link sets and it could choose a random strategy within that range.

As for a single-player game, it's not all 100% different from a colony or MP. game. An MP game has a goal. Eliminate your opponents, be the first to race to space while also slowing your opponents' climb, have the most ore, etc. The computer can run a set of links towards any one of those goals. In a single player game, the computer's goal can be, for example, "Prevent user from making it to space." Attack the crap out of spaceports, labs, residences. Leave the CC alone as to not leave the player feeling bitter, etc.

No - creating an AI engine is not hard at all. This isn't going to be the first one I've done, and it won't be the last one I'm going to do, either. This is the first real-time strategy game AI I've done, however, hence why I'm trying to figure out the best data structure to store, load, and execute strategies. In an FPS AI, the best data structure to use is a combination of linked-lists and queues. For a strategy AI, where plans are much more complex than find cover, appear from behind cover, kill, take cover, you need a more efficient way of finding a table of links than a linked-list. A hash table is the fastest way of doing so, as far as I can see.

I'm also fully aware that we require a library of functions for the AI, and intend to work with that "old ai" system in close conjunction with my own function loops to create an easily repeatable, easily incorporated AI system for any type of map. (It's simple to create a whole seperate AI for each type of map, the challenge will be making it universal, but I'm willing to accept it.  (thumbsup) )
"Wake up, Mr. Freeman. Wake up and...smell the ashes." ~The G-man in Half Life 2

Offline LupusShearhart

  • Newbie
  • *
  • Posts: 13
Ai Data Structures
« Reply #6 on: May 23, 2005, 07:58:09 PM »
Quick update:

I hit an inherent flaw with the above data structure. Sure - it creates the links properly, however, what if you were to try to decide different levels of active searching from the AI itself for attacking? (Example levels: Peaceful, passive, neutral, aggressive, war-loving... names change, same principle.) This is going to change the way the links are accessed. Different AI types will have to access different sets of links, therefore I'd have to create another array to crate a 'table of links', or a 'table of contents' so to speak, so you can have a certain number of peaceful AI setups, as well as a certain number of aggressive AI setups. The only flaw with that is, the lack of efficiency, however, in order to make the code easy to use for other coders when I'm done, it's kind of necessary. The question is, what kind of array should I set it up as?
"Wake up, Mr. Freeman. Wake up and...smell the ashes." ~The G-man in Half Life 2

Offline BlackBox

  • Administrator
  • Hero Member
  • *****
  • Posts: 3093
Ai Data Structures
« Reply #7 on: November 03, 2005, 11:32:43 AM »
This post was posted by LupusShearhart after the DB rollback occurred. Since it's long, and contained useful info, I've decided to post it here, after rolling the DB forward again from backups.

-------------------------------------

Well - I'm back, almost six months later, and six months smarter. I just finished up my summer internship with the Brookhaven National Laboratory, and let me say this:

I hate Fortran. Hate it. Hate it. Hate it.

With that out of the way, I've got good news. Though I haven't been able to work on the AI coding for OP2 as much as I would have liked to in the past six months, I was, indeed, able to continue my work towards it since September. (Please, don't get me wrong, I've been busy as anything else compliments of classes this semester.) The good news is that, for Multiplayer games, I've figured that the host's AI setup would probably be the best to use per game. This makes the AI non-uniform, and therefore even more unpredictable. If there is more than one AI player suggested, then the system will move to player 2's AI model, then continue down the list. So the procedure is as follows:
  • Host starts a game. Decides on a 6 player map.
       
  • Two people join. Host has player slot zero, Player 1 has player slot 1 and player two has player slot 2.
       
  • Host decides to make the game 3 vs. 3, humans vs. Computers. Sets player slots 3-5 to "AI" via a hacked-in dropdown box. (Debatable, still trying to figure out a better way to do this.)
       
  • AI 1, or slot 3, uses the Host's AI script for the selected difficulty level.
       
  • AI 2, or slot 4, uses Player 1's AI script for the selected difficulty level.
       
  • AI 3, or slot 5, uses Player 2's AI script for the selected difficulty level.
       
  • The above is a simple recursion algorithm, coupled with a little file I/O. The above also allows for multiple AI "personalities" and game-play styles, thus adding to the challenge. If no players exist, and the host wants to play an "instant action" style game, or if there are more AI bots than players, the recursion algorithm jumps to the Host again after there are no more human players in the list.
       
  • AI scripts will be saved in XML file formats. This keeps the original data structure in a strict organizational pattern to allow for fast indexing, so many a low-end computer should have zero problems with loading a full game of AI entities.
       
  • There will be several pre-made AI scripts that will be included in the package for loading challenging(or not-so challenging, based on the difficulty level) AI entities when the game is run for the first time after the package is installed. (Essentially, if you pick *hard*, it will load hard, then kick your butt and steal your wallet, even without a long learning process. But by the time you figure out its patterns, the patterns will have changed.)
If anyone has any other suggestions or criticisms, throw them my way, please. The more criticism I get, the better off I am in the long run. :)

(By the way, my previous post has been rectified in this post. Any truly dilligent coder would have caught it. XML. The XML would be that "table of contents" and the array would be a lot easier to code, now. The real challenge now is going to take me a good three months at best. I have to code the many different AI functions and loops that the "table of contents" links the AI to. Not incredibly difficult, just amazingly time consuming, in the fact that there's almost an infinite number of ways to accomplish a single goal. (Colony building, for example. Where to build things, how to set up defenses, how to most efficiently lay everything out per function, etc.) Finally, what I'm going to have to do is design a beta-test package, and encourage everyone who gets it to do everything to try to "break" the program, so most of the bugs can be found. I'll make another post begging for volunteers when the time comes, though.)

Once again, I apologize for my heavily extended leave. It was highly unexpected, and I was kind of hoping to have this AI system almost done already. Then life said, "Hey, guess what, Ed... no. You fail." Oh well. "Hey, guess what, Life... no. You were wrong." I'm back on the horse. If anyone has any questions, hesitate not, to leave me a private message.
« Last Edit: November 03, 2005, 11:33:34 AM by op2hacker »