Complexity of finite-state partial information games Given a deterministic partial-information zero-sum game with only finitely many states,
  
  whose possible outcomes are [lose,draw,win] with values [-1,0,+1] respectively,
  
  what is the complexity of approximating the value of such a game additively within $\epsilon$?


In particular, I can't come up any algorithm whatsoever for doing that.
The rest of this post is devoted entirely to giving a more thorough description

of the problem, so if you can already figure out what the question at the top

of this post means, then there's no reason for you to read the rest of this post.

Given a referee machine with states $\{1,2,3,...,S\}$, with a designated initial state $s_0$, a state $s_a$
whose score pair is $[-1,+1]$, a state $s_b$ whose score pair is $[+1,-1]$, and states of the form

$[\mbox{p1_info,p2_info,num_of_choices,player_to_move,next_state_table}]$ where:


$\mbox{player_to_move} \in \{1,2\}$
$\mbox{next_state_table}$ is a function from $\{1,2,3,...,\mbox{num_of_choices}\} \to \{1,2,3,...,S\}$
$\mbox{p1_info},\mbox{p2_info}, \mbox{num_of_choices} \geq 1$


When the machine is in a state of that form:


sends $\mbox{p1_info}$ to Player_1 and sends  $\mbox{p2_info}$ to Player_2,
sends $\mbox{num_of_choices}$ to the indicated player, waits for an element of $\{1,2,3,...,\mbox{num_of_choices}\}$
as input from that player,
then goes to the state indicated by $\mbox{next_state_table}$


When the machine enters one of the other two states $s_a$ or $s_b$,


halts with that state's score pair as its output


There is a natural two-player game: the referee machine is started in state $s_0 = 1$,

the players provide the inputs that the referee machine waits for, if the referee machine

halts then Player 1 scores the first value of the machine's output pair and Player 2

scores the second value of the machine's output pair, otherwise both players score 0.



  What is the complexity of the following problem?
  
  Given such a referee machine and a positive integer N, output a rational number
  
  that is (additively) within 1/N of the value of the natural game for Player 1.


As mentioned earlier in this question, I can't come

up with any algorithm whatsoever for doing that.
NOTE: my purported algorithm was incorrect; I deleted it. 

One thing to realize is that it doesn't matter whether the game is deterministic or not. To randomize, the referee can ask each of the players to contribute a random number mod $p$, and then add them. It's easy to show that if the players use their optimal strategy, the sum is a random number mod $p$, which the referee can then use to randomize his strategy. This doesn't greatly increase the number of states in the game. 

For a lower bound on the complexity, the question of approximating the value of a simple stochastic game is not known to be in P. Using the randomization trick I gave above, it is easy to write a simple stochastic game as a refereed game with a polynomial-size lookup table.