Artificial Intelligence, Minimax, and Game Theory
First off, if you ask what a minimax strategy is in game theory, it is a strategy that maximizes the game states available for your player. That is rational: you want the most points. At the same time though, other players want to do the same and their game states are maximized when your game states are minimized usually. So you are maximizing the worst case payoff in minimax, where the worst case arises based on looking at the range of possible outcomes from choices by the other player and deciding what is the worst case. In Tic Tac Toe, for example you move based on where you think the game will go, and you assume the opponent will bring upon you the worst case on his move and not make a silly human error that lets you get away. That is if you are using minimax.
In computer science to generate an artificial intelligence to play a game like Tic Tac Toe, we use a recursive algorithm to implement minimax by thinking like this: if I have a set of choices, I should always select the highest value choice. In other words, I should always push the game into a direction where when the opponent makes his or her best move against me, and keeps doing that, I will eventually win the game when either side runs out of moves: we place values on the end states. It is a recursive algorithm simply to fill out the possibilities tree of game states, as I value the game states from left to right and choose the highest game state, and to value an unknown game state, I dig into that game state, valuing from left to right again, until I hit the bottom of the tree when every state from left to right has a value and I choose the maximum value to pass back up the tree until the whole tree fills out to give us the all important values of our immediate choices of game states for which we pick the highest one.
The computer is unbeatable at Tic Tac Toe, as we can only draw, and that is because we run out of moves quickly. In chess for example, we may not run out of moves for a long time, and there are more possibilities of moves for each piece, and as a result the human player may as a result of feel be able to push the computer player to a worst set of game states by the end of the game when the computer’s logic begins to dominate again. That is why you see human players offering draws to computer players near the end game.
Philosophically, preparing yourself to battle against your opponent reducing you to your worst may not be the best approach if you know you can’t be reduced to your worst, or if you can reduce the opponent to his worst first. In both cases, we would rely upon moving several times in a row and winning a victory or moving in some way to bring a great victory.
Take for example, the Chinese KMT, whose leader Chiang Kai Shek famously said he didn’t lose to Mao for the fate of China but lost to Russia. His highly competent German-trained divisions went into colonial occupied Shanghai and drove out the Japanese only to hold positions that were seemingly doomed by insurmountable odds as the Japanese Air Force, Navy and main Army moved in. But by their bravery, these Chinese KMT along with General Zhang Lingfu’s mechanized division and others, managed to divert the Japanese offensive from northern China and make it a West East front in China along what was a very long front instead of what the Japanese desired which was a simple North South front, which would have allowed the Japanese to win quickly. These Chinese KMT nationalists, sort of like nationalists in the USA today, did not maximize the worst case of outcomes as they assumed the Japanese would pound them but went in anyway instead of retreating. And that is for the same reason why I don’t retreat from my “Occupy Wall Street” movement whose guys I liked except for their methods, and instead join with the German-trained Romney Tiger Sharks with my Zhang Lingfu Mechanized Mako Sharks, which are Asian, with helpers from the Great White Shark Donald Trump, and we now hold the Bay of Harvard, Massachusetts Bay, while waiting certain doom and gloom from Russian MiG scary mother f II which is like a Zerg Overmind for those of you who like me didn’t play enough video games as a kid, but we aren’t going to ask Protoss from Chicago to send us Dark Templar Cerberus to slay such Overmind but are prepared to keep slaying it over and over again until it is finished, and that is because if Chicago is Athens and Sparta, and Boston is Constantinople, Boston girls don’t want the leftovers of the Chicago crowd, and are instead going to be Christian until Boston looks like modern Greece and Chicago like EU, but again Boston doesn’t want to just be EU, so like Greece would say to Turkey, the Chinese KMT say to the jets, and the private equity real estate sharks say to state capitalism, if you want our stuff, “Persians come and get them!” – 300