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.
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:
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.
We wish to thank:
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
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.
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.
This page is not connected with or endorsed by The LEGO Company. LEGO, LEGO TECHNIC and LEGO MINDSTORMS are trademarks of The LEGO Company.