Let's invent a new game!

It all started as all good things start these days : on irc.ⁱ

cads Hey guys, are you familiar with the multi-armed bandit problem?
mircea_popescu Yes.

moiety I thought most bandits had multiple arms.
mircea_popescu It's a formulation of the explore/exploit dilemma.

cads moiety: A one armed bandit is a slot machine, while the multi-armed bandit problem considers the best play in a situation with multiple slot machines with uncertain odds.
mircea_popescu Like suppose you're naked outdoors circa 4500 bc, and very hungry. You find a bush with berries. How long do you spend grazing and when do you leave looking for more bushes ?

moiety When you have collected them all from the first.
mircea_popescu Yes well, it gets more complicated than that.

moiety I know sorry I couldn't resist.
mircea_popescu God forbid someone marries you.

moiety I think we can all safely assume thats not going to happen.
mircea_popescu Attn all present JPM bankers: the girl won't leave till she's bled you dry!

moiety LOL!
mircea_popescu heheⁱⁱ.

asciilifeform Re: multi-armed bandit: http://lalandlab.st-andrews.ac.uk/tournaments/tournament1/sociallearning.html This is old news; 2nd tournament is mostly done now, too.
mircea_popescu Basically the appeal of Civ was exactly this.

asciilifeform Contest inspired by Axelrod's prisoner's dilemma tournament.
mircea_popescu You know this inspires me ? One could formalise the problem with strings.

asciilifeform They sorta did.
moiety That's just along the road from me!
mircea_popescu Hear me out : you define actual words in the dictionary as "good stuff", and each player gets a selection of poems to complete. Words themselves are worth points, filled lines are worth more points, filled poems even more. Then you give everyone strings, and they can read one char at a time for a cost. Or skip the string, for a larger cost. Obviously player can only eat a word if the whole word has been read.

asciilifeform This sound like fun, but the contest was a robot-writing one rather than between players directly. The final reports are worth reading.
mircea_popescu Yes yes! You have to write the scripts for this, I was just describing what your bot is supposed to do. Well not your "your". One's.

asciilifeform What's the goal? To reproduce the poem before the other players?
mircea_popescu Get most moneyz. The key here, of course, being that the strings are not all created equal. Each string has its own per-character entropy, from epsilon to 8-epsilon.

asciilifeform 'Read one character at a time' << from another player's slate?
mircea_popescu No, the string is in the middle. "All players get copies of the same strings" say.

asciilifeform Might want to describe this for the simple (i.e. mathematically)
mircea_popescu That'll be hard ;/ Ok but let me try. The game board consists of an endless set of strings, which all start as natural language constructs and are "decayed" by bit flipping by an actual RNG. Once the decay is complete the game board is ready. Any number of players can play. Each player gets the same copy of the same list of strings. At any point each player has the choice of either reading one more character from their current string or advance to the next string. Each player has a pre-given "Table" consisting of a number of natural language poems. These are actual literature. Whenever a player has read a natural language word (ie, found in the dictionary) out of the string (exact match, no mixing of letters or anything Scrabble-ish) he now has that word. The word on itself is worth something. If the word is actually part of one of the player's poems on their table, it's worth more. If the player completes a line or a poem, more bonuses. He wins with the highest score once all players have read "all" strings.ⁱⁱⁱ

asciilifeform Sounds like a variation on 'Erudit'
mircea_popescu Does it ? Cause that's what I was looking for, to see if this is original or I'm just ineptly stumbling on well known (to everyone else) history.

asciilifeform And it's not clear, from this description, that the ideal strategy is any kind of problem. s/erudit/scrabble
mircea_popescu Why is that ?

asciilifeform Well, consider a bot. he can contain whatever, so he has an embedded dictionary (for the natural language of the poems). Or, failing that, simply the set of necessary words (all words from his poem slate).
mircea_popescu No problem. So ? It is a given the bot would contain the dictionaries, sure.

asciilifeform If the current buffer at any time does not match the beginning of any useful word, switch. Unless i'm missing something.
mircea_popescu Uh. So you switch on character 1 of all strings ?

asciilifeform Not all, but once 'x' becomes 'xy' and there is no 'xylophone' in the table...
mircea_popescu Seems to me a better strategy may be to stick with a not-so-entropic string than to switch and perhaps get a very entropic string. Even if the xy atm has no xylophone.

asciilifeform Illustrate?
mircea_popescu Ok. String one : xygfredfoxjumpedoverstan.
String two acadafabadabababbadaafa.

asciilifeform From whence do the strings come?
mircea_popescu They all start as natural language constructs and are fuzzed to different (and unknown to players) degrees. Some are very badly fuzzed. Some very slightly. Some in between.

asciilifeform Random selections from dictionary, then permuted a character at a time before start? And with varying degrees of noise?
mircea_popescu Random selections from the set from which poems given out, and then noised. Basically the player becomes an exercise to measure the fuzzer parameters in a half-blind fashion.

asciilifeform But noised to differing degrees, deliberately?
mircea_popescu Yeah.

asciilifeform Then strategy is clear, measure the noise.
mircea_popescu That in principle is clear, but it helps as much as "capture enemy pieces" helps in chess I suspect.

asciilifeform Certainly.
mircea_popescu Because measuring the noise has a cost in itself. Moreover, take our original two strings. When do you measure the noise ? xy is noisier than ac. Sampling problems. xyg way noisier than aca.

asciilifeform Noise being 'frequency of substrings that contain no valid words,' perhaps.
mircea_popescu 2nd still less noisy.

asciilifeform Fuck, I've played this game! With genetic sequences. Long story.
mircea_popescu I was going to say, basically this game is the game of fucking life. Every programmer ever has basically played this with compilers and errors and blabla. Every engineer idem.

asciilifeform I meant, literally this game. With homology modelling.
mircea_popescu O wow srsly ? Is it named anything ?

asciilifeform Not afaik.
mircea_popescu Hey.

asciilifeform But an actual expert might know. (I was thrown into that line of work by accident.)
mircea_popescu I guess ima clean it up and put it on the T.

asciilifeform I also have a hunch that it is a variant of Knapsack Problem.
mircea_popescu It certainly is. I'm just not sure it's reducible to it.

So now, as the old greeting goes... what do you know, what do you say ?

1. Told ya... [↩]
2. There's a huge discussion of pole dancing we're skipping here. O you wanted to read it ? Tits! I mean, tough! [↩]
3. Obviously "all" will have to get defined somehow on an endless board. The last player with money could be a definition, you get negative you're out. Arbitrary string counts could also be used. Or whatever. [↩]