Sunday, July 7, 2013

Atmel Microcontroller Plays the Tic-Tac-Toe Game

A couple of years ago I made an electronic Tic-Tac-Toe game with  Pololu baby Orangutan controller as the central component. Pololu  is an excellent device  but for Tic-Tac-Toe game it was an overkill. Its motor drivers were of no use and  it required  at least 5 V power source, so I had to add an adapter to make device workable on two batteries. Recently I decided to gain some experience with bare bone Atmel controllers and repeated this project with ATmega 168. Setting  this controller to the lowest possible frequency (1 MHz) allowed me to eliminate the power adapter. (Two AAA rechargeable batteries provides 2.4 V, which is more than enough for ATmega 168 at this frequency). Here is the circuit diagram of this toy.



Let us look at the list of components:


1. All electronics were mounted on a RadioShack component PC Board 276-168.
2. Central processor Atmega 168 (do not remember where exactly I bought it, many online providers sell it)
3. Nine Bi-polar bi-color 5mm Green/Red LEDs. (again I did not keep the record of purchase,  some online providers sell it)
4. RadioShack 2 AAA battery holder  270-398
5. Nine resistors 51 Ohm 0.25 W (0.125 W is OK as well)
6. Panasonic  EVQ-WTEF2515B Encoder (goldmine-elec-products.com; alas, looks like they do not sell it anymore)
7. Ceramic capacitor 0.47 uF.
8. RadioShack slide switch 275-409
9. Male headers 2.54 mm to make six contacts ISP header. SItes pololu.com or hobbyengineering.com sells various types of them.
10. RadioShack 2-pack 14-PIN IC socket (optional, just to have the possibility to reuse controller  on other projects).
11.Hook-up 26 gauge wire ( hobbyengineering.com ) and 30 gauge precut wire  (Frys electronic store).





As  an enclosure  I used a box from Johnson&Johnson emergency kit. I had to treat edges of the board with file to make it fit into the enclosure.


As you can see the density of project components on the boards is not high.  Soldering elements  to the board and connecting it with 26 gauge wire was not that hard. To find out how LED was oriented on the board follow the simple rule: top of any LED on my diagram corresponds to the longer LED leg.  Contacts of panasonic encoder are very fragile  so I used 30 Gauge wire here. The PC board layout does not provide the proper place to solder ISP header. So I have to separate  three contact plates with utility knife and solder wire directly to contact plates occupied by headers.




Of course, the main part here is the program. For machine to choose the right move there is a well known algorithm: game tree search.   There are many sources to look for. In particular I have used this Berkeley lecture: http://www.cs.berkeley.edu/~jrs/61bf10/lec/18.pdf and strictly followed the described here game three search with simple pruning algorithm converting pseudo code into the C language. The only deviation from the algorithm  I did during programming  of the first  computer move. If computer starts the game it chooses randomly among central and four corner squares. If computer does not start the game it makes its first move in to the center if the center is  free  or chooses randomly any corner square if center is occupied. There are two reasons for such deviation. Making a move when the board is  empty means too many choosing attempts (hundred thousands) and it will take a lot of time  for a low frequency controller to calculate it. In addition introducing some randomness makes the game on the computer side less predictable and boring.


Source code for the toy is available here https://bitbucket.org/jumbleview/three-in-a-row/src/


After compiling code with free Atmel Studio 6.1, the resulting hex file was written into the controller flash memory with the help of Atmel ISP MKII (I bought  mine at mouser.com )


Let us look at the compiler printing regarding the program memory allocation:

Program Memory Usage : 3548 bytes   21.7 % Full
Data Memory Usage : 57 bytes   5.6 % Full


Based on that we can conclude that  after recompilation the code will work on any of controllers from the line:  Atmega48, ATmega88, ATmega168, ATmega328.


And finally here is how the Atmel controller plays the Tic-Tac-Toe game: