“I’m glad Ben hasn’t had any more insane posts about Boggle. That kid is whack. Wait… what’s this? Another Boggle post? AUGH! <insert hot pokers in eyes>”
First of all, did you know that there are two versions of Boggle. There are 4x4 and 5x5 grid versions. The 5x5 versions disallows three letter words. I had initially started with 5x5 but then switched to 4x4 when I realized that’s what the original game was. Plus it was a lot faster to run my program on a 4x4 board.
Some interesting game facts I learned along the way:
- The longest words that you can make on a 4x4 board are inconsequentially, quadricentennials, and sesquicentennials.
- To prevent a certain word, F and K only appear on the same cube so they can’t be used in one word.
Anyway, yes, it’s true that for the past 2-3 weeks I’ve had Boggle on the brain. After finding a very quick way to solve for all the words on a Boggle board, I wondered if the cubes that come in the Boggle box are the optimal set of cubes. Is it possible to generate a new set of cubes that produce a higher average score per board than the cubes they provide?
This stymied me for quite a while, but a genetic algorithm ended up solving the problem for me.
Background
The basic idea of a genetic algorithm is to have a population of different genes. Each gene in this case represents 16 Boggle cubes, enough to fill a 4x4 board. Each gene is used X times to gather an average score for that set of cubes. After each gene has been thoroughly tested, a weighted random algorithm breeds genes together to form a new population which, in theory, carries on the strongest traits of the previous population. Random mutations are thrown in to stir up the pot a little. Wash, rinse, repeat. In theory, your gene pool gets a little better every generation.
Details
I started off following that algorithm pretty closely, but along the way I made some modifications.
- Breeding happens at the cube level. So I take X cubes from the first parent and n – X cubes from the second parent.
- Every time a word is found for a given board, I increment a hit counter for each cube that was used in a word. During breeding, I weight the cubes based on the number of times they were used in a word in that generation.
- Mutation happens per side of each cube. If the random number generator says a mutation should occur, the letter I pick isn’t quite random. It’s weighted based on the frequency of each letter’s occurrence in English words.
- I added multithreading using the Smart Thread Pool. Each gene got it’s own thread and then the threads would recombine for breeding at the end of a generation.
Settings
- There are more than 1,000,000,000,000,000,000,000,000 possible boards for any set of 16 cubes. Once I realized that (thanks to Dave for pointing that out) I had to really crank up the number of boards I try with each gene before moving on to breeding. Around 200,000 boards gave a pretty good estimate even though it’s still a VERY small portion of the total number of possible boards.
- I cranked up the mutation rate once I started mutating per cube side and picking the most frequent letter. Before that, I wasn’t getting enough mutations to make things interesting because a mutation would replace a relatively good cube with a completely random one which was very unlikely to get picked in the following generation. Once the mutations became generally useful, I made them happen about 0.5% of the time.
- I started with a population size of 50 genes but eventually cranked it up to 200 for a little more diversity.
- It only took about 12-15 generations to peak at a pretty good solution.
Before sharing my results, I’ll tell you that when I ran the boggle cubes through a million board shakes, I got an average score per board right around 73. Note that this would vary slightly based on the acceptable word list that is used.
Initially I was having trouble getting above 60 but once I made the tweaks mentioned in the bulleted list above, I was able to get a set of cubes with an average score of 115! Here it is:
| EONMXH | ATILSM |
| VASTHN | RSAIOL |
| NJWLOD | FTDAIG |
| TOAETT | SAORIO |
| SICPTT | IEPWKE |
| EICETH | RDPEON |
| RIEEST | EAUPRT |
| AAEIBW | MASYDN |
I’m curious how Alan Turoff came up with their set of cubes. What was their metric? It was created in 1972 so I doubt it was done using a computer. Was Alan a brilliant linguist? I determined the success of a board based on the total number of points available on a board, but it would also be possible to do this by looking for the most number of words per board.
What I have found is definitely NOT the optimal set of cubes. I think something other than a genetic algorithm is needed because it is very influenced by the random set of cubes that is started for the first generation. Simulated annealing might be better, but I think I’m going to try to drop this little obsession and call it good.
Unless one of you jokers can come up with a better set of cubes than me.
The other night, I decided to look into how to create 8-bit music. You know… that music style that you heard on your original Nintendo. Think Mario.
It turns out there is a thriving community on the intarwebz around this type of music. FamiTracker is one of the most popular editors. Creating a new song means typing in each note key by key, defining the falloff off the volume and many more parameters. I created the first bit of Moonlight Sonata in MP3 form for your listening pleasure.
The whole idea started because I thought it would be fun to have Tyla walk down the aisle to an 8-bit version of the Wedding March. It’s probably a good thing I’m not in charge of the music.
There’s not way around it. Tyla cries at movies. A lot. I’ll be sitting there enjoying the movie and maybe even laughing, but when I look over at her she has turned into a waterworks. Anything involving a dog is usually good for a few tears. Who knew that “The bad man punted Baxter” wasn’t comedic genius? No worries Tyla, it’s just one of the many reasons I love you.
The other night, she forwarded me a website called cryingwife.com. This guy posts videos of his wife crying after movies like Star Wars, Lord of the Rings, and even Dawn of the Dead.
Kudos to this guy for turning it into an internet sensation. He’s making the talk show rounds so if his site is down, try again later. It periodically gets hammered.
PS. Did you see in the FAQ that he has two dogs named n00b and ROFL?
Crystal Mountain recently announced that as soon as the season ends this year (April 19), they will begin installing a gondola from the base area to the top of Rainier Express. While this doesn’t open up any new terrain, it should reduce congestion on the Rainier Express lift and also provide a nicer dining experience at the Summit House in the summer. Over on my SeattlePI blog, I did an interview with the Crystal Mountain marketing team to get some more details. I’ll post it here to save you a click, but you can go to the SeattlePI Ski Blog for the full thing and my other ski related posts. My questions are in italics and their answers are verbatim.
How long has this plan been in the works? We submitted our Master Development Plan to the Forest Service back in 1999, along with 6 alternatives. The approval came in 2004.
How long will the ride be from the base to the top? 10 minutes
What is the capacity of each cabin? 8 people, with a total of 18 cabins to start, and the option to add an additional 18 more. Each cabin costs $40,000.
Will the top of REX be relocated at all to make room for the gondola? No, see photo attached.
Will this be a new gondola or was it purchased from another resort? It will be brand new, we're ordering it from Dopplemyr.
How will the gondola towers and associated tree clearing affect Exterminator? There will be very little tree clearing and the towers will not affect the skiing on Exterminator, they will be off to the skiers left of the run.
What is the planned scope of the terrain park? A lot of this is in the works, we have a guy (who's currently the terrain park superviosr at Park City – he will manager our terrain park next winter) working on the layout and features right now. Mostly jib features, boxes, rails and other things to bonk/jib off. Boxes and rails? Yes! Jumps? No big table tops or anything like that, just small jib features. Halfpipe? No
Will the terrain park have a park pass program associated with it like other local resorts? Still TBD
When people see large expenditures like this, many people think that a ticket price increased must be coming with it. Will we be paying more next year? That is not a safe assumption. We're working on ticket and pass rates now, one of the ideas is to leave the ticket rate at $60 and give people the option to pay more (like $5-7) for Gondola privileges. We plan to have rates set by the end of March. And people can expect season pass rates very similar to last year. We're going to offer the Quad pass again, which will be under $600 for unlimited access! You can't beat that!!
Will the gondola be the only lift open for dining during the summer? Yes, starting the summer of 2011.
Are there any plans to bring back scenic lift rides or lift-served mountain biking in the summer? Scenic rides & Sunset dinners at the Summit House (Washington's highest restaurant) are for sure. Mountain biking TBD. We're also looking into installing a zip line for summer 2011.
Some day when I’m old, one of my grandkids is going to ask me what I drove when I was younger before hovercars were invented. How that kid got past the armed guards protecting the Intergalactic Ruler’s Office is beyond me, but I should probably have an answer for him before the guards come to take him away. Crazy kids.
So here’s what I’ve owned up to this point. Before this, I drove a 1989 Ford Taurus LX and a 1991 Ford Probe GL but those both belonged to my parents.
| Vehicle | Years Driven | Picture |
| 2002 Ford Mustang GT Premium | 2002-2006 |  |
| 1995 Kawasaki Vulcan 800 | 2005-2009 |  |
| 2006 Subaru Impreza 2.5i Wagon | 2006-present |  |
| 2009 Kawasaki Concours 14 ABS | 2009-present |  |
AndyD recently notified me of some distressing news: the original Red Robin location is closing! It’s at the south end of University Street Bridge in Seattle. I’ve eaten there before, but somehow I didn’t know that was the very first one. The Seattle Times has a nice writeup on the history of the location and the ensuing franchise. I find it amazing that the founder sold most of his stake in the company in 1985 for $6 million and then sold that original building for $2.2 million a few years ago.
It’s sad that such a great restaurant chain won’t be keeping it’s original location in tact. I guess, at least for this location, there really is a bottom to their bottomless fries.
I’ve had key lime pie on my mind for quite a while, and, while standing in the grocery store last weekend, I decided it was time to give it a shot. I pulled up a recipe on my phone and was shocked at how simple it was. Key lime juice, egg yolk, and sweetened condensed milk. But what is a key lime? Can I use regular lime juice? I ended up finding a bottle that said it was key lime juice so I went for it. It turns out that key limes are a lime variety thought to have originated in the Florida Keys.
It was ridiculously simple to put the pie together. I didn’t do any whipped topping, but it came out delicious. This recipe comes from the Nellie and Joe’s Key West Lime Juice bottle.
Ingredients
- 14oz can sweetened condensed milk
- 3 egg yolks
- 1/2 cup key lime juice
- 9”graham cracker pie crust
Mix all the ingredients together and pour it into the pie crust. Bake for 15 minutes at 400 degrees. Let sit for 10 minutes before refrigerating. Serve cold.
More Posts
Next page »