@trichoplax I'm working again on the KoTHComm (working towards making it a server). I'd love your input on several matters

I've only made one KotH so far but happy to give whatever input I can...

1. Keep 6 running totals of games. Call them 6 buckets. The first game played contributes to the 1st bucket, the second game played to the 2nd bucket, ..., the sixth game played to the 6th bucket, then the 7th game played to the 1st bucket again. Each one has a total score and a total number of games, so you can work out the average score per game and put the players in order. If two players are not in the same order in all 6 buckets, then they show as joint place

Equivalently: Run 6 ongoing tournaments and only declare a player sole 1st place when they are uncontested 1st place in all 6 tournaments

and if you have bigger differences than that?

like what if the ordering was A B C D in one bucket, but C B A D in another?

I tried a few approaches to automatically determining when places can be confidently considered distinct, and this is the one I was happiest with

It doesn't matter - you just compare pairwise.

...what would it show?

is B the unambiguous 2nd place?

If that makes 1st and 2nd positions joint place, and another bucket makes 2nd and 3rd positions joint, then all three will be joint 1st place

is A and C tied for first?

(B is in the same position both times)

ABC are 1st, D is 4th

Ok. I asked this question on stats.SE, and they gave me a similar response

I can't remember the code exactly, but I think it starts at the top and checks if anyone lower is ambiguous, and if so makes them joint 1st.

You can't say confidently at this stage whether B is higher or lower than A, so it's not about exact position (2nd) but relative position (not confidently above or below A). And same for B and C

makes sense

It means in a tournament the first 100 games can easily be all joint first, even though 27th place is much lower than 1st place, because there is a chain of ambiguities that prevents drawing a confident line between any two players

It doesn't need to be 6 buckets, I just arbitrarily settled on less than 5% chance of putting a given two players in the wrong order confidently, and 6 is the minimum required to give a probability less than 5%

yeah, that's going to be a parameter for the tournament

I guess if you input a confidence level it should be possible to automatically decide how many buckets. Don't ask me how at this time of night though :)

When I worked it out for 5% months ago, I did it just based on two players, but I believe the result holds

It's coming back to me. I worked it out for the worst case where the two players are identical (paste in the same code for both players, then they should always be joint place).

For N buckets, what is the probability that two identical players appear in the same order in all N buckets (and therefore are assigned distinct places incorrectly)

so, there's a 5% false positive

that doesn't say anything about false negatives

(that said, false positives are far worse)

Yes it only considers false positives. They could well stay joint for a very long time (arbitrarily long if the players are arbitrarily close)

anyways, I think I have enough information to continue on that front

next up: I plan on taking scoring and selecting players out of the controller. The only code you will write is actual game logic. If I pass in a list of strings (representing the source code of each of the players), and you return a list of scores, does that sound reasonable?

I've taken the approach of waiting for a distinct 1st place and then posting the leaderboard with other places still joint

"You" being the controller writer for the specific KotH that is using the framework?

yes

And the controller writer can still choose what confidence level to use when running the framework?

yeah, there are going to be lots of parameters you can choose. How players are chosen, how scores are generated, etc

Sounds good then

I should mention in case you haven't seen it: codegolf.meta.stackexchange.com/questions/13891/…

Dave's controller runs my KotH much faster than my controller

It's in JavaScript, but might be relevant

oooh, I haven't seen that

do you know why it runs faster?

it still runs them locally, right?

It uses JS magic well beyond my knowledge. Not sure which makes the biggest difference, but it uses web workers, better function return caching (memoisation) than I'm using, and runs several games in parallel during a tournament.

(embarrassingly I forgot to implement caching until fairly recently, despite forcing the ant functions to be deterministic - it sped up over 10 times when I did)

Yes it's still a static webpage - I don't think Dave's has a back end

ooooh....I'll need to pass you in some form of random seed

to allow determinism

bah, except that gets messy with JS as you can't seed Math.random

Yes it has seeded random for debugging so you can get the same results every time (so both my controller and Dave's had to implement a random number generator as JS doesn't provide a seedable one - I went with xorshift)

For tournaments mine uses cryptorandom

For my KotH the seed was only needed for the controller front end to allow a player to debug their entry. The ant function itself was not passed any random seed as they were forbidden from storing state (including calling a random number generator since that stores a state that updates each time it is called)

The randomness was used to rotate the 3x3 view that was passed to the ant function, so it would never know which direction it was facing

ok. Last question, regarding visualization. Since games are running on the server, I need the ability to send the game state over to the client to be rendered. How much work would that be, to serialize and deserialize the state of the game (after each turn)?

I have much less back end experience...

nah, that's not what I'm asking

For my particular KotH, it's an arena of 2,500 x 1,000, and each cell can be empty, food, or and ant of one of 5 types and one of currently 27 players

if your controller needed to output some JSON each turn representing the state of the game, how hard would that be to write?

JSON.stringify...

and similarly, you would need to write a function that would take that JSON and make it pretty

you have your entire game state in a single variable?

JSON.parse...

If it's in more than one, you just put them in an object and then stringify

I don't know how efficient that is, but it's easy to write

do you have any variables stored in a closure, or anything?

because you can't stringify a function's closure AFAIK

If you're sending after each turn then I'm guessing that can be done fast enough for viewing at a reasonable speed, or you could send every nth turn if the viewer requests faster

I'll actually be running these games independent of the viewer

so you can watch them at any time

I have closures for the caching and the seeded random

and go forward or back in turns

If you store all the turns that won't be a problem as you won't need to send any functions - is there another reason?

I'm just trying to gauge how difficult it would be

For your question 2 (from the start of this conversation) would each KotH be either JavaScript or Java, or will some have both?

the controller must be in one or the other

and (at the start) submissions will need to be in that language

I already have code to allow cross-language communication in Java

I don't think writing code would be difficult but I don't know how fast it would be to send a large game state

so that wouldn't be too hard to add

I don't know what Java can do in terms of evaling code.

I know Java. I'm confident I can do what I want in Java

my current KotHComm already adds players via eval

For JavaScript, I've gone with a masked eval that shields the function from global variables but isn't strong sandboxing. I think Dave's controller has better sandboxing but I haven't looked at how it works (possibly the web workers)

The impression I get from the chat in my KotH's chatroom is that my code is simpler and easier to understand, but Dave's code is much more effective if you can get your head around it

isn't that true of all faster code?

This was only my second real JavaScript programme, and I'm still learning, so my code has lots of room for improvement. And Dave's isn't just faster - I think it's more secure too...

I don't know how much effort you'd want to put into caching. For my KotH it made a huge difference, so tournaments now get a unique 1st place in days rather than months, but I'm guessing the vast majority of KotHs won't have deterministic functions

So KotHComm sits on the server. Is the controller code sent to the server or does the controller communicate remotely?

I can't do anything with caching

the controller code is also on the server

So the controller is passed the player code and runs a single game and returns the results, but the server can also pass single turn results back to the client machine?

Is this live or after the game has finished?

I guess it could be live

but games typically go really fast

I mean, how long does a single game take of formic functions?

Mine was taking 20 or 30 minutes before I implemented caching...

Now about 2 or 3

(On my machine, which is fast)

for a single game?

that's crazy long.

It's 16 players per game, but each queen can produce many workers, and the ant function gets called independently for each one. Some of the more advanced players produce hundreds of workers, so there can be over a thousand workers running around in some games

how many turns?

Dave's is faster - I haven't measured it with the newer players but it should be a big difference. I'm thinking of implementing better caching in mine to try and speed things up. I have a bounty coming up some time next month so I'd really like to be able to finish a tournament in a day rather than a week

30,000 turns per game

so, around 30 million function calls

2,500 pieces of food on the arena, so that's a theoretical maximum on the number of workers (and there is now at least one player than can regularly cover the entire arena)

Probably less than 30 million in most games

They have 5ms per move but most use far less, even before caching reduces it further

so, I've done a bunch of timing tests in Java

that equates to about 30 seconds

(in Java)

Is that just for raw function calls without content?

yeah

JavaScript has got pretty fast then...

Even with caching there's logic

...what are you caching?

if a function call is the same, you don't call the move() function again?

The ant function takes a view and returns a move. If the view has been seen before I don't call the ant function but just return the stored move

yes - you beat me to it...

that means we're talking around 5 to 10 times faster for Java vs JS

well...maybe not

were some of the bots super slow?

bah, I'd just have to do the test myself

Mine just stores stringified views and uses hasOwnProperty to look them up. Dave's hashes the view to an integer and uses it as an index into an array - which I'm thinking of implementing next to speed mine up

Bear in mind we're comparing my inefficient controller. I'll run a tournament in Dave's now and see what the average time per game is after a few minutes

anyways, the last thing I need to iron out is the process of executing code. I need to make it easy for the developer to write the controller, easy for the player to write a submission

I want it so people can run this stuff locally without having to run a server locally

Just checked and it takes about 2 minutes to finish the quickest of 5 games on Dave's controller (although it is running all 5 in parallel using some kind of web worker magic)

So it seems it's not as much faster as I'd thought (games have slowed down recently with a few players who produce huge numbers of workers)

Do you want the player's code to be picked up automatically from the answers?

@trichoplax yes, I've already got code that does that

I'm impressed by the self moderation in your room :)

it's my menacing demeanor

@DestructibleLemon I don't know which would be the right room for that but it sounds fascinating - feel free to ping me from TNB if you find or make a room for it

yeah, I'd provide some input as wel

I tried to get a koth room going but it keeps freezing even if it gets unfrozen

I was thinking bots would have no memory, so you could even memoize certain game states

I don't particularly care if you discuss it here

cool

so, if I understand it correctly, the bots output their desired outcome?

but there's a chance that it is different?

no, the bots output an action, just like a regular koth

or do they output the percentages?

but it's perfectly deterministic due to the koth controllers method

@NathanMerrill Sounds like making it easy for the players is already covered if all they have to do is write code. I suppose making it easy for them to test their player against the others without having to post an answer first is important

like a regular probabilistic koth, but with the many-worlds hypothesis basically

@trichoplax exactly. They need to be able to run it locally

I still don't understand: Where are these percentages coming from?

So the server wouldn't cater to running tournaments for all the players, just the official tournaments for leaderboards?

so like, if an action had a 30% chance of succeeding, the controller would run the game both as if it succeeded, and as if it failed, then multiply the resulting score of the game where it succeeded by .3, and the score of the game where it failed by .7, and add them together

So you have moves A, B, and C, and each does one of two things with some probability?

the bots don't do anything related to probability manipulation

@trichoplax sort of happens in many koths though doesn't it

action might be attacking, for example

even if I did offer a "run for my submission" option, it wouldn't be the same. Many people would prefer not to have to wait for the server to run their code before fixing bugs, etc

(myself included)

Ah of course - running locally will probably be quicker than waiting for the server even if the local machine is slow, just because it only has to handle one tournament

i'd also probably try to limit the amount that bots try to use their own rng, because that would make it non-deterministic

I don't plan on making a single game fast either on the server: I just plan on running lots of games in parallel

@DestructibleLemon I generally ban RNG, or provide a seeded random

You could supply them with a RNG that works many-worlds style, if you don't mind waiting a very long time for the game to finish...

the random variable would itself introduce chance, even if it's seeded

because while it deterministically figures out its random numbers, it's by chance that it succeeds or fails deterministically

given the same seeded random, there's no way for the function to output something different

bah, there are two different randoms going on here

i mean, technically not random, but it has the same feeling in a lot of ways

Can the players infer from the world they are in that their opponent must have taken a different action in, say, twice as many other worlds based on the action they just saw them take in this world?

if you're going to make actions randomly have different effects, I'd lean against providing the players with additional randomness

^

if they want randomness, they should use the built-in one

That's what I did for mine, and they have used it effectively in lots of interesting ways

well you see, if i only use the binary choice probability, that's two game states, but an rng will have more than 2 outcomes

that's my main issue

If the binary choice doesn't have 50% probability for each, then you multiply the number of worlds by more than 2 each time

because the result will be entirely deterministic by force

evaluating every outcome

@trichoplax no you don't?

...evaluating every world is expensive

consider a single turn for 10 players

@NathanMerrill it is... which is why an rng would make it work

Oh no you still just run two and multiply by the probability - I got confused

that's 2^10 worlds instantly

I was thinking it would be feasible with a game which has the ability to memoize

the only issue... convergent sums

you can memoize functions, but how do you memoize game state?

Maybe if your world is small enough that the results overlap and can be culled

ok maybe not memoize, but i mean... you could use game states multiple times, if there are multiple ways to arrive there

if that's the case, then you don't have an interesting KoTH

Mine worked with memoisation because the view of each ant was so small. Depends how much information each player is supplied with

because those KotHs are easy to solve

i have no actual ideas though

think about it: if the total number of possible states is low, then you can solve the game by iterating through every possible state

ok so what i'm thinking is

if the total number of possible states is high, then there's no way you can generate them all

say you have two tanks firing at each other, each having a possibility of failing

I'm not convinced that a world that often converges on the same state will necessarily make for a trivial game. I'm not sure how to reason about it though

if they both fail to hit, and have no memory, they have the same state as two turns ago

@trichoplax I mean, I could conceive of a game that follows some sort of exponential distribution for states

but i mean, you could fail to hit, then hit, and end up in the same state as if you hit, and then failed to hit

where certain states are far more common, but the interesting ones are less common

@NathanMerrill I'm thinking that if you don't control which state you move to next, and the choices you make lead to several parallel paths, then the wider game over many worlds may still be non trivial

if you have health, its true that you can't get to a state with more health, but further down on the tree, two states could be the same

Assuming the player never sees the many worlds overview

like how you can end up in the middle of one of those binomial distributing thingies with the marbles

regardless, if it is possible for a computer to calculate all of the possible outcomes of different actions, then my solver can do the same thing

And health wouldn't prevent memoisation if the player is unaware of their health

it's literally the same code

@NathanMerrill What if what you see your opponent do is one of the two options for choice A, but also one of the two options for choice B, so you can't tell whether they chose A, in which case the action you see them take exists in only 10% of worlds, or they chose B, in which case the action you see them take exists in 90% of worlds. Still not sure if that doesn't become trivial with more thought though

Back to the server idea: Do you have any plans to support Japt? I was wondering if someone would make a Japt KotH following the success of JS KotHs, since Japt compiles easily to JS (and this can be done in JS)

no plans, but I wouldn't be against it

@NathanMerrill are you saying that it's trivial to make a solver? i think that's inaccurate, because it's not solvable just because everything is evaluated

your solver would have to evaluate every possible choice

which is more than the controller does

I'm guessing if you support JS then someone could just include the compilation step in their JS controller, but it might be quicker if it were built in server side

it only splits by 2 every time, and some of those games possibly exist

...I need to go. You can keep on talking to to me, but I'll reply in a bit

Sure

I think the main issue is making the program calculate potentially convergent sums

because it's possible for the bots to never deal any damage

that's possibly an issue

I don't know if it will turn out to be possible to make an interesting KotH out of this idea, but some of the most interesting things on PPCG started out with ideas that were obviously impossible...

I don't know what you mean by convergent sums

i mean

it's possible that a game state could possibly lead back to itself with a low probability

Would you not have a fixed number of turns?

or not so low

@trichoplax mmm i guess that's a decent idea

except it messes with my idea of sharing outcomes somewhat

but i think that might be the best idea

do bots have access to the game turn?

Either that or make turns monotonic (so you can only move in one direction score-wise - you can end up in the same state by different routes, but never get back to a previous state)

you could speed it up if they don't

i think that it's probably possible to calculate convergent sums

it's trivial to detect, as well

the only issue is i have no koth ideas

@DestructibleLemon In my KotH they didn't, but I deliberately wanted a very low information game - they didn't even have access to which direction they were facing. For yours it could work either way

true

If you have a score/health/whatever that starts out at 100 and always decreases each move, then the game ends when it reaches zero in all worlds. That still allows different worlds passing through the same health after a different number of moves (useful for caching), but a given world will only pass through a given state once, as it's health will be strictly less in all subsequent moves

If the health decreases by between 0.1 and 1.0 each move, then the game will take between 100 and 1000 moves per world

If there are only 2 players per game then you can terminate a world as soon as one player reaches zero health

i think making the turn number invisible will allow some time optimisation, even if some of it has been removed by having turn numbers

but i mean, it would be undecideable whether or not the game was ever going to end in some game types if that didn't happen

You could also use a Monte Carlo approach rather than following every possible path. For enough samples it will get arbitrarily close to the same result

yeah but... the entire purpose of this idea is that it isn't monte carlo

@DestructibleLemon this sounds like a KotH idea to me :)

most koths are monte carlo

@trichoplax no idea for the actual game part

only a constraint, which i guess breeds creativity or whatever the saying is

I like games with very simple rules - you don't necessarily need to add much beyond what you already have. One of the KotH's I want to make is incredibly simple because I had an idea and then just stripped away all the complexity until it was as simple as I could get it without being trivial to win.

I hadn't heard that saying, but I've long thought that constraint was a good way to come up with more ideas - so it rings true

@trichoplax the only thing i've said about actual game rules, is a tank example

i could use that maze idea i had possibly

i was planning on removing the look action and stuff

Would you want something on a grid or in continous space?

the maze idea was on a grid

So you just need to think how movement on a grid can have two possible options for each choice of move

no, i think you've misunderstood me

the bots don't do anything different from a normal koth

it's just that any time a probabilistic action occurs, like the possibility of succeeding on an attack, it evaluates both possibilities

No I get that. So for example, you could choose how many grid squares to move in your turn, knowing that the probability of succeeding is 1/number of squares you move. So you can choose to move one square, with no probabilistic split, or two squares with a 50% chance of failure, or 10 squares with a 90% chance of failure. So the bot just either succeeds or fails each time it tries to move, but the controller tracks many worlds in which each of the two possibilities happens each move

not everything needs to be probabilistic

if i have everything probabilistic it makes the computing power required go up a lot

I understand the controller will run a lot faster if there are only occasionally probabilistic splits :)

But if there is a lot of splitting then predicting the outcomes will become intractable, so it might be feasible to have much shorter games

(and still give the players zero chance of brute forcing it)

as for brute forcing, it has the exact same issues as in any probabilistic koth

it doesn't necessarily need to be two options, it just needs to be not many options

so, if an option has 4 possibilities, it's not that bad

Worth thinking about how you combine the many worlds into a final score too. My ant KotH rewards consistent performance over good average performance. If your score is the best achieved in all the many worlds, the leaderboard will have the players in a different order than if your score is the average achieved in all the many worlds. Then you could weight the average too if that makes brute forcing harder

i would pick the average

otherwise the battles would be nonsensically optimising for best possible

because everything automatically succeeds, and your opponent automatically fails, which makes it very easy to get a good score

For the ant KotH the score is based on the order of players in that game, but not on how much they won by. So a player who occasionally wins with a huge margin does not appear as high up the leaderboard as they might expect, since they don't get any additional reward for being further ahead, only for how many times they are first

Although the bot never knows the difference between a monte carlo KotH and a many worlds KotH, I'm trying to think of a way that it would make a difference to the player writing the code for a bot. That might give some clue as to what would make a good contest

i could do highest average score, or i could do the same as in the ant koth, except i'm not sure how your algorithm works

and depending on how quick games are, it could be 1v1 or something

which means calculating who is more likely to win is easy

if you want consistent scores, then the median is a good way to calculate that

i think that it might be more about victories than scores

I like median over many games, but I'm not awake enough to think what median over many worlds would do

The ant KotH is an analogue of counting victories rather than scores.

@NathanMerrill i think that if a bot wants to trade off for possibly high scores, it can do that, at the expense of other possible scores

Except extended for 16 players per game

being in a many-worlds koth means it's consistent by default

i think you could count the median in many worlds... just that it doesn't really make that much sense, or does it...

like, your median score could be from different worlds from your opponents, which means that decreasing your opponents score, at the cost of your own score, is an option

@trichoplax i know how you would implement it though

basically, organise possibilities by score, with possibilities having a width of how likely they are, then take the middle. easy to implement by the way

It's possible to make median work with many worlds

yep, exactly like that

but it's possible they meant they don't know the implications

@trichoplax Oooh...I know how to do this.

the only issue with median, is that it isn't recursive

which can be solved, but it's not as nice

because you can do weighted averages with weighted averages

what about having a mode, or something

mode can be really variable

yeah

I'll write a different KotHComm for each language

so, it my JS KotHComm wanted to support Japt, it'd be easy

and I can make KotHComm run solo so that people can run locally