An Internet-based Tic-Tac-Toe: Lesson 1

1 The Game Rules

Learning to program using a rich high-level programming language like Java is not a one day trip. You must have a great motivation to overcome all intellectual obstacles and frustrations and to reach a level of knowledge and experience to feel completely comfortable when creating code for a new computer application. To enjoy programming it's absolutely necessary to be motivated for the work you undertake. The motivation may be manifold, but most people need a practical context, also called Learning by examples. The examples should be fully-functional and correspond to the center of interest of the current computer community (computer users and developers). Gaming and Internet communication is currently a hype and a wonderful educational playground where all important programming concepts, from simple to advanced, can be trained, among them data structures, algorithms, graphics, multithreading, client-server architecture and event-driven programming. But this tutorial is not restricted to education, you will end up with a fully professional game application.

Our aim is to develop an Internet-based two-players game using a game server that handles player teams in multiple game rooms. To let us concentrate on important programming concepts and not on gaming details we choose a very simple but nevertheless famous game that many of us played with pencil and paper during boring lessons in elementary school: Tic-Tac-Toe. In the final version as many pairs of players may be in action at the same time, running on the same or different computers at any locations and with no firewall restrictions. Only normal browser-like HTTP access to the Internet is required. This is possible by using the TcpJLib library with a relay server that tunnels all data transmission to HTTP-requests/replies. By using the JGameGrid library, the creation of the graphics user interface including sophisticated mouse actions is a snap. The reduction of the code complexity when using these libraries compared to pure Java API programming is of several orders of magnitude, but the essential programming concepts remain visible (class construction, logic flow, data structures, event-handling, etc.).

First we remember the simple rules of Tic-Tac-Toe:

[Random House Dictionary]

2 The Quick-and-Dirty Solution

Looking at a bigger picture we see two programming thrills: Presenting/handling the game board (graphics/mouse events) and the communication (TCP/IP link) between the two players. In this first approach we solve the problem quick-and-dirty without bothering to follow clean OO design principles nor to obtain a code project that can be expanded for more general game scenarios. We attack the problem as if we were at a informatics competition miraculously equipped with a Java game and communication library: JGameGrid and TcpJlib. It's also like working for the game industry where advanced tools are used because there is no time to reinvent the wheel.

The application TicTacToeLight derives from GameGrid in order to have easy access to the rich bouquet of its methods. It implements a GGMouseListener and a TcpNodeListener because we want to get notifications for mouse and communication events. We want to support a multi-room environment where each player team is located in a distinct "game room" identified by a room name that is asked from the user when the application starts. It is like "knocking" at the door of the game room. If the room is empty, the person can enter and waits for a second person to come in. Then the game starts. The second person makes the first move by left clicking on an empty cell. An X-mark is shown on the board. The first person makes the second move. An O-mark is shown in both boards (and so on). Because in reality the players are at remote locations, each player "sees" an identical game board.

The fundamental notion in game theory is the game state. It is a description of the current game situation that is unambiguous and minimal in the sense that few or no information of the game state can be logically retrieved from other information (e.g. by applying the game rules).

A game can be considered as moving from one game state to another. In other words, it is a state machine (automata). Graphically we can represent the automata graph (or diagram) with vertexes that represent the game states and edges that represent the moves. Because the game develops from one state to another in timed steps the edges are oriented (represented by an arrow). Unless the game is very simple the number of possible game states (not violating the game rules) is tremendous. The transition from one game state to the next one may be the player's decision (like in Tic-Tac-Toe) or at random (like throwing a die).

For same games the game graph may degenerate to a tree (a graph with no cycles). This is the case for Tic-Tac-Toe as shown in the following figure:

The tree ends at vertexes that corresponds to a wining state or a full board (the game is a draw). It can be shown that each of the players may use a strategy to end in a draw.

When constructing multi-user computer games it is important to decide which game information should be kept local and which information must be exchanged. Here some practical recommendations for developing game applications that executes in parallel and communicates together:

• Exchange as few data as possible; exchange not the whole game state, but only what is updated
• Inhibit most application actions (disable mouse and keyboard actions except for quitting) while data is exchanged or the player waits for another player's move. Enable user actions only when you are sure that all incoming data is fully processed and the player has the next move
• Take into account that there is a certain time delay between data is sent until it arrives at the destination. This delay may vary between a few milliseconds to some 100 ms (or more in a network jam). Don't use fixed time delays, but send back a confirmation message if you must be sure the data arrived at the destination

In the following implementation the game board is a GameGrid instance with 3 x 3 cells. Each cell is either empty or contains an instance of the MarkX or MarkO class. No supplementary data structure is necessary to store the current game state because each cell can be requested by the getOneActorAt() method if it is empty or contains a X or O mark.

When a player draws his mark by clicking into the cell, in the mouseEvent callback addMark() creates a new Actor and adds it to the game grid. Then the location of the new Actor is transferred via TCP/IP to the teammate where the messageReceived() callback is triggered. The location is extracted and addMark() puts the new mark into the corresponding teammate's cell. In this way both game boards always reflects the same current game state and each player can check himself using isOver() if the game is finished because a horizontal, vertical or diagonal line is filled or all cells are occupied.

For this test, isOver() converts the game state into a comma separated string pattern. Horizontal, vertical and diagonal lines are scanned and 'O', 'X' or space characters inserted. Then the pattern is searched for a "OOO" or "XXX" substring. Because each player performs this check individually with the same game state, there is no need for exchanging information when the game is over.

Like in everyday life, some effort is needed to establish a contact with a person of the same interests. To bring players together, the name of a game room is requested when the player application starts. Three situations are possible:

1. The room name is not yet in use (the room is empty). The person enters and waits for a teammate
2. There is already another person waiting. The person enters and the game starts
3. The game room is occupied by two players (the game is in progress). The request is to enter is rejected

Fortunately the TcpRelay provides us automatically the necessary information of new TcpNodes that connects to the relay by executing notification callbacks. If the room name is used to define the session ID, the rooms are automatically separated. (We append the room name to a long random string to avoid conflicts with other sessions running at the same time.) Nodes in the same session are notified via the statusReceived() callback when other nodes enter or leave the session. By parsing the text parameter it is easy to distinguish the three situations. (To keep the program simple we do not detect when a player terminates his application nor do we support to redo a game in the same room.) Here comes the fully functional code:

Now you worked through the code, it's time to play a game.

Execute the program for each player on the same or different computers using WebStart.

(continued in Tutorial 2)