Making a useful automatic solver for sokoban puzzles has been a project of mine for years. Now, I have many projects and little time, but this one I've worked hard at, many times, from many different approaches and in many different languages.
Returning to the language I know best (after all), Java, I have finally made a useful sokoban solver. It's possibly the most stupid solver I've written, it's basically a depth-first search, but it works. And it's generic! I have made a library which can take as input arbitrary puzzles, and do a depth-first search on the game tree. I have even made a (much) improved version, which needs some more info, but which can search from the end positions at the same time.
I used a simple labyrinth game to debug the interfaces. When it worked, I tried it out on a marbles/atomix type game - that was less useful, because although marbles is a reversible puzzle of the kind my library is designed for, any given state has quite a lot of predecessor states, and there are many possible end positions. Still, puzzles with three or four marbles were usually solved - eventually :-)
Sokoban, to my delight, was much easier. Even with no checking for dead squares (squares where a crate can never be safely placed), and just forward search, the first 11 puzzles in Yoshio's Autogenerated fell in seconds! David Skinner's Sasquatch, though, is a lot tougher. When I implemented dead squares checking, the first two fell easily enough, but after that... There are usually a lot of crates in handmade levels. I suspect I have to check dynamically for stuck crates to have a chance at those. But I haven't even implemented backwards search yet, so there is plenty of room for improvement!
It would seem sokoban is easier than marbles/atomix for the purposes of this search. On the other hand, I've tried to make sokoban solvers for years, so I've picked up a lot of tricks, like dead crate elimination. Perhaps there are such tricks for marbles/atomix too, but I couldn't think of any.
It's the java standard library which has made this possible for me. In particular the new generic collections in 1.5 (which Sun has decided to call 5.0 for PR reasons). Also, Stig Brautaset's Generic Game Tree Library has been an inspiration, although I haven't really looked at the code... I've just read about it and tried the examples.
In fact, this project has been so wildly successful (I only started it days ago!) that I want to make a generic alpha-beta-search game-tree library of my own, for java, as a school project. Threaded, so that the computer opponent can look forward when it's your turn to move, too. I don't know if Stig Brautaset's library is multithreaded, but I suppose that if I want to avoid charges of plagiarism I shouldn't look too closely at his source code anyway :-)
Comments are disabled because of spam. Instead, mail me at stud hials no with 020042 in front of the @. That one is for you too, Stig. (You do google your name occasionally, don't you? :-)
Via Crooked Timber I find this hilarious collection of hilarious wisdom from British folk ballads.
If we apply it to norwegian folk songs we get some fun too, although I think we should include the danish ones as well. Honorable mention to anyone who can identify the songs these are taken from.
---
Don't sell your fiddle to start farming. You will regret it.
If you are a girl at a dance, do not loosen the red golden bands you've tied your boyfriend with. He will run off if you do.
If your boyfriend was lost at sea and a young sailor approaches you and asks you to marry him, refuse him. He will probably turn out to be your old boyfriend, after all, and then he will be impressed by your faithfulness.
If you come to a town where people are commiting suicide on a grand scale because their suitors/daughters/uncles/mailmen commited suicide first, get out of town before you're caught up in it, too.
If you are a poor girl, don't save your coloured cap for your wedding, even if you got it from your mother. You will probably never marry anyway.
But even if you are poor, marrying people who live inside a mountain is never a good idea.
If your mother tells you that she saw your wife with one of the people who live inside the mountain, kill your wife. Don't worry if she is innocent, she will plead for your soul in heaven if she is. You will go to heaven (although your mother won't)
If you are a pretty girl, you shouldn't marry anyone unless he's good for at least 500 riksdaler.
If you are out on the sea to fish coalfish, and your annoying neighbour appears, grab your chance, take your oar and knock him into the sea.
If you've watched your favourite sheep carefully for 15 years, don't let her go off on her own. The wolf will eat her.
It's a good idea to shoot huge crows before they kill you.
If you are a knight and a fairy wants to dance with you, it might be best to say yes, even if your fiancee is waiting. If you refuse her, she will curse you, you will die, and you fiancee will die of a broken heart.
Don't boast too much that you'd rather have your boyfriend than the king. The king might be jealous, come to slay your boyfriend, and then you'd be obliged to avenge him.
If a dragon wants to marry you and threatens to kill you if you don't, marry him. You're too young to die, and anyway he's probably just an english prince who has been cursed.
List of norwegian ballads from UIO
I wrote a letter to Vårt Land again. It was in response to what a principal from a christian private school wrote, but since I didn't have it in front of me (and din't even remember his name) I didn't direct it at him specifically.
My basic point is that it would be wrong for the state to prevent parents from instructing the beliefs to their children, even when these beliefs are unfortunate and wildly opposed to the views of the majority (or in other words, just plain wrong).
I took the new chronology theories supported by Anatoly Fomenko as an example, along with creationism. Hopefully the creationists see that there are problems with allowing everyone to teach anything.
To amend that, I suggest that although society can't censor parent's instruction, society as a whole also has a duty of instructing its children, without being censored with the parents. What I propose (in fact I think this is more or less current law) is that in the standard lessons such as science and history, the official views should be taught - by people who know and believe in them, otherwise it won't be a fair representation. Then, in lessons peculiar to their school, the unorthodox beliefs will be taught. Although the teachers in these classes can speak as if creation was a fact and misrepresent science all they wish, it must be obvious to the students that this is not what society at large believes: they can't call the class "science" (or "naturfag"), because that is reserved for the official views. If this confuses the students, well, that's a pity, but such is the price of being a minority in a pluralistic society.
The alternatives, which are
1. supressing some or all dissenting views based upon some arbitrary criteria
2. Allowing all views to be taught as equally valid
are worse, and unacceptable, although I suspect that many people will choose 1. and make poor attempts at explaining why of course their beliefs are reasonable, but everyone elses is not, and should be disallowed.
I could have chosen holocaust denial as an example rather than the more benign "the middle ages never existed" theories, but out of respect for Godwin's law I didn't. Godwin's law applies in more places than usenet, it's just bad form to draw in nazis everywhere, it makes people shut their ears, even when there are important points to be made.
I did write that article, and posted it in a comment at Norvegicus. Magellsen liked it, so he put it up as a guest feature (after asking me first, of course). Wow. I have a great deal of respect for the Norvegicus people, having my article published there is a big thing indeed for me.
I might want to translate it one day, but there are other things which should probably be emphasised in a text directed at english-speakers. I have always wondered why US-style libertarians are so keen on harsh punishments and the death penalty in particular. From a liberal point of view, punishments are right out. If we live by the creed "My freedom ends where your freedom begins" (plus the assumption that our freedoms are essentialy the same, of course - that we are of equal worth), then making judgements and proscribing mandatory acts of repention is wrong. The only thing we are permitted is absolutely minimal self-defence (though we may discuss that that means, of course).
Oh, and if anyone reads my weblog they may notice that I have disabled comments. This is because I had to delete over 200 comment spams after I gained internet access again. My version of movable type has no spam filtering, and you have to click-and-delete every single post. I notice that my webmaster, Paranoidkoala, is experimenting with a new system. I sure wouldn't mind switching to something better...