|We don't bite newbies here... much|
Need a Strategy to work outby msk_0984 (Friar)
|on Jul 02, 2007 at 06:38 UTC||Need Help??|
msk_0984 has asked for the
wisdom of the Perl Monks concerning the following question:
Hello Monks, I need a strategy to biuld this please help mee out i hav this project to be complted but i am unable to find out a good strategy got soem ideas but they r really not applicable over here ...........
I need your help i need soem good solution strategies Here is wat i need a breif explaination
WHAT IS NASH EQUILIBRIUM?
Nash equilibrium is defined as an outcome with the following property: each player's strategy is the best response against the other player's strategy. In other words, Nash equilibrium consists of two actions that are best responses against each other.
If players' actions are best responses against each other, then neither player will be willing to switch to another action given that his opponent sticks to the equilibrium action. In other words, a player cannot do better by changing his mind, given that his opponent doesn't change his mind. Why? Because if a player changes his mind and switches to another action, this action will be inferior (remember that the equilibrium action is the BEST response against the opponent's action). As a result, the player will be worse off! In a sense, every Nash equilibrium defines a saddle point from which nobody wants to deviate.
WHAT IS STRATEGY?
Do not confuse a strategy with an action. In most of your games, there are only two available actions. On the other hand, a strategy is a complete algorithm for playing the game that specifies which action the player must take at every step of the game (since the game is played 1000 times between two strategies, there are 1000 such steps). Therefore, you need to implement three different algorithms and play them against each other in a round-robin tournament.
HOW GOOD MUST YOUR STRATEGIES BE?
It does not require that you choose perfect strategies. However, I will give you bonus points if your strategies are good, i.e., they can defeat most other strategies. An example of a weak strategy is a strategy that always plays the same move (1000 times) regardless of the opponent's behavior.
HOW TO CHOOSE STRATEGIES?
A good strategy must take into account the history of all previous moves played by the player and his opponent and define the player's next move. The main problem in defining the next move is that the strategy doesn't know how the opponent is going to play (please, keep in mind that the players make their moves simultaneously without knowing what the other player is going to do). A "smart" strategy would try to predict the opponent's next move based on the history of his previous moves. Since every game is played 1000 times in a row, the strategy can collect information about the opponent's past moves, opponent's reactions to specific moves (or to specific move sequences) and came up with a reasonable guess about the opponent's next move. As you can see, a good strategy would try to learn from the previous moves and adjust its behavior appropriately in order to defeat the opponent.
The bottom line is that a good strategy must be dynamic. It would take into account the opponent's previous moves and adjust its behavior appropriately. In other words, it will dynamically change its behavior as a response to the opponent's past behavior.
HOW ABOUT RANDOM STRATEGY?
The simplest dynamic strategy is a random strategy. However, it is not a very smart choice because it does not learn from the opponent's past moves. After you come up with some good strategies, you could test them against a random strategy to see how good they are. In fact, playing against a random strategy is not as easy as it could seem (because one cannot come up with any rational expectations. If your opponent plays randomly, then everything is possible).
There is no problem if one of your strategies is purely random.
WHAT YOUR PROGRAM SHOULD DO?
- Three different strategies, i.e., three methods that can play a round of 1000 games in a row against the same opponent. In every single game (there are 1000 such games in a round), the output of your method must be an action. Usually there are two available actions, and your method (strategy) must decide which action to play.
- A main program that can play a round-robin tournament between the three strategies (methods). When the main program plays two strategies against each other, it enters a loop (of 1000 repetitions) in every step of which it receives the outputs from the strategies, determines the outcome, and sends each strategy its score and the opponent's move (remember that when a strategy decides which action to play, it doesn't know how the opponent is going to play). After all three strategies are played against one another, the main program reports the final result from the tournament.
Please provide me a better strategy or any good idea for this and help me out monks....
Work Hard Party Harderrr!!