LoCo Day 11

I’ve almost got things working again in the current refactoring. The current sticking point is how the server now sends JSON-encoded messages to the browser instead of HTML fragments. This will be needed for implementing a game since there will be things sent during a game other than bits of webpage to display. However, my JavaScript-fu is pretty weak, so it’ll take a little more effort to figure out why things aren’t working on the browser’s side of things.

Comments Off

LoCo Day 10

Today’s roadblock came courtesy of the aeson package, or one of its recursive dependencies. I wanted to try using it instead of json to generate JSON, since the programmatic interface seemed a bit simpler and more elegant. Alas, one of aeson’s dependencies doesn’t work due to a bug in GHC. Also, possibly as a result of that same bug, the act of installing the package screwed up the rest of GHC’s package repository to the point where it could no longer find all the other packages that had been installed, and reinstalling them mysteriously broke other unrelated packages too. I finally had to nuke the whole thing and install all the packages I’m interested in from scratch.

Then, of course, I tried installing aeson again to see if maybe the repository corruption was a weird fluke. It wasn’t.

So, I sunk a lot of today’s development time messing with that. Needless to say, I’ve kicked aeson aside and went back to using json.

A third of the way into November, I must say I’m much farther behind than I expected I would be. I still haven’t worked on the actual game part of this game; it’s all been setup and infrastructure stuff. Sigh.

Simple ways to keep your computer more secure

Making your personal computer or laptop completely secure may not be realistic, but there are several fairly straightforward things you can do to make it a lot more resistant to attack. And yes, if you’re on the Internet, your computer will be attacked sooner or later. Probably sooner. Of course, even if you follow all of these suggestions, you still won’t be completely immune to attack, not the least of which because I’m sure I’ve overlooked other important things to think about, but you’ll be in much better shape than most of the other computers that are out there.

Essentials

Keep your software up-to-date. All modern operating systems, as well as an increasing number of applications, are able to automatically check for and install updates. This is good. Often, those updates include security patches to fix vulnerabilities. The sooner you can get those vulnerabilities fixed on your computer, the smaller the window of opportunity for an attacker. Your computer wants to take care of this for you, so let it.

Don’t run as an Administrator-level account. Yes, yes, it’s your computer, of course you’re the administrator and should be able to do whatever you want with it. But the vast majority of the time, you’re not doing anything that actually needs administrator privileges. The problem is, if you’re running as an administrator, then so are all the programs you’re running, and if any of those get compromised, the attacker can easily get full control of your computer. Running as an ordinary user won’t stop you from getting attacked, but it will make it more difficult for a successful attacker to get control of your computer. As a side benefit, it also makes it more difficult for you to accidentally break something important. Those rare time when you do need administrator privileges, then go ahead and log into the administrator account, do what you need to do, then log back out.

If you’re not doing both of these two things, you’re living dangerously, and it’s only a matter of time until you suffer the consequences.

Important

Don’t hook your computer directly to the Internet. That consumer-grade home router is actually doubling as a hardware firewall, blocking attempts coming from the Internet to initiate a connection with your computer. This makes it a lot more difficult for something on the Internet to exploit a vulnerable service on your computer that you might not even be aware is running.

Run a firewall on your computer. No, this isn’t redundant with the above suggestion, especially if you have a laptop. Your home router isn’t going to be able to protect you when you take your laptop somewhere else. A firewall running on your computer isn’t as robust as a separate hardware device, but it’s a lot better than nothing when you’re connecting to someone else’s network, especially if it’s some sort of hotspot or public network where you have no idea who else might be on the same network.

Run an ad-filtering extension in your web browser. What does this have to do with security? It’s not unheard of for attackers to create ads with hidden malicious payloads and have them hosted by advertising networks. By blocking ads, you prevent this type of attack from succeeding, even if your browser is vulnerable to the exploit being used. As a bonus, you won’t have nearly so many ads distracting you when you browse the web.

Run antivirus software and keep it up-to-date. Antivirus software is far from being a silver bullet when it comes to protecting your computer; it’s far more effective to prevent something malicious from getting onto your system in the first place (as the rest of my advice up until now has aimed at), but there is value in being able to detect and remediate attacks that do make it onto your computer. Just don’t count on antivirus as your single line of defense; its biggest weakness is that it’s only able to protect against specific attacks that are already well-known.

Encrypt your laptop’s hard drive. Encrypting your hard drive helps limit the damage you’ll suffer if your laptop gets stolen while it’s powered off. The thief will have your laptop, but he or she won’t be able to read any of the information stored on it, and most of the time the information is far more valuable than the hardware itself. Do keep in mind that hard drive encryption only helps in this scenario; if the laptop is on, or asleep, or hibernating, the decryption key will still be in memory, allowing the computer to easily decrypt the disk’s contents on demand.

All of these I only call “important” instead of “essential” because each mainly addresses only particular types of attacks, whereas the “essential” tips provide much broader coverage. Still, you should follow them unless you have a compelling reason not to.

Advanced

Use NoScript or a similar JavaScript-whitelisting extension in your web browser. OK, this one isn’t quite so simple, but it provides a lot of security against malicious websites, so it’s worth mentioning. Firefox’s NoScript extension prevents JavaScript code from running in your browser unless it comes from one of the servers on its whitelist. After you first install it, you’ll need to tell it which servers to whitelist. This is easy to do while you browse; whenever a script gets blocked, NoScript will unobtrusively offer the option to add the server to the whitelist.

Pretty soon after you start using NoScript, your whitelist will have grown to include all the sites you visit regularly, so you won’t notice anything different in your day-to-day browsing. So what’s the point? A common attack against web browsers is to upload malicious JavaScript code to some server they control, then attack a bunch of popular websites to include a link to the malicious code. With NoScript, that malicious code on the attacker’s server, which you’ve never heard of and thus have not whitelisted, will not run, and so will never have a chance to try to attack your browser.

I list NoScript as an “advanced” technique because not only does it take some work to set up, but you’ll find that a lot of websites stop working correctly if JavaScript is disabled. A few times I’ve even encountered cases where shopping transactions ran into problems when the storefront redirects to a third-party processing server that blindly assumes you have JavaScript enabled and fails silently if you don’t. So, NoScript isn’t a fire-and-forget solution, but it significantly raises the bar for attackers trying to get your browser to run malicious JavaScript, since now they have to get that script hosted on one of the relatively few servers on your whitelist.

Outward: Chapter 9: Underneath

“What’s the situation?” TSgt Abernathy demanded as soon as she set foot in the lab. SrA Grant followed her in, stationing herself on the side of the door as SrA Roberts who, in turn, was no longer listening to his iPod.

“Over the past nine hours,” Todd began, “we’ve recorded five separate changes in the object’s position. Each time it’s dropped vertically by a few millimeters, sometimes accompanied by a lateral shift of a few micron.”

The previous night, he and Luke had abandoned their attempts to scan inside the object, and had replaced their equipment in the chamber with a series of infrared lasers aimed at varying points on the sphere’s surface, each one continuously measuring the distance between it and the laser. The results confirmed their suspicion from last night: the object was indeed moving downward. Not quite enough to notice visually, but easily measurable.

“The cause?” TSgt Abernathy asked.

Luke shrugged. “It still doesn’t look like it’s actually doing anything. I think the pallet it’s resting on is starting to buckle under the thing’s weight.”

TSgt Abernathy considered this. “That pallet’s rated to support objects heavier than it. It’s possible making the hollow for it to rest in weakened it a bit, but it shouldn’t have by that much.”

She opened the door to the anechoic chamber and cautiously stepped inside. It didn’t look like anything was different, but she could hardly push the object out of the way to take a peek underneath it to see if the pallet was damaged at all. She stepped back into the lab and shut the door.

She needed to think. She paced back and forth across the lab for a few minutes as everyone looked to her for instructions on what to do next.

Finally she said, “I want to look underneath it. You, get some men in here to lift it up. You, get that equipment out of there. They’re going to need room to move. How delicate is it?”

As Todd lifted the phone to call the crew at the loading dock, Luke replied, “Not particularly, as long as you don’t drop it or anything.”

“Good, then you,” TSgt Abernathy continued, pointing to SrA Roberts, “help him clear it out of there. Let’s move.”

Just as Luke was carrying the last of the laser arrays out of the chamber, two work men with a cart loaded with portable jacks arrived at the lab.

“Good, just in time,” TSgt Abernathy said to them. “Lift that thing up in there.”

The work men looked at each other, and then at Todd. Todd nodded at them, and the two got to work.

“You know,” Todd said, “we may be working on your contract, but you can’t just give orders to the other employees here.”

“In fact I can,” TSgt Abernathy countered. “The National Security Act of 1947, as amended, grants full authority over situations involving alien activity on earth, supplanting any other civil or private authorities, to three individuals, in descending order: the President, the Secretary of Defense, and the Commander of Air Force Exosolar Command,” she recited, ticking off each on her fingers. “And the Commander of AFEXOCOM has delegated control of this particular operation to me. So yes, I can tell your employees what to do when it involves that thing in there. Is that clear?”

Todd gulped. “Yes, ma’am,” he replied.

“Wait,” Luke said, “isn’t the National Security Act something to do with intelligence? What do aliens and the military have to do with it?”

Before TSgt Abernathy could regale Luke with tales of last-minute amendments slipped in to unrelated must-pass post-9/11 intelligence reform legislation and congressmen with strange theories about Roswell and Area 51, the room shook and a loud crash thundered from the chamber next door. She immediately burst through the door to see what had happened, followed by Luke and Todd.

The pallet supporting the object had snapped in two once the workmen had began lifting it by either side. The object was now resting directly on the floor of the chamber, stationary. At least, stationary as far as anyone could tell.

TSgt Abernathy pulled one of the halves aside to get a look at what the object had until moments ago been resting on. The hollow that had been dug into the center of the pallet to hold the sphere in place was now a hole that went clean through the pallet. There weren’t any scraps or shavings to suggest what had happened to the material that was supposed to be there. It was just sort of…

“Eaten away,” TSgt Abernathy said quietly. She straightened herself and turned to the two engineers. “Is there anything directly underneath this room?”

Luke thought. “The subbasement? I don’t know what’s underneath here, specifically, but it’s mostly storerooms and a couple equipment rooms. Never been down there myself.”

“First time for everything, then. Grant, you, Mr. Aaronson, and I are going to go down and take a look. Roberts, you keep an eye on the object. Radio me if there’s any change. Mr. Wright, you try to monitor the object as best you can. Move out.”

Before he was quite able to get a grasp of what just happened, Luke found himself riding the service elevator down to the subbasement with TSgt Abernathy and SrA Grant. He looked over and saw SrA Grant doing something with her sidearm.

“Do you really think that’s going to be necessary?” he asked.

SrA Grant shrugged. “‘Be prepared,’” she said, slipping it back into its holster.

“I thought that was the Boy Scouts.”

“Still a good motto.”

The doors slid open. The subbasement floor plan was pretty much identical to the basement’s, just with dimmer lighting and dirtier hallways. He led the other two down the hall to what, according to the plate on the door, was an equipment storeroom underneath the anechoic chamber. He swiped his badge, opened the door, and flipped on the light. He then quickly stepped out of the way to let SrA Grant enter first.

The room was full of dusty metal shelves stacked with boxes or, failing that, clumsily stacked piles of equipment. The sort of room where old or broken hardware went to die. The contents in the shelf in the center of the room, however, had a different fate. Something from the ceiling had been dripping on it.

A few metal stubs poking from the shelving’s support columns were the only sign that there had ever been a top shelf. A good chunk of the shelf below that had also been eaten away by something. There was a wide pool of something viscous atop a pile of discarded network switches on the middle shelf.

“Well there’s your problem,” SrA Grant joked.

“What is that stuff?” Luke asked.

“Don’t touch it,” TSgt Abernathy said.

“Well, duh,” Luke replied.

Luke heard a quick burst of radio static behind him. “Roberts, this is Abernathy, come in, over.”

“Was it leaking?” Luke wondered.

“Leaking, oozing, peeing, bleeding, does it matter?” SrA Grant said.

“Roberts, contact Maj Raskin. Tell him we have a situation here. Containment breach, still assessing. Over.”

“Bleeding?” Luke asked. “Like, alien blood?”

“Who else’s blood would it be?” SrA Grant replied.

“No, I know it’d be alien blood. But is it like alien blood? I mean, Alien alien.”

SrA Grant looked at him.

“No, I mean, Alien alien, like the alien from Alien. The movie. You know, facehuggers, and acid for blood.”

“Oh, you mean Xenomorphs. It’s not that.”

“How do you know?”

“A, Xenomorphs don’t build ships. B, Xenomorphs are too big to fit inside that thing. And C, Xenomorphs are fictional.” SrA Grant started walking around the room, checking the other shelving units for similar damage.

“Roger that, no change in the object so far. Be careful up there. Abernathy out.” TSgt Abernathy slid the radio back into her uniform.

“Ma’am, the damage seems to be limited to the shelf underneath the object,” SrA Grant reported.

“If it’s acid,” Luke wondered aloud, “it seems awfully specific about what it dissolves.”

“What do you mean?” TSgt Abernathy asked.

Luke pointed up at the ceiling. There was a small hole in the drop tile above the ruined shelf. “It ate through there, but only just enough to drip down to here. And then look how it’s just pooled on top of here, when it had no trouble getting through the two shelves above it. Shouldn’t it keep dissolving this too, on and on until it, um, whatever you call it when acid’s dissolving something and then stops dissolving it when the acid runs out of itself?”

“Nervous? You can head back up if you want.”

“Eh.”

“He does have a point, though,” SrA Grant added. “Besides, if it was getting dissolved, there should be a big puddle of melted stuff. It’s just… gone. Weird.”

TSgt Abernathy nodded. “Just like the pallet it was sitting on.” She wished she had a way to scoop up a sample of whatever was pooled atop the equipment on the shelf.

Luke froze. “Did you hear that?”

The other two fell silent. “Hear what?” TSgt Abernathy asked after about ten seconds had passed.

“It was a kind of metal tinkling noise.”

“I hear it too,” SrA Grant announced. “It’s coming from this corner.”

The other two converged on her position. She was staring at a shelf full of boxes, listening intently.

“It’s definitely coming from behind here,” she said. “Here, help me move this junk out of the way.” She began slowly picking up boxes from the bottom shelf and setting them on the floor behind her.

“There!” TSgt Abernathy said, pointing.

They all saw it. The shadows prevented any of them from getting a good look at it, but there was definitely movement along the wall behind the shelf. Whatever it was, it quickly slipped through a hole in the wall.

“What’s next door?” TSgt Abernathy asked.

“Another storeroom, I think.” Luke replied.

“Let’s check it out.”

The three went back out into the hallway and half-ran, half-creeped to the next door down. SrA Grant flattened herself along the wall next to the door and gave a hand signal.

“Wait, what does that mean?” Luke asked.

“She wants you to unlock the door and step back, then she’ll open it a crack and look inside,” TSgt Abernathy replied.

“All that from a… whatever she just did?”

“Just do it.”

Luke swiped his badge and stepped back. SrA Grant slowly inched the door open. “Sergeant,” she said, “you’re going to want to see this.”

TSgt Abernathy pressed her head against the door to see inside. There was more than one of them. Half a dozen, at least. They were small, and made of metal, and skittered across the floor on little feet. No, scratch that. Not all of them were quite so little.

She grabbed the handle and shut the door. She then pulled the radio out of her pocket. “Roberts, this is Abernathy. Contact Maj Raskin. Definite loss of containment. Potential foothold situation developing. Recommend evacuating and quarantining the facility. Awaiting orders. Over.”


Chapter word count: 1,855 (+188)
Total word count: 16,020 / 50,000 (32.04%)

Urandom fun fact

In turns out that if you’re wiping an external 1 TB hard disk using pseudorandom garbage, the process is CPU-bound and not I/O-bound:

$ sudo dd if=/dev/urandom of=/dev/sdb bs=4K
dd: writing `/dev/sdb': No space left on device
244190647+0 records in
244190646+0 records out
1000204886016 bytes (1.0 TB) copied, 136230 s, 7.3 MB/s

For those of you who have trouble dividing by 3600 in your head, 136,230 seconds works out to about 37.8 hours, with the CPU pegged at 100%. (Well, 50% since it’s a dual-core system, but whatever.)

My guess is that the process of actually encrypting the disk (once I initialize a file system on it) will take even longer, assuming that AES-256 encryption is slower than whatever PRNG algorithm Linux uses to drive /dev/urandom is.

Edit: Actually, that’s extremely incorrect. Encrypting the partition doesn’t actually write anything to it other than some kind of header identifying it as an encrypted partition. Yes, that means that almost all sectors are initially garbage if you try to decrypt them, but with a brand-new partition all sectors are initially garbage anyway. Creating the file system itself doesn’t try to read anything, either; it just writes to the sectors that will make up its index. And once you’ve mounted the file system, you’ll never try to read uninitialized sectors anyway, since there aren’t any files there.

In other words, the only O(n) step when creating an encrypted disk is wiping its previous contents; everything else is O(1) or O(log n) at worst. So why wipe with pseudorandom garbage instead of all zeros, which would be much faster? It’s (hopefully) computationally infeasible to distinguish uninitialized sectors (which look like random garbage because they are random garbage) from encrypted sectors (which look like random garbage because they’re encrypted with a strong algorithm). Not being able to tell where the data even is on the disk makes an attacker’s job more difficult.

Thanks to strong encryption, an attacker now has to either throw a lot of CPU power at the problem or use alternative means for recovering the data.

throw gauntlet(“nanowrimo”);

For some reason back in April, Renee challenged me to do NaNoWriMo this year.

Well, it’s on like Donkey Kong.

After all, someone around here has to show show all of you how it’s done. Again.

I’ve got a sort of weird mish-mash of ideas that I think I may be able to work together into something halfway passable. I’ll need to sit down and do some outlining to make sure all the major plot points will fit together and that the story can be sustained for thirty chapters.

Naming the major characters would also help, I guess.

So, who else is going to be foolish enough to try to pound out 50 kilowords next month?

How many bridge auctions are possible?

Implementing the bidding logic in Old Lady has become a real slog. Each new bid branches the decision tree even more, and each chunk of decision logic only applies to a handful of nodes in the tree. Right now I’m at the point where each check-in of a new set of code only applies to a fairly narrow case that can arise during the auction, but all those annoying little cases must be implemented.

It doesn’t take long until you start to wonder, just how many possible auctions are there in a round of bridge anyway?

As you’d probably guess even if you don’t play bridge, an auction is a sequence of bids. The ultimate goal of the auction is to arrive at a contract that one partnership will try to meet by taking tricks. (A secondary yet very important goal is to communicate with your partner through the bids you make what your hand looks like.) Ignoring whatever bidding system the players might be using, the rules of bridge constrain what the possible sequences of bids are.

While it’s theoretically possible to exhaustively enumerate all possible auctions, since we want to answer the question before we all die of old age, let’s use a little math to count faster.

The backbone of the auction are the bids that specify a possible contract. A contract is a rank (1 to 7) paired with either a suit (♣, ♦ ♥, or ♠) or no-trump (NT). That gives 7 x 5 = 35 possible contracts.

Contracts must be bid in ascending order, with the denominations ordered ♣ < ♦ < ♥ < ♠ < NT. For example, once 2♥ is bid, nobody can bid 2♣ or 1♠.

If we just look at the contracts that are bid during an auction, this means we don’t have to worry about the ordering of the contracts that are bid: the rules force one single possible ordering. Each contract may or may not be bid during the auction, for a total number of “backbones” of 235.

While that’s a pretty big number already (over 34 billion), we’re not even close to finished, since there’s plenty of other bids that don’t try to name a contract.

First, to get it out of the way, there is exactly one possible auction where no contracts are bid: all four players pass. We’ll ignore this special case for the time being and assume at least one contract is being bid in the auction.

Before the first contract is bid, up to three consecutive players may pass. We’ll call this series of passes at the beginning of the auction the “prelude”. There are 4 possible preludes in a non-trivial auction: no passes, one pass, two passes, and three passes.

Aside from passing, other possible bids are doubles and redoubles. A double can be bid by one of the opposing players after a contract is bid; it roughly means “there’s no way you’re going to make that contract”. A redouble can be bid after the other partnership bids double; it roughly means “wanna bet?”

Between two consecutive contracts in an auction is what we’ll call an “interlude”. There are a few things that can happen here:

  • Zero, one, or two players can pass.
  • The opposing partnership can double the contract, with possible passes before and after.
  • The opposing partnership can double the contract, and the original partnership can redouble it. Again, passes may occur before, after, and in between these bids.

Counting how many ways these three cases are possible:

  • If the contract is not doubled, there are 3 possibilities: no passes, one pass, or two passes.
  • If the contract is doubled but not redoubled, there are 6 possibilities: either zero or two passes, then the double, then zero to two passes. 2 x 1 x 3 = 6.
  • If the contract is doubled and redoubled, there are 12 possibilities: either zero or two passes, then the double, then zero or two more passes, then the redouble, then finally zero to two passes. 2 x 1 x 2 x 1 x 3 = 12.

All together, there are 3 + 6 + 12 = 21 possible interludes between each consecutive pair of contracts in the auction.

Finally, bidding ends when three consecutive passes are made after a contract is bid. Again, the contract can be doubled or redoubled. By a similar analysis for what we did for the interlude, there are 7 possible “epilogues”: 1 + 2 x 1 x 1 + 2 x 1 x 2 x 1 x 1 = 7. (Same analysis as before, but now the final set of passes must be three, so there are fewer possibilities in each case.)

Now, how to combine all these numbers together? Let’s use our terminology to look at the structure of a few simple auction templates:

  • No contracts: pass pass pass pass
  • One contract: prologue contract epilogue
  • Two contracts: prologue contract interlude contract epilogue
  • Three contracts: prologue contract interlude contract interlude contract epilogue

Let’s let i be the number of contracts in our auction. Whenever i > 0, the auction will have one prologue (3 choices), i – 1 interludes (21 choices each), and one epilogue (7 choices). That leaves the number of ways to choose i contracts out of the 35 possible contracts. Luckily, a little elementary combinatorics already gives us a function to compute that: 35 choose i.

So, for any given i > 0, the possible number of auctions with exactly i contracts is:

3 \cdot \binom{35}{i} \cdot 21^{i - 1} \cdot 7

Which can be simplified a bit to:

\binom{35}{i} \cdot 21^i

Interestingly, if we plug in i = 0 to that formula, it just so happens to return 1, which is the number of auctions with no contracts in them. We don’t need the i > 0 restriction after all.

As a result, the total number of possible auctions in a single deal of bridge is exactly:

\sum_{i=0}^{35} \binom{35}{i} \cdot 21^i

Which is roughly 9.7 x 1046, or exactly 96,559,237,760,273,012,340,173,944,583,707,028,522,342,023,168.

That’s a lot, though the vast majority of them will never come up in practice. Luckily not all of them require special handing.

[Edit: For comparison, the number of possible ways to deal the cards in bridge in the first place is “only” about 5.4 x 1028, or exactly 53,644,737,765,488,792,839,237,440,000.]

Music Applet 2.4.0 released

Music Applet 2.4.0 has just been released. The main change is that it now supports the recently-released Banshee 1.0, in addition to older versions of Banshee. There’s also improved support for debugging crashes, as well as an updated Czech (cs) translation.

Unfortunately, the new version of Banshee doesn’t provide a way to manipulate song ratings. Once that gets fixed in Banshee, I’ll update Music Applet accordingly.

A few technical notes on Banshee 1.0 support: since this new version of Banshee completely changed its D-Bus interface, there’s now two plugins for Banshee: the old one and the new one. While it’s inelegant to have two plugins for what the user sees as one program, it’s the only reasonable technical solution, given that the two versions of Banshee are completely different as far as Music Applet is concerned. If you have problems with Banshee support after upgrading the applet, check to make sure the new plugin (now called “Banshee”) is enabled. The old plugin has been renamed “Banshee (pre-1.0)”. I have no plans to remove support for old versions of Banshee any time soon.

Not the kind of chess master I had in mind

When I started this correspondence-chess-by-blog-comments experiment, I said I didn’t know what would happen, and it turns out I was right:

(11:40:01 AM) Renee: Pawn to D4.
(11:40:01 AM) me <AUTO-REPLY>: Your move.
(11:59:40 AM) me: 1. … d5
(12:01:28 PM) Renee: I roll 3 d6′s for stealth check.
(12:02:45 PM) me: Which piece are you trying to bluff?
(12:02:57 PM) me: Or, um, stealth
(12:03:49 PM) Renee: your knight and that ogre in the corner with the mustache and glasses
(12:04:29 PM) me: You pass your check
(12:04:44 PM) Renee: woo!
(12:09:24 PM) me: The knight can’t see out of his armor and the ogre is distracted by the shiny knight armor
(12:10:37 PM) Renee: I wish to unsheath my sword with a free move, and move towards the ogre..um..stealthily
(12:11:50 PM) me: The ogre doesn’t notice
(12:12:21 PM) Renee: am I close enough to strike?
(12:13:03 PM) me: Yes
(12:13:15 PM) Renee: I roll d20 for attack
(12:13:35 PM) Renee: hrm, 10
(12:15:11 PM) me: You swing your sword clumsily and hit the ogre in the kneecap for 7 damage
(12:15:19 PM) me: The ogre notices you
(12:15:54 PM) me: He clubs you for 8 damage
(12:16:07 PM) Renee: ouch
(12:16:33 PM) me: Could’ve been worse — he rolled 1d10 + 1d8
(12:16:42 PM) Renee: am I lucid enough to retaliate?
(12:17:05 PM) me: Yes
(12:17:25 PM) Renee: 14
(12:20:46 PM) me: Um… ok… you 14 the ogre in the eye for 11 damage
(12:21:12 PM) Renee: haha
(12:21:42 PM) me: The ogre is confused by the use of integers as verbs and runs away, dropping his +2 club of clubbing
(12:22:52 PM) Renee: alright!
(12:23:23 PM) Renee: can I discard my sword and take the club of clubbing?
(12:23:36 PM) me: Sure
(12:24:30 PM) me: You pick up the club of clubbing and feel you could attract hot ogre chicks at the disco, assuming your search check is able to locate hot ogre chicks, which are slightly more elusive than the Higgs particle
(12:26:47 PM) Renee: Can I ask the confused knight where the nearest disco is?
(12:28:53 PM) me: The knight offers you directions to The Rook’s Castle on h5. He also comments that his friend as a club just like yours.
(12:30:23 PM) Renee: I thank the knight, and offer him my loose change as a tip for the service
(12:31:28 PM) me: The knight points to the nightclub in the next square, but gives you a long set of directions involving a series of L-shaped hops
(12:33:01 PM) Renee: I disregard his roundabout directions and attempt to move directly into the next square
(12:33:30 PM) me: You succeed
(12:34:38 PM) Renee: I attempt to enter disco through front door
(12:37:06 PM) me: The bouncer (a lawful neutral bishop) asks you to pay the cover before allowing you through. The cover charge is precisely the amount of loose change you previously had.
(12:37:58 PM) Renee: dang
(12:38:16 PM) Renee: I offer to trade goods for entry in place of the cover charge
(12:39:26 PM) me: The bishop impatiently taps a “no bartering” sign with his crosier.
(12:40:16 PM) Renee: I curse myself for not making a character who can read and head back to the neighboring square where the knight was
(12:40:43 PM) me: The knight greets your cordially
(12:41:33 PM) Renee: I remind him of the tip and ask if there’s anyway he would give it back in exchange for something else
(12:42:10 PM) me: He offers to return your tip in exchange for you returning the knowledge of the location of the nightclub.
(12:43:16 PM) Renee: I snicker to myself, and agree
(12:44:29 PM) me: The knight brandishes his +1 sword of neurosurgery and asks if there is any other knowledge you would like to have excised from your cranium during the procedure.
(12:46:06 PM) Renee: I use a free move to hold my club of clubbing up in front of me as if trying to hide behind it, stammering something about maybe there being something else the knight wants instead
(12:48:17 PM) me: The knight dejectedly sheaths his sword and laments that his line of work offers so few opportunities to use his medical degree
(12:49:28 PM) Renee: I sympathize whilst backing towards the door
(12:52:48 PM) me: You find yourself outside on a rectilinear grid. The ground is dark.
(12:54:31 PM) Renee: I roll for “Where to hell am I?” check
(12:55:50 PM) me: You check your CPS receiver and see you are on g5
(12:56:44 PM) Renee: I check for loot
(12:57:56 PM) me: Roll me a search check
(12:58:19 PM) Renee: 16
(12:59:52 PM) me: You find a pointy hat with a diagonal slit in the top sitting on the ground five feet away.
(01:00:29 PM) Renee: cool, always wanted one of these. I take the hat
(01:03:30 PM) me: It looks surprisingly clean, but a little big. It miter might not fit you. [The DM points out he did restrain himself from making any "knightclub" jokes so far.]

I thnk the moral of the story is, if you ever play chess with Renee, bring a source book and some polyhedral dice.

Comments Off

Is the only winning move not to play?

I have no idea how well this is going to turn out, or how long it will last, or even what will happen, but there’s only one way to find out:

1. e4

Happy Halloween!

Um, I mean, “Merry Christmas.” I keep getting those confused, since OCT 31 = DEC 25.

*rimshot*

And for those of you who buy into the whole “War on Christmas” nonsense, this one goes out to you (possibly NSFW, as if you’re at work today anyway):

God hates Christmas trees

Thus saith the LORD, Learn not the way of the heathen, [...] For the customs of the people are vain: for one cutteth a tree out of the forest, the work of the hands of the workman, with the axe. They deck it with silver and with gold; they fasten it with nails and with hammers, that it move not.

Jer 10:2-4

Of course, not to be outdone, the Puritans hate Christmas entirely:

For preventing disorders, arising in several places within this jurisdiction by reason of some still observing such festivals as were superstitiously kept in other communities, to the great dishonor of God and offense of others: it is therefore ordered by this court and the authority thereof that whosoever shall be found observing any such day as Christmas or the like, either by forbearing of labor, feasting, or any other way, upon any such account as aforesaid, every such person so offending shall pay for every such offence five shilling as a fine to the county.

Records of the General Court, Massachusetts Bay Colony, May 11, 1659

Comments Off

Rationalizing the Traveler’s Dilemma

Another recent article in Scientific American is about the Traveler’s Dilemma problem in game theory.

For those too lazy to click on any of those links, here’s the basic problem (taken from the Wikipedia article):

An airline loses two suitcases belonging to two different travelers. Both suitcases happen to be identical and contain identical antiques. An airline manager tasked to settle the claims of both travelers explains that the airline is liable for a maximum of $100 per suitcase, and in order to determine an honest appraised value of the antiques the manager separates both travelers so they can’t confer, and asks them to write down the amount of their value at no less than $2 and no larger than $100. He also tells them that if both write down the same number, he will treat that number as the true dollar value of both suitcases and reimburse both travelers that amount. However, if one writes down a smaller number than the other, this smaller number will be taken as the true dollar value, and both travelers will receive that amount along with a bonus/malus: $2 extra will be paid to the traveler who wrote down the lower value and a $2 deduction will be taken from the person who wrote down the higher amount. The challenge is: what strategy should both travelers follow to decide the value they should write down?

Traveler’s Dilemma can be seen as a generalization of the infamous Prisoner’s Dilemma problem (and in fact reduces to it if you replace $100 with $3 in the problem statement), and suffers the same perverse situation where rational players will make the choices that result in the worst outcomes for them.

Why’s that? Suppose you and the other player both pick $100, which results in both of you getting $100. However, if you pick $99 instead, you get $99 + $2 = $101, which is better, so you’d choose $99 instead of $100. (In fact, choosing $99 is always at least as good as, and sometimes better than, choosing $100.) But since the other player is also rational, he’ll also choose $99 instead of $100, and as a result both of you would get $99. Similarly, if you reduce your choice to $98, you would wind up with $98 + $2 = $100, which is better than $99. Of course, the other player also knows this, and will choose $98 instead of $99 as well. According to this analysis, the race-to-the-bottom continues until both you and your opponent choose $2, resulting in each of you only getting $2.

Another way to look at it is, whatever the other player picks, your best strategy is to underbid him by $1. Since he’s also playing rationally, he’ll try to do the same to you. As a result, you both pick the lowest choice possible, because any other choice will fare strictly worse against that same rational strategy — both players picking $2 is the Nash equilibrium.

However, this analysis is empiricly wrong. When you do a Traveler’s Dilemma with actual people, most don’t play the Nash equilibrium as we would expect from the above analysis. Instead, most of them choose a high dollar amount, typically somewhere between $90 and $100. According to the analysis, this is an irrational choice, but since most players play this way, the result is that they have a far better outcome than if they had picked $2, so the irrational choice is better.

So, is playing irrationally is the truly rational way to play? Or is there something wrong with our original analysis?

My hypothesis to explain what’s going on holds that the players are in fact playing rationally; it’s just that our game theoretic model isn’t properly considering the valuations the players are actually using.

I believe the game theoretic model for Traveller’s Dilemma makes a critical error in the assumptions it makes about the players: it assumes they are completely risk averse, unwilling to risk choosing anything other than the option with the highest guaranteed payoff. Note that choosing $2 is the only choice that guarantees the player will make at least $2 in the end; all other choices risk making $0 depending on how the other player chooses.

In reality, people are going to have some non-zero degree of risk tolerance; they’ll be willing to accept the risk of a non-optimal payoff for the chance of a larger one. Just how much risk a person is willing to accept depends on their own risk tolerance profile, and the dollar amounts at stake.

Here’s why I think rational real-world players tend to choose something in the $90s instead of the Nash equilibrium of $2. They understand that choosing $2 guarantees them a payoff of $2, but $2 is of little real-world value to most people. After all, what can you buy with just $2 anyway? However, the maximum possible payoff is $101, and they’d prefer a payoff closer to that than $2. But to get a payoff in the $90s, both players need to choose something in the $90s. A player doesn’t know with certainty what the other player will choose, but it’s likely the other player will see little value in $2 but a lot of value in the $90s. So, the player must choose whether or not to risk a guaranteed $2 for the chance to get $90 or so. Since $2 is almost worthless but $90 certainly isn’t, most players choose to take the risk.

This line of thinking doesn’t provide any obvious dollar amount a player is expected to choose, but does provide an escape from the race-to-the-bottom scenario in the traditional analysis. (In fact, if individual dollars aren’t very valuable to a player, he probably isn’t too concerned with getting $93 versus $95 anyway.) Since most people are willing to take the risk, chances are the risk does pay off, and both players come out much better than they would have if they had played the Nash equilibrium.

Like all good hypothesis, there is a way to test mine against the traditional model (and the null hypothesis of “people are dumb but like picking big numbers”. My hypothesis depends on the absolute dollar amounts involved in the game: it assumes that $2 is of little value to a player but $90+ is. The traditional model, however, does not. I predict that if the game were changed so that the allowed range ran from $2,000,000 to $100,000,000 and the bonus/malus was increased to $2,000,000 — in other words, multiply all dollar values by 1,000,000 — we would see most players play the Nash equilibrium instead of taking the risk.

Why? Because to most people, $2,000,000 is a lot of money, and risking losing that for the chance to gain $100,000,000 is a lot harder to swallow. Plus, when the decreasing marginal utility of money is considered, that $100,000,000 isn’t actually worth 50 times more than $2,000,000, whereas $100 would be seen as worth 50 times (or possibly more!) as much as $2. On top of that, it’s hard to wrap one’s mind around just how much $100,000,000 is; I could find a way to send $2,000,000 without too much difficulty, but $100,000,000? I’d have to really work to spend half of that before I die.

So in Traveller’s Dilemma x 106, a player is expected to be a lot more risk averse than before. And since both players must take the risk to see the payoff, few, if any, players are actually going to take it, it’s much less likely for the risk to actually pay off. As a result, most players will stick with the Nash equilibrium of $2,000,000 as the rational choice.

(By the way, if anyone wants to run this experiment with real money, I volunteer.)

So, Traveller’s Dilemma doesn’t show that people don’t act rationally, just that the game-theoretic model doesn’t properly consider risk tolerance of the players. Sure, people act irrationally all the time, but this situation isn’t one of them.

Paul v. Scientific American

[Editor’s note: Sent to the editors in question. By some corollary to Skitt’s Law, naturally, I managed to screw up the second set of page references in the copy I sent them. Sigh.]

In the June 2007 Scientific American article “Breaking Network Logjams”, the sidebar on page 83 claims “Still, when neither a nor b is 0, both receivers can retrieve the proper messages successfully.” Alas, selecting codes is not quite that easy: a and b must be relatively prime to 2m (where m is the number of bits per message). Only then is

a * X + b * Y = E (modulo 2m)

guaranteed to have a unique solution when all variables except either X or Y are known. a and b needing to be nonzero is merely a special case of this requirement.

Luckily, since 2m will never have any prime factors besides 2, choosing odd numbers for a and b guarantees they will be relatively prime to 2m. Although this means that a purely random choice for a and b will only work 25% of the time, it is trivial to restrict the random choice to only odd numbers to begin with.

The example on pages 82 and 83 in fact demonstrates what happens when a and b are chosen poorly. In the example, a = 3 is a safe choice, but b = 20 is poor, since 20 and 32 have a common factor (4). In solving

3 * 21 + 20 * Y = 23 (modulo 32)

there are four possible values for Y: 6, 14, 22, and 30. There is no way to tell which possible value for Y corresponds to Ben’s message; as a result, Carl is unable to receive Ben’s message reliably.

Happy Pi Day

Yes, I know. I grasp calendars so rarely state it’s today.

Everyone worldwide, rejoice posthaste, for pi day returned!

Each circle we sketch must use not integers, but an amazing geometric ratio!

[Editor's note: as I can't think of any words with zero letters in them, that's about as far as I can go with this.]