I''m interested in developing NPCs that can anticipate your next attack based on the ones that went before. For example, assume all attacks are labelled A-Z. If you used attacks A,B,C,A,B,C,A,B on an NPC, it should guess that the next attack is more likely to be C than B or A. It could then take action based on this knowledge.
I can see that this might bear a resemblance to the ''predictive text'' feature on a cellphone, but that requires a dictionary of words in the first place. This system would need to learn and revise its expectations as it goes along. I''m not sure how it would resolve ambiguities though.
I would also assume that there''s some sort of algorithm used in many compression schemes that will seek out commonly-used sequences (such as A,B,C above) in order to replace them with a smaller token in the compressed file. Perhaps this could be used to generate the dictionary for the above routine... and maybe the frequency with which the sequence was found would be added to the dictionary so that the ambiguity can be resolved in favour of the most likely sequence.
Is this a reasonable route to take? And is there a standard algorithm or family of algorithms for doing this sort of thing?
[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]
Predicting patterns/sequences
This sort of sequence analysis has been done for simple games (rock/paper/scissors, etc.). The obvious solution is to maintain a frequency table of the last so many turns and predict the historically most frequent class. Assuming there is a pattern to find, this can work well- at least on simple games. After reading about this years ago, I wrote a small program and let some family and friends try it out. After winning about half the time (as you''d expect), the machine would start to guess fairly well what (rock/paper/scissors) the human player would do next. Some players said it was spooky.
The fundamental design trade-off here is how long of a history to maintain. The longer the history, the more complex the discovered patterns, but the less examples one has to draw from.
The fundamental design trade-off here is how long of a history to maintain. The longer the history, the more complex the discovered patterns, but the less examples one has to draw from.
quote:Original post by Kylotan
I''m interested in developing NPCs that can anticipate your next attack based on the ones that went before. For example, assume all attacks are labelled A-Z. If you used attacks A,B,C,A,B,C,A,B on an NPC, it should guess that the next attack is more likely to be C than B or A. It could then take action based on this knowledge.
I''m not sure what you mean exactly by the "predictive text" feature but isn''t this basically identical to the the algorithms used by random name/word generators? For each letter you record how many times each letter has followed it and create a mapping like (for the sequence you gave) A->(A,0)(B,3)(C,0), B->(A,0)(B,0)(C,2) C->(A,2)(B,0)(C,0). From there it''s just a probabilistic guess as to which will come next. You can also do it higher order for more intelligent guesses, ie recording which character probably comes after a given pair of characters.
The book "AI Game Programming Wisdom" contains a few sections on doing exactly what you want. The basic idea is to keep a history of events, for your example "ABCABCAB". Then, you find the longest match of the last characters that has another character following it, so you would start with B and find the matches(3). Then you would look for AB and mark the matches(2 not counting the one that ends the buffer), then CAB and find a match(1), then BCAB(1) and then finally ABCAB(1) (CABCAB only has 1 match at the end of the buffer so it can't be used for prediction). Once the pattern ABCAB is found (at the start of the buffer, because the other match would be at the end and nothing follows it), the program can predict that the character following it that time will follow it this time as well. Since a "C" follows the newest(excluding the one that ends the buffer) "ABCAB", the program can expect C to happen next and begin to respond in an appropriate way.
In order to cope with no matches of even 1 letter (or maybe even on matches of 1 letter), you could also keep a table of probability for each move independant of the one before it. You can then either randomly select one based on its probability or choose the most probable next move. You might even want to count the occurances of each following character when doing multi-letter matches, so you can detect ABCD being a lot more common than ABCC and react to D instead of the fairly rare C (usually though, implementations just look at the match closest to the end of the buffer, which is better at learning recent 'trends', but worse at reacting to a person's general preference to do A over B. not sure which one would give better results when trying to predict a combat choice)
As has been said, applying this to simple games like RPS can give surprising results (the machine winning much more than 33% of the time. If you play long enough it might even start winning all the time).
Dobbs: The problem with storing it in a table like that is that it can have HUGE ram requirements if you want a very high order table. For the alphabet for example, a table for 10-letter combos would take an array with 141167095653376 (141 trillion) elements, most of which would be 0 (maybe you could use a sparse matrix class, but I don't think it would be any faster than just searching for the pattern, especially if you use the optimizations the book suggests).
[edited by - Extrarius on April 2, 2003 12:18:58 PM]
In order to cope with no matches of even 1 letter (or maybe even on matches of 1 letter), you could also keep a table of probability for each move independant of the one before it. You can then either randomly select one based on its probability or choose the most probable next move. You might even want to count the occurances of each following character when doing multi-letter matches, so you can detect ABCD being a lot more common than ABCC and react to D instead of the fairly rare C (usually though, implementations just look at the match closest to the end of the buffer, which is better at learning recent 'trends', but worse at reacting to a person's general preference to do A over B. not sure which one would give better results when trying to predict a combat choice)
As has been said, applying this to simple games like RPS can give surprising results (the machine winning much more than 33% of the time. If you play long enough it might even start winning all the time).
Dobbs: The problem with storing it in a table like that is that it can have HUGE ram requirements if you want a very high order table. For the alphabet for example, a table for 10-letter combos would take an array with 141167095653376 (141 trillion) elements, most of which would be 0 (maybe you could use a sparse matrix class, but I don't think it would be any faster than just searching for the pattern, especially if you use the optimizations the book suggests).
[edited by - Extrarius on April 2, 2003 12:18:58 PM]
Well obviously you wouldn''t store it in a table/matrix/array type structure, I''d say a sparse tree-like structure would be better. In fact I brought the idea up originally because of Kylotan''s remarks about compression algorithms - I once did an LZ compression implementation, which does something very similar to what Kylotan wants, and the implementation worked very much in the way I suggested and was implemented with a trie.
I agree that it wouldn''t scale well to high order cases and/or lots of moves but that just means it''s only a viable option for small cases. To me the associated algorithms are much simpler than lots of string matching.
I agree that it wouldn''t scale well to high order cases and/or lots of moves but that just means it''s only a viable option for small cases. To me the associated algorithms are much simpler than lots of string matching.
You may want to look into the field of data mining. The whole field aims to extract common patterns (sequences too) from a database. A couple guys from IBM are the root of all modern research in DM...
Mining Sequential Patterns: Generalizations and Performance Improvements
There are some incremental descovery algorithms which may be applicable too. Fascinating topic.
Artificial Intelligence Depot - Maybe it''s not all about graphics...
Mining Sequential Patterns: Generalizations and Performance Improvements
There are some incremental descovery algorithms which may be applicable too. Fascinating topic.
Artificial Intelligence Depot - Maybe it''s not all about graphics...
Consider, though, that such a large space could only be extremely sparsely populated. Confining the analysis to shorter sequences trades off pattern length (complexity) for many more examples per cell. How likely is any 10-character sequence to appear more than once? Patterns of length 4 might happen often enough to be useful.
quote:Original post by Extrarius
The problem with storing it in a table like that is that it can have HUGE ram requirements if you want a very high order table. For the alphabet for example, a table for 10-letter combos would take an array with 141167095653376 (141 trillion) elements, most of which would be 0 (maybe you could use a sparse matrix class, but I don''t think it would be any faster than just searching for the pattern, especially if you use the optimizations the book suggests).
Depends on the application... If its a fight game like mortal combat, tekken, whatever, people develop strings of combos they like to do (say 3 different 3-attack combos in a row over and over, thats 9 attacks).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
