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 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.