gave stronger hardness result
Source Link
user6973
user6973

By Theorem 3.1 and the proof's IPS being one-way, that problem
for all real numbers $\epsilon$, if ​ $0<\epsilon$ ​ then the promise problem

Input: ​ a game as described in my question
must output YES if : ​ ​ ​ the game's value for Player 1 is greater than 1-$\hspace{.025 in}\epsilon$
must output ​ NO ​ if : ​ ​ ​ the game's value for Player 1 is less than $\epsilon$

remains RE-hard even when

player_to_move is always 1 ​ (i.e., only 1 player is needed)
and
s0 ≠ sa ​ and ​ sa is not in Range(next_state_table)
(i.e., it's literally impossible for the player to lose)
and
p1_info and p2_info and number_of_choices are independent of the state
(i.e., the player's only feedback is whether or not it just won)

.

By Theorem 3.1 and the proof's IPS being one-way, that problem remains RE-hard even when

player_to_move is always 1 ​ (i.e., only 1 player is needed)
and
s0 ≠ sa ​ and ​ sa is not in Range(next_state_table)
(i.e., it's literally impossible for the player to lose)
and
p1_info and p2_info and number_of_choices are independent of the state
(i.e., the player's only feedback is whether or not it just won)

.

By Theorem 3.1 and the proof's IPS being one-way,
for all real numbers $\epsilon$, if ​ $0<\epsilon$ ​ then the promise problem

Input: ​ a game as described in my question
must output YES if : ​ ​ ​ the game's value for Player 1 is greater than 1-$\hspace{.025 in}\epsilon$
must output ​ NO ​ if : ​ ​ ​ the game's value for Player 1 is less than $\epsilon$

remains RE-hard even when

player_to_move is always 1 ​ (i.e., only 1 player is needed)
and
s0 ≠ sa ​ and ​ sa is not in Range(next_state_table)
(i.e., it's literally impossible for the player to lose)
and
p1_info and p2_info and number_of_choices are independent of the state
(i.e., the player's only feedback is whether or not it just won)

.

Source Link
user6973
user6973

By Theorem 3.1 and the proof's IPS being one-way, that problem remains RE-hard even when

player_to_move is always 1 ​ (i.e., only 1 player is needed)
and
s0 ≠ sa ​ and ​ sa is not in Range(next_state_table)
(i.e., it's literally impossible for the player to lose)
and
p1_info and p2_info and number_of_choices are independent of the state
(i.e., the player's only feedback is whether or not it just won)

.