Minimax Search and the Oracle of Old Toronto

Minimax search is an algorithm for determining which action to take in a multi-player game. The algorithm literally searches through all different sequences of moves, looking for a series of moves that will maximize its performance. At each point in the search, the algorithm considers the current game state (e.g., chess board configuration) and all possible moves from that state. In order to determine which move the current player would (or should) make, the search recursively branches off and tries ALL possible moves. The algorithm continues to search further and further into the future, until it reaches a state indicating the end of the game and determines who would win from that sequence of moves. The algorithm can then pass the outcome back to the previous state and use it to determine what move the player would make at that state. Specifically, if the current state represents the opponent's move: the algorithm assumes the opponent will choose whatever move is in their best interest. And, if the current state represents your move: the algorithm chooses the move that is best for you. By using the computed outcomes of each move (assuming the opponent will play as well as possible), the algorithm can choose the move that is best.

The war with West London was not going well. The armies of Old Toronto were stretched too thin, and the supply lines we cut off. If something did not change soon, the province of East Shore would be lost.

General Grimm was sitting in his command tent studying maps when the oracle arrived. Despite having heard the tales since he was a child, General Grimm was still shocked when he saw her. She was at least ninety years old and dressed like a punk rocker. She wore ripped jeans and a Bronze Maiden '32 teeshirt. Her snow white hair was in a perfect mohawk.

"Madam Oracle." he started.

"Hi" she replied while looking around the tent. She noted that there was nothing of value to take.

"Our forces are in trouble. We are stretched too thin, and our supply lines have been cut off. We need your guidance." the general pleaded. He had heard stories about the tribute demanded by the oracle. During the battle of South Atlantic she had demanded that the commander organize a three-stage, two-day concert. But, General Grimm did not have the time or men to organize a massive party for her. He was desperate.

"Okay." answered the oracle.

"Well... then..." stammered the general. That was too easy.

"You are waiting for my demands. Aren't you?" The oracle asked. She had seen this before, and frankly she was tired of the reputation she had earned during her party days. Now she just wanted to get this over with, go home, and take a nap. "I don't do that anymore." she clarified. "Show me the maps."

The general pointed to the maps on the table. They showed his army stationed a few miles from the Farnough Castle. The castle was the largest West London stronghold in the region. He had been planning on trying to take the castle the next day.

"That will not work." replied the oracle simply.

"Why not? We can take the castle! They do not have provisions to withstand a long siege." argued the general.

"True. But, if you do that then they will march their reserves south and attack Hampton. You will be forced to divert your forces to protect the city. And, they will move in their northern armies to take Old Toronto. You will lose in 26 days."

"How do you know this? Have you seen a vision?"

"No. I do not see visions. I am not the Oracle of Delphi with her magic, her prophecies, and her irrational love of marching bands. I actually work for a living." This was obviously a sore point for the oracle.

"Then, how do you know?" pressed the general.

"It is simple. Look at the possibilities at each step. Once you attack the castle the forces of West London only have three options. First, they could send troops to free the castle. Second, they could attack Hampton. And third, they could do nothing. Doing nothing would obviously mean they lose, so we can discard that possibility. Sending troops to free the castle would work, but would deplete both your armies. It would only stall any real progress. Finally, there is attacking Hampton. If West London attacks Hampton: you then have three options. You could defend Hampton, attack one of their cities, or do nothing. Doing nothing means you lose Hampton. Attacking one of their cities would require a two week march, and during that time Hampton would fall anyway. So, you would have to defend Hampton. And once you send your troops to defend Hampton, the capital of Old Toronto is unprotected and West London will obviously conquer it. The end."

As the oracle spoke, she drew out a branching diagram on a piece of paper. At each branch point she put a little note, such as "Your armies outside castle, their reserves attacking Hampton." Each branch represented a decision that either he or the West London commander could make at that point in the battle.

"But... If I attack one of their cities maybe they would pull their troops back from Hampton" the general reasoned.

"No. Because, once you send your troops they could just take Old Toronto and win. Why would they miss an opportunity to do that?" As the oracle answered, she added the new branch to the diagram. At the end of the branch she drew a little diagram of Old Toronto on fire. She liked illustrating things.

The general was at a loss. The logic was sound, but depressing.

"So what do I do?" he asked.

"Obviously, you do not attack Farnough Castle." the oracle resisted adding a "you idiot" at the end. During her years of service, she had found that generals did not like being called idiots. In fact, she avoided calling anyone above the rank of second lieutenant an idiot. It was safer that way, and that still left more than enough people for her to call idiots.

"Instead, you attack the village of Antoch." the oracle declared.

"Why? That is a small cattle village. There is no strategic value there. Even the cattle are rather sickly looking."

"True. But West London will still need to rush to defend it. Otherwise, they will not be in place to stop you from taking Antoch." explained the oracle.

"So, we will win at Antoch?" asked the general.

"No." replied the oracle. "But, that battle is not important relative to the war. Once West London has moved their reserves troops to Antoch your can move your reserves to West Antoch. From there they will split the garrison at Farnough Castle. You can withdraw and march on East London. They will combine the divisions at Antoch and West Antoch and follow your reserves to East London. You can then take your main army and conquer West London. It will take 91 days and a few battles. But you will win." She continued to draw out the various battle states and branches as she spoke. Occasionally, she would add another branch with an obviously bad ending to illustrate why the general would want to make a particular move.

The general was stunned. This plan was so far in the future and required so many of the "correct" enemy responses.

"What if they do not follow the plan?" he asked. "What if they do not defend West Antoch."

The oracle thought for a second. "Then you win in 67 days. You will march from West Antoch to East London to West London. It is better for you."

"But, what if they do something else?" he asked.

"Then you win quicker. Defending West Antoch is the best that they can do. Any other move will play out worse for them and better for you."

The general looked confused. "And, you have not seen this in a vision?" he confirmed.

"No. I am just playing out all possible scenarios."

"All scenarios?"

"Yes. Every single one. I take EVERY possible move that you could make and determine which is best based on ALL the possible sequences of moves that follow. I do the same for West London assuming that they will make the best moves they can." explained the oracle. "I keep going back and forth, testing each move and response until someone has won."

"But what if they do not make the best moves?" The general looked worried. He did not like the idea that his success depended on him facing a skilled opponent. Despite the fact West London was winning, General Grimm still regarded them as dullards.

"Then by definition it is worse for them and better for you. I have determined how good each of their moves is by the best move you could make in response. And, I determine your best move by assuming that they will make the best move in response. If they do not make the best move in response, then they have to have made a worse choice. As long as you keep making the best moves, they cannot cause you to lose by fighting poorly."

The general still looked unconvinced.

"Consider Tic-Tac-Toe." continued the oracle. "What do you do if it is your turn and your opponent has two boxes in a row?"

"Block them?" the general answered hesitantly.

"Yes. Because you assume that if you don't, they will take the best move for them and win. So, can they throw you off by playing poorly? What if they don't block you when you have two in a row?" pressed the oracle.

"Umm… I win." answered the general.

"Exactly!" Excitement burned in the oracle's eyes as she spoke. She did love her work. "All that you need to do is play out all possible sequences of moves. Always assume the opponent will try to do their best and do the best move in response."

"And this is your skill?" the general asked. He realized he was probably being insulting. But this sounded more like logical reasoning than being an oracle.

"Yes." sighed the oracle. "My power is the ability to very quickly play out all of the scenarios in my head." She paused. "When I was younger I played up the magical aspect of my skill on purpose. It got me invited to the best parties."

"Oh." The general looked down uncomfortably at his shoes. He was acutely aware of the fact that the oracle's skill was that she was much better at his job than he was.

"So... Antoch?" confirmed the general.

"Yes." confirmed the oracle.

"Um... well then... thanks. I can take it from here." The general felt the need to reassert his authority. After all, he was the general. As the oracle turned to leave he quickly added "You know, next time it would just be less awkward for you to act all magical and have outrageous demands."

"Next time I will go back to that." she agreed. The oracle smiled as she left. Next time she was going to demand her own castle.