Increase food score when more in same direction

[brookstalley]

Description

• Add second phase to food cluster scoring that increases score when more clusters are in same direction
• Add indication of what clusters were considered to visual debugging

  TESTING STAGE

That doc seems to be empty. Currently getting average of 1792, median 553 across 10 runs.

Types of changes

• [ ] Bug fix (non-breaking change which fixes an issue)
• [x] New feature (non-breaking change which adds functionality)
• [ ] Breaking change (fix or feature that would cause existing functionality to change)

  Checklist:

• [x] I have read CONTRIBUTING.md
• [x] I fully understand the Github Flow and I'm merging into the develop branch , which is the default branch, and not the master branch
• [x] My code adheres to the code style of this project but most importantly of all to the things mentioned, which I have read, in CONTRIBUTING.md
• [x] If my change requires a change to the documentation, I have updated the documentation in /docs accordingly.
• [ ] I have included the results of the test required.

[ermiyaeskandary]

@brookstalley Link updated - sorry for the inconvenience...

[tjorim]

Looks good at first sight, my pc is currently testing this. May I ask why you opened a new PR? If it's just for the extra commit: when you push commits, the PR would be updated automatically.

[brookstalley]

Sorry for the extra PR; had a total meltdown with line endings and practically had to do a PC rebuild to recover.

[brookstalley]

Updated the algorithm... fixing a bug turned out to be a mistake. The current approach (mistakenly) treats food that is past the proposed target cluster as equally valuable with food that is straight behind the snake. I think it creates a more timid snake willing to turn around on a moment's notice.

Stats from 48 games: a: 4880, m:3220 [18553, 15885, 15603, 14712, 13886, 11631, 10320, 10041, 9505, 8568, 8247, 8246, 8192, 7161, 6319, 6261, 5764, 4836, 4647, 4513, 4428, 4353, 3826, 2614, 2597, 2201, 2001, 1656, 1247, 1168, 1052, 942, 692, 692, 691, 674, 577, 505, 279, 279, 279, 249, 180, 175, 175, 28, 21]

[tjorim]

Been running for 6 hours (13 games), average: 9812; median: 8920 [32199, 18557, 16456, 12197, 11741, 10053, 8920, 5305, 4551, 2810, 2296, 1515, 951] This was before commit 9329031.

[j-c-m]

@tjorim what is your ping to the slither.io servers?

[tjorim]

@j-c-m 5 servers pinged, average = 28.4ms ping 149.202.210.66 Minimum = 27ms, Maximum = 29ms, Average = 28ms ping 149.202.217.65 Minimum = 27ms, Maximum = 29ms, Average = 27ms ping 149.202.197.192 Minimum = 29ms, Maximum = 37ms, Average = 31ms ping 149.202.216.146 Minimum = 27ms, Maximum = 29ms, Average = 28ms ping 149.202.216.9 Minimum = 26ms, Maximum = 29ms, Average = 27ms

I had 1 window with 1 tab open and active/focussed, drawing not disabled (so like when a real user would play).

[ChadSki]

Great idea! I see how this could make the snake pursue linear clumps better.

Don't forget to run tests alongside a reference version, so we can see how it does in comparison! Scores can be different at different times of the day.

[j-c-m]

@tjorim thanks, I think latency (ping) to the server may be a huge advantage this make sense as I don't think there is any prediction.

@brookstalley check your ping as well. Also check the time of the computeFoodGoal() function before and after using console.time() and console.timeEnd() around some bigger snake deaths, delaying the collision checking for to long with food can be deadly. I had tried to incorporate something into the food algorithm that would increase the score of a cluster by the food behind it, my first pass was too slow but I think this is similar.

[brookstalley]

Ping times to servers I get assigned (usually in the 206.191.155/24 and 63.251.227/24 range) are about 60ms. To the servers that @tjorim posted, ~170ms.

@j-c-m excellent point on the timing issues with big snake deaths. That will especially be a problem when we are a smaller snake, because the food cluster size is smaller, therefore more total clusters. Right now the whole computeFoodGoal call runs about 3.5ms on average, but I've seen it run as high as 30ms for a while (and definitely more snake deaths when that happens).

There is probably an optimization around only scoring a subset of potential future food. Maybe using the FPS target and measuring how long scoreFood + scoreFoodBeyond take, and then only checking as many as we can in our time budget? The main computeFoodGoal loop would become something like:

var step = 1.0;
if (window.foods.length > (measuredFoodPerMs * targetFoodCheckMs)) {
  step = window.foods.length / (measuredFoodPerMs * targetFoodCheckMs);
}
var start = performance.now;
var checked = 0;
for (var i = 0; i < window.foods.length && window.foods[i] !== null; i += step) {
.
.
.
checked++;
}
var end = performance.now;
measuredFoodPerMs = checked / (end - start);

(with less ridiculous variable names and sorting out that i will be a float, just using that for illustration). What do you think?

[ermiyaeskandary]

@brookstalley Join the gitter chat in the readme!

[Seple]

Super! :+1:

[alexzeit]

Please have a look to the angle based food search and rank algorithm, it is simple and consider the food in the same direction by default: https://github.com/alexzeit/Slither.io-predator-bot/tree/collision-detect-simple