Complete Responsive Free – Price Plan Design – free project source code Download
Algorithm Game Theory – 1
In all the sports we play in reality, we cannot predict at the outset who will win the game, nor can we assume that all players will always make the best move. Besides, many games also require the help of luck. For example, in the game of cards, we do not know what cards the opponent has, or in the game of Ludo, we do not know when the six or the dice will come. In this series we will mainly deal with games that have the following features:
1. We have complete information about the game board, moves etc., we also know what position the opponent is in.
2. No luck is needed in the game.
3. At the end of the game, someone wins or loses.
4. There will be only two players in the game, the first and second players will take turns making moves.
5. Both players will make the best move at any point in the game, neither will make a wrong move. If a player has a chance to win, he must win, if there is no chance, he can never win because of his opponent’s mistakes. In short, each player will always make the ‘optimal’ move.
Complete Responsive Free – Price Plan Design – free project source code Download
While the types of games we will look at obey the above conditions, algorithmic games can be many more. Before reading this article, it will be helpful if you know the basics of dynamic programming.
In this type of game, by looking at the rules of the game at the very beginning or in the middle of the game, and by looking at the current state of the two players, it is possible to tell who will win the game if both players make optimal moves. Although in reality this kind of game seems boring, game theory has many uses in real life, game theory is used a lot in economics, politics, biology, etc., but in this tutorial we will learn about a small subset of game theory called ‘algorithm game’.
As a child I saw a game on TV in a magazine show, some marbles are placed on the table, an audience is brought to the stage. The presenter plays a game with the spectator, in the first move the spectator or the 1st player can pick up 2, 3 or 5 marbles, in the next move the presenter or the 2nd player can pick up 2, 3 or 5 marbles, after which the spectator picks up marbles in the same way. This will continue until no one can give more rice. The last person to pick up the marbles wins the game.
One after the other audience was seen coming and going in the show, it was not possible to beat the presenter in any way. If we analyze the game now, we will understand why it was impossible for even the most intelligent spectator to beat him.
In this game we need two pieces of information to know where the players are at any given time, how many marbles there are currently, and whose turn it is. If there are 5 marbles, then the player whose turn it is to make a move is in a ‘winning position’ or ‘winning state’, if he does not make any mistakes, it is impossible to lose him, he will end the game by picking up 5 marbles.
But if there are 1 or 0 marbles on the table then the player whose turn it is to make a move is in a ‘losing position’ or ‘defeated state’. We will now show that regardless of the number of marbles on the table, it is possible to know in advance whether the first player, the one who will make the move, is either a loser or a winner. We assume that no player makes a wrong move.
Complete Responsive Free – Price Plan Design – free project source code Download
Suppose there are n marbles on the table
The
3 things we need to keep in mind:
1. A position from which no further moves are possible is a losing position. For example in this game n=1
and n=0
This is a losing position. These are called terminal positions because no further moves are possible from this position.
2. If we are not in a terminal position, then we have to see if we can throw the opponent into a losing position with a move. If it goes then the current player is in winning position. i.e. n=5
If I want, I can pick up 2, 3 or 5 marbles and leave 5-2 = 3 or 5 – 3 = 2 or 5 – 5 = 0 marbles on the table. We already know that n=0 is a losing position from which no player can win. Since there are 5 marbles on the table, it is possible to move the opponent to a losing position, n=5
A winning position, if the current player does not make any mistakes, it is impossible to lose him from this position.
3. If the opponent cannot be moved to a losing position by any move from the current situation, the current player is in a losing position, unless the opponent makes a mistake, it is not possible for him to win anything.
Now we can easily find out what state the current player is in for any n with the following code:
We get the following output for each n:
0 means losing position, 1 means winning. From here it is clear that for n=15 the current player can never win. By removing 2, 3 or 5 marbles from 15 marbles we can leave 13, 12 or 10 marbles, but from the table it appears that all of them are winning positions, so it is not possible to win from the current situation. If the host starts the game with 15 marbles and makes the viewer the first player on that TV show, and if he is smart, it is impossible to beat him!
I am sure now you have understood how to solve such problems. Here are some problems to think about, all similar to the problem above:
1. Alice and Bob are playing a game, they have a number p=1
. In each move a player can multiply a number between 2 and 9 with p. If the number is greater than x after multiplication, he wins. Given the value of x, Alice always makes the first move. Who will win the game? (UVA 847)
2. UVA 11489
3. UVA 10891 for a slightly more difficult problem to solve
In the next part, I will discuss the most important topic of algorithm game, “nim game”.
Happy Coding…
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
All Links in Below:
Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.
Join Our YouTube Channel & Subscribe with Bell Icon for New Video:
Join Our Official Facebook Page For the Latest updates All Code Projects are Free:
Visit our service page to get premium services.
Free Website Create – HTML CSS, PHP, JavaScript Programming Projects For Free
Follow Us
Thank You,
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
FreeWebsiteCreate.net tries to provide HTML, CSS, SCSS, JavaScript, React, Android Studio, Java, PHP, Laravel, Python, Django, C#(C Sharp), and ASP.net-related projects 100% free. We try to make learning easier. Free Website Create always tries to give free projects to those who are new learners. Free projects and source code will help to learn easily. They can save time and learn more. In this post, we share a free portfolio project website code with HTML and CSS. This free code portfolio contains a single landing page with a responsive design. In this post, we get a free best carpenter and craftsman service website designed by FreeWebsiteCreate with HTML, CSS, Bootstrap, and JavaScript.