Use of DeBruijn's criteria to curtail sort duration

I have a concern. After viewing PegSolitaire, I see now the programmer uses 'DeBruijn's sums' to determine whether a result is possible. As yet I have no idea how to calculate these sums, but only know of their existance.

My question is: Is it regarded as unfair to do research to learn how to generate 'DeBruijn's sums'? It would surely result in the algorithm never taking more than 3 seconds to resolve.

I would not even had brought this up, as I consider this to be unfair, as you should use your own knowledge toward solving a problem. But xs0 mentioned a few days ago that there is a way to determine if a 1-peg solution is possible. He mentioned a 45 second problem being reduced to 2 seconds. This type of improvement is likely due to the use of these two 'DeBruijn's sums' to figure that no 1-peg solution is possible, and stopping as soon as a 2-peg solution has been found.

Is this the precedent in these PHP contests, to do research to aid in your solution? Also, I would like to know whether xs0 did research into these 'DeBruijn's sums' to enhance his algorithm.

I see he is on the focus group, so it is likely he did research into this peg problem while it as under consideration.

No disrespect, xs0, I just want to figure out what the rules are. This contest is about PHP coding, so perhaps working out the algorithm is less important than actually coding it.

Again, I only know of the existance of these sums, not how to generate them. I will only look this up if it is okay to do so.

When I looked at PegSolitaire again, I realised it was staring me in the face. It very easy to see from the operation of PegSolitaire how the De Bruijn sums are calulated. And they are always equal for the triangle board.

In fact, the modifications to my code were incredibly simple, and didn't add anything to the main algorithm, just a little bit before. It does not slow the algorithm at all. It took about 4 minutes to code.

So my original 74 second problem which I eventually got to run in 40.35 seconds, now takes 0.122 seconds to complete.

I haven't done much testing, but I am 99% sure no arrangement will take more than 10 seconds, and probably a lot less.

My algorithm is definately not perfect. I have already found layouts where it does not find the least moves.

Doing research on the problem is perfectly acceptable. Would you build a bridge without first researching other bridges to see where their strengths and shortcomings were? Doing research on the contests is the same. Feel free to dredge up any research you can. Pretty much any problem that I present is coded out there somewhere. Just remember, everyone else is on the same playing field. You still need to find a way to win. If everyone comes back with the same algorithm, it will come down to speed. That means the best PHP coder wins, i.e. whoever can make PHP perform the best...

No, I didn't do research into DeBruijn's sums

Also, 45->2 seconds improvement was not a result of what I did use, but resulted from inserting a "-" character somewhere in the script. It did worse on other boards, though. In any case, it was in reference on Anonymous wanting to get a hold of a difficult board - I was trying to say that no board is difficult for all algorithms...

You should also know that Matt already chooses a problem before forming a focus group, the group only helps make rules as clear as possible. It's not possible for a group member to influence the problem in such a way, as to make his work easier; the only advantage is 1-2 days of knowing the problem before anyone else does.


xs0

xs0: I was just speculating, not accusing in any way.

You had me worried, because it sounded like you reduced your algorithm from 45 seconds on one problem to 2 seconds, while keeping the good results on all others. I had been trying the same, but couldn't achieve it.

In my mind I imagined that you had done research into it, resulting in the sudden improvement.

That's all it was. I have no problem if you had researched into it, because that is allowable in these contests, I now know. But I believe you when you say you did not.

The only research I have done is to look at the program Peg Solitaire. For the disc stacking, I did no research.

Too bad I discovered this contest near its end.
I also just began coding in PHP.

PegSolit uses a breadth-first approach with an internal limit of positions for every level (I think it's 100,000 or so).

Does anyone used a similar approach ?
Also, does anyone used bits representation for the triangle ?

JC

JC: Speak english, my man. Breadth-first with limit on positions... you are confusing me.

About using bits to store pegs, I also thought about it, but to check for potential moves, you need to AND with 1 << n. Doing this lots of times could be annoying. You could use defines, but for me, they seem to be slooow.

Also, using an object for each hole allows you to link an hole to certain neighbours, which can simplify the setup.

For me, I like the code not to look too scary. Using bits could end up being good, but I fear the code will not look too nice. I am a C++ programmer, and often use bits and <<, >>. Especially in macros. But as PHP programmers are typically closer to web-page designers than programmers, it might be more difficult for people to benefit from more confusing code.

Just my 2 cents.

>JC: Speak english, my man. Breadth-first with limit on positions... you are confusing me.

Breath-first search means that the game is explored level after level, instead of a depth-first search.
In the pegs case, this means that you take the starting position, store all boards after the first move (this is level 1), then take all these boards and play one move on them, storing them (level 2), etc...
This method is efficient on this kind of problems (I'm using it to solve the french solitaire problem, with billions of positions :-)).
Using a limit means that instead of storing ALL intermediate positions, you store only a certain number (for example, 100).

The difficulty is to parse the tree in the reversed order, to get the solution !

>About using bits to store pegs, I also thought about it, but to check for potential moves, you need to AND with 1 << n. Doing this lots of times could be annoying. You could use defines, but for me, they seem to be slooow.

Yes, but you can easily generate some PHP code with a C++ compiler, for all the possible moves ???
No need to shift !

Something like:
if ($b&65537 && !($b&256)) domove(1);
seems pretty efficient (2 bits must be set, and 1 bit must be cleared, this is perhaps not the best way).
Also, 28 pegs=28 bits.

>For me, I like the code not to look too scary. Using bits could end up being good, but I fear the code will not look too nice. I am a C++ programmer, and often use bits and <<, >>. Especially in macros. But as PHP programmers are typically closer to web-page designers than programmers, it might be more difficult for people to benefit from more confusing code.

I don't know how much moves there are, but I guess there must be 76 or so.
76 moves give ONLY 76 lines of cryptic (and boring) code.
Also, you can put the moves in the order you prefer. Perhaps with center moves first ???

Doing loops on interpreted languages seems slower than using straight generated code...

JC

JC, when you talk about not using a loop, are you talking about the loop through the 45 possible moves for any layout?

Are you going to unravel a for loop with 45 iterations? It may be worth looking into, I hadn't really thought about it. Also, how will you handle checking the branch against previously handled branches. Or will their never be previously done branches, because you are doing one level at a time.

You start at level 1, and generate copies of all boards with different starting moves. Obviously, you would need to use bits to do this.

If you stop generating layouts at each level at 100, surely that won't be too good. After your first cut of 100, each following one will only be the left portion of the previous level's possibilities.

Will this not be detrimental to the results?

And why 100? Surely 1000 would be better. It should be possible to get the processing for each layout < 0.001 second. 28 levels would mean that it would definately take less than 30 seconds.

Also, if you had two seperate moves, that didn't affect each other, you could do either move first, followed by the other. This would result in two equal layouts in two level's time. Would you simply remove the duplicates at the new level? How would you then get the move list at the end? You store the move with the layout, as many as their are. At each level, do you store all the moves that resulted in each particular layout with that layout. You could end up with 1000 arrays, each with 15 moves and a layout. Arrays in PHP are objects, are they not? Or would you store the moves in base 36 in a string?

Now that I think about it, that could very well work. The only question is, how fast will it run in PHP? I will have to find out...

-edit-

Sorry, I'm a little bit tired. Obviously, 45 links couldn't be stored in base 36 (duh!).

Ah, after following what Vertigo was saying and playing with the program, I now see what the sums are about... I can't prove it or anything, but it seems to somehow make sense.

Ah, I dno't know if I can implement it in 4 mins though :O
Then again, I still can't go faster than .5 seconds per state (the same problem I had on Fri)

>JC, when you talk about not using a loop, are you talking about the loop through the 45 possible moves for any layout?

No, simply something like that:
function solve($board)
{
if ($board&bits1 && !($board&bits2))
{ solve($board^bits3); }
...
}
The if() line must be repeated 45 times, with different bits1, bits2 and bits3 !

>And why 100? Surely 1000 would be better. It should be possible to get the processing for each layout < 0.001 second. 28 levels would mean that it would definately take less than 30 seconds.

I said 100 as example. I have no idea what might be the better value. I think this can be determined empirically...

> Would you simply remove the duplicates at the new level? How would you then get the move list at the end?
Of course, you can use a hashtable to store all the positions. This should automatically remove the duplicate positions.


About the DeBruijn criterion, it's a pattern over a board.
There are 2 kinds of patterns on a square game:
123123
312312
231231

and
123123
231231
312312

Computing a sum should be equivalent to xoring the values where there is a peg.

JC

I don't see how these things are too useful, because this method does NOT deny the existence of 1-peg solutions; it limits your search, but I don't see now how this can be only a 4-minute process unless your algorithm was previously along these lines...

Finally we can talk about stuff

First, I think that the DeBruijn's sums are not very useful - they'd help if one wanted to reach a particular ending state, because it's a criterion for determining whether that's possible. But in this contest, no particular end state was requested, so its usefulness is limited. OTOH, it does seem that if the sums are 0, a 1 peg solution is not possible, so that can be used. I'm not sure if it works in general, though.

I found a similar approach - I labeled all holes with A, B or C, so that each move involves one hole from each group (from top to bottom, left to right it goes ABCCABABCABCABCCABCABABCABCA). Now you can play the game with just these three groups. Basically, only 2 things are possible - either you end up with 1 peg or with 2 from the same group. In the latter case, you know you can't get a 1-peg solution. While it doesn't seem very significant, it is very useful to be able to stop searching on 2 pegs - in most cases such a solution is found very quickly.

I used bits to store the boards. While actual move finding is not that much faster than with using arrays, it does reduce memory usage considerably. A 28-member array or object is definitely more expensive than a single integer (I'd say at least 56-fold - one integer for index, another for value for each member).

A big speedup I got was from limiting the moves checking for each possible move. If you make the move 4-2-1, you don't need to check the whole board again - the moves in the lower part are either still possible or still not possible. So I hacked up a proggy that generated those 90 functions (I checked with Matt -- this isn't considered lookup tables). An additional nice thing is that with this approach, you also know the state of the three holes in question, so there's no need to check those as well. This whole thing resulted in more than 100% increase in speed.

I stored each board I reached in a hash to avoid going the same path more than once. I tried using the 6 rotations/inversions at first, but the overhead of using those was too big generally, so I ended up storing just 1 position. In most cases, a mirrored/rotated position was not reachable from the initial state anyway.

Since I was doing depth-first search, the most interesting thing, of course, was choosing the order of the moves in each position. I tried four criteria - the number of moves possible, the number of pairs of pegs that were together, and absolute difference of those two from the last move. It turned out that while each of these helped considerably in particular situations, the overhead of calculating them was too high. I tried all 632 combinations, orders and signs of the criteria, and on runs of 1000 boards, the simplest one was the fastest consistently - the next board I visit is the one with the least moves available. I'm not sure why less moves is better (it doesn't seem very intuitive to me), but it definitely worked better on average.

The final thing I did was to avoid checking for time constantly. If you can avoid doing if(time()<something) each move, you gain a few percent of speed again. At first, I used iterative code with declare(ticks=1000) which set a variable. But then I came up with a small trick - output buffering. If you use a ob handler, your code will get called no matter what. So, I put the output code inside a function and called ob_start() with it. If the code times out, the timeout warning is printed before the ob function gets called, so it's easy to output what you want from there.

All in all, on my PIII/800 the code was searching around 4000 boards per second, so I'm quite satisfied with the end result. I'll have to wait and see how it does in the contest, though.

Congratulations about your ideas, xs0 ! It's very clever.

>I think that the DeBruijn's sums are not very useful

Yes, you're right.
The DeBruijn sum doesn't vary during a game.
So, it's useful only at the beginning, to determine if final with 1 or 2 pegs is possible.

>I tried using the 6 rotations/inversions at first, but the overhead of using those was too big generally, so I ended up storing just 1 position.

I recently discovered how to improve rotations of bits in this case.
Let's take the 3 triangle:
a
b c
d e f

if you number the pegs consecutively:
a,b,c,d,e,f
the rotation/reflexion will cost a lot !
But, if you number them as follows:
a,d,f,b,e,c
(note the order of the items)
the rotation will be done as:
$board=($board&bits1)>>1+($board&bits2)<<2;
where bits1 and bits2 are 2 values to be determined.
BTW, in this contest, the rotations/reflections were useless.

xs0, I'm very impressed by your analysis of this problem.
I'm eager to see who won and how.

JC

I'm confused again. You guys say rotations/reflections are useless. But when I tried, almost half the branch matches were a different rotation/reflection. Unless I had some huge mistake, they don't seem that useless.

JC, are you sure you are not only thinking in a breadth first context?

For me, rotations/reflections definately helped. So sue me.

As for the board with the centre peg missing, all the first moves are identical, except for rotation/reflection. In a breadth-first context, do you create new layouts for each? And in depth-first, do you search one branch completely, then search each other branch again? Obviously, in this cose it could be avoided, because the DeBruijn sum is 0, therefore you can stop at 2-pegs. But other times it is not so.

xs0 says "In most cases, a mirrored/rotated position was not reachable from the initial state anyway." Again, almost half the matches for me were a different form.