Internet
|
Adversarial programs must by nature communicate some shared state such as a chess board or moves to a new state. Obviously, the problem is more interesting and realistic if the opponent is unknown to some degree possibly located at a distance such as over the Internet.
Python has rich support for Internet programming; our interest is in UDP and TCP for communicating between two adversaries or agents.
In turn-taking games such as tic-tac-toe or chess, one program is usually designated as making the first move while the other program awaits a response.
TCP requires that one program open a port and await a connection (server) and the other open a connection (client) creating an asymmetry between the client/server programs. After a connection is established, messages can pass in either direction.
Server - Starts first and waits for a client. Otherwise, no different from client.
Client - Starts after server.
UDP does not require an open port on the receiving end before a message can be sent. Programs can be symmetric, that is identical, the key requirement is that they can negotiate which program starts first.
Client/server model can also be used with UDP, one program is designated to wait for the other to make the first move. While simplifying program logic, two different programs are needed.
Simpler to use than TCP but does not ensure reliable delivery of data. Not a real concern for our applications.
Below is a simple client/server.
- server=socket(AF_INET, SOCK_DGRAM)
server.bind(('localhost',8888))The server starts and binds port 8888 for communication.
- data, address = server.recvfrom(1024)
The server waits for a message on port 8888.
- client=socket(AF_INET, SOCK_DGRAM)
client.sendto('Hello', ('localhost',8888))
The client starts and sends 'Hello' to the localhost on port 8888. localhost is the local machine.
- print data, ' ', address
server.sendto('Hi', address)
server.close()The server receives and prints 'Hello' and sends 'Hi' to client then closes.
- data, address = client.recvfrom(1024)
print data, ' ', address
client.close()The client receives and prints 'Hi' and closes.
| Server | Client |
| from socket import * server=socket(AF_INET, SOCK_DGRAM) server.bind(('localhost',8888)) data, address = server.recvfrom(1024) print data, ' ', address server.sendto('Hi', address) server.close() |
from socket import * client=socket(AF_INET, SOCK_DGRAM) client.sendto('Hello', ('localhost',8888)) data, address = client.recvfrom(1024) print data, ' ', address client.close() |
Tic-Tac-Toe
Recall that MINIMAX(state) returns the action yielding the maximum value from that state. Below is a function in which the computer is MAX and a human plays MIN. Interaction is through a keyboard and screen.
| Minimax Tic-Tac-Toe MAX=Computer MIN=human |
| def run() : board=[0,1,2,3,4,5,6,7,8] while not win(board) and not tie(board) : board[MINIMAX_DECISION(board)]='X' # Computer if not win(board) and not tie(board) : display(board) board[input('Your move? ')]='O' # Human display(board) |
Changes to our Tic-Tac-Toe to compete computer against another computer are minor, restricted to replacing human play with that of a machine. Note that MAX plays X and MIN plays O, MAX remains the same, maximizes X and minimizing O. MIN attempts to maximize O and minimize X through the UTILITY function assignment of +1 for O wins and -1 for X wins.
MIN must be started first since it waits for MAX's move. Once started each plays in its turn, receiving and sending the board state from and to the other until either a win or tie occurs.
Change localhost to a Internet host address (e.g. www.csci.ius.edu) in MAX to play against a different opponent.
OR
Note that MIN does not maintain any state, any board positions can be sent that have successor states. Sending a board without successor states will cause failure since it that violates a requirement and MIN does not check whether the state is terminal (a win or tie) before generating successor states.
| MAX (client) | MIN (server) |
| from socket import * import pickle def run() : s=socket(AF_INET, SOCK_DGRAM) board=[0,1,2,3,4,5,6,7,8] display(board) while not win(board) and not tie(board) : board[ALPHA_BETA_SEARCH(board)]='X' if not win(board) and not tie(board) : display(board) s.sendto(pickle.dumps(board), ('localhost',888)) data, address = s.recvfrom(1024) board = pickle.loads(data) display(board) s.close() |
from socket import * import pickle def run() : s=socket(AF_INET, SOCK_DGRAM) s.bind(('localhost',888)) while True : data, address = s.recvfrom(500) board = pickle.loads(data) board[ALPHA_BETA_SEARCH(board)] ='O' s.sendto(pickle.dumps(board), address) s.close() |
pickling
The sendto and recvfrom UDP functions only handle strings not lists, etc. The game board list is passed between the two opponents so it is necessary to convert between a string for communication and a list for internal processing.
The pickle module is used for converting between a list and string:
- list to string - pickle.dumps( [0,1,2,3,4,5,6,7,8]) converts the list to a string '(lp0\nI0\naI1\naI2\naI3\naI4\naI5\naI6\naI7\naI8\na.' (though not very readable to humans).
- string to list - pickle.loads('(lp0\nI0\naI1\naI2\naI3\naI4\naI5\naI6\naI7\naI8\na.') converts the string to a list [0,1,2,3,4,5,6,7,8] (though not very readable to humans).
Errors
error: (10054, 'Connection reset by peer') - Connecting to the machine failed most likely due to a bad address, no receiving program was bound to the socket or your fire-wall software won't allow Python access to the Internet.