Computationally bounded version of Nash equilibrium?

Question

I'm wondering if there is a computationally bounded version of the Nash equilibrium concept, something along the following lines.

Imagine some kind of two-player perfect information game which is played on an $n\times n$ board, and which is complex in the sense that optimal play is EXPTIME-hard. Suppose also for simplicity that draws are not possible. Imagine a pair $(A, B)$ of randomized polynomial-time Turing machines playing this game against each other. For each $n$, let $p_{A,B}(n)$ be the probability that $A$ beats $B$ at the order-$n$ game. (For concreteness, let's say that $A$ gets to play first with probability 0.5.) What I think would be cool is if one could prove the existence of a pair $(A,B)$ with the property that no randomized polynomial-time Turing machine $A'$ dominates $A$ (where "$A'$ dominates $A$" means $p_{A',B}(n) > p_{A,B}(n)$ for all sufficiently large $n$), and similarly no randomized polynomial-time Turing machine $B'$ dominates $B$ (where "$B'$ dominates $B$" means $p_{A,B'}(n) < p_{A,B}(n)$ for all sufficiently large $n$).

Somehow, I suspect that this is too much to hope for, but is there any hope for something like this to be true, perhaps for a restricted class of games?

One motivation for this question is that I am looking for a way to formalize the notion that a given chess position is "advantageous for White." Classically, a position is either a win for White or it isn't. However, chess players, both human and computer, have an intuitive understanding of what it means for White to have an advantage. It seems to have something to do with the probability that White will win, given that the players are computationally bounded and have to guess at the best move. For a specific pair of randomized algorithms one can of course talk about the probability that White will win, but what I'm wondering is if there can be, in some sense, a canonical pair of computationally bounded players whose winning probabilities yield a value for the position that depends only on the game itself and not the idiosyncrasies of the players.

Answer 1

I can't think of any way there could be an easy, completely elegant/satisfying answer to this question, particularly because the ending payoff is so hard to compute; however, my thoughts are too lengthy to post as a comment.

The best idea I have is this: In the case of chess, try approximating the probability that White will win based on White's material advantage (i.e., extra pawns, knights, etc.) for a given position by randomly selecting positions with that exact amount-of-material configuration. Perhaps in the case of "all-rooks chess," we could say, "How likely is White to win with 8 rooks to Black's 17 rooks?" Perhaps this probability is 4%; to calculate it, we would have to examine (say) 1000 different randomly generated chess positions that have 8 white rooks and 17 black rooks, and then look ahead (say) 10 moves deep in every case, and see what the new material configuration is. Then, take the expected odds based on the material configuration at the end, and force each side to select the path that involves each side taking the best possible option at every turn, given the expected odds at the end.

Of course, it would be necessary to find the material configuration for every relevant possibility (M,N) of M white rooks to N black rooks...presumably starting at the lowest ordered pair (M=1,N=1) and working up from there.

For the original position, don't just go with the statistic you get (i.e., if the original position has (M=6,N=7) rooks, don't just assume that White has a 25% chance of winning because that's the expected odds of victory for (6,7)); instead, because you can be more precise, look 10 moves deep as usual with just this one position and find every possible ending position. Then, find the right path (that involves optimal play by both sides) to a 10-moves-deep-configuration, and select this path's expected odds as the expected odds of the original position.

I think this process can be done in polynomial time. Looking k moves deep for fixed k in chess is polynomial in the size of the board, and the total number of white and black rooks is expressed in unary (in a sense) because that number must be smaller than the size of the board.

If this sounds complicated and hard to explain, that's because it is. A more succinct summary of what I'm describing is: Use recursion and basic statistics to calculate the odds of victory for white given M white rooks and N black rooks on the board. Then use these values to look k moves deep and ascertain the odds that White will win in the original position.

Final comment: I think this problem is also interesting for non-EXPTIME-complete games, such as tic-tac-toe, which according to Wikipedia is PSPACE-complete. Further, I believe a process like the one I described above could also be useful there too, although obviously it would be impossible to have a "material" advantage in tic-tac-toe; there would have to be some other basis for judging the superiority of X's or O's position.