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).
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.
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
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:
