Let's invent a new game!

Thursday, 20 February, Year 6 d.Tr. | Author: Mircea Popescu

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

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 heheii.

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.iii

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. []
Category: Trolloludens
Comments feed : RSS 2.0. Leave your own comment below, or send a trackback.

4 Responses

  1. I'm not sure I understand the rules. Are there spaces?

    Let's say the dictionary is English words, and I read in "fad", and the next letter is 'e' and I read that too. Do I get points after 'fad' (since that is a word), and also after I read in the 'e' (since 'fade' is a word)?

    What if there was an 'x' in front -- do I still get points after I've read in "xfad" because a suffix of what I've read is a word?

  2. Semi-rational mutagenesis.


  3. Mircea Popescu`s avatar
    Mircea Popescu 
    Thursday, 20 February 2014

    Bugpowder> Semi-rational mutagenesis
    Bugpowder> mircea_popescu: I played that game quite a bit in grad school.
    Bugpowder> For example http://nar.oxfordjournals.org/content/28/16/e78
    mircea_popescu> Bugpowder o hey so it has a name and everything ?
    mircea_popescu> asciilifeform check it out
    Bugpowder> Well, it's not exactly the same game but similar enough
    Bugpowder> You use degenerate PCR primers to evolve and screen fluorescent protein genes
    mircea_popescu> shorter alphabet basicall ?
    Bugpowder> trying to find an new one that matches
    Bugpowder> well... 4 characters
    mircea_popescu> shorter alphabet / longer verses.
    Bugpowder> but you mutate base on the codons
    * punkman1 has quit (Ping timeout: 272 seconds)
    Bugpowder> so 3^3 'letters'
    mircea_popescu> interesting
    Bugpowder> since you need 3 to actually code an amino acid.
    * punkman (~punkman@unaffiliated/punkman) has joined #bitcoin-assets
    mircea_popescu> but isn't it 3^4 then ?
    Bugpowder> uhhh
    Bugpowder> 4^3
    Bugpowder> yeah
    mircea_popescu> right
    Bugpowder> though some represent the same letter
    Bugpowder> http://dps.plants.ox.ac.uk/langdalelab/protocols/PCR/degenerate_primer.pdf
    Bugpowder> So you can specify ATGC
    mircea_popescu> well cool!


    Meta-problem solved :)

  4. Mircea Popescu`s avatar
    Mircea Popescu 
    Thursday, 20 February 2014

    @ESRogs In principle particular variants of the game could played which counted both fad and fade or forced you to pick one. I would guess in all meaningful variants xfade would be legitimately read as fade, so basically you're allowed to select any substring that's a word out of your string.

    Obviously this is more exploratory than set in stone, some practice'd be required to refine the best ruleset for whatever circumstance.

Add your cents! »
    If this is your first comment, it will wait to be approved. This usually takes a few hours. Subsequent comments are not delayed.