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.



No comments

Other posts

Writing Theory — Blending Worlds
We look at writing as some of the most basic function in human minds and societies. For example we can use writing to become better thinkers, make powerful minds, or become really bright and smart. Writing is tricky though. Are you making things happen to record them or just recording them? Outside of your role in your works, are you a regular person or do you act all the time...
Read more
Econometrics and Statistics: One Reality
Source is Introduction to Econometrics by Stock and Watson. Given data, econometrics uses statistics to make measurements in economics. We define probability as the proportion of time that the outcome occurs in the long run. We define a sample space as the set of all possible outcomes. A random variable comes from a random outcome and this random variable can take on different numbers: it is a numerical summary of...
Read more