Consider a game in which two players, Fred and Barney, take
turns removing matchsticks from a pile. They start with 21
matchsticks, and Fred goes first. On each turn, each player may
remove either one, two, or three matchsticks. The player to remove
the last matchstick wins the game.
(a) Suppose there are only 5 matchsticks left, and it is Fred’s
turn. What move should Fred make to guarantee himself victory?
Explain your reasoning.
(b) Suppose there are 10 matchsticks left, and it is Fred’s turn.
What move should Fred make to guarantee himself victory? (Hint: Use
your answer to part (a) and roll back.)
(c) Now start from the beginning of the game. If both players play
optimally, who will win?
(d) What are the optimal strategies (complete plans of action) for
each player?
Hope your writing looks readable and please draw the tree if possible.
Ans A)
The one who removes last stick wins and we can remove either 1,2 or 3 sticks therefore if 5 sticks are left then Fred should remove only 1 matchstick which will be left with only 4 matchsticks to choose for Barney in next round.
Barney can maximum choose 3 sticks then Fred will move final stick to win the game; If Barney removes 2 sticks then too Fred will win the game by removing 2 sticks ; If Barney removes 1 stick then too Fred will win by removing 3 sticks
hence Fred should remove only 1 stick when 5 sticks are left.
Ans B)
If 10 match sticks are left then Fred should remove 2 matchsticks so that 8 will be left
Now if Barney removes 3 matchsticks then 5 are left and we can follow part A)
If Barney removes 2 matchsticks then 6 are left and Fred can move 2 more match sticks which are left with 4 sticks to remove for Barney but Barney at most can remove 3 match sticks and hence Fred will win.
If Barney removes 1 matchstick then 7 are left and Fred can move 3 more match sticks which are left with 5 sticks to remove for Barney but Barney at most can remove 3 match sticks and hence Fred will win.
Ans C) & D)
The player who starts the game should always win if and only if he start the game by choosing 1 matchstick.
Game Plan as below
Now assume Fred starts the game and removes 1 matchstick therefore in 2nd round Barney can at most remove 3 matchsticks. The Game plan is Fred should make these sticks removal and they are 5th, 9th, 13th,17th.
In 2nd round when Barney removes any sticks between 1 to 3 then in 3rd round Fred will remove only up to 5th stick.
In 4th round Barney removes any sticks between 1 to 3 then in 4th round Fred will remove sticks up to 9th stick
similarly in the 10th round Barney is left with only 4 sticks and he can not remove more than 3 sticks and this game would be won by Fred in 11th round by removing 21st stick
Consider a game in which two players, Fred and Barney, take turns removing matchsticks from a pile. They start with 21 m...
1. NIM game. This is a different version or easier version of NIM game Consider a pile of 5 matchsticks. Two people take turns removing 1 or 2 sticks each time from this pile. Suppose both players play smartly (nobody plays a fool move trying to let the opponent wins. But there is only one winner anyway) a)If the person getting the last stick wins, will the first player win? Why? Show the steps the first and second player will...
A subtraction game Subtraction games are two-player games in which there is a pile of objects, say coins. There are two players, Alice and Bob, who alternate turns subtracting 4.9. A SUBTRACTION GAME 19 from the pile some number of coins belonging to a set S (the subtraction set). Alice goes first. The first player who is unable to make a legal move loses. For example, suppose the initial pile contains 5 coins, and each player can, on his turn,...
Answer the following Nim game style questions. (Robert's Game) In this game, two players take turns removing stones from a pile that begins with n stones. The player who takes the last stone wins. A player removes either one stone or p stones, where p is a prime dividing the number of stones in the pile at the start of the turn For which n does the First Player have a winning strategy? A winning strategy for the First Player...
Your task in to design a game of Nim in Python. In this game “Two players take turns removing objects from distinct heaps or piles. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap/pile. The goal of the game is to avoid taking the last object.” (Wikipedia) In your implementation of the game, there will be 3 piles of objects. At the start...
Problem 4. (20 points) Pebbles Game. Two players play a game, starting with three piles of n pebbles each. Players alternate turns. On each turn, a player may do one of the following: take one pebble from any pile take two pebbles each from two different piles The player who takes the last pebble(s) wins the game. Write an algorithm that, given n, determines whether the first player can "force" a win. That is, can the first player choose moves...
In a game of Tic Tac Toe, two players take turns making an available cell in a 3 x 3 grid with their respective tokens (either X or O). When one player has placed three tokens in a horizontal, vertical, or diagonal row on the grid, the game is over and that player has won. A stalemate occurs when all the cells on the grid have been filled with tokens and neither player has achieved a win. Write a program...
In traditional Tic Tac Toe game, two players take turns to mark grids with noughts and crosses on the 3 x 3 game board. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row in the game board wins the game. Super Tic Tac Toe game also has a 3 x 3 game board with super grid. Each super grid itself is a traditional Tic Tac Toe board. Winning a game of Tic...
In a game of Tic Tac Toe, two players take turns making an available cell in a 3 x 3 grid with their respective tokens (either X or O). When one player has placed three tokens in a horizontal, vertical, or diagonal row on the grid, the game is over and that player has won. A stalemate occurs when all the cells on the grid have been filled with tokens and neither player has achieved a win. Write a program...