Post by NASH7777 on Jul 8, 2006 15:07:06 GMT -5
Had to do a report for gov school on game theory and stuff. Three of us did game theory and kinda had to cover different areas of it. It's a semi-informal report. This is what I got, so read if your interested. Comments appreciated.
~~~~~~~~~~~~~~~~
Game Theory
Brock Nash
Game theory provides analytical tools for examining strategic interactions among two or more participants, but is game theory nothing but ‘games’? No, in fact game theory can be applied to many aspects of life, psychology, and areas one might consider as far too serious to be classed as a game. But what makes a game, what do they mean by game theory, and how can understanding game theory be of a benefit? Though this report can not go in full detail, it will take you through some aspects of game theory, some issues with human versus computer in game theory, and teach you a practical way to utilize game theory.
To be considered a game in game theory, there are certain aspects that should be present. These five main elements are players, strategies, rules outcomes, and payoffs. The players, as you might assume, are the decision makers in the game. They can be humans, computers, or real world entities such as nature. Now we know that computers can not make what we call true choice but they have a way of analyzing a situation and responding in a certain way even if it is more grounded than human logic. Strategies are available to each player, and it usually refers to something similar to the psychology of the player, whether you want to win by hindering your opponent’s best options or by trying to take your own best options. Being able to identify the opponent’s strategy and adjusting your own is another part of strategy. Rules are things that govern the player’s behavior and can limit them in one way or another. Rules are the influence for strategy because not until after the rules are known can you form your strategy. Rules do not have to be the exact same for each player and rules can be flexible in that they only apply under more specific circumstances. Outcomes are the results of choices made at a given point in a given circumstance. Outcomes can be that you gain an advantage by a move or they can be the final outcome of the game entirely. Payoffs are accrued by each player based on the final outcome. This can include winning a prize to just having the satisfaction of having won the game.
The use of game theory extends many branches of our society. The business world can use its concepts in making choices weather to invest in something, buy out another company, consolidate companies, or even where to market. Psychology uses game theory in understanding why people make choices and how people analyze situations. Political science, sociology, education fields, and computer science all utilize game theory in some form. Game theory obviously extends much more than a simple bout of tic-tac-toe.
There also exist many examples in our culture and society of game theory. For example, the movie Princess Bride had a scene where there were two people to drink from one of two cups each. One of these cups was poisoned. Would the person who was trying to poison the other put it in the other’s cup, or would they have known to put it in their own cup in hopes that the other would switch to counter the others evil intent? How much psychology and strategy is too much? There’s no limit when you start reversing reverse psychology. In the scene they both repeatedly switch the cups on each other with the other looking away. Another good example to check out is the movie “A Beautiful Mind.”
The most renowned game is Prisoner’s Dilemma. In this game two suspects are arrested by the police, we’ll say prisoners A and B. The police have insufficient evidence to convict them of the crime but separate them and offer them each the same deal. If one testifies for the prosecution against the other and the other remains silent, the betrayer goes free and the silent accomplice receives the full 10-year sentence. If both stay silent, the police can sentence both prisoners to only six months in jail for a minor charge. If each betrays the other, each will receive a two-year sentence. Neither prisoner knows for sure what choice the other prisoner will make.
~~~~Did have a chart of game in here, cut for post
Both players want to win, but if they both get greedy and try to win big, they both will lose. However if they both go for the small win they will be ok, but one prisoner may see this as an opportunity to head for the big win and the other player will pay for it greatly. Prisoner’s Dilemma is a perfect example of a non-zero sum game. A Zero-sum describes a situation in which a participant's gain or loss is exactly balanced by the losses or gains of the other participant, thus a non-zero sum game is when participants can all gain or suffer together.
There lies a gap in game theory when it comes to human participants and computer ones. Computers can obviously analyze information much faster than we can, but we can easily skim over situations and see things that may be too deep for a computer to establish in a timely matter since it has to analyze more cases, even absurd ones, while we take the more obvious routes quicker. Many other issues come about that need to be addressed as well. Chess will be the concentration since almost all of these issues come into effect in chess.
Extensions are the main problem with computer AI (artificial intelligence). Simply searching everything to a given depth means that the computer spends too much time looking at really stupid lines and not taking enough time for the important ones. To counter this, we allow the computer to do ‘singular extension’ in which if one move is found to be much better than all the others, this move is allowed to be searched deeper. This form is called ‘sex,’ subsequently the computer only looks at sexy moves.
The horizon effect was formerly a huge problem with programs. Suppose you have a piece trapped, the human can see the pattern and will try to counter by doing something a few moves earlier. The computer will rarely do this because of any other event that may be going on on the board that was the concentration of the computer and the moves to counter may be at a depth farther than the computer checks for. This problem is lessening because of sex which allows for the depth of the moves to be taken as ‘sexy’ and the computer will analyze them.
Null moves are when the player is allowed to pass or not take action during their turn. This is not normally allowed during chess but we can see the problems it can create. There are times in chess where being able to pass would be very advantageous. However, the null moves can normally good positions and completely reverse the game. The advantage works both ways for if null moves are good or bad. In either situation null moves being allowed or not allowed can completely destroy all advantage of a player. The computer-chess community is broken over null moves, but most computers use null moves but switch them off when the number of pieces on the board becomes small to control how the computer analyzes the situation and how deep it runs its searches.
Remoteness is another issue mostly in the fact of how to handle the computer. The computer may be in a winning position but the computer still has to ‘win’. Unfortunately the winning pattern may be just a little too deep for the computer to see and thus create a loop of moves for the computer. The computer then may never win the game even though they are in position to win. This can be fixed by a simple statement like “computer to win in 3 moves” and force a resignation on the other player’s part.
The idea of having a game end in a draw or requesting a draw is tricky. When do you know when to accept a draw? When are you to offer a draw? Computers deduce this in a manner of giving pieces a rank and have a property called contempt. The more your rank is on the player, that being the more good pieces you have, the less likely you are to accept a draw. But just because you have a higher rank doesn’t mean your in a better position which is why ‘contempt’ is put into place. Contempt is a way off looking at your future potential. If you can take the person’s queen in a few moves you can factor that in to you having a slightly bigger advantage.
An aspect we do as humans that computers have trouble conceptualizing is the battle of simplicity versus complication. Sometimes it is better to sacrifice a few players in order to clear up the board so it is easier for you to win. And sometimes doing a move and hoping that your opponent can’t see the slight advantage you just gave them is a good tactic that a computer can’t seem to learn and implementation of this has been a mixed bag when it comes to programming it in. It truly depends on how observant your opponent is.
Time management also plays a part. How long should you have to wait for your computer opponent to move? Well how smart do you want your opponent to be? We as our opponents are bound by time. Though their always exists more optimal moves then others, we don’t have the time to completely analyze all scenarios if the game is advanced enough. Most chess games have a meter you can set for the opponent to how fast but stupid or slow but smart you want your opponent.
Opening moves and ending moves are the hardest for a computer to do. The opening moves have been fixed by allowing some common strategies to start the player out and have it randomly pick one of them. However there is no set way to do this for the end moves. Often at the end of a game there exist very few pieces and a lot of open space. This means there are a lot of possibilities and the computer has trouble handling this. For example when a certain five pieces remain there are fewer than 160 million configurations, which is within scope of a reasonably powerful computer.
Merely talking about game theory and analysis isn’t enough to comprehend some of the ideologies behind game theory. Therefore the following will take you through some of the steps of analyzing a sample game. Most everyone can figure out tic-tac-toe and come up with a strategy so that they always win or at least end in a draw, but what do you do if the game is more complex than that. Of course experience is helpful and through experience we develop strategy to help us succeed in winning. Here is a temporary link to the game being described:
Windows: wah.midco.net/brocknash/NashGrid.exe
Mac: wah.midco.net/brocknash/NashGrid.app
A brief explanation of how the game works is required. There are two players that start at 2 locations on a 5x5 grid. Each player has an equation associated with him/her. The first player chooses values of A and A in the equation Ax+B (A and B must be integers). This information is public to the second player and the second player must quickly respond with what they want to be a counter equation of the same type. The value of x starts at 1 and is called the frame. The equation for player one is evaluated and the number answer is reduced mod 9. Each value possible corresponds to a movement. 0-Right, 1-Down Right, 2-Down, 3-Down Left, 4-Left, 5-Up Left, 6-Up, 7-Up Right, 8-Stay. The player then moves in that direction, if they are at the edge of the board, it wraps around to the other side. The second player runs his/her equation with the frame also 1. After both players have moved the frame count increments up by one and the process continues. The goal is to have you player land on the other player, this means you win the round. The round is considered a draw if by the 100th frame no one has one. After a round is won, the players switch who gets to come up with their equation first and play another round. Either the first to so many points or the person with the most points after so many rounds determines the ultimate winner. This game is considered one of Perfect Information and is also a zero-sum game since only one player can win. Another way to play and analyze a win is if the player has won the most times in the least number of frames.
~~~~Had a screenshot of game, cut for post
First off one must analyze how the game works in order to develop strategy. One of the most important things to notice is that the equation is always eventually evaluated to mod 9. This allows us to always simplify the opponent’s equation which makes it easier to analyze patterns and strategy. For example the equation 10x+81 can be reduced to 1x+0. All we did was reduced the integers by mod 9. This also shows us that there is a finite number of equations (81 to be exact 9x9), while normally it would have seemed infinite since the integers go on forever.
Let us start playing the defensive second player side. To develop strategy in this game we develop a system of taking our opponent’s equation and editing it to develop our own equation. The notation for this is {+M, +N} this would mean we add M to their A to make our A and add N to their B to make our B. Another notation would be {M, +N} meaning we always use M as our A and our B is their B plus our N. Now the next part for strategy either comes by experience or taking the time to analyze every possibility to create different strategies. For practical purposes of this report there will be strategies provided for your need. Let us take the strategy of {+1, +0}. With this strategy we have 45% chance of winning, 22% tie, and 33% loss. We may also look at it as 67% of a content outcome and 33% bad. Even though we have less than 50% chance of winning with the draw outcomes, this strategy is quite favorable.
A strategy like above is easy to remember, also if we specifically know just one of their digits we can see how our odds change but being able to remember how your percentage changes by knowing each digit is much more of a feat and should be left to those geniuses amongst us. For example, using the {+1, +0} strategy when their A value is 0 gives us the 6/9 for winning and 3/9 for losing, but when their A is 7 it gives us 2/9 win, 4/9 loss, and 3/9 draw. But a just stated, remembering trivial info like this isn’t easy or suggested. Let’s take the strategy {+0, +1} now. This has 36% win, 51% draw, and 12% loss. With such a low loss % it is a very convenient strategy. In fact if we know their A is a 1, 2, or 3 we have no chance of loss with this strategy, which leads us into our offensive strategy. If we see that our opponent is using this as their strategy we know not to have our A be those values. In fact remembering at least one counter for common opponent strategies is important. For example, having “0x+6” as our start will give us a win in the 3rd frame or better yet “6x+2” will give us a win in the 2nd frame. Frame wins are only important if you are using them to be a factor of having beaten the player in the least number of frames to determine the true winner. Another important trick both on offense and defense is to hide your equations with modulus 9 taken into account. This way it is harder for opponents to see your strategies and harder for them to counter your equations. Ultimately the key is being able to mix up your strategies effectively, identify and counter opponent strategies, and being able to disguise your work, because even though this is a zero-sum game, it is complex enough that you don’t have time to do produce a simple 100% counter efficient method like you could in tic-tac-toe.
Overall understanding game theory can help you in many situations whether it be in a simple game for entertainment, a business situation, or even a tight crime case you got yourself into. And though there exists many problems in properly analyzing game theory, there are methods around them or at least ways to overview them and come up with half decent strategies.
~~~~~~~~~~~~~~~~
Game Theory
Brock Nash
Game theory provides analytical tools for examining strategic interactions among two or more participants, but is game theory nothing but ‘games’? No, in fact game theory can be applied to many aspects of life, psychology, and areas one might consider as far too serious to be classed as a game. But what makes a game, what do they mean by game theory, and how can understanding game theory be of a benefit? Though this report can not go in full detail, it will take you through some aspects of game theory, some issues with human versus computer in game theory, and teach you a practical way to utilize game theory.
To be considered a game in game theory, there are certain aspects that should be present. These five main elements are players, strategies, rules outcomes, and payoffs. The players, as you might assume, are the decision makers in the game. They can be humans, computers, or real world entities such as nature. Now we know that computers can not make what we call true choice but they have a way of analyzing a situation and responding in a certain way even if it is more grounded than human logic. Strategies are available to each player, and it usually refers to something similar to the psychology of the player, whether you want to win by hindering your opponent’s best options or by trying to take your own best options. Being able to identify the opponent’s strategy and adjusting your own is another part of strategy. Rules are things that govern the player’s behavior and can limit them in one way or another. Rules are the influence for strategy because not until after the rules are known can you form your strategy. Rules do not have to be the exact same for each player and rules can be flexible in that they only apply under more specific circumstances. Outcomes are the results of choices made at a given point in a given circumstance. Outcomes can be that you gain an advantage by a move or they can be the final outcome of the game entirely. Payoffs are accrued by each player based on the final outcome. This can include winning a prize to just having the satisfaction of having won the game.
The use of game theory extends many branches of our society. The business world can use its concepts in making choices weather to invest in something, buy out another company, consolidate companies, or even where to market. Psychology uses game theory in understanding why people make choices and how people analyze situations. Political science, sociology, education fields, and computer science all utilize game theory in some form. Game theory obviously extends much more than a simple bout of tic-tac-toe.
There also exist many examples in our culture and society of game theory. For example, the movie Princess Bride had a scene where there were two people to drink from one of two cups each. One of these cups was poisoned. Would the person who was trying to poison the other put it in the other’s cup, or would they have known to put it in their own cup in hopes that the other would switch to counter the others evil intent? How much psychology and strategy is too much? There’s no limit when you start reversing reverse psychology. In the scene they both repeatedly switch the cups on each other with the other looking away. Another good example to check out is the movie “A Beautiful Mind.”
The most renowned game is Prisoner’s Dilemma. In this game two suspects are arrested by the police, we’ll say prisoners A and B. The police have insufficient evidence to convict them of the crime but separate them and offer them each the same deal. If one testifies for the prosecution against the other and the other remains silent, the betrayer goes free and the silent accomplice receives the full 10-year sentence. If both stay silent, the police can sentence both prisoners to only six months in jail for a minor charge. If each betrays the other, each will receive a two-year sentence. Neither prisoner knows for sure what choice the other prisoner will make.
~~~~Did have a chart of game in here, cut for post
Both players want to win, but if they both get greedy and try to win big, they both will lose. However if they both go for the small win they will be ok, but one prisoner may see this as an opportunity to head for the big win and the other player will pay for it greatly. Prisoner’s Dilemma is a perfect example of a non-zero sum game. A Zero-sum describes a situation in which a participant's gain or loss is exactly balanced by the losses or gains of the other participant, thus a non-zero sum game is when participants can all gain or suffer together.
There lies a gap in game theory when it comes to human participants and computer ones. Computers can obviously analyze information much faster than we can, but we can easily skim over situations and see things that may be too deep for a computer to establish in a timely matter since it has to analyze more cases, even absurd ones, while we take the more obvious routes quicker. Many other issues come about that need to be addressed as well. Chess will be the concentration since almost all of these issues come into effect in chess.
Extensions are the main problem with computer AI (artificial intelligence). Simply searching everything to a given depth means that the computer spends too much time looking at really stupid lines and not taking enough time for the important ones. To counter this, we allow the computer to do ‘singular extension’ in which if one move is found to be much better than all the others, this move is allowed to be searched deeper. This form is called ‘sex,’ subsequently the computer only looks at sexy moves.
The horizon effect was formerly a huge problem with programs. Suppose you have a piece trapped, the human can see the pattern and will try to counter by doing something a few moves earlier. The computer will rarely do this because of any other event that may be going on on the board that was the concentration of the computer and the moves to counter may be at a depth farther than the computer checks for. This problem is lessening because of sex which allows for the depth of the moves to be taken as ‘sexy’ and the computer will analyze them.
Null moves are when the player is allowed to pass or not take action during their turn. This is not normally allowed during chess but we can see the problems it can create. There are times in chess where being able to pass would be very advantageous. However, the null moves can normally good positions and completely reverse the game. The advantage works both ways for if null moves are good or bad. In either situation null moves being allowed or not allowed can completely destroy all advantage of a player. The computer-chess community is broken over null moves, but most computers use null moves but switch them off when the number of pieces on the board becomes small to control how the computer analyzes the situation and how deep it runs its searches.
Remoteness is another issue mostly in the fact of how to handle the computer. The computer may be in a winning position but the computer still has to ‘win’. Unfortunately the winning pattern may be just a little too deep for the computer to see and thus create a loop of moves for the computer. The computer then may never win the game even though they are in position to win. This can be fixed by a simple statement like “computer to win in 3 moves” and force a resignation on the other player’s part.
The idea of having a game end in a draw or requesting a draw is tricky. When do you know when to accept a draw? When are you to offer a draw? Computers deduce this in a manner of giving pieces a rank and have a property called contempt. The more your rank is on the player, that being the more good pieces you have, the less likely you are to accept a draw. But just because you have a higher rank doesn’t mean your in a better position which is why ‘contempt’ is put into place. Contempt is a way off looking at your future potential. If you can take the person’s queen in a few moves you can factor that in to you having a slightly bigger advantage.
An aspect we do as humans that computers have trouble conceptualizing is the battle of simplicity versus complication. Sometimes it is better to sacrifice a few players in order to clear up the board so it is easier for you to win. And sometimes doing a move and hoping that your opponent can’t see the slight advantage you just gave them is a good tactic that a computer can’t seem to learn and implementation of this has been a mixed bag when it comes to programming it in. It truly depends on how observant your opponent is.
Time management also plays a part. How long should you have to wait for your computer opponent to move? Well how smart do you want your opponent to be? We as our opponents are bound by time. Though their always exists more optimal moves then others, we don’t have the time to completely analyze all scenarios if the game is advanced enough. Most chess games have a meter you can set for the opponent to how fast but stupid or slow but smart you want your opponent.
Opening moves and ending moves are the hardest for a computer to do. The opening moves have been fixed by allowing some common strategies to start the player out and have it randomly pick one of them. However there is no set way to do this for the end moves. Often at the end of a game there exist very few pieces and a lot of open space. This means there are a lot of possibilities and the computer has trouble handling this. For example when a certain five pieces remain there are fewer than 160 million configurations, which is within scope of a reasonably powerful computer.
Merely talking about game theory and analysis isn’t enough to comprehend some of the ideologies behind game theory. Therefore the following will take you through some of the steps of analyzing a sample game. Most everyone can figure out tic-tac-toe and come up with a strategy so that they always win or at least end in a draw, but what do you do if the game is more complex than that. Of course experience is helpful and through experience we develop strategy to help us succeed in winning. Here is a temporary link to the game being described:
Windows: wah.midco.net/brocknash/NashGrid.exe
Mac: wah.midco.net/brocknash/NashGrid.app
A brief explanation of how the game works is required. There are two players that start at 2 locations on a 5x5 grid. Each player has an equation associated with him/her. The first player chooses values of A and A in the equation Ax+B (A and B must be integers). This information is public to the second player and the second player must quickly respond with what they want to be a counter equation of the same type. The value of x starts at 1 and is called the frame. The equation for player one is evaluated and the number answer is reduced mod 9. Each value possible corresponds to a movement. 0-Right, 1-Down Right, 2-Down, 3-Down Left, 4-Left, 5-Up Left, 6-Up, 7-Up Right, 8-Stay. The player then moves in that direction, if they are at the edge of the board, it wraps around to the other side. The second player runs his/her equation with the frame also 1. After both players have moved the frame count increments up by one and the process continues. The goal is to have you player land on the other player, this means you win the round. The round is considered a draw if by the 100th frame no one has one. After a round is won, the players switch who gets to come up with their equation first and play another round. Either the first to so many points or the person with the most points after so many rounds determines the ultimate winner. This game is considered one of Perfect Information and is also a zero-sum game since only one player can win. Another way to play and analyze a win is if the player has won the most times in the least number of frames.
~~~~Had a screenshot of game, cut for post
First off one must analyze how the game works in order to develop strategy. One of the most important things to notice is that the equation is always eventually evaluated to mod 9. This allows us to always simplify the opponent’s equation which makes it easier to analyze patterns and strategy. For example the equation 10x+81 can be reduced to 1x+0. All we did was reduced the integers by mod 9. This also shows us that there is a finite number of equations (81 to be exact 9x9), while normally it would have seemed infinite since the integers go on forever.
Let us start playing the defensive second player side. To develop strategy in this game we develop a system of taking our opponent’s equation and editing it to develop our own equation. The notation for this is {+M, +N} this would mean we add M to their A to make our A and add N to their B to make our B. Another notation would be {M, +N} meaning we always use M as our A and our B is their B plus our N. Now the next part for strategy either comes by experience or taking the time to analyze every possibility to create different strategies. For practical purposes of this report there will be strategies provided for your need. Let us take the strategy of {+1, +0}. With this strategy we have 45% chance of winning, 22% tie, and 33% loss. We may also look at it as 67% of a content outcome and 33% bad. Even though we have less than 50% chance of winning with the draw outcomes, this strategy is quite favorable.
A strategy like above is easy to remember, also if we specifically know just one of their digits we can see how our odds change but being able to remember how your percentage changes by knowing each digit is much more of a feat and should be left to those geniuses amongst us. For example, using the {+1, +0} strategy when their A value is 0 gives us the 6/9 for winning and 3/9 for losing, but when their A is 7 it gives us 2/9 win, 4/9 loss, and 3/9 draw. But a just stated, remembering trivial info like this isn’t easy or suggested. Let’s take the strategy {+0, +1} now. This has 36% win, 51% draw, and 12% loss. With such a low loss % it is a very convenient strategy. In fact if we know their A is a 1, 2, or 3 we have no chance of loss with this strategy, which leads us into our offensive strategy. If we see that our opponent is using this as their strategy we know not to have our A be those values. In fact remembering at least one counter for common opponent strategies is important. For example, having “0x+6” as our start will give us a win in the 3rd frame or better yet “6x+2” will give us a win in the 2nd frame. Frame wins are only important if you are using them to be a factor of having beaten the player in the least number of frames to determine the true winner. Another important trick both on offense and defense is to hide your equations with modulus 9 taken into account. This way it is harder for opponents to see your strategies and harder for them to counter your equations. Ultimately the key is being able to mix up your strategies effectively, identify and counter opponent strategies, and being able to disguise your work, because even though this is a zero-sum game, it is complex enough that you don’t have time to do produce a simple 100% counter efficient method like you could in tic-tac-toe.
Overall understanding game theory can help you in many situations whether it be in a simple game for entertainment, a business situation, or even a tight crime case you got yourself into. And though there exists many problems in properly analyzing game theory, there are methods around them or at least ways to overview them and come up with half decent strategies.
