Nov. 2003 - v1.1 released.
It is able to use all the battle history for its pattern matcher (most pattern matchers are limmited to 5.000-10.000 last observations) and it is able to "average" several patterns to create a best estimate (like Aspid).
The previous version was skipping many, many turns. In order to avoid it, I added MultiThreading to the bot: The main thread (the bot one) controls the bot and searches for the best patterns. The second one deals with insertion of enemy information into the data structures (inserting is very time consuming, because it precalculates the indexes).
As always, from the RobocodeRepository.
It has a good gun (at least equal - I hope - to Aspid), but it uses Aspid/MicroAspid? movement, which dates from Dec'02, and became quite obsolete againts the top-bots. It's not finished yet, and I plan to change its movement...
It uses Random Movement, exactly the same as Aspid and MicroAspid.
It features a PatternMatcher with the same principles as Aspid (it is able to match several patterns and "average" them). The advantage over Aspid is that it can use all the previous history (not only the last 5.000 observations like Aspid). It should give it some advantage in long matches (ie. more than 10 rounds). The PatternMatcher is also a SymbolicPatternMatcher (it makes easier to process the data) and the information is heavily indexed and stored in a tree-like structure to make it fast to retrieve it.
It just moves randomly and is confident in his luck.
I's just a 1v1 bot.
Don't know.
Nothing yet.
It's just another snake's name. Because is based on Aspid (the concepts are the same) I thought t would be a good idea.
Not for the moment, but I'w be happy to comment how it works with anybody interested.
Put in a good state-of-the-art movement.
Also, it seems the gun is not as good as expected. Once the skipped turns problem was fixed, I expected it to place close to Aspid, but it didn't happen :-(
It's not really tested...
I'm curious as to why the data insertion is the sow part, and not the pattern searching? I don't know much about MultiThreading, but maybe I should make some experiments with it. My gun also skips more turns than I would like it to, even if it's not a very slow gun imho... -- ABC
I'm using a VariableLengthMultiplePatternsSymbolicPatternMatcher? (nice name for a page). The information is stored using a tree, where each node is one of the symbols. Also, each node has a vector containing all the indexes that match a given pattern (defined by the path you follow from the root node to the current node). Thus, to search for a given string of symbols (pattern), Vibora just goes down the tree, and then returns a vector containing ALL the indexes that match. It makes the time necessary to retrieve ALL the past patterns that match the current pattern linear to the lenght of the pattern (it is FAST). But it creates many objects when inserting new data. Also uses sorted maps that are able to search the leafs of a node very eficiently, but take a longer time to insert... So matching the patterns is fast, but inserting the data is slow. As I don't need the pattern matcher to have ALL the data there (I can live with some delay in the data used for pattern seaching) the update is made by another thread. This way I don't skip turns.
Anyway, there is probably a bug, because I'm not getting the expected results. -- Albert
Wow, I will have to read that paragraph a couple more times to see if I understand what your talking about :). Looks like the memory consumption will be huge? -- ABC
To make it simple, I'w not include heading change for now, and assume bots accelerate/deccelerate a 4 per turn (to make the exaple shorter). Also, I'w will assume the maximum deep for the tree is 3
Imagine you have a bot that moves like follows (the values are the velocity of the bot each turn):
8,8,8,4,0,4,8,8,4,0,0,4,8,8,8The first thing Vibora does is to translate this into a symbolic space and convert it to an string:
![[Home]](/images/RoboWiki.png)
velocity -> { A,B,C } where A=8, B=4, C=0
The resulting string will be: *AAABCBAABCCBAAA
(The first asterisc is there just for convenience, to match the root node)
Then, it inserts the string into the tree, step by step. Note that the 1st level of the tree contains a length 1 matches, the 2nd level of the tree contains the lenght 2 matches, the 3rd level contains the lenght 3 matches and so on:
The empty tree will be:
*
Then inserts the elements as follows (the example is for the first 7 elements only):
* * * * *
| | | |--------| |--------|-----|
A(1) A(1,2) A(1,2,3) A(1,2,3) B(4) A(1,2,3) B(4) C(5)
| | | | | | |
A(2) A(2,3) A(2,3) A(4) A(2,3) A(4) B(5)
| | | | | |
A(3) A(3) A(4) A(3) A(4) A(5)
* *
|--------|-----------| |-----------|-----------|
A(1,2,3) B(4,6) C(5) A(1,2,3,7) B(4,6) C(5)
| |----| | |------| |----| |
A(2,3) A(4) C(6) B(5) A(2,3) B(7) A(4) C(6) B(5)
| | | | | | | | |
A(3) A(4) B(6) A(5) A(3) C(7) A(4) B(6) A(5)
Now the enemy bot keeps moving and at a certain moment we want to target it. Matching the longest sequence, or a number of sequances of a minimum lenght, or a minimum number of sequences is now very easy:
Assume the last movements of the bot where 4,8,8. Then translate into an string *AAB (the leftmost character is the most recent observation) , and then go down the tree. For the example tree it will start from the '*' node, then move to the 1st level 'A' node, then down to the 2nd level 'A' node, and it will find no more nodes to go down, so it will return (2,3).
Vibora has been able to retrieve all the patterns that match the current one with the longest sequence in a very fast way (it imposes also some conditions on the minimum number of indexes returned). It allows it to search all the history (not only the most 5000 to 10000 most recent observations).
Now it just goes to the original series, projects the future positions from time 2 and 3, and "averages" the resulting bearings to decide where to shot.
Memory is not an issue, because I'm not one of these masochistic people that runs 1000 rounds matches :-)
-- Albert
1000 matches is not enough! :) -- Frakir
12.07.2005 Does anyone has a copy of this Bot, preferable the source? The Repository seems not to have one. Thanks. --bjd