The Game Of Nim

◦ Discuss other variations of Nim including their winning strategies.
• Charles Bouton, 1901
◦ Coined the name “Nim” for the game
◦ Developed a complete theory of the game, including a winning strategy
Rules of Nim
• Game starts with a number of piles (or rows, columns, etc.) and a number of objects (pennies, peanuts, counters, etc.) in each pile.
• Example
Rules of Nim
• Two Player Game
• Players take turns
• On each turn, a player must choose one pile and remove at least one object from the chosen pile.
• Example
Rules of Nim
• Two ways to play:
◦ Normal Play: the player who removes the last object is the winner
◦ Misère Play: the player who removes the last object is the loser
Winning Strategy
• *For the normal play convention
• Convert the size of each pile into its binary notation
• Add the columns up independently modulo 2.
• The resulting value is called the Nim sum
Winning Strategy
• Example
Binary
• 7 = 1 1 1
• 4 = 1 0 0
• 5 = 1 0 1
1 1 0
Nim Sum
Winning/Losing Positions
• A winning position occurs when the Nim sum equal zero
• A losing position occurs when the Nim sum is greater than zero
• A player can always make a move from a losing position to a winning one.
• Once in a winning position, the next move will always result in a losing position
• Therefore, the optimal strategy is to always be converting losing positions to winning positions on each move.
Winning Strategy
• 7 = 1 1 1
• 4 = 1 0 0
• 5 = 1 0 1 1 1 0
0 0 1 = 1
1 0 0 = 4
1 0 1 = 5
0 0 0
1 1 1 = 7
0 1 0 = 2
1 0 1 = 5
0 0 0
1 1 1 = 7
1 0 0 = 4
0 1 1 = 3
0 0 0
Winning Strategy
• Intuition
◦ If...

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!