INTERNET-DRAFT CS 4385 t3pospec.txt May 1999 Expires: Jun 1999 TIC-TAC-TOE PROTOCOL (T3PO) Version 1 -- Protocol Specification Table of Contents 1. Introduction............................................. 1 2. Description.............................................. 2 3. Packet Format............................................ 3 4. Game Behavior............................................ 8 4.1 Normal Game Behavior................................. 8 4.1.1 Startup.........................................8 4.1.2 Play............................................9 4.1.3 Termination.....................................9 4.2 Behavior Under Error Conditions.......................9 4.3 State Diagrams.......................................10 5. Glossary.................................................12 6. References...............................................12 7. Acknowledgements.........................................13 1. Introduction This document describes the tic-tac-toe protocol (T3PO), an application-level protocol implementing a simple, reliable service on top of UDP to play the game of tic-tac-toe. The formats of the UDP messages exchanged by T3PO peers and the procedures for sending and receiving those messages are described in some detail. The interface between the T3PO protocol level and higher levels is left unspecified. In order to establish communication between the two parties, one will act as a server listening to a well-known port. The other party will act as a client, sending a request to begin a game to the server at the well-known port. The server will then reply to the client, indicating a new port at which the game can be played. The server will then relinquish the well-known port and play the game at the new port. [page 1] CS4385 TIC-TAC-TOE PROTOCOL May 1999 2. Description Tic-tac-toe is a popular game that is very simple to play. Usually, it is played on a piece of paper with two players in close proximity. A grid with nine spaces is drawn similar to the one below: | | | | | | | | ------|-----|------ | | | | | | ------|-----|------ | | | | | | | | Players then decide who gets to go first and which symbol they prefer to use as their marker (i.e. an X or an O). Players then alternate turns placing their mark in an available space. The goal of the game is to place three marks all in one row, one column, or on a diagonal. It is possible for the game to end in a draw; this condition arises when all spaces are filled and neither player has achieved the game goal. Below are two sample boards. The first board demonstrates a win and the second demonstrates a draw. | | | | X | | | | ------|-----|------ | | O | X | | | ------|-----|------ | | O | | X | | | | A win [page 2] CS4385 TIC-TAC-TOE PROTOCOL May 1999 | | | | X | X | O | | ------|-----|------ | | O | O | X | | ------|-----|------ | | X | O | X | | | | A Draw The purpose of the T3PO protocol is to allow two people to play the game of tic-tac-toe from two computers, possibly located far apart, by passing messages using the User Datagram Protocol (UDP). 3. Packet Format Table 1 shows the T3PO message format. All messages have the same fixed-length 64-bit format. Each T3PO message is transmitted as a single UDP datagram. Multi-byte message fields are transmitted in network byte-order, i.e. big-endian byte-ordering. All messages are listed in Table 2. Table 1: T3PO Message Fields Field Name Bits Notes ---------------------------------------------------------------------------- Version 2 Defined as binary 01 for this version Error/Message bit 1 0 = Message / 1 = Error Type 4 Code for message type or error type. Reserved 7 Available for future options Board State 18 Bit string that represents state of game board. (See below for details) Game Identifier 16 Uniquely identifies the game session Checksum 16 Computed value to check for errors [page 3] CS4385 TIC-TAC-TOE PROTOCOL May 1999 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Ver|E| Type | Reserved | Board State/Port | |0 1|M| | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Game ID | Checksum | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Version - Field to indicate the version of the protocol. This field is fixed at 01. Error/Message bit - This bit is a flag to determine how the Type field should be interpreted. Type - This 4-bit field is used to transmit error and message codes. Table 2 lists the message types, Table 3 lists the error types, and Table 4 assigns numeric values to the codes. Table 2: T3PO Messages Message Message Type Abbrev Sender ----------------------------------------------------- Play Request Play Client Play Acknowledgment AckP Server/Client Play Rejection RejP Server Move Notification Move Client/Server Move Reject RejM Client/Server End of Game EndG Client/Server Quit Quit Client/Server - Play Request (Play) message - This message is sent by the client to the server as a request to initiate a game. - Play Acknowledgment (AckP) message - This message is sent by the server to the client to indicate the game request was accepted. It indicates the port the server will use for game play; the server's game play port and the client's port together are used to determine who goes first (see Section 4.1). If the server is to make the first move, it must not make it until it knows that the client is ready to receive at the new port. Therefore, the client must echo the AckP message to the server at the new port. For simplicity, the client echoes the AckP message no matter which side is chosen to go first. After the client sends the AckP, the client will be in the Play phase. After the server receives the AckP, server will be in the Play phase. (See Section 4.2.) [page 4] CS4385 TIC-TAC-TOE PROTOCOL May 1999 - Play Rejection (RejP) message - This message is sent by the server to a client indicate that another game is currently in progress. - Move (Move) message - This message can be sent by either player to inform the opponent of the move that was made. The Board State field of the packet is used to transmit the move information. Upon sending the Move message which results in normal termination of the game (Win or Draw), the player will wait for the EndG confirmation message. - Move Reject (RejM) message - This message can be sent by either the client or the server to notify the opponent of a disagreement with their most recent move. This disagreement can stem from the opponent submitting a Board State that is not in agreement with the game state that would be possible from the previous move submission. Examples include, but are not limited to, attempting to occupying a space that was already taken, or attempting to occupy multiple spaces on one move. Upon sending or receiving the RejM message, the game will be aborted. - Game End (EndG) message - This message must be sent by either the client or the server when it has received the last move, in order to confirm the ending of the game. The Board State field confirms the final move information. Upon sending the final Move message, a player waits for the EndG message. Upon sending or receiving the EndG message, a player will neither send nor expect to receive any further messages from the opponent. - Quit Request (Quit) message - This message can be sent by either the client or the server to terminate the game prematurely. Upon sending or receiving the Quit message, a player will neither send nor expect to receive any further messages from the opponent. [page 5] CS4385 TIC-TAC-TOE PROTOCOL May 1999 Table 3 : T3PO Error Codes Error Notes ------------------------------------------------------------------------ Internal Error The protocol or tic-tac-toe program experienced an internal error and is unable to process the packet Version Error Packet received used the wrong protocol version number Unknown message type Packet received used an unknown message type Invalid Game ID Packet referenced an invalid Game ID Invalid Checksum Packet referenced an invalid checksum value Unknown Error Any error not specified above The following table assigns numbers for use in the message/error type field of the packet. Table 4 : T3PO Defined Numbers MESSAGES ======== Name Value ----------------------------------------------------- Play Request (Play) 1 Play Acknowledgment (AckP) 2 Play Rejection (RejP) 3 Move (Move) 4 Move Reject (RejM) 5 End of Game (EndG) 6 Quit Request (Quit) 10 ERRORS ====== Name Value ----------------------------------------------------- Internal Error 0 Version Error 1 Unknown message type 2 Invalid Game ID 3 Invalid Checksum 4 Unknown Error 15 [page 6] CS4385 TIC-TAC-TOE PROTOCOL May 1999 Reserved - Reserved for future use. Must always be set to all zeroes. Board State/Port - This field is used in an AckP message to indicate the port at which the server is listening in order to begin the game. The field is used in a Move message to transmit the state of the board. Board positions shall be viewed on a 3x3 grid according to the conventions shown in Figure 1. | | | | 1 | 2 | 3 | | ------|-----|------ | | 4 | 5 | 6 | | ------|-----|------ | | 7 | 8 | 9 | | | | Figure 1 Player numbers are assigned once a determination has been made as to who makes the first move. By convention, the player who makes the first move will be called Player 1. The player who makes the second move shall be referred to as Player 2. Each position can take on 3 different values: 0 - Unoccupied (bit pattern 00) 1 - Occupied by Player 1 (bit pattern 01) 2 - Occupied by Player 2 (bit pattern 10) It should be noted that a bit pattern of 11 for a position is not allowed. The board state is placed in the Board State field according to the convention specified below. The state at the beginning of a game before any moves are made would have the following bit pattern: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Ver|E|msg/err| Reserved |W| Board State | |0 1|M| type | | |0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Board Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | If Player 1 decides to take the center space for the first move, then the Board State field would contain the following bit pattern: [page 7] CS4385 TIC-TAC-TOE PROTOCOL May 1999 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Ver|E|msg/err| Reserved |W| Board State | |0 1|M| type | | |0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Board Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Game ID - This field is used to uniquely identify a session. The client will fill this field as part of the original Play Request message. It is used to ensure that a game in progress is not disrupted by a third player. Every message sent by either player during the course of a game must carry this number. Checksum - This field is used to detect transmission errors. The checksum is the bitwise exclusive-or over all four 16-bit words of the message. Before sending a message, the sender sets the value of the Checksum field to be CSUMRESULT, defined as 0xdeaf. Next, the sender computes the bitwise exclusive-or over the series of four 16-bit words. Finally, the sender writes the result of the exclusive-or in the Checksum field of the message, overwriting CSUMRESULT. Upon receipt of the message, the receiver computes the bitwise exclusive-or of the four words of the message. If no errors have occured, the result will be CSUMRESULT. 4. Game Behavior There are three major phases involved in playing the game. The first is the Startup phase, in which the game play is established between the two parties playing and the server determines who makes the first move. During the second phase the Play phase, the players take turns sending moves. The last phase, Termination, occurs when the game is over. Since the game is being played using UDP, there is no connection to teardown. 4.1 Normal Game Behavior 4.1.1 Startup The initial behavior of the client and server is to communicate that they are willing and able to play the game. This is accomplished using a three-way handshake (similar to that of TCP). The steps for normal operation are as follows: a. client sends Play Request message (Play) to server b. server sends port number on which the game will be played to the client (AckP) c. client echoes the AckP message to the new port The client port number and the server game port number are used to determine who goes first. If the sum of the two port numbers is odd, then the client will move first. If the two port numbers is even, then the server will go first. [page 8] CS4385 TIC-TAC-TOE PROTOCOL May 1999 4.1.2 Play Once the Startup phase has been successfully completed, play may begin. This involves the players alternating sending moves to the opponent until the game ends. The steps for game playing are: a. a player sends Move message (Move) to the opponent b. upon receipt of a Move message, if the move is valid, the player responds with a Move message (Move) if the move is not valid, the player sends a Move Reject message (RejM) to the opponent and aborts the game. 4.1.3 Termination Eventually, game play will end. Possible reasons for this are: a player no longer responds, a player sends a Quit message, or the game has terminated normally. The two normal conditions under which the game will end are one player winning the game or a draw occurring. Normal termination is implemented as follows: a. the player making the final move sends the Move message b. the opponent sends an EndG message with the final board state 4.2 Behavior Under Error Conditions A 30 second limit will be placed on the total "think time" plus transmission time for each player. To reduce implementation complexity, the method of handling reliability is asymmetric: the server will set a timeout equal to the think time. When the server side is in a state in which it expects to receive a response from the client, it sets the timer. If the timer expires, the server will retry its last message. The server will send the message a total of three times. If the timer expires three times with no response from the client, the server will abort the game. Note that this reliability method requires that the client be able to recognize duplicate packets (and respond by resending the last packet). Because the protocol does not include a sequence number, duplicates are recognized by comparing the current packet with the last packet received. The client will implement a 2-minute timer. It sets a timer for 2 minutes when it is in a state in which it is expecting a message from the server. If the timer expires, then the client will abort the game. [page 9] CS4385 TIC-TAC-TOE PROTOCOL May 1999 4.3 State Diagrams Client State Diagram (Error-Free Operation) +----------+ +----------+ | | no event | | | Start/ |---------->| Waiting | | Idle |(send Play)| for AckP | | | | | +----------+ +----------+ | | recv AckP/client is first| |recv AckP/server is first (send AckP)| |(send AckP) +-------------+ +---+ | | V V +----------+ recv Move +----------+ | |<-----------| Waiting | | Thinking | | for srvr | | |----------->| message | | | (send Move)| | +----------+ +----------+ | | | | |(send last Move) | | | | recv Quit| | |recv Quit/ | | |recv last Move | V |(send EndG) | +----------+ | | | Waiting | | | | for EndG |--+ | | | | |recv EndG | | +----------+ | | | V | | +----------+ | | | | | +-------->|Game Over |<-------+ | Exit | | | +----------+ [page 10] CS4385 TIC-TAC-TOE PROTOCOL May 1999 Server State Diagram (Error-Free Operation) +----------+ +----------+ | | recv Play | | | Start/ |---------->| Waiting | | Listening|(send AckP)| for AckP | | | | echo | +----------+ +----------+ | | recv AckP/server is first| |recv AckP/client is first | | +-------------+ +---+ | | V V +----------+ recv Move +-----------+ | |<-----------| Waiting | | Thinking | | for client| | |----------->| message | | | (send Move)| | +----------+ +-----------+ | | | | |(send last Move) | | | | recv Quit| | |recv Quit/ | | |recv last Move | V |(send EndG) | +----------+ | | | Waiting | | | | for EndG |--+ | | | | |recv EndG | | +----------+ | | | V | | +----------+ | | | | | +-------->|Game Over |<-------+ | Exit | | | +----------+ [page 11] CS4385 TIC-TAC-TOE PROTOCOL May 1999 5. Glossary client: An application program that requests game establishment. server: An application program that establishes a new game upon request from a client. player: Refers to either the client or the server; used when the role is unimportant in the context being described. 6. References [1] G. Scott, "Guide for Internet Standards Writers", RFC 2360 [2] J. Postel, "User Datagram Protocol", RFC 768 7. Acknowledgements The starting point for this specification was the draft submitted by Donia Robinson, Scott McFarland and Ken Kladitis. The main modifications were (1) change to the "who goes first" algorithm, (2) simplification of the message exchange, (3) change in algorithm to detect a packet loss. [page 12]