For the past few months, I’ve been playing Hanging with Friends with a few friends of mine. Hanging with Friends is a modified version of Hangman: your opponent gives you a word with one of the letters filled in and the rest left as blanks, and you have to guess the word one letter at a time without making too many mistakes. Once you try solving a word, you’re given a set of letters that you can use to construct a word that your opponent in turn tries to solve. The first person to fail to guess five words loses.
On a recent long, boring drive up I-5 I found myself thinking about Hanging with Friends, and what it would take to have a computer both solve Hanging with Friends puzzles well and come up with good puzzles of its own.
Solving Puzzles
Solving Hanging with Friends puzzles is pretty straightforward from an algorithmic point of view, as long as you have the dictionary of possible words handy. The program is given a template for a word as input (?op?er in the above example, where ? represents an unknown letter) and is expected to produce the next letter that the player should guess. One possible solution starts by filtering the dictionary for words that match the template; in the above example, “copter” would match the template but “spam” or “bacon” would not. It then counts the number of times each guessable letter occurs in this set of candidate words, and returns the letter with the largest count. The idea here is that an incorrect guess eliminates the largest number of candidate words.
If you don’t have a dictionary (or have to operate on the assumption that the dictionary isn’t perfect), things get a lot harder. You could do arbitrarily sophisticated things here; one thing that comes to mind is using a dictionary to learn what groups of English words tend to go together and guess those in an intelligent way. For example, if you’re given a word whose last three letters are “i??”, you might want to guess n, g, n, t, m or e because of the common word groups “ing”, “int”, “ine” and “ime”, or if you’re given a word where the revealed letter isn’t a vowel, you might want to guess each of the vowels. You probably would want to take frequency of occurrence of these common word groupings in the dictionary into account here as well. What you’d probably want is to train some sort of learning system to do this; there are a ton of different possibilities here.
Making puzzles
Picking good words to give your opponent is a little more tricky. Abstractly, you may want to pick words that are hard to solve. Typically these are words that are long, probably uncommon, and have a large number of distinct letters, since those words give your opponent more opportunities to make a mistake. You might also want to pick words with high scores. Hanging with Friends rewards you with some amount of in-game currency for each 200 points scored when creating puzzles for your opponent (using Scrabble-style scoring with letter scores and position-based score multipliers). This in-game currency can be exchanged for power-ups that make a word easier to guess by eliminating letters when you’re the one solving, or feeding you hard-to-solve words when you’re making the puzzle. In-game currency can also be used to purchase various cutesy avatars and whatnot in their in-game store. Of course you can purchase in-game currency with real money (this is where Zynga’s signature brand of devious social engineering rears its ugly head), but with two copies of an algorithm like this and a colluding friend, you could mine in-game currency as efficiently as possible. Not that I’m suggesting such a thing, of course.
To keep things as generic as possible, what you’re really looking for is the ability to pick a word with the maximum value for some cost function from the set of words that can be generated using the tiles you’re given. The algorithm when cast this way is also pretty straightforward if you have a dictionary at hand: filter the dictionary to the set of words you can legally play, give each word a score, and pick the highest-scoring word.
On Word Commonness
One additional ingredient that’s missing from the above algorithms is some notion of the commonness of a word. Intuitively, words that aren’t commonly used are harder to guess; in the above example of “?op?er”, I’m more likely to guess “copter”, “copier”, or “gopher” than I am to guess “mopier” or “dopier” because I use the former set of words more often than I use the latter. Word commonness is a tricky thing to get right; even if you had a corpus of information the size of the Internet from which to draw (which companies like Google do), the problem is complicated by the fact that many people have trouble with spelling and sometimes use one word when they mean to use another. Another complication is that the frequency of some words can vary substantially based on context; for example, computer scientists use the words “ping”, “packet” and “hash” more frequently than other people do. That said, a good first approximation would be to count the frequency of each of the dictionary words in the largest corpus of English text you could find.
The Code
I went ahead and implemented a simple version of the algorithms described above and put it on GitHub as hanging-tools.
Disclaimer (so that people won’t immediately stop playing Hanging with Friends with me): I didn’t use these tools to cheat in any of my Hanging with Friends games, although I did feed it old puzzles as test cases.
If you’re interested in playing around with this (or fixing my bugs!) I’d be interested to see what you do with it. That repository also comes with a copy of the ENABLE dictionary, which Zynga apparently uses as the basis for their word database.
Sonic hasn’t had all that great of a run for most of the past ten years or so. The franchise was handed off to a bunch of different teams in the 2000s, each of which had their own vision of what a Sonic game should look like. Unfortunately, each of those visions was more mediocre than the last. Recently though, the future’s been looking a little brighter for our spiky blue hero. Sega put a new guy in charge of Sonic’s future direction last year, and one of the first things his team did was pull all the recent “average” Sonic titles from the shelves. Shortly thereafter, they released Sonic Colors, Sonic 4 Episode 1 and Sonic Generations, and they all got pretty good reviews (for next-gen Sonic titles, anyway). Sonic 4 Episode 1 and Sonic Generations both attempt to re-attract the “older” generation of Sonic gamers who remember a time when Sonic titles were known for being good instead of, well, laughably awful.
The next big thing in Sonic’s “everything old is new again” renaissance is the re-release of Sonic CD on PC, XBox 360, PS3 and iOS devices. I’ve already played through Sonic CD several times (in emulators and on the Sega CD), but I bought it again for XBox 360, and I’m really glad I did.
Sonic CD is in many ways the spiritual successor to the original Sonic the Hedgehog, even though it was released a few months after Sonic 2. Most of Sonic’s sprites are re-used from Sonic 1, special stages are accessible at the end of the level rather than at checkpoint lampposts, and each zone has three acts rather than two. Sonic CD takes advantage of the ill-fated Sega CD’s hardware, sporting a CD-quality soundtrack (which was a novelty in 1993) and levels that are absolutely massive by comparison to those in the first couple Sonic games.
The big novel gameplay mechanic in Sonic CD is time travel (because really, what series doesn’t get better with the inexplicable addition of time travel?) Each level in Sonic CD is playable in three time periods: past, present, and future. Sonic gets between time periods by hitting a Time Warp sign (conveniently labeled Past or Future) and then running at top speed for a few seconds without stopping. The future is further subdivided into the “good” future and the “bad” future. Dr. Robotnik has put a machine in the past on each level that powers his badnik army; if Sonic travels to the past, then finds and destroys this machine, the future is saved (unlocking the “good” future); if not, Robotnik has taken over in the future and it isn’t a very happy place (the “bad” future). If you unlock the good future in every level or collect all the Time Stones (the stand-ins for that classic Sonic macguffin, the Chaos Emeralds), you get the good ending.
Sonic CD is pretty much tied with Sonic the Hedgehog 2 on my list of the best Sonic games of all time. The fact that every level is essentially four levels is a testament to the enormous amount of room the designers had to work with on the Sega CD. The different time periods aren’t just palette swaps either; they actually went through the effort to modify the graphics and level design and write different background tracks for each one. The soundtrack (while very ’90s) is pretty great in both Japanese and English versions (the Japanese boss music is by far my favorite). The “go really fast for a while without stopping” requirement for time travel actually inspired some really inventive level design; speed traps and loops that were just nuisances before become things the player actively seeks out. Seeking out Dr. Robotnik’s machines in the past puts a much larger emphasis on exploration, although you can still race through the levels at full speed if you want. It’s got “replay value” in spades.
What really sets Sonic CD apart from any other Sonic game from that era are the boss battles.
Typically a boss battle in a Sonic game is a pretty standard affair. Dr. Robotnik shows up in some kind of mech whose design is inspired by the level’s overall theme (i.e. if you’re in an ice level, that mech’s gonna have a freeze ray), you hit him seven or eight times while dodging his attacks, most of his mech explodes and he runs away. Sonic CD’s bosses are in that same vein, but are a lot less conventional. You’re still fighting Robotnik in a mech most of the time, but in one level he’s at the top of a giant diabolical pinball machine and you only have to reach him and hit him once to end the whole thing. In another, he locks you in a room containing a fearsome death trap and watches in mounting dismay as the death trap slowly tears itself (and his conveniently placed adjacent control room) apart. In still another, he traps you underwater only to make the critical mistake of making a shield for his mech out of air bubbles. Really inspired and original stuff, some of the best of the whole series.
Oh, and did I mention that in one level there’s a shrink ray?
Yeah, in one level? There’s a shrink ray.
To their massive credit, Sega has really done Sonic CD justice with this re-release. Rather than sticking a huge border around the old VGA graphics like a lot of 16-bit game conversions, they actually took the time to port it to 16:9 native. Many people think the US soundtrack wasn’t as good as the Japanese soundtrack, so they included both soundtracks. They even added Tails in as a playable character. I mean seriously. That’s pretty awesome.
Seriously. Play this game. It’s well worth the $3-$5 you’ll pay for it on your platform of choice.
Posted: July 19th, 2011 | Author:Alex | Filed under:Fun and Games | Comments Off
Technically, Sonic Mega-Mix is a disassembly modification of Sonic CD. The modification is so extensive, however, that it’s pretty much an entirely new game. I’ve been disappointed with the mediocrity of official Sonic games for a long time, so games like this are a breath of fresh air. If you’ve got even a remote interest in re-living the glory days of Sonic’s 16-bit past, grab an emulator (the best one I’ve ever seen is Kega Fusion) and download the game here. It won’t disappoint.
My friend Kevin and I built an arcade machine between October and December of last year. It’s currently sitting in UCSD’s CSE department in the graduate student lounge. You should check out the arcade machine’s homepage for more information about the machine itself and how we built it.
You can get kits similar to this one that are somewhat more professionally done, but they typically cost thousands of dollars and pretty much consist of the same thing this does: a specially-shaped wooden box with a computer inside running special software. The total out-of-pocket materials cost for this cabinet was about $300 (one third of which went to the logic board interfacing the buttons to the computer) and it looks pretty good. So the lesson here is, if you’ve got the time and the materials you might as well do it yourself. Luckily, Kevin has a garage and a table saw, both of which were pretty crucial to success here.
Some lessons from this that aren’t in the homepage linked above (that’s right, you get special behind-the-scenes commentary, you lucky dogs):
Cutting plexiglass is a giant pain. The guys on YouTube make it look so easy! We spent a lot of time and went through a lot of plexiglass getting those cuts right. Specialized “acrylic cutting” tools are a total waste of money, just use a razor-blade. After multiple failed attempts at cutting it ourselves, we went to Lowe’s to get a sheet of plexiglass cut for the large piece in front that masks the edges of the monitor. They have a special plexiglass cutting machine (essentially a giant razor-blade on a track) that went right through it. Unfortunately, when we got back from Lowe’s we found that the piece we’d had cut was 1/8″ too short (d’oh!). Measure twice, cut once kids!
The front piece we used is actually a scrap piece of plexiglass left over from our “experiments” (read: a lot of sharp, broken pieces of plexi and swearing) that happened to be just long enough. At one time or another, shards of plexi took on various uses throughout the project including a straight edge and a putty knife.
Don’t use untracked international air mail, even if it’s cheaper. The guys that made the controller board for our arcade buttons are in the UK, and we’re in California. To save $20 (because we’re graduate students and poor, or cheap, or both), I had them ship it by free, untracked air mail. After waiting over a month for it to arrive, we complained and they shipped us another one, this time with tracking, and it was there in 48 hours. We still don’t know what happened to the first one. Maybe customs thought it was a bomb. Or “free air mail” is DHL throwing the package west and seeing how far it goes. Who knows.
Quick-disconnect terminals are great. I was dreading having to solder wires to arcade buttons to make this thing work. I may have a degree in electrical engineering, and I’ve got some theoretical grounding in electronics, but not a lot of hands-on experience. Unless you count that time I shorted a power supply across the ground plate on a breadboard and burned my hand. That was an experience.
Thankfully, all the micro-switches on the buttons have quick-disconnect terminals, a.k.a. “wire connection for dummies”. Crimp the connector onto one end of a wire and slide it onto the terminal and boom, instant connection, no soldering required. This means that if we ever have to replace buttons, one of us won’t have to crawl underneath it with a hot soldering iron.
Django is pretty cool. Every time someone plays a game on the arcade machine, we log what game they played and how long they played it. We wanted a quick-and-dirty way to see what games were popular, and also to see remotely if the machine was being used or not – mainly because we didn’t want to have to walk down the hall to see if anyone was using the machine. The arcade machine’s user interface pushes this information out by copying a JSON file over SSH to my workstation whenever its state changes. We’re thinking about using Django as part of another project, so I decided that this would be a good excuse to do a really simple Django app. I went from starting to read the tutorial to having a working website in 90 minutes. And I went through two different designs. Hot damn.
There you have it. If you end up building your own machine based on what we did, please let me know!
I have an XBox 360 with a couple of wireless controllers that have rechargeable battery packs and this thing called a “Play ‘n Charge” cable that allows the controllers to charge over USB while still being usable. I picked up one of my controllers after a long (read: months) period of not using it to find that it had completely discharged. Not only that, but it wouldn’t even charge over the cable; the charge indicator light turned from red (charging) to green (charged) almost immediately. For a long time, I thought I just had a faulty battery and ran off of AAs. Then I found this thread.
Disclaimer: I am not an electrical engineer. Well, technically I am, but seriously … I’m not an electrical engineer. I may have gotten the details of this wrong.
All rechargeable batteries will lose their charge if not charged in a long enough period of time. Apparently, if a battery gets sufficiently discharged, it will have trouble accepting a charge at all. The XBox will then become confused, interpreting the inability to pass current through the battery to charge it as the battery being fully charged (hence the “a few seconds of red light, followed by a green light” phenomenon).
Here’s the two step solution:
Plug the controller (with rechargeable battery attached) into the XBox with the Play ‘n Charge cable. The light on the end of the cable should turn on and be red.
If the light stays red for a couple minutes without turning green, keep the controller plugged in. Otherwise, unplug the controller from the Play ‘n Charge cable, count slowly to five, and go back to step 1.
After some number of tries (nominally less than 50), the XBox and battery should finally figure it out and charging should begin.
Radiohead’s latest music video was shot without cameras. Instead, they used a combination of reflected light and lasers to generate clouds of points in 3D. Google was nice enough to provide the rest of the world with some of the 3D point cloud data collected for that music video. A big piece of that data is about 2100 frames of lead singer Thom Yorke’s head. A frame of the original data (when output via Processing) looks like this:
If you look closely, you’ll notice that the point cloud is really noisy around the edges. A simple high-pass filter later and that same frame looks like this:
That’s a little more manageable. I figured, why stop at point when you can have 3D surfaces? One of the more straightforward ways to make a 3D surface out of a bunch of points is to stick a bunch of triangles in between the points, creating what’s called a Delaunay triangulation. This is a really compute-intensive calculation and I don’t exactly have a supercomputer on hand, so I did a lot of fudging and approximation. Even with all that fudging, each of these frames took as much as 5 minutes to render. This process has been running for most of last week while I’ve been at work. That same frame above looks like this when Delaunay-triangulated:
Notice that it’s a little noisy, which is mainly due to some approximation on my part as well as some leftover noise in the point cloud. The video below shows what happens when you sequence all 2100 frames together. Enjoy!
Posted: May 1st, 2008 | Author:Alex | Filed under:Fun and Games | Comments Off
Apparently there’s a fan-made project that aims to redo all of Sonic 2′s sprites in HD while keeping the gameplay physics intact. Apparently Capcom’s doing this with Street Fighter 2 for some reason (don’t get me wrong, it looks amazing).
It’s a shame that, since Sega is incapable of making a good business move where Sonic is concerned these days, this will never be allowed to happen. Still, a guy can dream.
Posted: January 5th, 2008 | Author:Alex | Filed under:Fun and Games | Comments Off
I just bought The Orange Box off of Steam. It turns out that, since I already bought Half-Life 2 and Half-Life 2: Episode 1, I can give the extra license I purchased as a gift. If anyone wants that extra license, let me know and I’ll hook you up – first come first serve.
Remove Garfield’s speech bubbles and you turn arguably one of the most unfunny cartoons of all time into a strangely moving, surrealist cartoon about a lonely single man talking to his overweight cat.
Here are some of my favorites:
More of these can be found at Tweebiscuit. Happy holidays everybody.
