Ranking tree

[synkarius]

Add a ranking tree to the ConfidenceScore decision logic. Should figure out that if character a beat character b and character b beat character c, that when a and c fight, a should get some confidence credit.

[reconman]

Is there even anything in place to check if character A has won against character B before?

[synkarius]

No. Some sort of efficient data structure would have to be built from the records.

[synkarius]

I'm open to restructuring the records entirely if a better way exists. The whole way they're stored currently was just the first thing that came to mind, and can probably be improved upon.

[synkarius]

I've been thinking about this one. I think I've got a working ranking algorithm in mind, maybe not perfect, but at least consistent.

[reconman]

The moving up and down after matches is a big problem.

Imagine this Branch: [Unbeatable X, High S, Mid S, High A, Low A, Mid B]

High S beats Mid S so it moves up and Mid S moves down which results in this: [High S, Unbeatable X, High A, Mid S, Low A, Mid B]

If High S beats Mid S I would do nothing in the branch. If Mid S beats HIgh S, however, I would move Mid S up and leave High S where it is.

[synkarius]

You're right. Any thoughts on the branch-intersperse case? That one is by far the most problematic, and difficult.

[reconman]

I've thought about that one before you made your comment. It's a bit problematic that the characters above the lose character are considered weaker than the winning character. Same goes for the weaker characters than the winning character.

My approach was

var newBranch = winnerBranch.slice(0, winnerCharacterIndex+1); newBranch = newBranch.concat(loserBranch.slice(loserCharacterIndex, loserBranch.length));

winnerBranch = winnerBranch.slice(winnerCharacterIndex+1, winnerBranch.length); loserBranch = loserBranch.slice(0, loserCharacterIndex);

branches[winnerBranchIndex] = winnerBranch; branches[loserBranchIndex] = loserBranch; branches.push(newBranch);

but soon I realized that much information would be lost this way.

Your original approach is better than mine. I just tried to write an object-based approach with a real tree with up- and downlinks but that would create endless loops when counting wins and losses.

[reconman]

What do you think of this idea:

this.sideBranches = []; //in class definition

var newBranch = winnerBranch.slice(0, winnerCharacterIndex+1);
newBranch = newBranch.concat(loserBranch.slice(loserCharacterIndex, loserBranch.length));

winnerBranch = winnerBranch.slice(winnerCharacterIndex, winnerBranch.length);
loserBranch = loserBranch.slice(0, loserCharacterIndex+1);

if (winnerBranch.length > 0)
   this.sideBranches.push(winnerBranch);

if (loserBranch.length > 0)
   this.sideBranches.push(loserBranch);

if (winnerBranchIndex > loserBranchIndex) {
    delete this.branches[loserBranchIndex];
    delete this.branches[winnerBranchIndex];
} else {
    delete this.branches[winnerBranchIndex];
    delete this.branches[loserBranchIndex];
}
branches.push(newBranch);

The characters added to the normal branches now stay in the sideBranches to keep the information. If a character is not found in the normal branches, the sideBranches are searched. Both characters have to be in the same sideBranch.

When an character contained in sideBranch wins or loses a match against a character in a normal branch they are inserted into the character's branch directly above or below.

The only problem is that you would need another array when 2 characters from different sideBranches fight.

[reconman]

The sideBranch can only be deleted when all characters contained in it are contained in normal branches too.

[synkarius]

I like this a lot. It preserves information much better than my original way. The downside is that the fragmentation might never resolve, but then again, most of it might. I'd be interested to see the result of the 22k match seed data-- what percent ends up fragmented, or what are the average branch sizes, etc.

As for needing side branches for the side branches, etc., two ideas come to mind. The first is to just take the leftovers which would have become side branches and just make them regular branches. Using your code, this would result 2 branches becoming 1-3 branches, but with information perfectly preserved. The other idea is to augment the structure a bit so that some sort of branch-level recursion is possible. I guess I'm in favor of whichever one reduces fragmentation more.

OR... we could try more than one of these and let the bot decide. Depending on how the RankingTree is implemented to weigh in on a given match, it could turn out that fragmentation is actually more important than accuracy (though I doubt it, I still kind of want to try it...)

[synkarius]

All that said, my gut says, try the "add the side branches as main branches" way first and experiment with the other stuff later.

[reconman]

You're right about the side branches being main branches. The code then looks like this for joining two branches:

var newBranch = winnerBranch.slice(0, winnerCharacterIndex+1);
newBranch = newBranch.concat(loserBranch.slice(loserCharacterIndex, loserBranch.length));

winnerBranch = winnerBranch.slice(winnerCharacterIndex, winnerBranch.length);
loserBranch = loserBranch.slice(0, loserCharacterIndex+1);

if (winnerBranchIndex < loserBranchIndex) {
    if (loserBranch.length <= 1) { //only the loser is left in the branch -> remove branch
        delete this.branches[loserBranchIndex];
        loserBranch = null;
    }
    if (winnerBranch.length <= 1) { //only the winner is left in the branch -> remove branch
        delete this.branches[winnerBranchIndex];
        winnerBranch = null;
    }
}

else {
    if (winnerBranch.length <= 1) { //only the winner is left in the branch -> remove branch
        delete this.branches[winnerBranchIndex];
        winnerBranch = null;
    }
    if (loserBranch.length <= 1) { //only the loser is left in the branch -> remove branch
        delete this.branches[loserBranchIndex];
        loserBranch = null;
    }
}

if (winnerBranch) //winnerBranch was not deleted
    branches[winnerBranchIndex] = winnerBranch;

if (loserBranch) //loserBranch was not deleted
    branches[loserBranchIndex] = loserBranch;

branches.push(newBranch);

[synkarius]

That looks right.

[reconman]

What's your idea on calculating the scores in the RankingTree? It's clear that the confidence is based on how far two characters are apart in a branch.

How about something like this:

confidence = Math.abs(characterIndex1 - characterIndex2) / 5.0;
if (confidence > 1)
   confidence = 1;

[reconman]

Of course that 5.0 can be replaced with a gene value.

[synkarius]

That's basically what I was thinking. The ranking delta times a chromosome. Check out this section to see how the other Scientist measures are included:

https://github.com/synkarius/saltbot/blob/master/src/strategy.js#L366

[reconman]

Sorry, I momentarily didn't think of the other aspects when calculating the confidence. I haven't got much sleep for several days and have to write my Bachelor thesis.

[synkarius]

Also, congrats on nearly completing your degree! :)

[reconman]

I've just committed some changes so the import works. The problem is that 11000 branches are created with a maximum of 10 characters per branch. The most common branch sizes are 2 and 3 characters.

Could you please look for any bugs? I will do the same tomorrow.

[reconman]

Currently one code branch exists where the branches are merged "correctly" and one where they are just merged like winnerBranch + loserBranch. Both methods and the algorithm without a ranking tree have to be compared.

[synkarius]

I'll help test this.

[synkarius]

Here's my data so far. "high-frag" is the one with the incorrect number of branches. "W + L" is the simple merging version. "intersperse" is my original technique.

30k matches / pre tree          : g70   63.8% $53m
30k matches / high-frag         : g70   63.5% $55m
30k matches / W + L             : g70   63.2% $55m
30k matches / intersperse       : g70   63.6% $58m

30k matches / pre tree          : g200  63.8% $54m
30k matches / high-frag         : g200  63.5% $65m
30k matches / W + L             : g200  63.3% $65m
30k matches / intersperse       : g200  63.4% $64m

So far, I'm only convinced that we are better off with the tree than without it.

[synkarius]

Also, I misspoke earlier. "deltaBranch" was necessary for intersperse to work. It aligns the winner with the loser.

[synkarius]

Damnit, all that testing was invalid. The simulator didn't have a RankingTree. I forgot to put that in.

[synkarius]

Well, I guess those 1000 generations weren't for nothing. Now we have some idea of the variance possible.

[synkarius]

Alright. So I made a few new branches. "pre_tree" is what we now have an abundance of data for... "intersperse" is my original technique. "mergesafe"-- a new idea I had based off of "high-frag"-- it preserves information perfectly like "high-frag" does, but creates about one branch per 5.5 characters on average.

I'll be testing all of these, but they should all get mergesafe's simulator updates or any testing done on any of them will be worthless. I'm going to start with mergesafe and "W + L".

[synkarius]

As I was working on this, I thought to myself, "we may as well do this right." This whole time, I've had limiters on SaltBot which were intended to make chromosome evolution more interesting. I removed them and got the following results:

30k matches / mergesafe       : g3    $57m
30k matches / mergesafe       : g45   $65m

I'm certain that the results have nothing to do with mergesafe being better than the others, and everything to do with Scientist being allowed to care about nothing else but win ratio if it wants to.

I was afraid this would happen, and though I've enjoyed working on RankingTree with you, I'm closing this issue because any work we do on this is basically irrelevant.

I've created another branch "high_frag", to preserve that version of RankingTree, and I'll leave all the other branches out there.

[reconman]

Right now the tree still exists in the master branch and is still being used. Is that what you want?

[synkarius]

I think what we should do with the dominated features (everything except win ratio), is put them in the information message. Win ratio and odds are already in it. Even though they are worthless in the betting decision logic, they're still interesting to see before every match.

[reconman]

You didn't answer my question.

[synkarius]

Sorry, you're right. Used to contribute to Scientist's decision logic: no.