"Coins" : Backwards Induction through Reinforcement Learning
Coins is a relatively simple game where fifteen coins are placed in a pile and two players take turns removing either one, two, or three coins from the pile. The winner is the player who removes the last coin from the pile. It is a game of strategy, and a perfect strategy exists where the player who goes first can always win.
Software
Try playing and see if you can figure out the perfect strategy. You can play against four different kinds of computers. There is a random computer, which will just make random moves and is pretty easy to beat, a novice computer, which makes random moves unless it sees the opportunity to win, a perfect computer, which will always win if you do not play with the perfect strategy, and a learning computer, which is by far the most interesting. The learning computer starts out by essentially making random moves, but as it plays more and more it learns the perfect strategy. You might not want to play the learning computer enough to see it improve, it takes about 400 games, so instead you can pit it against one of the other computer players and let it play a few hundred games to get some experience. Try playing the learning computer for a few games and then let it get some experience against the novice or perfect computer for a few hundred games. After it gains some experience it might be good enough to win every time if it goes first, or play just as well as the perfect computer if it goes second.
When you start Coins you will see the game window. It contains all the information needed to play a single game, and is setup by default to have the Learning Computer going first and the Novice Computer going second. If you play the two computers against each other, when you click the "Start Game" button you will be asked how many games the computers should play.
To play against the computer yourself change either Player One or Player Two in the Game menu to Human. Then, when you are ready to play, click on "Start Game". You will now be able to use the "Take One", "Take Two", or "Take Three" buttons to remove coins from the pile. The number of remaining coins is displayed at the top center of the window, as "Coins: XX", and as the number of coins shown on the right side of the game window.
There a many different combinations of players that you can set. Try a few out and see if what happens meets your expectations. Also, keep in mind that anytime you change players the change only takes effect when the next game starts. You can click on "Stop Game" to stop a current game.
Remember that the most fun computer player to toy around with is the Learning Computer. If it gets too good and you want to try teaching it in a different way you can use the "Reset Learner" option under the "Learner" menu.
So why is the "Learning Computer" so fun to play with? Well, for one thing it starts out with absolutely no knowledge about how to win the game. At the beginning, all it knows is how many coins are left in the pile and how many coins it can possibly take, and all it ever knows is the number of coins left in the pile, how many coins it can take, and how good it thinks taking some number of coins is based on how many coins are in the pile.
To learn more about reinforcement learning, try the Smarts simulation, or the LEGO© Mindstorms demonstration.
