My exhaustive testing indicated that the shortest path to the goal position in Scarne’s challenge was at least 71 moves long. I relaxed the criteria a bit, and obtained a solution which requires 72 moves, which (if I haven’t made an off by one error, still checking that out) is an actual minimal cost solution!
This solution doesn’t actually include the 5 hopping moves at the beginning (it complicates the calculation of the heurstic values and slows down the search), but I suspect I’ll get that figured out someday soon. Enjoy!
After running all night, I can assert with confidence that there are no paths of length 71 or less. I’m obviously not going to get to the ~100 move mark with the current heuristic and transposition tables alone.
Addendum: I’ve actually just got a version of the game which doesn’t include the initial five “hopping” moves. I need to work on appropriate heuristics that take into account these initial five moves and create an appropriate move generator soon.
After a couple more hours of typing, I managed to get a start on Scarne’s Challenge. I’ve got a simple version of IDA* with transposition tables working, along with a simple heurstic based entirely on summing the shortest path distance between where a node is and its desired final position. It is smart enough to find solutions to simple problems. For example, if you start with the board in the goal position except with 2 and 1 swapped, it finds the 22 move sequence that reverses their position after searching 411,573 nodes. For the official challenge position of course, it fairly quickly determines that the path must be at least 66 moves long (not suprising), but the combinatorial explosion is working pretty hard there. I obviously need to use a smarter heuristic (perhaps based upon the ideas that Korf used in solving random instances of the 5×5 puzzle) to have any hope of finding the answer to this problem in non geologic time.
You can swap two pieces in place in Scarne’s challenge, but not in the normal 8 or 15 puzzles. This is because there are no odd length cycles in the 8 or 15 puzzles, but there are cycles of length three in Scarne’s challenge. The easiest way to see this is to draw the graphs out The 15 puzzle has no triangles in the graph, but Scarne’s Challenge does. (Does this mean that Scarne’s challenge is in some sense easier? I’ll have to think about it some more.)
Well, I decided to start my exploration of the Scarne’s challenge by writing a simpler program to test out my recollection of how the A* algorithm worked. I chose to implement a simple version of iterative deepening A* for the 8-puzzle, the simple 3×3 sliding tile puzzle that perhaps might be more familiar as a 4×4 puzzle. I spent a little less than two hours writing the first version, which did manage to find minimal solutions to the search problem, but seemed to search too many nodes to do so, even allowing for the simple heuristic that I used.
Continue reading “On search…”
At the Hacker’s picnic the other day, Bill Ragsdale was trying to drum up interest in participating in writing computer players for Scarne’s Challenge, a solitaire boardgame first created in 1950. The board has 24 numbered spaces plus an empty center space, and 24 numbered tokens placed randomly. The idea is to slide pieces along lines into the open space, and restore all the numbered pieces to the appropriate spaces.
It is similar in concept to the popular 15-puzzle: a sliding block puzzle, but with a larger search space. The number of possible board starting positions is 24!=620,448,401,733,239,439,360,000, or about 620 sextillion possible configurations. Clearly exhaustive search is not a good way to proceed with this problem.
Nevertheless, it appears to be on the border of doability using clever versions of iterated deepening A*. Korf and Taylor found optimal solutions for the simpler 24-puzzle.
I’ve begun working on implementing a computer player using ideas from their papers.
Excuse our dust. Eric Meyer’s book on cascading style sheets made me rethink the strategy and design of my website, and it will probably take a few more days of tweaking for the dust to settle. Hopefully the end design will be worth it. We’ll get back to real projects soon.
I just picked up a copy of a new book on Cascading Style sheets by Eric Meyer. He’s a wizard of all things having to do with style sheets, and rather than just describe the syntax and options (which are easy to get from htmlhelp.org) he presents style sheet wizardry in the form of thirteen projects that he works through a step at a time. While I just got the book yesterday, it seems quite good, and I’m undoubtably going to spend some time this weekend putting some of it to use redoing the templates for this site. Don’t be surprised if this looks worse before it gets better!
Just like the talking Barbie who drew the ire of feminists everywhere by claiming that "Math is hard", I find myself asking more and more often "Why is programming so hard?"
Continue reading “Why is being a programmer so difficult?”
Open source software owes its existence to the convergence of three technologies:
- Fast, cheap computer hardware
- Fast, cheap networking
- Cheap compilers
Inexpensive PC hardware provides the raw grist for programmers. GCC provided a reasonable way to program this hardware. Cheap networking allowed the fruits of their labors to be propagated to people all over the world.
We’d like to think that free software will prove to be a never ending resource, but I believe that open source software is in
serious danger of becoming extinct.
Continue reading “Threats to Open Source Software…”
I love twiddling around with fonts, but let’s face it: most of them completely suck, especially for display on screens and in web browser. Without any doubt, the best widely available fonts were Microsoft’s core webfonts, which used to be freely downloadable from their website. Unfortunately, they recently
announced that they were withdrawing free downloads of these fonts.
Continue reading “Say Goodbye to Microsoft Webfonts?”
I had no meetings scheduled for the afternoon, so I decided to trek into San Francisco and attend the Linux World Expo. I was mostly curious to see how the shakey economy had affected the world of businesses without business plans. I was expecting a blast crater on the exhibit floor, but was actually surprised at the fair number of booths that were reasonably well stocked with both workers and attendees. Still, I couldn’t help feeling that not all is rosy in the world of Linux.
Continue reading “LinuxWorld Expo”
Recently I’ve become rather interested in the topic of the design and printing of books. It seems that many modern books are incredibly poorly designed and typeset, despite the existence of excellent tools that should make book production simpler. The problem is that while software has been created to reduce the tedium, it has not created tools that replace inspiration and skill. In trying to understand the process of book design and typography, I bought an inexpensive and excellent book by Eric Gill called An Essay on Typography
Continue reading “An Essay on Typography“
In an earlier story I mentioned the project to fly a model airplane across the Atlantic Ocean. So far they have managed to lose two of their four planes in rather disappointingly short periods of flight. Check here for updates. I’m keeping my fingers crossed for them.
I have a love/hate relationship with Slashdot. They do occasionally point me at interesting stories, some of which I shamelessly swipe for this site. But often they post stories with an editorial slant which doesn’t even border on absurd. No better example can be the story today entitled
Will CGI Collapse the Hollywood Economy?
Continue reading “Will CGI Collapse the Hollywood Economy?”