I have just received a communication from someone (unknown to me) via
LinkedIn, asking about a computer program that I wrote (and continually
revised) throughout the 1980s that solved the '8-puzzle'. I replied that I would have to get into my time
machine and set it to return 34 years, but first I'll retrieve whatever shreds of
memory I can find for the blog.
I came across this puzzle in a book written by
David Levy; looking at the list of publications on his wiki page, this was probably 'Computer Gamesmanship: Elements of Intelligent Game Design' , published in the early 80s. One has to remember that I first 'met' a
computer at the end of 1982: this was a teletype connected to a phone line
that was connected to a PDP-11 computer about 20 miles away. I also had absolutely no background in programming, so this book
talked about topics that were far above my ability. The 8-puzzle problem
served as an introduction to all kinds of topics in computer science: how to
draw a grid on a VT-100 screen, how to get direct input, how to check for
legal moves, linked lists, hash tables ... there's a lot in there.
Looking for the 8-puzzle on the Internet now, I see that it's a favourite topic of
computer science degree courses, which makes sense. I think that
this site
gives a good introduction to what the 8-puzzle is, who developed it (I remember
it as a plastic toy from my childhood) and how to solve it with the computer.
Note that this assignment is numbered COS 226 that probably means that this is
an intermediate course in computer science.
This site
gives another good explanation of the puzzle and how to solve it.
I wish I had access to these web pages back in the day instead of having to
stumble in the dark, teaching myself all kinds of techniques. All I had were a
few pages in Levy's book and another book about data structures in Pascal,
instead of detailed guides.
My program had two modes: user and computer. First the computer would create a
random initial configuration, then the user would be given the opportunity to
solve the problem, whilst the computer counted how many moves the user
required. For my program, this mode taught me about user interface: how to
react to user input and how to change the display depending on the
input.
But it was the second mode that was the more interesting: 'teaching' the
computer how to solve the puzzle. Levy wrote about the 'minimax' algorithm,
but it wasn't until one day I was in the computer science library of Bar Ilan
university that I found out what this was. I imagine that I was doing some
reserve army service in the lab
at Tel Hashomer hospital, as the university was within walking distance (don't
forget that I was/am a good walker; this was probably 2 km away). I acted like
I had the right to access books and journals, and no one asked me who I was.
Every few months I would have a new idea as to how I could improve the
evaluation function of the current configuration (basically, how far
the current configuration is from the goal) in order to figure out what the
next move should be. I also stored the various configurations for two reasons:
I wanted to prevent the computer getting into a loop, and I wanted to look at
the configurations myself to see how I would have acted. I remember now that I
had a standard configuration that took me something like 37 moves to solve;
any program version that took more moves needed to be improved. I also wanted
to surprise myself and see whether the computer could solve this test
configuration in fewer moves; after all, I'm no expert in this puzzle, and so
it would be quite possible that the computer could beat me.
On the left is a picture of the solved 8-puzzle, or as we would call it in
computing terms, the goal configuration. I note one major difference from
this configuration and my goal configuration (that presumably came from the Levy
book): mine had the empty space in the middle, so that the second row would be
'4/ /5' and the third row would be '6/7/8'. This may seem like a minor point but
it's very important.
Looking at the program code that has been stored
here
(I wonder how; did I give permission for this?), I am sad to say that although
there are comments, they rarely state anything that is not obvious. There is
certainly no explanation about the algorithm or how the evaluation function
works.
What Levy called IIRC the move generator (i.e. which tile should be moved next) appears to be implemented in the function makenode. Going back to the first picture of a real 8-puzzle, there are only two moves possible in this configuration: either the 1-tile would be moved down or the 5-tile be moved left. I would think that this latter move would be better then the 5-tile would be in the correct column but in the wrong row. Moving the 1-tile wouldn't appear to do much. But that's why the program has its evaluation function in order to calculate which move is better.
function evaluate (var p:square): integer;
var
i, tmp: integer;
ch: char;
blank: boolean;
begin
tmp:= 0;
i:= 0;
while i < 9 do
begin
i:= i + 1;
ch:= p[i];
blank:= ch = ' ';
if not blank
then tmp:= tmp + table[(i-1)*9 + ord(ch) - zero]
else tmp:= tmp + table[i*9];
if blank
then if i <> 5 then tmp:= tmp + 2
else
else
case i of
5:;
2,4,6,8:
if p[5] <> ' '
then if (p[preint[i]] <> prech[ch])
and (ch <> prech[p[5]])
then tmp:= tmp + 5
else
else
if p[preint[i]] <> prech[ch]
then tmp:= tmp + 5;
1,3,7,9:
if p[preint[i]] <> prech[ch]
then tmp:= tmp + 3
end
end;
evaluate:= tmp
end { evaluate };
The above is not spaghetti code: it's actually presented in quite a logical format, but there's no explanation. Earlier in the table there are definitions of tables used in this function, but these definitions are opaque: I don't remember why certain values were chosen or what they do. The name 'prech' implies to me that there function checked which tile preceeded which; apparently this was an effective approach.
