Robo Home | Changes | Preferences | AllPages

Vibora is another pattern matcher bot. Not finished yet, and not competitive nowdays against the top-bots (I'w have to change the movement to make it competitive). But I wanted to release something before going holidays, to here it is.

Nov. 2003 - v1.1 released.

What's special about it?

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).

Great, I want to try it. Where can I download it?

As always, from the RobocodeRepository.

How competitive is it?

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...

How does it move?

It uses Random Movement, exactly the same as Aspid and MicroAspid.

How does it fire?

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.

How does it dodge bullets?

It just moves randomly and is confident in his luck.

How does the melee strategy differ from one-on-one strategy?

I's just a 1v1 bot.

How does it select a target to attack/avoid in melee?

Don't know.

What does it save between rounds and matches?

Nothing yet.

Where did you get the name?

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.

Can I use your code?

Not for the moment, but I'w be happy to comment how it works with anybody interested.

What's next for your robot?

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 :-(

Does it have any WhiteWhales?

It's not really tested...

What other robot(s) is it based on?


Comments, questions, feedback:

Cool! So you're into movement a while now? That's bad news for us as your competitors! -- PEZ

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

Here it goes a graphical explanation:

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):

The first thing Vibora does is to translate this into a symbolic space and convert it to an string:
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

Robo Home | Changes | Preferences | AllPages
Edit text of this page | View other revisions
Last edited July 12, 2005 14:30 EST by (diff)