Compute maximum PRF advantage
So does that mean the advantage is: $1 - (2^{-3})$ ??


That would be the advantage if the attacker knew apriori that the key was 000; however in this model, the attacker knows that the key is one of the eight listed values, but doesn't know which one (and each of the eight possibilities are equiprobable).

So, if the attacker doesn't know what the key is, what strategy of inputs can the attacker use to get the optimal advantage?  Hint: if the attacker is restricted to a single query, what's the probability distribution of the output of the block cipher; how does that compare to the probability distribution of a truly random output?