Peg Solitaire, Final Analysis

by Yi Cao

1. Introduction

Peg Solitaire is an interesting contest. The problem is simple and easy to be understood. Anyone with reasonable MATLAB knowledge should be able to develop a valid solver. However, the problem is also so hard that after 7 days of hard work, many contestants believe we are still far away from the optimal solution. This motivated a long post-contest discussion in the newsgroup.

After 7 days evolution, the winning code Buy a ticket, like many other mature code submissions, had become very complex- the code was over 30,000 characters. To explain such a code within a limited space is a difficult task. I'd like to thank Alan Chalker, who did a great job putting very detailed comments twice into winning entries during the contest. Most of these comments are still available in the final wining code. Because of his great work, in this Final Analysis, instead of to explain the winning code, I decided to tell stories about code development and contest evolution. From these stories we may better understand the code origins.

2. Initial code development

The initial code provided by contest team was a good starting point for initial development. The initial code provides a way to find out all valid potential moves at a stage. However, the initial code just simply returns the first available moves.

            moves = [I(h(1) J(h(1) K(h(1)) L(h(1)));

An intuitive improvement to this code is to find the best move, i.e.

C0 = board(M(h))-board(F(h));

          [v,k]= max(C0);

     moves = [I(h(k) J(h(k) K(h(k)) L(h(k)));

Here the metric is the single jump value, C0, Then, make a loop to repeatedly find the best move until all possible moves exhausted. This was my first meaningful submission .LocalMinimum During development of this entry, I found a bug in the original grade function. By debugging the grade function, I found a way of post-process to truncate the move-list to get the maximum score. This was my next submission LocalMinimum+depth, and also was my first best result entry in this contest.   

From this on, I started to think about possible improvement. Firstly, I focused on to move all prefixed index calculation to outside of the loop. This was done by introduced F, M, and T vectors. This reduced computation time by half. Then I considered finding a way to check potential consecutive moves. After jumping from F to T, there are maximum three possible consecutive jumps. Therefore, I defined K1~3 and L1~3 to represent destinations of these three possible jumps, and used M1~3 and T1~3 for quick reference to the board. This significantly reduced about 2000 points in score. The entry Thursday Solution was the second best in the darkness.

During twilight phase, I realized that the maximum objective function, C0+CV, where C0 is the value of a valid jump, whilst CV is the value of a valid consecutive jump, may not always lead to the best solution. For some cases, C0+CV*d with different weight d may perform better. This led to the twilight winning entry, Friday_speed2. The code actually is a multiple solver. It takes the speed advantage gained at the darkness to call the original solver tree times, each with a different weight, and then returns the best solution.

3. Tweaking and improvement

As daylight began, the twilight winning code immediately was taken over by tweakers to improve. It took only 18 minutes for David Jones to be the first leader of the daylight. From then, the code had been improved by numerous tweakers. Most of them were parameter and random tuning to get better results. A few algorithmic contesters focused on computation speed such as to enable other tweakers to make more calls to subsol, hence to reduce the overall results. Among these improvements, the following three were the most important:

1. Nick Howe discovered an entry Juno37 submitted by Jim Mikola in the twilight. The newly discovered solver, solveri was able to provide better results for certain cases although it took longer time. Nick Howe successfully combined solveri with the dominant solver, subsol in his submission, JuChimera to win the Saturday Early Morning Special.
2. Nathan Q submitted his entry bigh_L8 at 06:12 for the Big Sunday Push. He developed a way to update the list of all valid moves without re-calculation of the whole list (moveid1~3). This improvement overcame the computation bottle neck of subsol and significantly reduced CPU time by 9 seconds.
3. Markus Buehren introduced another improvement to simplify the calculation of CV. Markus provided an interesting story about how this improvement had been used for three times and finally helped him won the Big Sunday Push prize.
4. I made a nother effort to improve the code during the Tuesday Leap competition. I combined several improvements to Nathan's and Markus' codes into a single entry, collaboration solver. Unfortunately, this entry did not go to the top. It was beaten by other randomly tweaked entries. Luckily enough, within half an hour, it was discovered by Jin. He made it became the top entry, collaboration solver b. Later, it was taken over by Sergey Yurgenson and helped him to win the Tuesday Leap.

Before the end, there was another interesting competition, the 1000 character challenge.  Sergey Yurgenson again was the winner. He introduced a magic weight 1.3 to modify the metric, which made him unbeatable for this mid-contest. Probably, few contesters noticed this magic weight, or really thought through the reason behind this great success, except two secrete aliases.  

4. Final sprint

Due to the loss on Tuesday, I swore to find another improvement to win the final.  Finally, I did, finding a way to make updating all valid moves simpler by introduce rMap, which reduced CPU time by 4-5 seconds. But I knew that was not enough. 

On the final day, 7 hours before the end, the queue was quiet. When I opened my computer, I found a suspicious entry submitted by matlabboy, with email address noone@nowhere.com. Intention of the entry was clear - to distract attention.  I guess this must be an entry to test an important new algorithm. By checking the code, I found an unusual line moves=[0 0 0 0]; at the place where subsol should return a solution. Therefore, I realized that this entry made some improvement to solveri and wish to test its real effect. By searching for matlabboy, I found three entries. By comparing results and CPU time of these three, I picked up the one which gives the best trade off, and combined it into my final improvement.

In the final hour, I opened several submission pages in web browser windows, each of which was filled with a code I was going to submit. At the same time, I kept scanning the queue. Firstly, I found David Jones's entry, which introduced a magic number to adjust the random sequence, rand(57); Then, I found MarkR's entry, which included a new set of ddlist. Both were leading entries. Hence, I copied both into all my submission pages. Before that, I also noticed Jin submitted Iamcrazy prob series, which detected a set of specific conditions to call solveri. I used these conditions in some of my submissions as well. Finally, about 5 minutes before end, I clicked all submit buttons but the last one was rejected by the sever with a message the queue was closed.  

5. Post contest discussion

The final results did surprise me for there was such a big gap between the winning entry and others. The question, which part of the winning code contributed the most puzzled me for several days until I saw message by Hannes Naud (alias matlabboy) in the newsgroup. He explained the idea behind the new metric (weight of peg moved / weight of lifting peg) they introduced in solveri. According to Hannes, they thought that the total weight can be removed is beyond control hence could be assumed as constant. Hence, they introduced this ratio metric to minimize the lifting cost per unit weight to be removed.

Based on this idea, I tried the similar ratio metric (C0+CV*d)./board(F(h)) in subsol. It was found that the new metric is able to reduce the overall score by several hundreds. Later, Sergey Yurgenson reported that using a weaker ratio metric, (C0+CV*d)./board(F(h)+1) is even better. Finally, I tested the weaker metric with both subsol and solveri and with appropriately tuned parameters. I was able to reduce the overall results of the actual suit to 38060 without increase CPU time. This result is much lower than the 3-minute best result we were able to achieve during contest.

In the post-contest newsgroup discussion, Nick Howe reported his solution to the Weighted English Board problem, proposed by Lucio in his mid-contest analysis, with score 359 comparing to Lucio's original solution score 407 although the new solution has 4 pegs remaining on the board. By comparing these two solutions, I found the reason, which makes the new solution is better. The new solution uses small weight pegs for lifting. Particularly, it repeatedly uses pegs with weight 1 and 2 as lifting pegs, while in Lucio's solution, no lifting peg has been used twice.

6. Conclusion

The score can be represented as:

Score = sum of original weight C weight removed + lifting penalty

           = sum of weight remaining + lifting penalty

           = J_remain + J_lifting

It is clear that J_remain and J_lifting have equal importance. Now, consider a board has n pegs with weights: w1 > w2 > w3 > ... > wn. Compare two move lists:

Solution 1: w2 over w1, w3 over w2, ... , wn over wn-1. J_remain = wn, J_lifting = w2 + w3 + ... + wn.

Solution 2: wn over w1, J_remain = w2 + w3 + ... + wn, J_lifting = wn.

These are two extreme cases: solution 1 has n-1 jumps, each has positive contributions, and only one peg with minimum weight left on the board; whilst solution 2 has only one jump and leaves n-1 pegs on the board. Intuitively, solution 1 would be understood as an optimal solution, or better than solution 2. However, they are equivalent.

Like a waterbed, if we push hard on J_remain, J_lifting will increase, whilst by pushing J_lifting, we may end up with a large J_remain.

As a summary, we can conclude that this is a multiobjective problem. The two objectives, J_remain and J_lifting should be jointly considered in a solver. One way to tackle this multiobjective problem is the ratio metric (J_remain/J_lifting) and weaker ratio metric (J_remain/(J_lifting+alpha)). Another way, we also can use J_remain+(1+alpha)*J_lifting as metric but tuning 0<alpha <1 to get the best results.  The effect of alpha on J_remain, J_lifting and score based on my darkness code is plotted in the figure below. This figure clearly shows the multiobjective effect by altering alpha.

.

The post-contest discussion indicates how important it is to openly exchange ideas. I hope that in future contests, we can invent some mechanisms to encourage similar collaboration.