Whitby goodness

[ciphergoth]

I had a lovely Whitby - a little more muted than usual, partly because of colds at our end and partly because of colds very sadly keeping ergotia and lilithmagna from joining us, but very nice all the same. My Friday night outfit was particularly well received, and will no doubt be reprised.

Now I'm obsessing with trying to get a paper ready by November 25 for FSE 2006. I have to keep a little quiet about what I'm doing until January 27th, since submissions are anonymous, but, it's cool.

Update with a geek puzzle: here's a simple game. I lay out a set of tiles that say Y or N; say I lay out

NYYNYNN

You lay the same number of tiles underneath:

NYYNYNN
NNYYNNN

The rules are: (1) if a tile is the same as the one above, you have to lay the same tile to the right. So you're not allowed to lay

NYYNYNN
NYYYNNN
-^- not allowed: because the first column is N N, you must lay N as your second tile.

(2) you get a point every time you lay a tile which is the same as the one above.

NYYNYNN
NNYYNNN
1010011 - four points

The least you can score is always zero: it's always a legal move to lay tiles which differ in every place from the ones above. What's the best you can score for NYYNYN, and how many ways can you do it? Can anyone give an algorithm which determines the highest you can score, or which generates all of the possibilities which give you a given score?

Comments

[mskala.livejournal.com]

And if you want all of them - keep lists of all optimal solutions at each stage, instead of just one. That may kill worst-case efficiency, though.

[ciphergoth.livejournal.com]

Check out my bit of Python above - it's easy to do in linear time with dynamic programming. You collect answers to the question "What's the best and worst score I can achive against the i-tile suffix of this puzzle, using a solution starting with x?". So you end up storing four small integers per tile; I actually used a bitmask representing possible scores. Then it's easy to iterate through all the answers that score k, because it's easy to answer the question "Given this prefix (which scores y), can I add tile x to it and achieve my target score?".

You can easily generalize this to any game played on an FSM where transitions score points and you know your opponent's moves in advance.

[hythloday.livejournal.com]

any game played on an FSM where transitions score points and you know your opponent's moves in advance

Nim, in other words?

[ciphergoth.livejournal.com]

I can't quite work that out:

First, Nim's not really an FSM: there are infinitely many possible Nim boards.
Second, you don't score points for the transitions - the game is decided at the end.
Third, you don't know your opponent's moves in advance!

But maybe there's a clever way of thinking about Nim that turns it into a problem fitting the above constraints?

“Apart from that, Mrs. Licoln, how was the play?”

[hythloday.livejournal.com]

First up - infinitely many Nim boards. There are, it's true, infinitely many ways of laying out a board for a game of Nim, but once you've made that board, there are a finite number of ways of playing it. This struck me as similar to your game, in that you can lay out an infinite number of tiles, but once you do, there are only a finite number of ways I can lay out my tiles.

Second - ah, you formally score points at the end, it's true, but you can regard a game of Nim for a player as a set of transitions in and out of Nim numbers - the player gains a point when he gets to a Nim number and loses a point when he strays off it - then whoever has "more points" (although there's only one) at the end of the game wins.

I misunderstood what you meant by "know your opponents moves in advance" - I though you meant in the sense of chess vs. roshambo rather than in the sense of your game (did you give it a name?) vs. chess. I suppose in an optimally played game of Nim, one *does* know one's opponent's moves, in effect, because they'll either be a move to a Nim number or a move that will let one get to a Nim number, and the Nim number that one will get to is known, but that's clutching at straws rather.

I'm not certain, though, that there isn't some kind of relationship between the two - if it becomes more apparent to me I'll let you know, if you like.

Re: “Apart from that, Mrs. Licoln, how was the play?”

[ciphergoth.livejournal.com]

Any problem solvable in X time can be transformed in X time into any other problem, so of course you can transform Nim into an instance of the problem my program solves. However, the relationship this establishes is trival and uninteresting, because all the real "work" in solving the problem is done in the transformation step, not in the "solving" step.

(for X substitute polynomial, linear, subquadratic, or whatever)