The Nineteenth Byte

9:02 PM

I think I'm going to write up a multiplayer deadlock challenge

You each have a fork, and each of you needs two forks to eat your dinner. You get paired up with 2 other entries and can send one of say three simple messages like "Hey, gimme that fork." or "Here, have my fork"

And each round you can grab a fork next to you, place a fork next to you, or do nothing

Conflicts are settled as "do nothing", so that two people grabbing the same fork can't have it.

Peter Taylor

@Rainbolt There's an argument for starring posts which are useful rather than those which are just funny. </unrealistic_optimism>

PhiNotPi

Maybe a "pass the plate" challenge.

Where you are at the Thanksgiving dinner, and your goal is to get the food you want before everyone else.

Rainbolt

@PhiNotPi I was hoping to encourage teamwork instead of greed

Peter Taylor

@Rainbolt Can't you install it in a VM? Or is that still too dirty?

Rainbolt

@PeterTaylor Yes, and we have tons.

But that doesn't count as a whitebox test

We aren't allowed to pass whitebox testing without seeing it work on a very specific machine

Martin Büttner

9:08 PM

@PeterTaylor since your unrealistic optimism is unlikely to be satisfied, there's still the option of coming to terms with it, and just saving conversations if they are useful

Peter Taylor

I've seen an arguably worse situation with an installer. Another developer accidentally installed one of our products for desktop machines on our main server. And for some reason it won't uninstall.

Rainbolt

@PeterTaylor You're pretty good at reducing challenges into their mathematical parts, and you've been here a while. Is my idea similar to any challenge you can think of?

Peter Taylor

A dining philosopher's king-of-the-hill?

Rainbolt

Yup

Basically, is the addition of teamwork different enough from every other deadlock challenge?

Peter Taylor

The only related question I think I've seen is codegolf.stackexchange.com/q/20340/194

And that's really quite different.

TheDoctor

9:10 PM

hm

Rainbolt

Ok. That's enough encouragement to sandbox at least. Then we'll see if anyone else can find a closer duplicate

Peter Taylor

How do you envisage it working, in terms of knowledge about the other players? I suppose there's a possibility that it boils down to a slightly more complicated prisoner's dilemma.

Rainbolt

You can't be betrayed though. The only goal is to cooperate and get through each trial as quickly as possible

Let's say you run through three trials and it takes you 10, 15, and 450 rounds for your entire group to finish eating.

Martin Büttner

who wins?

Peter Taylor

Wait, so everyone in the triplet scores the same?

Rainbolt

9:14 PM

Yes, so we have to score you multiple times with different partners to get a meaninggul result

So let's pretend that we have 500 samples and that 15 is a good median

PhiNotPi

If I understand you correctly, here is how a sample game would work:

Rainbolt

10 and 450 represent the other 499 samples

PhiNotPi

There are contestants A B C D

Peter Taylor

Ok, that makes it a bit less prisoner-y.

PhiNotPi

So you do the trials:

A B C

A B D

A C D

B C D

Peter Taylor

9:16 PM

In that you both benefit from asymmetric options.

Rainbolt

That is an exhaustive list of all possible combinations

PhiNotPi

And if trials 1, 3, and 4 are the best, then C is the winner.

Rainbolt

Not necessarilly what I had in mind, unless I want the number of trials to grow exponentially

Well, from ABC you get a single number

Let's call it 10

A B D scores in 15

ACD in 20

and BCD in 400

So A has scores 10, 15, and 20

Meanwhile, D has racked up 15, 20, and 400

PhiNotPi

Yes, that's what I was thinking.

Rainbolt

So A would beat D in this case if we go by median

I think we could run hundreds of mini trials this way and get a much better median

PhiNotPi

9:20 PM

Are there going to be 3 bots per trial?

Rainbolt

Possibly. Could be more. If you count placing the fork, picking up the fork, and eating each as a separate action, then we're already talking about 10-12 rounds in a perfect game. If you add a fourth player, it gets a lot more complex, but a perfect game is still only 10-12 rounds

I think I'd like to keep it odd anyway. Among three players, only one person can ever eat, one person will be holding a useless fork, and the third will just be sitting there.

I think that makes it interesting enough

PhiNotPi

If there are three players per trial, then x^3 - 3*x^2 + 2*x is the number of trials with x contestants to play every combination.

We don't have to play every combination, just a reasonable fraction of them.

Rainbolt

Exactly ^

If you get randomly paired up 100 times, that should be good.

What are the odds that you got lucky or unlucky 51 times

PhiNotPi

Since each trial will probably be < 100 rounds, you can probably play many hundreds of trials.

Rainbolt

Yea, I guess the more the better

PhiNotPi

9:26 PM

I think that there may be more efficient methods than randomly grouping.

Rainbolt

Divide the entire group into pods of 3. The remainder gets to play with some premade submissions

Repeat

I think I'll title it "Give Me Your Fork So I Can Eat My Dinner"

Would you click that on the Hot Network Questions list?

PhiNotPi

Such as making sure that bots are groups with 2 other bots they've never been groups with before.

Rainbolt

After an infinite number of trials, doing it that way would be equivalent to random groupings, assuming the PRNG was sufficiently fair

Like rolling a die, you should get 1 2 3 4 5 6 an equal number of times by rolling a bunch, or you could force it to land on each one

PhiNotPi

If you make the (incredibly strong) assumption that the trial scores are a linear combination of the different bots, then you only have to do X trials and solve a massive system of equations.

A+B+D=15; A+C+D=20, etc.

But sadly, I have a feeling that won't work at all.

Martin Büttner

@Rainbolt Maybe if it wasn't in title case ;)

Geobits

9:36 PM

I think just Give me your fork! works well enough.

Rainbolt

Is it long enough?

PhiNotPi

@Rainbolt Since we aren't running an infinite number of trials, intentionally doing different combinations gives us more information than running similar trials.

Martin Büttner

@Rainbolt yes, 15 characters

PhiNotPi

That title seems fine.

I have to leave now.

Rainbolt

That makes sense, but I won't ping you.

So much room for improvement in the department of KotH controller code

Unique pairing mechanisms, outputting meaningful statistics rather than relying on Google Spreadsheets

Multithreading so that instead of timing an entry and then disqualifying it, I can just kill it when time is up

Maybe I'll build a class and distribute it here

Then I could say I accomplished something

Peter Taylor

9:43 PM

@Rainbolt You're not the first person to say that

Rainbolt

Is that so?

Peter Taylor

There was a meta thread all about it a while back

Rainbolt

It's also not the first time I've said it.

You never know - I may have sparked that thread

Peter Taylor

3

Q: Posting a challenge framework?

I'm a big fan of king-of-the-hill, and I'd like to see more of them. One of the problems is that they take a bit of work to set up and run. More than your average code-golf question, for instance. Creating a controller isn't that hard, but it would be easier (and thus have a lower entry barrier)...

Rainbolt

10:02 PM

@PeterTaylor Ok, you got me to look through two months worth of transcript and still fail to find the discussion I had about building a framework for KotH challenges.

Time to go home and make some beef wellingtons

Peter Taylor

I'm going through a long list of triangular arrays of numbers looking for combinatorial identities. There's potentially a CG question, but once someone spots the trick everyone will copy it.

Martin Büttner

@PeterTaylor like this one? codegolf.stackexchange.com/questions/24909/kolmogorov-mania

Doorknob

@PeterTaylor Like "Sink or Float." :D

Martin Büttner

@Doorknob that was my first thought, too, actually ^^

Peter Taylor

@Doorknob ?

Doorknob

10:13 PM

Never mind, "Sink or Swim"

38

Q: Do We Sink or Swim?

The Problem A doomsday scenario is described by three numbers on a single line, n, m, and p. Following that line are n lines with m values per line. Each value represents the total units of water each cell can hold. The following p lines describe the weather for the next p days. 1 unit of rain ...

Ah. Sort of.

dat ♦

The trick (not that it's much of one) reduces it to almost a dupe of codegolf.stackexchange.com/q/3815/194

TheDoctor

)_)

0

A: Make it look like I'm working

emerge @world full recompile on gentoo

Quincunx

10:29 PM

7

Q: Bounty-like feature on metas

Sometimes on a site's meta, I want to draw more attention to a question that has been sitting in the dark. Usually when this happens, I am even willing to offer my reputation as a bounty. But metas don't allow for bounties. On main sites, we have a bounty feature to allow users to draw extra att...

feature-request bounty per-site-meta

I put a bounty on a meta question about putting bounties on meta questions!

Doorknob

Ha

Ok, leaderboards for the Slime KotH are now up! :D

TheDoctor

^_^

overactor

10:45 PM

hi all

@Doorknob, can we see how the rounds went down?

New Meta Posts

11:31 PM

0

Q: Are we allowed to offer real-world prizes such as gift codes to the winner of a challenge?

Now, I was thinking recently, and I was wondering, are we allowed to offer real-world prizes, such as gift codes, to the winning user of a code-golf challenge or a popularity-contest?

discussion

Doorknob

11:59 PM

@overactor Yeah, I posted the scoreboard a few hours ago

Transcript for