If you are willing to allow the optimal-against-this-pool strategy to run the entire tournament as a subroutine, I think it can guarantee a tie by cloning the eventual winner.
It may be able to do better than that, but it depends on the details of the pool whether there are points “lying on the ground” to be picked up; I suspect there are with this pool, but I don’t have a great example.
How difficult would it be tell if a strategy was optimal against this pool?
One could try to improve by testing modifications of the winner, such as:
if OpponentDefectedBefore(7) then MyMove=D else if n>98 then MyMove=D else MyMove=OpponentLastMove unless OpponentMove=MyMove 1-99, in which case Turn(100)=cooperate
or
if OpponentDefectedBefore(7) then MyMove=D else if n>97 then MyMove=D else MyMove=OpponentLastMove unless OpponentMove=MyMove 1-98, in which case Turn(99)=cooperate, and if OpponentMove=MyMove 1-99, Turn(100)=cooperate.
If it tells you what to do, not just depending on what your opponent does, but on what you do, then testing 1-move modifications is sufficient to test optimality.
The statement of sufficiency I made is true for all complexities of opposing strategies.
The statement of insufficiency is not. If the opponent’s strategies are, for instance, linear, then it should be false. But some opposing strategies ARE very complex, so it’s presumably true.
How difficult would it be to code an optmal-against-this-pool strategy? How well would it do?
If you are willing to allow the optimal-against-this-pool strategy to run the entire tournament as a subroutine, I think it can guarantee a tie by cloning the eventual winner.
It may be able to do better than that, but it depends on the details of the pool whether there are points “lying on the ground” to be picked up; I suspect there are with this pool, but I don’t have a great example.
How difficult would it be tell if a strategy was optimal against this pool?
One could try to improve by testing modifications of the winner, such as:
if OpponentDefectedBefore(7) then MyMove=D else if n>98 then MyMove=D else MyMove=OpponentLastMove unless OpponentMove=MyMove 1-99, in which case Turn(100)=cooperate
or
if OpponentDefectedBefore(7) then MyMove=D else if n>97 then MyMove=D else MyMove=OpponentLastMove unless OpponentMove=MyMove 1-98, in which case Turn(99)=cooperate, and if OpponentMove=MyMove 1-99, Turn(100)=cooperate.
It depends on how big your strategy is.
If it tells you what to do, not just depending on what your opponent does, but on what you do, then testing 1-move modifications is sufficient to test optimality.
If not, then it isn’t.
Doesn’t an optimization question depend as much on the complexity of opposing strategies as it does on the complexity of my strategy?
The statement of sufficiency I made is true for all complexities of opposing strategies.
The statement of insufficiency is not. If the opponent’s strategies are, for instance, linear, then it should be false. But some opposing strategies ARE very complex, so it’s presumably true.