Assassin’s Creed Vs. Excel: Who Wins?

Assassin's Creed Vs. Excel: Who Wins?My post on using Excel to solve problems elicited an exciting response from White Razor, who used Excel to solve an Assassin’s Creed puzzle — not the usual response! He included a video that shows what he did, but for people unfamiliar with this type of computation, I advise reading the following explanation before viewing the video.

A quick overview might help understand the process, especially for those who have not used the Solver function in Excel. The first step is to recognize that the problem can be expressed in terms that can be programmed into Excel. The Assassin problem seems to combine parts of the six wave forms at the left in the illustration to recreate the large form shown in the right. (Gamers, please forgive me. I do not play and might be using peculiar terminology.) This is obviously an involved process that would take a long time for a human, perhaps using overlaid transparencies to attempt to find a solution if confined to using paper and pencil.

A better way is to characterize the wave segments numerically. This is done for the desired output in the illustration by breaking the output wave into four parts with each art characterized by the peak in amplitude. The units are arbitrary, but must be constant throughout. There is some magic here because we have little reason to believe that specifying the amplitude will be sufficient to characterize the wave. In general, it will not. White Razor seems to have guessed that this would be sufficient based on the fact that the nature of the game is that a relatively simple solution is possible. We will stick with that, but if you want to use a similar technique on real world data, be warned that it probably will not work. In this artificial puzzle, it is the right approach, but for real world data, a more complex method will be required.

Next, the same process is performed on each of the wave segments. Now that the data has been characterized numerically, we can start with Excel.

For versions of Excel with a ribbon, clicking on the data tab and selecting “What-If Analysis” will open a window with the option of “Goal Seek.” This is a function that will cause a spreadsheet to search through values of variable until a value is found which results in a computed goal as close to what you desire as possible given the constraints of the conditions you enter. Goal Seek works fine if you have an expression of the type y = f(x), and you wish to find an x which returns a desired y (maybe the extreme value of y or some other condition). It is a brute force method of simply putting in a series of x and computing the results. Computers can do this type of grunt work much better than humans. However, if you have more than one parameter to vary, Goal Seek will not work easily. The answer is to load the Solver add-in. For some reason that escapes me, Microsoft made Solver readily available in Excel, but you must jump through some hoops to load it. After it is loaded, it will always be there, ready for you to insert into a spreadsheet. Solver is similar to Goal Seek, but it can handle problems like finding the right combination of the six possible waves to make a desired output with ease.

At this point, you might want to look at the video. The first 2:40 minutes set up the problem and discuss digitization of the input wave forms. Then the author opens Excel and shows how to solve for the proper output in a matter of seconds. The key is to define a binary variable for each of the six waveforms. When the individual wave forms are multiplied by the binary number, they are either present at full value or zero. Then solver is set to sum all six vectors (the four numbers defining each wavelet can be considered a vector) while turning the binary elements associated with each wave vector on or off until the sum of the enabled (Binary =1) wave vectors gives the desired output.

Note that Solver stops when it finds a combination that satisfies the constraints. This is not necessarily the only possible solution. It is simply the first one to be found. Changing the arrangement of the input data and the constraints could lead to other solutions. So the great strength of Solver is that is can find a valid solution quickly. A weakness of this brute force method of plugging in values and testing is that if you want to find all possible solutions, you need to do a bit more work. That is for another example.

Another point to keep in mind is that no higher math or complicated manipulations were needed. A person who has used Solver previously could set up the whole spreadsheet and get an answer quickly using only summation and multiplication. The process only seems complex the first time you try it.

In the last post, three puzzles were presented as a prelude to Excel. Here are the answers:

(1) abs(x) = max(x, -x) max(x, y) = ½(x + y + abs(x — y)).
(2) In the normal version, neither side can force a win.
(3) Boxcars have the edge with odds of 7/13.

People who want to see how the solutions were found can visit the puzzle site I referred to. Solutions to the various alternatives to the second puzzle are still being worked on by several readers and will be discussed at a later date.

Article Written by