Tuesday, May 8, 2007

Puz15

Intro:
This is a Java programming project for my Video Game Design class in high school. It is a simulation of those puzzles where you have 15 tiles numbered from 1 to 15 and you have to slide them around to get them all in order.
The challenging part is to have the computer solve the puzzle for you. I'm learning different approaches to this problem in the class. (Meanwhile the rest of the class learns what an array is, just to give you an idea of how badly out of place I am)

Approach Number 1: Dumb Brute Force
So the simplest way to solve any problem: try every single possible solution until one works. This means taking the original board and creating 2-4 new boards, each with one of the different possible moves (2 if the empty is in a corner, 4 if in the middle, etc)
At the time I thought how I handled this was very clever. Have a container object that holds three things: the board, the one move it took to get to that board, and a pointer to the container that holds the move before this one. (Java doesn't support pointers in their useful sense, but that's what they really are. shhhh!) It's a tree, except instead of the roots pointing out to the leafs, the leafs point inward, which makes getting the complete list of moves at the end real easy. Just unwind the linked list back to the original board!
Unfortunately I later realized that it wasn't such a hot idea. Brute force means the number of movecontainers will grow very very fast. (By move 20 we are WAY into the millions of moves) For the first time, I ran out of memory! A lot sooner than I expected as well... Turns out that the Java Virtual Machine (where you code runs) limits itself to a predefined amount of memory, which is all it uses. I remember resetting this in Windows XP at some point just for the fun of it, but this was Linux, so I couldn't figure out how to do it...
15 minutes of google-fu latter: To changed the amount of memory allocated to the JVM, pass it the parameter -Xmx256m (In this case to give it 256MB of memory) This was fine because I do all of my programming in the shell anyways, so the complete command is:
java -Xmx256m classname
classname in this case being puz15. So there's that problem fixed, now back to the program to figure out why it ate up 64MB so fast...
That clever linked tree of move lists for each node, means that all the movecontainers that I've looked at and decided they weren't the solution yet, are still referenced by their children. This means the useless boards (integer array[16]) never get unreferenced and are never garbage collected by the JVM. This is where programming object oriented really shone. There is one function that unwound the linked list to collect the move list. Everywhere that needed a move list just called this one function, so I changed it from unwinding a linked list and had it just store a local complete move list. The older boards drop out of reference, garbage collected, bam, more memory!

Approach Number 2: Smart Brute Force
So then for the next step. As the program stood at this point, every board spun off 2-4 child boards, which each spun off 2-4 children, etc etc. Great, but many of those moves are moving one tiles back and forth, each time spinning off new lineages of stupidity, all rechecking the same moves. So what we need is some way to check if a board has already been examined and its children created before we bother repeating our work.
This is where I should have learned how to use hash tables, but I really hate the thought of hashing something down because I know that when you simplify something you might simplify two things to the same simplification. I came up with a personally favorable way to do it which guaranteed zero collisions.
Really two ways, both the same principle. Each board consists of 0-15 in 16 positions. (0 is for the empty space) Hey, 0-15, that's one digit of hex... I can represent each tile as 0-9 a-f, create a 16 character string and I can represent the whole board in a way that's real easy to sort, store, and compare later!
The second way is more complicated and I didn't implement it for technical reasons: 0-15 requires 4 bits to store. (15 is 1111 in binary) So to store the entire board I need 4 x 16 bits. That's 64... long integers are 64 bits! I can take each tile, bit left shift it (multiply by 2) to it's position on the board and just add all of them. (If you didn't understand that, it's ok) So then I end up with one number completely describing the board. Single numbers are even easier to store, sort, and compare than strings! The problem is that Java doesn't support unsigned longs as far as I can tell, so I only get 63 bits plus a sign bit (saying if it's positive or negative)
So long story short: I implement this "board to hex string" function and now it's smart enough to not try and solve it by endlessly sliding one tile back and forth.
It's still pretty heavy though, and takes more than 900 trials to solve a 10 move board. (At the same time it rejected more than 1000 duplicate boards, and that's not even counting the children of those duplicate boards or their children, etc!)

Approach Number 3: Informed Search
This is where the computer really starts getting smart and is less of a really fast monkey on a keyboard. I just started implementing this today in class but the concept for it's pretty simple. So as the program slogs through this giant field of possible moves, it'd be great if there was some way to figure how close something looks to a solution without actually figuring it out. Then based on that score, work more on the paths that seem to be heading towards the castle more than away from it.
The way I am doing this is through an algorithm called the Manhattan Distance, which is pretty much the vertical + horizontal distance between two points. So to find the "score" of any one board, first total the Manhattan Distances for all 15 tiles, then add on to that the number of moves it took to get there (To see if there is a more efficient way to get to the current board) and there you have it, a distance score! Now where before the queue for boards to be processed used to be just a list where new boards were added to the end, now they can be sorted and prioritized based on promise.

I will keep you readers updated on how this goes as I work on it. I think this Wikipedia linking madness is a good call as far as helping some of our less technical readers. Enjoy!

1 comment:

  1. Hi Kenneth
    You are clearly one clever dude mate! Gifted, I would suggest! Good on you!
    I had not realised you were a mere child so to speak compared to me anyways at 54 years old.
    When I was your age in 1970! ( I am a snake too! And snakes are very cool people) I contemplated studying computer Science and didn't because!
    I thought I had missed the boat! If only I had known, I might have been worth millions now instead of pretty close to nothing!
    Anyway, here I am now studying computer Science majoring in Internet and Forensics at the front of the next great revolution in computing as everything moves on to the web.
    Very exciting!
    I will be spending more time reading your blog!

    ReplyDelete