Project 2: Map that Set

Let N denote the set {1,...,n}, where n is a parameter. An adversary chooses a maping m from N to N, i.e., a function that for each integer i between 1 and n takes on some value m(i) from N. Your job is to identify m. Note that m is not required to be injective or surjective, i.e., two different members of N may map to the same value, and some values may not be the image of any arguments. We'll write m as an N-element tuple, where the value in position i is m(i). For example, here are two possible mappings when n=9.

• m₁ = (1,2,1,2,1,2,1,2,1)
• m₂ = (9,8,7,6,5,4,3,2,1)

You get to ask a series of questions that will be answered by the simulator. Each question specifies a subset S of N, and the answer to that question is the set of values that m takes for arguments in S. There is no ordering within answers, so you don't know which output corresponds to which input. So, if S={1,2,3}, then the answer would be {7,8,9} for the mapping m₂, and {1,2} for m₁.

Each guess can be based on the results of your earlier guesses. A simple strategy can guarantee success in n turns: simply specify each member of N as a singleton set. It shouldn't be difficult to see that better strategies are possible. For example, the five guesses {1,2,3},{4,5,6},{7,8,9},{1,4,7},{2,5,8} are sufficient to identify m₂. (Why? Can you do even better?) On the other hand, these five guesses aren't nearly as helpful for m₁, since each answer will be {1,2} which is relatively uninformative.

You will write two pieces of code. One will guess mappings as described above, trying to minimize the number of guesses needed. Another will play the adversary, choosing mappings that are likely to be hard to guess. Guessers and adversaries from different groups will be run against each other for a large number (hundreds) of games. While the identity of the opponent will be unknown, both guessers and adversaries can learn from the previous games in order to detect strengths and weaknesses in the opponent's strategy. Guessers and adversaries will be separately ranked based on their performance in a tournament at the end of the project.

Some things to think about:

• For sufficiently small n, it might be possible to exhaustively analyze the whole game. For how small an n is this likely to work?
• This game is like the game of Mastermind, in that there are repeated guesses with the aim of identifying a hidden pattern. Can strategies from Mastermind be adapted for this game?