The worst offender is a flood fill algorithm, from what I can tell.

path-finding can easily be cached, not much is gonna change throughout the journey. Finding adjacent white cell is easy. I have no idea what else are you doing

@Alion is it run a 1000 times each round?

No, 3 times.

are you looping like for (y ...) for (x ...) or like for (x ...) for (y ...)

flood fill over the board? The board is tiny

@tomsmeding Doesn't matter because flood fill is random access anyway.

fair point

depth-first or breadth-first

or unanswerable :p

@tomsmeding Breadth-first... ish.

you have a queue with region-border cells to visit?

Yes.

and are you popping from or inserting at the front of that queue, which I assume is implemented as a JS list?

then that might be slow :p

because it's gotta move the rest of the list with it

@tomsmeding No, I'm algorithmically sound, with a singly-linked list with start and end.

how are you doing a linked list in js :')

that doesn't sound like something that's performant in js, especially with the GC that will run overtime with many objects

Well, yeah, I showing the GC the middle finger on every step I make, unfortunately.

can someone confirm that this does the same thing as DFSBot: pastebin.com/6NEhcg3z

because its like a million times faster

managing the GC for writing performant code is a black art that I don't master :p

did you implement pruning?

yes

@tomsmeding I don't either. My entire bot is essentially a garbage factory.

I'm probably making MBs of garbage per frame.

Speaking of which, I should restart my Chrome because it's slowed to a crawl at this point, brb.

@SamYonnou it seems pretty different, in the same seed going in a straight line vs the published - in a circle

hmm let me test some more

oh

i think there might be a bug in DFSBot (at least I'm pretty sure its doing something unintentionally)

or no never mind my brain isnt working properly

> my brain isn't working properly

Me since finding this challenge.

Now my bot for some reason just stays before the target location and I can't figure out why.

Random tournament of 20 games.

This list excludes the slowest bots >1ms, for quicker results.

@dzaima are you sure? It seems to be doing the same thing with both implementations for me

replacing the continue in the pruning part with a shouldHaveSkipped flag and then printing out "oops" if the actual algorithm picks this route as the best scoring one and running a tournament now

ah that's because i messed up the original bots logic along the way :-)

God damn it. Another day, another Bug Of The Year. This time featuring wrongly ordered arguments.

Time wasted: ~1.5 hours

Is there some way to profile bot code?

oh derp thought an if was an else if

@dzaima this should do it: pastebin.com/wkTppSLj

You can use DevTools in Chrome.

I commented on his answer suggesting my pruning solution, hopefully he uses it

the correct version of hte pruning only reduces the time to like 14-15ms for me

but still a lot better than the 60-70ms it was before

saves a minute and a half per game

now to see what can be done about MC...

Very little I think

I'm busy with it myself, but feel free to look :p

im gonna try reusing arrays instead of creating new ones in the loop

@SamYonnou am I correct in thinking that your changes change the amount of Math.random calls? That'd explain the differences in seeded games

@dzaima oh yeah it will reduce the number of those

@tomsmeding reusing arrays helps a little bit, down from 52ms to 42ms for me

doing this: pastebin.com/t7chi28v

I'm this close to getting the main functionality of my bot working.

pretty sure it doesnt mess the bot up... but my track record isnt great at that :)

Right now I'm wrestling with my travelToList function (that returns an array of travel directions sorted by how close to the target they are), but I can't seem to remove the horizontal bias, meaning that my bot goes left-and-right constantly if the target does that as well.

@Alion randomize which direction is done 1st

@dzaima No good, would help a little but not eliminate the problem.

@Alion why would there ever be anything that'd get past that

@dzaima Literally encountered that as a first case, which is why I'm working on it.

I have to tiptoe to not give away the details of my bot, lol. Maybe I should stop...

@SamYonnou 2 games finished equally (except in time :p)

My goal is to have a function that makes the bot travel towards the target along the axis that has the longest path.

@tomsmeding also the const lastDir in your randomStep method isnt actually used for anything as far as I can tell, but removing it doesnt really affect the time by much (maybe 1ms faster)

(1,0) to (5,1) first travels along x until it is at (4,0). And it has to be consistent.

Then it's fair game, it can be either (5,0) or (4,1). Just that first condition has to be satisfied.

I already have a function that does that, but it doesn't return a list sorted according to those rules, only the first direction.

Chebyshev distance can probably save me here, but I'm not entirely sure how yet.

Added this into controller.js (runBots()) to measure slowest bots.

@Alion I used if (Math.abs(myX - target[1]) > Math.abs(myY - target[2])) { to decide if I should go horizontally in one of my bots, not sure if it actually helps but ¯\_(ツ)_/¯

function travelToList(goal, start = me) {
    const relative = sub(goal, start);
    return [...realNeighborsOf(start), start].sort((a, b) => (chebyshevDistance(a, goal) - chebyshevDistance(b, goal)) * gridSizeSqr + (distance(a, goal) - distance(b, goal)));
  }

Here's what I ended up with.

@SamYonnou thanks for looking at it! The lastDir stuff I found as well, but I didn't think it'd matter so didn't bother to remove it yet

If reusing arrays actually helps, sure, I'll look at it in an hour or two

It seems to have helped but who knows, maybe there was some background process on my computer that was screwing with the performance of my browser

@SamYonnou I too saw a 10ms improvement

you can also try to do some magic with the random number generation

since you never actually use all of the random bits

you only need 6 bits for the < 0.95 part and 3 bits for the random direction part

but doing that will be a royal pain in the you know where

and according to the internet most browsers use a pretty fast RNG so it might not help that much

ouch

Managed to optimize a bit also.

I've already got something interesting working, but for now it's woefully retarded.

I don't know if I should submit or not.

@tomsmeding what about keeping track of the change in score during randomStep and not having to do calcScore every time?

this pastebin.com/9tb6UzFF is about 26ms for me down from 42ms

but I haven't tested it for correctness :-)

you can also try to get rid of having to copy anything at all, but that would require keeping track of all random moves you make and then undoing them at the end of the loop

probably not too too hard, but I don't really want to try it, but you're welcome to :-)

@SamYonnou doesn't seem to do the same exact things as the posted one

the change shouldn't have affected any RNG so thats a bad sign

in fact it looks stupid (don't know if the original is stupid though)

(stupid as in doing nothing repeatedly standing in unpaintable area)

looks like there is a new version of MC up anyway

er or maybe I just clicked on a different bot by mistake, disregard :-)

According to this, the following code doesn't produce uniformly random results?!?

// DO NOT USE, BIASED LOGIC
function randomInt(min, max) {
  return Math.floor(Math.random() * (max - min)) + min;
}

It's literally, character for character what I wrote D:

Well, I don't care enough anyway so I'm gonna stick to my own implementation.

it shouldn't really be any more biased than Math.random() itself

generating 10million numbers in [3, 7) gets me [2500666, 2497163, 2500765, 2501406]

maybe they mean its biased because of floating point error but that shouldn't come into the picture unless your [min, max) is massive

No, it's because the total range isn't divisible by (max-min)

So min is slightly more likely than max

@Spitemaster why would min be preferred though

do you mean the version that uses modulo? i was talking about the version that just uses floor

Oh yeah, I was thinking about taking the last few bits. But it's the same kind of issue.

That is, not an issue in anything but cryptography

@Spitemaster except that the last few bits are actually at least 32, making the difference practically 0 unless you're generating gigabytes of random data

Yes. That's the point.

and I wouldn't want my browser generating gigabytes of random data so there's no point in not using that anyways.

@SamYonnou I've saved your last version; later this weekend I'll either use an improved version of the current MC (using your work of course), or the one I'm trying to develop here

the last version that was trying to compute the scoreDelta apparently had some problems, so might need bugfixing before it can be used

@tomsmeding this version seems to work fine and does speed up by ~10ms

@SamYonnou That version is now live. Note that I flipped the arguments to copy2D; maybe I'm just too used to C to not have (destination, source) :p

Hm... I don't know how I'm going to name my bot.

Maybe it's slightly too early to be thinking about that, since projected delivery time is 2 days away, but still.

I should probably name it something evil, since it is evil.

I thought of the names before making the bots ¯\_(ツ)_/¯

I usually do that as well, but this time my idea was so different and so spontaneous that I didn't have the chance...

you can always call it EvilBot5000

9000 is better clearly

I wanted 5000000 but that sounds a lot better when read aloud than it looks on paper

you can always test whether the controllers have unicode support and throw in some ARABIC THOUSANDS SEPARATOR's in there, à la 9٬000٬000

@tomsmeding well there already is the ¯\_(ツ)_/¯

fair point

Bots may work together but must not communicate with each other

does that include communicating in game e.g. by performing some predetermined set of moves to identify one another?

@SamYonnou I'd guess not, I think that's just meant to address communicating with localStorage

you can't really work together without communicating :p

@dzaima What do you mean?

you can kind of work together by just having the same goals, or goals that complement each other somehow

Oh, didn't catch context. Nevermind.

Someone about this competition:

Because we're not assholes and don't want to make the tournament unrunnable, I guess.

that was my response too

implicit rule "don't be a jerk"

I'd definitely want to see a theoretical, non-competing entry, though.

that would be interesting for sure

That just calculates literally all options until the end of the game to find the optimal game.

And then some rudimentary calculations that estimate how many lifetimes of a universe it would take.

And how many more atoms we need in the universe if we could fit 1 GB of data into each one.

@Alion with a DFS there wouldn't be that much storage needed, just time

@dzaima Was about to say, we could probably get away with some decent space constraints, yeah.

One game step can have, on average, 9.31e20 outcomes with 30 players present.

That's quite your branching factor.

Windows calculator reports an "Overflow" when calculating that to the power 2000.

@Alion you can lower that quite a bit by simulating the other bots and once you know who is who, get only the moves the current state can allow

@dzaima But that won't automatically adapt to new entries, right?

@Alion if some entry doesn't match any entries pattern, just go with all directions

What if an entry uses Math.random?

@Alion I implied trying all relevant values in "get only the moves the current state can allow"

Back to the full brute-force approach - it would take no more than 1.586e+41938 iterations to compute the optimal game for 30 players for 2000 moves.

@kenorb FarSightedGreed is a slow bot?

@Neil It's quick, will include for the next time.

thanks

Now I can't help but wonder what the optimal strategy is.

@Alion by some reason that gives me the idea to make Jim prefer to not go near places where other bots have been in the past ~50 moves

@dzaima That actually sounds pretty good.

jim already does that with himself, no idea why I didn't think of extending that to everyone

@dzaima There is a stray console.log when Jim decides to ignore a troll.

@HeinWessels yay fixed

I slightly updated LittleBrother to try to confuse John. Might improve it tommorow

@HeinWessels that made it clear a lot less of Jims colors, which is even better :p

Yeah, just saw that XD I think I fixed it though

Nope, not fixed

heh

also, there is no good outcome for little brother. If you make Jim not detect little brother, that's good because it'll go away by itself without extra help. If it does get detected, it gets killed anyway

oh ಠ_ಠ I made a John detector for Jim but never got around to using it anywhere

My idea is that I wait next to Jim until he moves again, and just continue following him. But yeah, trollers are actually kind of lame. Next time I want to write something that can actually compete

I just tried to take it easy with my first KOTH

Oh no, I should've went with OOP from the start. I didn't, and now I'm paying the price.

Okay, it's actually a non-problem, but it very well could've been.

Alright. I'm done for today. I have managed to set up everything needed to start working on the bot behaviors.

Well, aside from testing everything, because that can only be done with the behaviors in place.

And with that I'll be going. See you guys tomorrow!