10 April 2007

Things of the moment

  • My current side project is fixing bugs in Python's DOM implementation.

  • Brainteaser: What if chess had a single level of undo? Specifically, after your opponent moves, you may, instead of making your next move as usual, roll the game back to the point just before your previous move and do something else instead. (Your game clock, though, would not be turned back.) How would this affect the game?

  • I'm trying to understand Haskell's existentially quantified types, and (a shallower question) why there's no Data.Hashtable.ST, darn it.

  • GoboLinux is a Linux distribution with a sane filesystem layout. From reading that one page, I like it. You can't fight with MSI for a week without realizing that the people who design installer systems have been working waaaay too hard, and that the fate of our civilization hinges on stopping them.

  • Yesno is a toy programming language in which every method call returns something immediately ...and returns the correct result eventually. It's either hilarious or awesome, probably. The obvious next step is to make it self-host.

  • In the spirit of yesno, here are two quick reviews of books I'm not done reading yet. (I'll refine these opinions later, maybe.) The Time-Traveler's Wife is too sentimental and too linear, and does not contain enough adventure or suffering. Oryx and Crake has a lot of the same strengths and weaknesses as 1984, but much more angst.


stuart said...

"What if chess had a single level of undo?"

I guess you've already seen John Baez's disucssion of something similar in This Week's Finds #240?

"imagine a video game where you can save your game at any state of play, and go back to these saved games whenever you want. And, you have to imagine being so paranoid that you always save your game before making a move."

Of course, that's infinite undo, not just one step. I wonder whether the setup discussed in that article can be modified to give what you want?

jto said...


Thanks! That's a very interesting post!

To adapt this kind of model to undo-chess, you would at least need some model of computation. This is because if there's no clock, undo is basically irrelevant (it's the same game either way), and if there is a clock, it has to measure something.

Then the first question is, can you prove for some nontrivial class of computation models that chess-with-single-undo is the same game as chess? At the moment, I have no idea.

From Eightball Master Claw said...

I don't think that chess-with-single-undo is the same game as [clocked] chess. With chess, as with any gaming, strategy is based on risks and risk assessment. You also can't equate it to a video game model, since a video game is [usually] single-player. Introducing the undo provides both players with an advantage.

Imagine there are only three options and the first is chosen. Once your opponent has moved, you're now armed with the knowledge of your opponent's move and its advantage in either direction. Having used your undo, your opponent now has yet to use his; he now knows that you can no longer undo anything else in the game. The knowledge of this changes how the game is played, and essentially the game itself. At what point do you play your undo, then? To keep your queen? It would almost seem as though the first person to use the undo is at the disadvantage.

The second question I would ask is: once you decided to use your undo, can your opponent undo his previous move?

GoboLinux looks nice, but I'd have to see. I've usually used CERN, because it's a free version of RHEL: easier for package management. Ubuntu, I've heard is great for laptop wi-fi.

jto said...

"once you decided to use your undo, can your opponent undo his previous move?"

Oh, good question. Yes. You could undo all the way to the beginning of the game this way, if both players cooperated.

"Once your opponent has moved, you're now armed with the knowledge of your opponent's move and its advantage in either direction."

Sure, if your opponent actually intends to keep that move. But he might just be bluffing or trying to see how you would respond. Or maybe he just wants to put you on the clock while he thinks!

I dunno if this is generally true, but my experience is, if my opponent's move actually reveals something immediately obvious, it's because I made a dumb mistake. Even a beginner looks at least one move ahead. Mathematical game theory ignores dumb mistakes.

My thought was, chess-with-single-undo might just be the same game as chess, but the board displays a hypothetical future (one move ahead) instead of the real current game state. It's kind of like the unintended consequences of mandatory safety features in cars (everyone just drives faster). Everyone would have to play out to the limit of their undo, because if you don't, the other guy will, and your clock will always be ticking.

But the possibility of consecutive undo-moves changes things a bit. It now seems like chess-with-single-undo gives you more freedom to make a move that invites your opponent to make an unobvious mistake, with no penalty for you if he/she comes up with the right response. But this is a good thing: at least the game focuses on subtler mistakes.

I think I like this idea...

jto said...


Sorry this wasn't clear, but you get one undo per turn, not one per game.

To avoid annoying strategies, the number of undo moves per player per game needs to be limited. I think taking a little time off the player's clock when he makes an undo move would be enough.