Mario's Lego Robotics Archive

TTT: A Lego® Mindstorms Tic-Tac-Toe Player

by Marco Beri, Giulio Ferrari and Mario Ferrari

The story

When during summer 1999 we decided to attend the MindFest at the MIT, we thought it would have been nice to go there with a Lego® Mindstorms robot of our own. The first thing we were looking for was an idea of something not necessary genial but possibly original and challenging for us to set up.

Marco had the idea of a robot that plays tic-tac-toe against an human opponent, and we immediately felt it was the right project to show at the most famous temple of AI in the world. So we started discussing the details of the project. We had clear in mind that our robot would have placed pieces on a board instead of marking symbols on a sheet of paper the classical way, but stated that all the rest was to be decided.


The project

Some of us (read "Mario") tend to be very tolerant on what is acceptable in a Lego® robot (like custom sensors) and tend to put a lot of resources in carrying it out: multiple RCXs, pneumatics, tons of motors, micro motors, rotation sensors and so on. Marco remarked that it would have been very nice to keep the project to a point where it's easy for others to reproduce, and that would have made the thing even more challenging for us. So we ended up with some very strong self-imposed constraints: to employ just a single RCX, basic RIS sensor equipment (two touch and one light sensor) and three motors (one more than the RIS equipment, but we absolutely needed it). For the same reasons, we decided to adopt NQC for the software development: the original Lego® software was beyond dispute for its great intrinsic limitations, while legOS and pbFORTH on the other side are much less widespread.

We had to face many problems, some of them are worth to be mentioned: how to handle pieces, how to communicate the robot the human's player move, how to tell the robot it is its turn to play, how to handle a grid of moves in code without an array structure.

To keep the story short and come to the point, we adopted the very well known plotter scheme, with two movements along two orthogonal axis. The head of our "plotter" mounts motorised pliers to handle pieces instead of a pen. Two motors are in charge to move the head along the axis, and two touch sensors keep track of the head position counting pegs along the guide-rails. The head of the plotter mounts a light sensor too that's used to scan the board and "see" what the situation is.

Our software plays a single move at each run. There isn't any overall game cycle, and its knowledge is limited to the current situation. We thought this approach keeps the software as simple as possible, and gives a more robust application within the limits of our very simple robot-human interface. It provides also a way to tell the robot when its turn to play comes, simply pressing the Run button.

Here is a brief step by step description of our code:

  1. Calibrate the light sensor for ambient light, reading some fixed position coloured bricks that mimic pieces.
  2. Scan the board, and store its status in an (emulated) array.
  3. Check if somebody wins. If yes, notify this with a sound and go to point 8.
  4. Decide where to move the next piece.
  5. If there isn't any possible move, go to point 8.
  6. Move the piece: take the piece provided by the human player on a special platform and drop it at the chosen location.
  7. Check if somebody wins. If yes, notify this with a sound.
  8. Return to neutral position.

Point 4 of this list contains the strategy of our robotic player. We would have loved to develop a learning player, but we considered this possibility out of our reach. NQC (or better the underlying firmware) has too many limitation to allow easily implementation of genetic algorithm, not to talk of neural networks. We had to face also our shortage of time, so we decided to implement a very simple "flat" strategy.


The Code

The original NQC code that we used at the Mindfest is available here: Download TTT NQC code (zipped, 4K).

Contributors

  • Marco Beri: The Idea. Most of software development. Testing.
  • Giulio Ferrari: Scanning process fine tuning. Pieces and board design. Testing.
  • Mario Ferrari: Hardware platform design and set up. Minor software development.

We wish to thank:

  • Carlo Ottolina and Marco Berti for their invaluable suggestions and support during our first Italian Legofest.
  • Dave Baum for having promptly fixed a minor problem of his great NQC compiler, appeared during TTT software development.

Details

We are not going to publish detailed instructions "Lego® style" on how to build your own tic-tac-toe machine, but we're glade to share some suggestions and pictures so everybody can get something more than a just an idea of how our TTT was made.

One of our main goals was trying to minimise the use of rare Lego® parts. For this reason, you should be able to set up your own tic-tac-toe robot having just a standard Robotic Invention System set, one additional motor and some other very common parts (though we didn't keep a precise inventory of the parts we used).

The rarest part we used is the light brick. During the test phase, we discovered that the scanning process was not affordable enough to produce always perfect results, so we reluctantly added a small Lego® 1x2 light brick right aside the light sensor to ensure good and stable readings in any lightning condition.
The light brick is available as spare part through Shop @ Home (in USA) or lego Service (in Europe) as set #5310. It's in the Pitsco catalog too, part number N970005.

Other things you might not have at home are the 6 long cables. If you have the RIS and an additional motor you probably have two or three of them. You might join together some shorter cables.
The long cable is available as spare part through Shop @ Home (in USA) or lego Service (in Europe) as set #5111. It's in the Pitsco catalog too, part number N779898.

You need also one of those 48 x 48 studs gray baseplates, but they're easy to find.


An overall look at TTT. From this picture you can get a general idea of how it works. There's a main trolley (black) that runs on two guide-rails (black). The trolley is made of two guide-rails where the "head" (yellow) moves orthogonally to the trolley itself.

Top view of the board. It's built over one of those large 48 x 48 gray plates. You can see the classical tic-tac-toe scheme, the two main rails, some blue (human player) and white (TTT) pieces, the black platform where TTT grabs its piece to play (upper left), the light sensor calibration area (blue and white bricks below the platform).

The platform is a 6 x 4 area, one brick + one plate + 1 tile high. It's covered with tiles to make TTT slide the grabbed piece. On the upper and left border of the platform there's a two brick high wall that provides a convenient way to align the piece properly. The human player has to put a white piece on the platform before each move.
The pieces are made of a 4 x 4 plate and a 2 x 2 brick of the same color, white for TTT and blue for the human opponent.

The right guide-rail. The rail is made of standard (black) beams mounted upside down to provide a flat surface where the main trolley can run over. The rail is supported with an external line of beams (studs up) and short beams behind the latter to support it. Final height is two bricks.
The right rail only shows a third line of (yellow, studs down) beams that support some gray 1 x 1 plates used to detect the main trolley (Y) position with a touch sensor.

This is the main trolley, bottom view. The whole trolley was built upside down (studs down). There are three long (12 studs) axles that connect the right motor-driven wheel to the left one, to provide better and smoother movement of the trolley. On the inner side of the wheels there are beams whose height go further the wheels themselves. These are designed to slide on the inner side of the rails to keep the trolley in place.

The motorized side of the trolley. The motor is connected to the wheel using a belt, from a small pulley (motor) to medium one (wheel).
Note the sensor used to detect the trolley position.

The trolley, right side. The sensor matches exactly the gray 1 x 1 plates on the yellow reference rail. To adjust the height of the rail, the yellow beams have been added a layer of plates.

The head, front view. This is the most complex part of TTT. There are two motors, one for the movement and the second to control the pliers. The head incorporates also a light sensor and a light brick (for board scanning), and a touch sensor (for positioning).
Everything in TTT is belt driven to allow tolerance through slippage if something goes wrong.
The motor on the left drives the pliers, while the right one drives the wheels.

The head, bottom-front view. The pliers have a fixed side (right) that incorporates the light sensor.

The head, bottom-rear view. Note the touch sensor used to track (X) position on the trolley, and the light brick to enhance quality and consistency of light readings.

The head, rear view. The switch on the head matches the 1 x 1 plates mounted on the (yellow) rail of the trolley. From this picture you can understand how the pliers work. On the back side there's a mechanism that (through the blue rubber band) keeps the pliers firmly in one of two positions: open or closed. This way there's no need to keep the pliers motor running to prevent the piece from dropping.

In this picture (rear view) you can see the pliers closed to grab the piece. The piece is not picked up, but simply grabbed, dragged over the board to the proper place and then dropped.

The head, top-front view. The pliers motor (right) mounts two connectors: the first comes from the RCX, while the second goes to the light brick. The light brick is actually turned on running the motor for a fraction of a second, in the direction used to open the pliers. This occurs while TTT scans the board, and at that stage the pliers are already open, so the belt slips and nothing bad happens.

The head, left side view.

The head, right side view.


Further improvements

Some ideas for variations to our project:

  • If you have two rotation sensors, you can set up a version of TTT that uses a polar (or cylindrical) coordinate system to address the board cells.
  • The pliers might be pneumatic.
  • It is possible to develop a learning version of our software, but not inside the limitations of the standard firmware (we'd love to be proven wrong on this). Using legOS or pbForth you might implement some kind of genetic algorithm, or even try an approach similar to Martin Gardner's matchbox computer.
  • You can do without the touch sensors for head positioning if you use the "stepper motors" suggested by Robert Munafo. Probably not very practical, but just to say you could use even less resources.
Copyright © 1996-2013 by Mario Ferrari. All Rights Reserved.

This page is not connected with or endorsed by The LEGO Company. LEGO, LEGO TECHNIC and LEGO MINDSTORMS are trademarks of The LEGO Company.