Some people got this optimization, others did not. This is the single most important optimization and is the focus of nearly all optimizations when dealing with larger boards.
If we started with a brute force searcher we can speed it up by orders of magnitude (1000-10000 times speed up is quite normal). If we can make it remember the positions it has seen in the past. The best way to illustrate this is to get out some pennies and place them on a paper board size 5 (or if you were a winner you can do this with your actual cracker barrel board). Place all pegs in then take out the pegs at holes 1 and 15 (top and bottom right). If you are missing a size 5 board here is a picture so you can at least try to mentally follow along.
Before we get going with this I am going to introduce a notation that we will use from now on for moves. The notation will be starthole-jump-endinghole … As an example 14-9-5 says to move the peg in hole 14 to hole 5 jumping (and removing the peg in hole 9).
So now that we have our board setup let’s look at how we can end up in the same place. If we were to move 13-14-15 jumping into the bottom right corner and we then moved 4-2-1 jumping into the top corner we would be left in a positions like this …
then
then we end up here ..
If however we were to reverse things from our starting board and move 4-2-1 into the top hole, then move 13-14-15 into the bottom right corner we would be left with the same exact board. By remembering that we have previously seen this board and that it was unsolvable we can prune our tree very efficiently.
then
then we end up at the same place
This optimization applies to nearly all searching problems but this one it is especially good for as it has a very high rate of repetition… To see just how high this rate of repetition is I used the problem set of all size 5 boards with 1 peg missing. I have added a counter to my entry as follows to keep track of how many previously found boards it was able to use as cutoffs .. To do this I added a public long cutoff to the UInt32Board class and in my Search(int) method I added the following line of code.
public long cutoff = 0;
if (found > 0) { cutoff++; return false; } |
Listing 1: changes to track cutoffs |
To see the cutoffs for yourself simply access this variable when you are done with the test to make things easier, you can just set a break point while it is generating the tests as it will be run for those boards already to determine if they are or are solvable. To give you an idea … in solving the first 15 positions it received 1508 cutoffs, keep in mind that these cutoffs are often quite high in the tree resulting in it not having to evaluate sometime tens of thousands of positions for each cutoff. To give you an idea of the difference, if I remove this optimization from my board my speed drop dramatically.
To illustrate the speed drop I will deal with a single board loaded using the following code.
static void SimpleTest() { int[] board = new int[28]; for (int i = 0; i < 28; i++) { if (i != 12) { board = 1; } } TestSimpleBoard(board); } static void TestSimpleBoard(int [] board) {
Young.UInt32Board b = new Young.UInt32Board(board); b.SetStartingPosition(board); Stopwatch s = new Stopwatch(); s.Start(); Console.WriteLine(b.Search()); s.Stop(); Console.WriteLine(s.Elapsed); } |
Listing 2: Code for benchmark |
With remembering previously seen positions my engine will finish this test in about 20 seconds (this problem is quite tough as it passes a parity check but is unsolvable). When I disable my previous board check, the code slows down dramatically. To run this test for yourself you can either comment out the code in my search routine building and checking previous positions or you can just comment out the “return false” near the top.
When we run my version without the remembering of previous positions we get a much different measurement. On my machine without the cutoffs it took over an hour before I killed it and it still was not done… why did it take this long? Well the version that remembered its previous positions benefited from a huge number of cutoffs while going through its search (79,150,041 to be exact which equates to around 1,000,000,000 leaf nodes it never had to search!).
As we can see from these basic tests remembering what we have seen and keeping ourselves from going down the same road makes a huge difference in how quickly we can process these puzzles. For those who were having a hard time beating brute force, this is the key in most problems. Of course when we get to larger puzzles we can’t always keep all of the positions we have ever seen so we need to get into some smarter algorithms.
How you store your previous positions is also paramount. We will discuss here for smaller boards and leave how to do it on larger boards for another post. A few people used what I considerred to be the best method which was just to store an array of bits (either as bytes or as UInt32s). You can then keep a single bit for every given position. For the largest puzzle this will work well on (a size 7 board which has 28 pegs) this will require a reasonable amount of memory 2^(28-3) or 2^25 bytes. This seems like a very big number but its not actually that bad, its only 33Mb of memory give or take. Storing a position and looking up a position are both assured to be O(1) operations as you have a completely unique key (the board itself).
Others experimented with other methods of storage, an interesting one was Wil who used a binary tree to store this data. By using a binary tree you may in many circumstances end up using less memory as you are only storing the positions you know to be solved (as opposed to every possible position). This will quickly fall to being more memory in cases where you have big problems though. The other issue you may run into with a binary tree is that it is O(log n) in terms of search speed. This can quickly add up if you are getting alot of misses as they will be your worst case.
One thing which should be noted about the storage of previously saved positions is that they can be shared by any board instances that are dealing with the same size board. It doesn't matter what your starting position is, the same stored positions still apply. For this reason I created a small manager class to deal with these saved positions. In fact these saved positions when done in a table based format (array of bits) are even completely thread safe without locking. The worst thing that can possibly happen is that you lose a saved position in the case that 2 threads are writing the same are of the array at the same time. Since this is only being used to help cutoff search paths this is not a major concern as it will only cost you a cutoff .. it will not in any way affect the correctness of the search.
We will discuss this more in later posts dealing with making our searching happen in parallel. Before we get there though we will look at some further algorithmic optimizations that we can use for all boards, the next post “Mirror Mirror” will discuss a major algorithmic optimization that a few people implemented.