Home Work 7: User Datagram Protocol |
Use Python, Java, VB, or other language to implement a simple TicTacToe game using datagrams. You are free to choose the interaction model for how you implement the game but the simplest is a peer-to-peer as only one program would need be written, each holding a copy of the game state, a more familiar programming paradigm.
The simpleChat model given in class is satisfactory for the TTT game in that it forces lock step synchronization between both chatters for the Python, Java and C++ versions by reading the keyboard input first, sending, then waiting to receive datagram input. In VB simpleChat the WinSock1_DataArrival subroutine is executed on the event of received datagram input and processes the input immediately by outputting to a text box. Datagram input can arrive at any time but for TTT the sequential nature of the game (each player taking turns) must be preserved. Be sure to address that problem in any language used rather than depending upon human cooperation to take turns.
The program requirements are:
Start - Write the TicTacToe game to play without any networking; after the program behavior is satisfactory, include network communications to pass the move of each player to the other using a datagram.
Taking turns - TicTacToe requires that one player start first but determining which player arbitrarily starts first using datagrams can be challenging. The simple approach is to have two different programs, simply designate one program to be the first player to send the first move while the other program expects to receive the first move. This approach requires two separate programs that implement the following:
First player X
|
Second player O
|
A more interesting approach is to implement a single program that determines which player should start first based on some criteria accessible to both players. One simple approach is for the host with the highest IP address to play 'X' and make the first move. Since a host knows its own and opponent's IP this is relatively easy when players are on different hosts. When both players are on the same host the port numbers will be different so the highest port number could determine which player starts first.
The following displays the IP and port number of the host sending a packet which can be used to decide who plays X or O. Note that since you know your machine's IP/port numbers and the other machine's IP/port numbers, this is not actually needed for the homework.
DatagramSocket ioSocket = new DatagramSocket(111);
byte receiveBuffer[] = new byte[128];
DatagramPacket receivePacket = new DatagramPacket(receiveBuffer, 128);
ioSocket.receive(receivePacket);
System.out.println(receivePacket.getAddress().getHostAddress());
System.out.println(receivePacket.getPort());
Waiting to start - Even the simplest of starting approaches must still
reconcile that both players must be ready (i.e. programs running) before either
can send a move. Consider the following scenario displaying the relative times
for each player:
Player X
|
Player O
|
Both players are waiting forever to receive a move because Player X first move was sent and lost before Player O program had started. The programs are deadlocked.
Obviously before the first move is sent both player programs must be running and player O waiting to receive moves. Because you are in control which program starts first, at least for this homework, you can start the proper program first.
Another solution is to synchronize the start of each program with the other by exchanging datagrams, each player must wait to receive a datagram from the other before the game starts. Note that the datagram sent by the first program started running will likely be lost and a second, third, fourth, ... may need to be sent. Because any datagram may be lost, in general it is impossible to guarantee that the players are synchronized. This is called the two-army problem, see the text. The best we can do is make a synchronization method that is reliable enough.
Normally reliable communication requires sending datagrams, wait for reply or timeout and resend. One synchronization approach that works reasonably well without timeouts is to number the datagram so that each side knows whether it started first or second. In the following, it is assumed that datagrams are not lost, only that any player program may start running first and that X moves first. Each player must receive a synchronization datagram before sending a move. To distinguish the synchronization datagrams below each will be numbered either 1 or 2. The basic approach is that the first program started will send a datagram 1 which is lost without the other player running. Each player must receive either datagram 1 or 2 to proceed. If a datagram 1 is received the player knows that it started first and needs to send a synchronization datagram numbered 2. If a datagram 2 is received, the player knows that it started second, the first player received the datagram 1 and is synchronized.
In the following scenario player X starts first and sends datagram X 1 which
is lost. Player O sends datagram O 1 and waits for a datagram. Player X receives
O 1, sends X 2, and sends X move. Player O receives X 2 and waits for the X
move. If the first datagram a player receives is 1 then the other player started
last and should be sent a 2 since the first datagram was lost. If the first
datagram a player receives is 2 then the other player has already received
datagram 1 and no more datagrams need be sent. The synchronized game start would
then be:
Player X
|
Player O
|
Note - The above approach has a flaw in that it expects one or the other player to start first and packet 1 to be lost. What happens if both start at the same time and both receive a packet 1? Both would send packet 2 but neither would be expecting another synchronization packet, instead expecting to receive a move packet. One inelegant solution is to check and discard packet 2 when a move is expected.
Document last modified: