The old algorithm was to go through all the variations and try to find a guess that matches the current state of the table. Assuming that the currently examined guess is the secret, will we get the same answers for the guesses that are already on the table as the answers are actually on the table? If yes, then the current guess can be the secret, and it is just as good a guess as any other guesses.
A more complex approach can implement the min-max algorithm (https://en.wikipedia.org/wiki/Minimax). This algorithm does not simply get the next possible guess but also looks at all the possible guesses and selects the one that shortens the outcome of the game the most. If there is a guess that can be followed by three more guesses in the worst case, and there is another for which this number is only two, then min-max will choose the latter. It is a good exercise for the interested readers. In the case of the six colors and four columns for the pegs, the min-max algorithm solves the game in no more than 5 steps. The simple algorithm we implemented also solves the game in 5 steps. However, we do not go in that direction.
Instead, we want to have a version of the game that utilizes more than one processor. How can you transform the algorithm into a parallel one? There is no simple answer to this. When you have an algorithm, you can analyze the calculations and parts of the algorithm, and you can try to find dependencies. If there is some calculation B that needs the data, which is the result of another calculation A, then it is obvious that A can only be performed when B is ready. If there are parts of the algorithm that do not depend on the outcome of the others, then they can be executed in parallel.
For example, the quick-sort has two major tasks: partitioning and then sorting of the two parts. It is fairly obvious that the partitioning has to finish before we start sorting the two partitioned parts. However, the sorting tasks of the two parts do not depend on each other, they can be done independently. You can give them to two different processors. One will be happy sorting the part containing the smaller elements; the other one will carry the heavier, larger ones.
If you turn the pages back to Chapter 3, Optimizing the Sort - Making Code Professional where we implemented quick-sort in a non-recursive way, you can see that we scheduled sorting tasks into a stack and then performed the sorting by fetching the elements from the stack in a while loop. Instead of executing the sort right there in the core of the loop, we could pass the task to an asynchronous thread to perform it and go back for the next waiting task. We just do not know how. Yet. That is why we are here in this chapter.
Processors, threads, and processes are complex and abstract things and they are hard to imagine. Different programmers have different techniques to imagine parallel processing and algorithms. I can tell you how I do it but it is not a guarantee that this will work for you. Others may have different techniques in their mind. As a matter of fact, I just realized that as I write this, I have actually never told this to anyone before. It may seem childish, but anyway, here it goes.
When I imagine algorithms, I imagine people. One processor is one person. This helps me overcome the freaking fact that a processor can make billions of calculations in a second. I actually imagine a bureaucrat wearing a brown suit and doing the calculations. When I create a code for a parallel algorithm, I imagine many of them working behind their desks. They work alone and they do not talk. It is important that they do not talk to each other. They are very formal. When there is a need for information exchange, they stand up with a piece of paper they have written something on, and they bring it to each other. Sometimes, they need a piece of paper for their work. Then they stand up, go to the place where the paper is, take it, bring it back to their desk, and go on working. When they are ready, they go back and bring the paper back. If the paper is not there when they need it, they queue up and wait until someone who has the paper brings it there.
How does it help with Mastermind?
I imagine a boss who is responsible for the guesses. There is a table on the wall in the office with the previous guesses and the results for each row. The boss is too lazy to come up with new guesses so he gives this task to subordinates. When a subordinate comes up with a guess, the boss checks whether the guess is valid or not. He does not trust the subordinates, and if the guess is good, he makes it as an official guess, putting it on the table along with the result.
The subordinates deliver the guesses written on small post-it notes, and they put them in a box on the table of the boss. The boss looks at the box from time to time, and if there is a note, the boss takes it. If the box is full and a subordinate wants to put a paper there, the subordinate stops and waits until the boss takes at least one note so that there is some room in the box for a new note. If the subordinates queue up to deposit guesses in the box, they all wait for their time.
The subordinates should be coordinated; otherwise, they will just come up with the same guesses. Each of them should have an interval of guesses. For example, the first one should check the guesses from 1234 up until 2134, the second should check from 2134 up until 3124, and so on, if we denote the colors with numbers.
Will this structure work? Common sense says that it will. However, bureaucrats, in this case, are metaphors and metaphors are not exact. Bureaucrats are human, even when they do not seem like it much more than threads or processors. They sometimes behave extremely strangely, doing things that normal humans don't really do often. However, we can still use this metaphor if it helps us imagine how parallel algorithms work.
We can imagine that the boss goes on holiday and does not touch the heap of paper piling up on the table. We can imagine that some of the workers are producing results much faster than the others. As this is only imagination, the speedup can be 1000 times (think of a time-lapse video). Imagining these situations may help us discover special behavior that rarely happens, but may cause problems. As the threads work in parallel, many times subtle differences may influence the general behavior greatly.
In some early version, as I coded the parallel Mastermind algorithm, the bureaucrats started working and filled the box of the boss with guesses before the boss could put any of them on the table. As there were no guesses on the table, the bureaucrats simply found all possible variations in their interval being a possibly good guess. The boss gained nothing by the help of the parallel helpers; they had to select the correct ones from all possible guesses, while the guessers were just idle.
Another time, the bureaucrats were checking guesses against the table while the boss was putting a guess on one of them created beforehand. And some of the bureaucrats freaked out saying that it is not possible to check a guess against a table if someone is changing it. More precisely, the code executing in one thread, threw ConcurrentModificationException when the List of the table was modified.
Another time, I tried to avoid the too fast work of bureaucrats, and I limited the size of the box where they could put their papers containing the guesses. When the boss finally found the secret, and the game finished, the boss told the bureaucrats that they could go home. The boss did that by creating a small paper with the instruction: you can go home, and put it on the tables of the bureaucrats. What did the bureaucrats do? Kept waiting for the box to have space for the paper! (Until the process was killed. This is kind of equivalent on Mac OS and on Linux as ending the process from the task manager on Windows.)
Such coding errors happen and, to avoid as many as possible, we have to do at least two things. Firstly, we have to understand how Java multithreading works and secondly, have a code as clean as possible. For the second, we will clean up the code even more and then we will look at how the parallel algorithm described earlier can be implemented in Java, running on the JVM instead of utilizing bureaucrats.