Dice Game
Dice Game
Introduction
I first read about this game in Ian Stewart's book "The Cow Maze" and immediately thought it had potential as an arduino project. The idea is that it is a game involving a dice, but with no random element of luck. In this game the top number on the dice is used to indicate by how much a number, or heap as I call it, should be reduced. The winner is the first to reduce it to exactly zero, or get the opponent to overshoot zero. What makes this into a game of skill is that, on any turn, the only numbers you can't use are the number already shown on the top of the dice, and the number the dice is resting on. There was a complete analysis of the game published in this book, so it looked like an ideal candidate for a computer verses human game.
The Dice Game
Internal Wiring
Finished unit
Theory
This is the sort of game that could easily be programmed to run on a desktop computer, with scope for some fancy graphics. Put from the point of high resolution, you can't get higher than reality, so it looked like a physical game implementation might work well. From the point of view of a physical game you need two elements, the ability to sense which number is on top a dice, and some way of keeping track of the current heap number. It is not so easy sensing the top number on a dice unless you set up a video camera and do some image processing. This is all very well but it rules it out as a stand alone game. However, using the widely known fact that opposite sides of a dice add up to seven, it is comparatively easy to sense the number on the base of the dice. The trick here is to replace the dots with small magnets and use Hall effect sensors to detect them.
At first sight it might seem that you need nine sensors to cover all the spot positions on a dice. However, when you look at it more closely, you will see a certain symmetry about the response from the sensors. Close examination show that there are pairs of sensors giving the same readings, therefore you only need one of those sensors to be present. There is a slight complication with the fact that the dice can be placed down in any rotational orientation, this means that with some numbers, like three for example, there are two possible patterns from the sensors. The upshot of all this is that we need five sensors to fully detect all the possible combinations of the dice.
Playing with dice but needing no luck
By Mike Cook
Design
Now we can begin to formulate a plan of this project. An Arduino processor, connected to five hall sensors along with an LCD to interact with the player, all contained in a nice wooden box. In order to eliminate any other controls, I used another sensor to detect when the box lid was open or closed, this acts to quit a game part way through and to start off each game. It also enable the LCD back light to be turned off when the game is not being played.
A vital aspect of construction is that the sensors must be placed in exactly the right place in order to pick up the magnets on the dice. This meant that it was best laid out on a printed circuit board where I could have absolute control over the component placement rather than being dictated to by the pitch of holes in strip board. As there was only one chip, the processor itself, then I incorporated that into the PCB as well. Finally the tiny surface mount sensors I chose, because they were the cheapest I could find, needed a low voltage supply. The maximum working voltage was 3.3V, so I arranged a 3.3V regulator and then added a series diode to take the voltage down another 0.7V, thus giving me a 2.6V supply. This meant that the voltage out of the sensors went from 0v to 2.6V, not enough to trip a digital input. However, by using the analogue inputs I was easily able to distinguish between the two states of the sensor. I decided to use some of my 5v power supplies so this project has no 5 volt regulator in it but you could easily fit one if you want.
Construction
First of all I made the box, I drew the panels of the box in Inkscape and exported it, in PDF format, for the laser cutter courtesy of The Manchester Fab Lab. I used 6mm ply wood to cut out the shape and glued the box together. The box was finished off with two coats of a light oak staining varnish. The difficult part was fitting the hinges. I managed to get some miniature hinges from a craft shop and also some M2 brass nuts & bolts from a model makers supplier. These were quite difficult to find but, after some searching, I found them here. The false base, or panel, in the box, where I mounted the electronics, is supported by four 24 mm long offcuts glued in the box corners. The length was designed so that you could just close the lid with the dice fitted in the recess and have the dice not come out of recess when the lid is closed. This false base was a neat push fit and no further fastenings were needed.
Next, I milled out a rectangular hole for the LCD surrounded by a larger recess so that the LCD slotted into place with the display expose. I was then able to fix the display with hot melt glue. A recess was also milled in the top side of the panel to hold the dice in place. This was made to the dimensions of the dice and milled out so that the original 1mm bottom sheet in the plywood was left intact. If you haven't got a miller you could as easily cut a hole through and then covered it up on the underside. The Gcode files for cutting this along with the PDF of the box cutout and software can be downloaded here. Just a point here that I did get two wooden dice, but one was not quite a cube it was longer by a few mm in one direction, so if you are going to get one then take your Verner callipers with you, and make sure you get one as close to a cube as possible.
One of the most difficult parts of the construction was fitting the lid closing sensor inside the plywood. A blind hole was drilled vertically down the side, and a hole was drilled horizontally to meet it. I did this after the box had been assembled but it would have been easer, and less potentially disastrous, to do it before. At the top I widened the hole to form a recess to take the minute printed circuit board. This contained only a hall sensor and a surface mount decoupling capacitor and was mounted so that the plain side of the board was uppermost. Then a small dab of black paint matched it to the colour of the cut wood and it all but disappeared. A small recess was cut in the lid over this point and a 3mm magnet was glued in. Just to round things off a magnet was inserted top and bottom of the lid at the front to give it a nice click feel when the lid was closed. To be honest I actually put two magnets in one side to take up the slack left by the slightly imprecise hinge fitting.
Next I had to replace the dots on the dice with magnets, these were the same type I had used from the lid and were 3mm diameter and 0.5mm thick, I got them from first4magnets.
I could have glued them straight in, or made a recess with a 3mm drill, but I wanted a flat bottom to the recess and so I milled a small round blind hole. Again the Gcode file is available in the download pack. I was worried that the dice might look odd with the shiny dots but when I showed it at a Maker Faire many people did not even know there were magnets on the dice until it was pointed out to them.
Electronics
The schematic is very simple just an LCD module, arduino processor ATMEGA168, a transistor to turn off the LCD backlight and five hall effect sensors. My choice of sensor was guided by one principal, price. This had the advantage that they were also very small surface mount parts, ideal for fitting in the lid. However, the disadvantage of this is that they were very small, some of the smallest parts I have ever prototyped with. They had to be placed on the board to pick up the magnets on the dice and so the simplest thing was to make a small PCB. This was milled out and again the Gcode file is included in the download pack. As it is only a single sided PCB I did not strive overly to have every connection made by the board, but rather just use it as a convenient prototyping platform, with many of the connections completed by wire links. Again the Gcode file is in the download pack. I swapped sensor 1 and 9 over just to spread the wiring density about a bit. Make sure you solder them on right first time. I had to remove one and the small copper pad came with it. Attempts to glue another pad on failed when the iron was applied and I ended up soldering directly onto the component pin, followed by a dollop of glue to stop any strain on the components. While this approach is possible, it is not recommended.
Firmware
The major requirement driving how the software is written is the requirement to restart and quit a game every time the lid is opened and closed. This could have been done by using interrupts from the lid sensor but as I said the sensor has a low voltage output, and I used the analogue input to read it. To make a proper interrupt generating digital signal I would have to have put it through a transistor. Instead I wrote the firmware as one great big state machine, with the lid sensor being read on every loop. I used the delay function where necessary to simplify the state machine but when ever there is an indefinite hold, like when you are waiting for the player to change the dice, there is a new state or sub state. For those who have not met it before, the idea of a state machine is that a variable, called a state variable, holds a number that indicates how far through the program we are. Each time round the big loop this variable directs the software into the part of the program that looks to see if an action has occurred to advance the state. If it has, then the state variable is updated, normally incremented, tasks like displaying something, are completed for the new state, and then the next time round the loop we check again to see if the holding action has been completed.
Each phase of the game is a state, like setting up the target heap, the player move, the computer move and so on. In each state there are some sub states, for example in the players move we have to wait for the dice to be picked up, then wait for it to be put down, each phase is controlled by a sub state variable. Next, we have to see if it is put down so a valid number is shown. If not an 'invalid' message is shown and the state set back to waiting for the dice to be picked up. If it is valid then the calculations have to be made to the size of the heap, check if you have lost, won or the game continues with the computer's turn.
At the heart of the game is the move matrix, this gives the computer's move for any given heap size and for any current state of the dice. Note that for example the move to make is the same if the 6 or the 1 is uppermost, in fact the move is the same for any 180 degree rotation of the dice. This gives a three line matrix. The heap size dimension of the matrix could in theory extend out to the maximum number of the heap. However, an analysis of the game shows that once the heap size is greater than 16 it repeats the last 8 entries. That means you can cope with any size of heap with a move matrix of only 16 moves. What you do is to take the heap and repeatedly subtract 9 from it, until it is in the range zero to 16, and use that number for looking up your move.
In the move matrix there are three sorts of moves, 1 to 6 is the number to play next, then there are moves with a higher number, these indicate a choice. For example if a move is flagged as 7 then you can move either 2, 3 or 4. Finally if a move is shown as 128 then no matter what choice you make you will always loose so the computer just picks a random valid move. There is a function called computerMove(); that looks up the move in the move matrix given the current size of the heap and what number is uppermost and then interprets the number it finds to produce the final move.
Mind the gap
I used my own version of the LCD library to access the busy flag so the LCD access was fast. In this application it is not strictly necessary. However, the sort of LCD module I had did not respond to the cursor correctly and the first eight characters are not adjacent with the second eight. Therefore there is a function that keeps track of how many characters have been written and adjusts the cursor to step over the gap.
The function generateHeap(); is used at the start of the game to pick a heap number that is winnable for the player. However, if the player deviates from the perfect game the computer can then get on the winning track and once on it the computer is not going to loose. Having said that, at the Maker Fair 2011 I had two people win who didn't really know what they were doing, so it is possible.
So here is a game of skill with a novel physical interaction with the computer, and just to show you can win here is a video showing two games, one with the computer winning, and one with the player victorious.