Comments on: Sky-High Boggle Scores with Simulated Annealing http://www.danvk.org/wp/2009-02-19/sky-high-boggle-scores-with-simulated-annealing/ Keepin' static like wool fabric since 2006 Wed, 08 Oct 2014 14:33:23 +0000 hourly 1 http://wordpress.org/?v=3.9.2 By: JohnPaul Adamovsky http://www.danvk.org/wp/2009-02-19/sky-high-boggle-scores-with-simulated-annealing/comment-page-1/#comment-29582 Mon, 22 Feb 2010 07:12:55 +0000 http://www.danvk.org/wp/?p=412#comment-29582 Whoops, missed a line in that board.

RSLCS
DEIAE
GNTRP
ATESE
SMIDR

That’s the one, I’d love to be able to edit my comment.

All the very best,

JohnPaul Adamovsky

]]> By: JohnPaul Adamovsky http://www.danvk.org/wp/2009-02-19/sky-high-boggle-scores-with-simulated-annealing/comment-page-1/#comment-29581 Mon, 22 Feb 2010 07:04:56 +0000 http://www.danvk.org/wp/?p=412#comment-29581 10,000 Boards/second is impressive.

Question: How does it scale on multi-core shared memory CPU’s?

In November 2009, deepsearch.c was capable of scoring 70,000 random 5×5 boards per second with the TWL06 lexicon on a Core2 Q9450 @ 3GHZ.

How? An immutable finite state automaton operating as a perfect and complete hash table. That’s how.

RSLCS
DEIAE
GNTRP
SMIDR

This board is the best Best 5×5 Boggle board for TWL06. It’s worth 10,769 points. The word list is mind boggling.

search “Boggle deepsearch” on Google. http://www.pathcom.com/~vadco/deep.html

Final question: Why bother changing more than one tile, when the smallest change possible will lead to the best board every time? Does your algorithm guarantee the highest possible board in a period of time shorter than over night?

]]> By: danvk.org » Breaking 3×3 Boggle http://www.danvk.org/wp/2009-02-19/sky-high-boggle-scores-with-simulated-annealing/comment-page-1/#comment-23504 Sat, 08 Aug 2009 17:51:28 +0000 http://www.danvk.org/wp/?p=412#comment-23504 [...] Find a very high-scoring board (maybe this way) [...]

]]> By: danvk.org » Solving Boggle by Taking Option Three http://www.danvk.org/wp/2009-02-19/sky-high-boggle-scores-with-simulated-annealing/comment-page-1/#comment-23368 Wed, 05 Aug 2009 01:18:08 +0000 http://www.danvk.org/wp/?p=412#comment-23368 [...] we spoke about Boggle, we used Simulated Annealing to get at the question “what is the highest-scoring [...]

]]> By: Mike http://www.danvk.org/wp/2009-02-19/sky-high-boggle-scores-with-simulated-annealing/comment-page-1/#comment-18236 Mon, 16 Mar 2009 04:28:46 +0000 http://www.danvk.org/wp/?p=412#comment-18236 Awesome stuff, Dan!

We should definitely get lunch together at some point… haven’t seen you in at least a year…

Also, as a security guy, I present for your amusement: cross-site boggling

]]> By: Greg http://www.danvk.org/wp/2009-02-19/sky-high-boggle-scores-with-simulated-annealing/comment-page-1/#comment-17455 Thu, 19 Feb 2009 21:51:47 +0000 http://www.danvk.org/wp/?p=412#comment-17455 I recall a story of two slot machines that had the exact same payout structure and frequency (ie: if you were blind, they were identical machines), but one would earn the casino far more money.

The difference was that one of them would show far more “almost wins” where the user was one click of one of the wheels away from winning alot of spare change. The psychological “near miss” kept people at the machine longer. Debatably, they enjoyed the experience more.

]]> By: danvk http://www.danvk.org/wp/2009-02-19/sky-high-boggle-scores-with-simulated-annealing/comment-page-1/#comment-17447 Thu, 19 Feb 2009 19:41:08 +0000 http://www.danvk.org/wp/?p=412#comment-17447 Craig: that’s one of the details that interested readers will find in my code (http://code.google.com/p/performance-boggle/source/browse/trunk/anneal.cc — only 150 lines!). I use the metallurgy analogy. There’s an ambient temperature that decreases over time. At lower temperatures, I’m less likely to choose a lower-scoring board. You can see this in the board progression. At first, it’s pretty random. Then it starts to only improve.

Craig paragraph 2: That’s not an approach I’d considered, but I like it. My code is fast enough that I can easily consider all boards at a distance <= 2. (more on that in a later post)

Craig paragraph 3: Reader must strip my CSS.

Greg: Sounds like an idea for a startup! =) It only took about two seconds to do the full annealing run I included in this post, so it would be completely feasible. You could even imagine requesting a low-, medium- or high-scoring board. Or a high-scoring board with a “qu” on it.

]]> By: Greg http://www.danvk.org/wp/2009-02-19/sky-high-boggle-scores-with-simulated-annealing/comment-page-1/#comment-17441 Thu, 19 Feb 2009 17:38:07 +0000 http://www.danvk.org/wp/?p=412#comment-17441 Thats a pretty fun little analysis. I could see it being useful too. Imagine someone wanted to create a software-based boggle game for people to play online or whatnot. It would be more fun in general to play on high-scoring boards than low scoring ones, so weighting the algorithm for generating boards to be a little less random could improve the playability of the game.

]]> By: Craig Fratrik http://www.danvk.org/wp/2009-02-19/sky-high-boggle-scores-with-simulated-annealing/comment-page-1/#comment-17440 Thu, 19 Feb 2009 17:09:50 +0000 http://www.danvk.org/wp/?p=412#comment-17440 Very cool dan.

The way I way I learned simulated annealing, as time went on, you were less likely to take the lesser board. Like steel particles as they cool during annealing.

Also, I seem to remember that you considered all boards that were one move away, and typically, you took the best one of those. The annealing part was that sometimes you just took a random choice.

Finally, it’s a good thing I came to comment. The color of the text didn’t come across in google reader.

]]>