Sign in to follow this  
Nateck

Memory Indexing

Recommended Posts

This would fit better in a database forum, but I couldn't find one here at GameDev. I had an idea, and I'm hoping to run it through the heads of people with more experience in databases. I'm developing some memory-based AI, and I'd like to use XML for easy organization of memories but I don't think that XML would be fast enough (for the amount of memories each AI will have, upwards of 1000). I was thinking about storing the memories in XML, but using SQLite to index it, so the AI could use an SQL query to find memories that match specific criteria, and then have them find it in whatever XML file the memory is stored in. Would that work, or even be faster than just XML? Thanks in advance!

Share this post


Link to post
Share on other sites


XML is just a storage format (usually with some structuring).
It would be a good way to save data but it would be miserably slow to scan in constantly when doing pattern matching searches
.


Your memories are what exactly ?? Incidents with situational factors and maybe some generated judgment/interpretation values??


Ideas can be associations between different symbols/concepts (like 'car' or 'alot' or 'happy' or ' Dec 7 1941' or 'red' or 'Fred' (a specific object)). A memory would be defined by a set of links to these ideas. You would probably want to store them in-memory as a network (or sets of networks).
The links could be bi-directional (and allow one to many multi-links)
Traversal routines would likely run much faster than trying to have SQL interpret associative equations (possibly text form even)


I remember one memory which was: (Dark+Stormy+Night) + (Thing+went bump) + (Mysterious + Scary) + ...


The number of tied together symbols can vary as well as their types and what else they link to (your searches may be correlating indirect linkages).

The associations themselves might have qualifiers -- like strong/weak or even a 'not' which indicates that it was learned that two symbols are not associated.




To dump a network of associations like this you would first list/define the individual symbols (each with a unique name) and then a list of the idea/concept associations (groupings of symbol names possibly with operators)
Each idea would have its unique identifier. Then finally your 'memories' would be listed defined from the previously defined ideas.

Loading the file data would rebuild the in-memory networks

The memory queries could find matches on sets of ideas or by supplied symol/concepts and decomposing the ideas. Queries might have to qualify each matching factor as to whether the memory does contain the idea/symbol or just might contain it (or definitely doesnt contain it (that 'not' association I mentioned which can be post added when queries turn up too many matches).

Share this post


Link to post
Share on other sites
The memories would consist of the issue that the AI is facing, what the AI did to attempt to overcome it, if it worked, and what was gained. In nature, there isn't much of a need to remember all the good things, just the problems and how to get over them. I was thinking of organizing them (in XML) something like this: Issue->WhatWasGained->HowOftenHasItWorked->Solution. Using SQLite, I could index it so the AI could search for issues that match certain criteria, or query to see if certain solutions have been attempted before. Once the SQLite returns the information on where the memory is.

Actually, I'd have another set of memories, but since they would be things like "#3142: rude" or "FoodIsIn: (4,3) | (17,2) | (-2,-14)" so I could use SQLite for those, since once the AI has the information, it has it and doesn't need to follow a big tree to find the solution.

Share this post


Link to post
Share on other sites
I don't see how XML is relevant here. It looks like the memories can be stored in a database without problems. As for how 'fast' it is, parsing XML can be very quick, but the idea is that you parse it into an internal structure that suits you and then navigate that, rather than navigating the XML node tree all the time. With that in mind you may as well just use the database for storage in the first place.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nateck
This would fit better in a database forum, but I couldn't find one here at GameDev. I had an idea, and I'm hoping to run it through the heads of people with more experience in databases.

I'm developing some memory-based AI, and I'd like to use XML for easy organization of memories but I don't think that XML would be fast enough (for the amount of memories each AI will have, upwards of 1000). I was thinking about storing the memories in XML, but using SQLite to index it, so the AI could use an SQL query to find memories that match specific criteria, and then have them find it in whatever XML file the memory is stored in.



int something[] = new int[300000000];
That's all what you require.

SQL can't be faster than direct memory access, and memory based AI is memory bound. 80 ns access is harsh enough already.

Share this post


Link to post
Share on other sites
@Kylotan -> I'd like to use the XML so I don't have to conform to SQL data types or columns. I can add as many <attribute>foo</attribute> (or whatever I call it) tags as I want, and the AI would still have no difficulty reading them (once it found them). About the speed, would it be faster to search through a ton of memories to see if a solution has been tried, or would it be faster to run an SQL query on the solution, and see what it pulls up?

@Raghar -> If I have 20+ AI going at the same time, is that practical? Yes, it would be faster, but the difference shouldn't be horrible. If I put it to file and only load what I need, when I need it, than I don't have to worry about RAM usage. Also, accessing it from a file means that I don't need to make sure that the AI save the file, because if they didn't, I might loose all the memories they created for themselves.

For clarification purposes, I'd like to point out that the SQL database would contain the "keywords" for memories and solutions, and the XML database would have the actual data. Also, I'll likely be running 20+ AI.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nateck
The memories would consist of the issue that the AI is facing, what the AI did to attempt to overcome it, if it worked, and what was gained. In nature, there isn't much of a need to remember all the good things, just the problems and how to get over them. I was thinking of organizing them (in XML) something like this: Issue->WhatWasGained->HowOftenHasItWorked->Solution. Using SQLite, I could index it so the AI could search for issues that match certain criteria, or query to see if certain solutions have been attempted before. Once the SQLite returns the information on where the memory is.
.



What you are describing is a pattern match for a set of solutions to situational problems. For a situation X (list of situational factors..) you tried Y (possibly several solutions (actions taken) with the results of success for them -- so that you can have the object react again with the best apparent solution (with a little experimentation thrown in to see if an even better solution might exist ...) It might also be used to tailor behaviors for a type of object which reacts in expected ways (traditions/instict etc..) or even a unique object that has its own preferences for its behavior.


The problem is that you have to decompose the particular game situation into a set of situational factors to use as keys of your pattern search. If this is hardcoded than you can tailor the fastor set by hand, but in a learning system the methods for general analysis of the game situation and discarding the irrelevant factor gets very complex ( moreso the more complex your simulation/game -- especially if you take time into effect -- factors that happen across a span of time instead of a simple snapshot of the current situation). The system has to make generalizations in classifying the situation or your pattern set (memories) will be too specific and hardly ever match.


In any case you have to match these factors against your memory 'rows' which sounds like multiple AND/OR clauses and you most likely cant do static business rules. XML is just the storage format, the data still has to be parsed and if it isnt already in binary form the interpretation will cost alot of extra processing. Speed might not be important for you project, so if you have an easy to program with library that takes XML, you can get to the more interesting parts of the project sooner.






Quote:

Actually, I'd have another set of memories, but since they would be things like "#3142: rude" or "FoodIsIn: (4,3) | (17,2) | (-2,-14)" so I could use SQLite for those, since once the AI has the information, it has it and doesn't need to follow a big tree to find the solution.



Those are 'facts' which are useful as input data for behavior calculations (ie - 'find food', or 'what approach do I take to an NPC'. They can be used as fill in data for the situational reaction/solution search. You face a similar problem of deciding which situational 'facts' are worth saving (instead of just having the simulation engine provide the current sensor info).
Saved facts can be used to plan action involving objects which are not currently in view or are effected by previously generated judgements/observations (the 'rude' NPC ...)



Oh and if you are worried about memory usage (as in it not fitting) we have so much memory now that its usually not a problem to fit the entire database in-memory. You can fit a huge amount of behavioral logic (data) in a GigaByte
(and you can have several of those if you really need them on the consumer grade computers these days). If your memories are changing/revised alot you can still write the 'mods' to an in-memory DB out to files if you ar worried loss from an abort.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this