Dr. Rainer Hessmer - Robot Plays Tic Tac Toe

Robot Plays Tic Tac Toe

Finally we are getting to the point where we can assemble the various building blocks into a WinForm application (project TicTacToe.Robot) that makes the robot arm play Tic Tac Toe against a human opponent. The TicTacToe.Robot project is part of the same TicTacToe.sln solution that we looked at in the last section (folder http://code.google.com/p/robotic-tic-tac-toe-lynxmotion/source/browse/trunk/#trunk/TicTacToe).

Here is a screenshot of the app at the beginning of a new game:

The file menu and the threshold entry field are the same as in the Collector application. The Delta Non Zero value is constantly calculated and indicates the changes of white pixels in the inverted black & white image between subsequent frame captures. It is internally used to make sure that frames are only evaluated when the image is fairly static. As a result the application ignores any frames while the human player sets his/her game piece. The Reset button is used to reset the system after a game is complete.

The four image boxes show the original image as captured by the camera, the converted and inverted black & white image, the detected rectangles that make up the board, and finally the detected unused game pieces. The last frame is only calculated when the robot actually needs to pick up a game piece to make its move. To the right of the image boxes a graphical representation of the board is displayed. As the game progresses it is filled with crosses and circles indicating the game pieces of the human player and the robot player, respectively.

The whole execution logic is controlled by a hierarchical statement machine. The current state is shown below the image boxes. At the very bottom the next robot move is displayed. It is filled in after the program detected the move of the human player.

The UI layer of the application is very thin. It communicates with the rest of the application logic via the MainModel class:

    internal class MainModel
            public RobotDriver RobotDriver 
        public string NextMove 
        public event EventHandler Changed;

        public MainModel()
        
        ...

The MainModel singleton instantiates

  • An ImageProcessor which handles the capturing, massaging, and drawing of images shown in the image boxes.
  • A BoardImageModel which is responsible for detecting the board and its state plus the location of unused game pieces.
  • A BoardManager which encapsulates the Tic Tac Toe playing logic.
  • A RobotDriver which executes the robot arm moves that pick up game pieces and put them on the board.
  • A ControllerHsm which is the hierarchical state machine coordinates the various activities.

With the exception of the hierarchical state machine the essential elements of the various pieces of code have been introduced in the previous sections. In the case of the TicTacToe.Robot project the code is just better factored into individual classes. This leaves us with the ControllerHsm class.

Hierarchical State Machine

The ControllerHsm class implements a hierarchical state machine based on my qf4net library. Here is the associated state chart:

When the state machine is initialized it falls into the InitializeBoard state. Here the system stays until it can detect the empty Tic Tac Toe grid. Once the board is detected it transitions to the Initialized state from where it directly falls into the WaitingForHuman state. Once the human move is detected it transitions to the RobotsTurn state where it tries to find a game piece on the left of the Tic Tac Toe grid to put onto the board. If a game piece is found it transitions to the MovingPiece state where it asynchronously moves one of the found game pieces. It stays in this state until the move is complete. If it can't find a game piece it transitions to NoPieceFound and keeps trying until it finds a game piece (hoping the human fixes the situation).

Once the robot move is done it either transitions back to the WaitingForHuman state or transitions to one of GameOver's sub states. The same transition to one of the GameOver states can happen when it detects the human's move and this move ends the game.

At any point in time the Reset button can be pressed. It results in a transition from the CatchAll state to the InitializeBoard state thus restarting a new game cycle.

The state diagram hopefully helps to make sense of the provided source code. Once a game is over the human player needs to remove the game pieces from the board and position the robot's pieces to the left of the Tic Tac Toe board. Then the Reset button needs to be pressed to start a new game.

Last Updated Thursday, 24 December 2009 01:40

News

Apr 4, 2010
Category: Robotics
Posted by: rainer
A new article about the Monte Carlo Localization algorithm is now available in the robotics section.
Jan 2, 2010
Category: General
Posted by: rainer
Information about ongoing projects will be available on my blog.
Dec 24, 2009
Category: Robotics
Posted by: rainer
Detailed information about my Tic Tac Toe playing robotic arm is now available under the Robotics section.