The project time and skill level is based on creating it from scratch, it should only take 10 minutes to put the code into the portals yourself.
Examining the game Nim is a common exercise in game theory classes due to the ease in which an unbeatable strategy can be devised. For this reason it is a perfect game to use when playing against a computer because the computer can be programmed to win every time.
Playing NimNim is traditionally played using a group of objects, such as pennies, sticks or matches. The objects are put into groups (most commonly 3) with varying numbers of objects in each. Each player takes turns taking any number of objects from a pile. To win the game you take the last object.
The Optimal StrategyNim has an optimal strategy meaning that if played correctly a certain outcome can always be achieved. In this case the outcome is winning whenever possible (I will explain unwinnable games later) and is easy to implement because it is based around the binary representations of numbers and XOR operation.
If you want to go more in depth the Wikipedia article is very informative. Focus on the Mathematical Theory section as it describes the strategy I implemented.
If you don't want to read the article a short summary of the strategy is as follows.
- First, nim-sum (a.k.a. XOR) all the piles. If the result is 0 you are in a losing position. Take one from the first pile to prolong the game and increase the chance of the player making a mistake.
- Second, nim-sum each individual pile with the result of step one. Identify a heap which nim-summing it with step one resulted in a number less than its size.
- Third, reduce the size of this pile to its size nim-sum the result of step one (as determined in step two). This is garunteed to result in the nim-sum of the piles being 0 which is a winning state
- Repeat after opponent's turn.
Shortcut:
When there are two piles left simple reduce them to equal sizes on your turn. Performing this operation guarantees the nim-sum will be 0 at the start of your opponent's turn because you are nim summing two numbers with the same binary representation.
Creating the Alexa SkillFollow my guide to create an Alexa Skill. The code an schema contents are below.
Future additionsI have submitted the skill for certification and am waiting for a reply. I am also working on a raspberry pi device which will use RGB leds to display the pile sizes in real time. This will be linked as soon as it is finished.
It's published!You can now open this skill from your Alexa without recreating the skill.
Comments