In order to compare our results with the benchmark in [1], we attempted to rewrite the SA algorithm presented in Saeidi's paper using our representation and his parameters (i.e. T = 5000 and cooling rate of 0.05). We performed testing on 10 scrambled cubes and obtained the following figures below. From all our testing, we could not converge to a complete solution no matter what modifications we made to the algorithm. Figures 4 show one of the best solutions we obtained from our test runs. Although our algorithm did not solve the cube to completeness, we note that the SA algorithm managed solve the cube somewhat rising clusters of colors (such as the orange "T" shape), which gives rise to our suspicions that the cube may have converged to a local optimum.

To quantitatively compare our performance to Saeidi's, we developed the cost function plots for the case in Figure 4 above in the following figures below. Notice in the left plot in Figure 5 that we have similar up and down oscillations compared to plot (a) in Figure 3 above. However, we note that many of our oscillations appear to span a much larger range compared to Saeidi's results. We can explain the large oscillations by the very nature of the move operations we are putting on the cube. Whenever we move the Rubik's Cube, although we may be moving some facelets back into their correct positions, there are also likely several over facelets that move to the incorrect position. Combining this with the probability to choose a non-greedy more results in the oscillations seen.

As seen from our results, we could not recreate Saeidi's work; there could be something he did regarding to his algorithm that he did not explicitly write down that allows for his SA algorithm to perform so well. However, we also do have some doubts regarding his results. If we examine plot (a) in Figure 3 above, the fitness of the cube seems to oscillate around a an average fitness of 40, but drastically converges to the solution past 350 moves. Intuitively speaking, this means the SA, during its exploratory phase (when the temperature is still high), is performing the correct series of sequences such that when the temperature begins to cool (which causes the algorithm to become more greedy), the SA algorithm takes a series of greedy moves that perfectly solves the cube. From our testing, although the exploratory phase of the algorithm does prepare the cube somewhat for the greedy phase when the temperature cools, this "preparation" only allows the cube to converge to a local optimum. Saeidi is either very lucky during this exploratory phase to solve all 200 cubes, or we are missing something with our implementation.

In order to improve the performance of our SA algorithm, we attempted to vary several parameters including changing the structure of the algorithm to evaluate at a single temperature multiple times before decreasing the temperature, modifying the temperature and cooling rate, etc. From our observations from our testing in Figure 5 above, we noticed that the cube performed much better if the initial temperature was lower (i.e. more greedy). Thus, we instead used a temperature of T = 2 and a much lower cooling rate. After performing another 10 runs on 10 scrambled cubes, we obtained the following results from one of those runs. We note that a greedier algorithm results in much better convergence to a solution; however, we still converge to a local optima.

Once again, to compare our performance with our previous performance, we plotted the various costs and best costs for the 10 runs. Note that the two top plots are associated with the run that produced the cube in Figure 6 above. Some things to note in the figure below is that although we manage to obtain better performance with the algorithm, we need far more evaluations (hence more moves) to achieve these solutions, and we still cannot completely solve the cube. There is much work to do in order to get this SA algorithm to completely solve a cube.