¿Versión computacionalmente limitada del equilibrio de Nash?

Me pregunto si hay una versión computacionalmente limitada del concepto de equilibrio de Nash, algo en las siguientes líneas.

Imagine algún tipo de juego de información perfecta para dos jugadores que se juega en un tablero , y que es complejo en el sentido de que el juego óptimo es EXPTIME. Supongamos también por simplicidad que los sorteos no son posibles. Imagina un par ( A , B ) de máquinas de Turing de tiempo polinómico aleatorias jugando este juego uno contra el otro. Para cada n , sea p A , B ( n ) la probabilidad de que A venza a B en el juego de orden n . (Para concreción, digamos que $n\times n$$(A, B)$$n$$p_{A,B}(n)$$A$$B$$n$$A$juega primero con probabilidad 0.5.) Lo que creo que sería genial es si uno pudiera demostrar la existencia de un par con la propiedad de que ninguna máquina de Turing de tiempo polinomial aleatorio A ' domina A (donde " A " domina A "significa p A ′ , B ( n ) > p A , B ( n ) para todos lo suficientemente grandes n ), y de manera similar no hay una máquina de Turing de tiempo polinomial aleatorizado B $(A,B)$$A'$ $A$$A'$$A$$p_{A',B}(n) > p_{A,B}(n)$$n$$B'$domina (donde " B ′ domina B " significa p A , B ′ ( n ) < p A , B ( n ) para todo lo suficientemente grande n ).$B$$B'$$B$$p_{A,B'}(n) < p_{A,B}(n)$$n$

De alguna manera, sospecho que es demasiado esperar, pero ¿hay alguna esperanza de que algo así sea cierto, tal vez para una clase restringida de juegos?

Una motivación para esta pregunta es que estoy buscando una manera de formalizar la noción de que una posición de ajedrez dada es "ventajosa para las blancas". Clásicamente, una posición es una victoria para las blancas o no lo es. Sin embargo, los jugadores de ajedrez, tanto humanos como informáticos, tienen una comprensión intuitiva de lo que significa que las blancas tengan una ventaja. Parece tener algo que ver con la probabilidad de que las blancas ganen, dado que los jugadores tienen límites computacionales y tienen que adivinar el mejor movimiento. Por supuesto, para un par específico de algoritmos aleatorios se puede hablar sobre la probabilidad de que las blancas ganen, pero lo que me pregunto es si puede haber, en algún sentido, canónico pareja de jugadores acotados computacionalmente cuyas probabilidades de ganar producen un valor para la posición que depende solo del juego en sí y no de la idiosincrasia de los jugadores.

No puedo pensar de ninguna manera que pueda haber una respuesta fácil, completamente elegante / satisfactoria a esta pregunta, particularmente porque el resultado final es muy difícil de calcular; Sin embargo, mis pensamientos son demasiado largos para publicar como comentario.

La mejor idea que tengo es esta: en el caso del ajedrez, intente aproximar la probabilidad de que las blancas ganen en función de la ventaja material de las blancas (es decir, peones adicionales, caballeros, etc.) para una posición dada seleccionando al azar posiciones con esa cantidad exacta -de-material de configuración. Quizás en el caso del "ajedrez de todas las torres", podríamos decir: "¿Qué posibilidades hay de que las blancas ganen con 8 torres contra las 17 torres de las negras?" Quizás esta probabilidad es del 4%; para calcularlo, tendríamos que examinar (por ejemplo) 1000 posiciones de ajedrez generadas aleatoriamente diferentes que tienen 8 torres blancas y 17 torres negras, y luego mirar hacia adelante (por ejemplo) 10 movimientos profundos en cada caso, y ver cuál es la nueva configuración de material . Luego, tome las probabilidades esperadas en función de la configuración del material al final,

Por supuesto, sería necesario encontrar la configuración del material para cada posibilidad relevante ( M , N ) de M torres blancas a N torres negras ... presumiblemente comenzando en el par ordenado más bajo ( M = 1, N = 1) y trabajando a partir de ahí.

Para la posición original, no solo vaya con la estadística que obtiene (es decir, si la posición original tiene torres ( M = 6, N = 7), no asuma que las blancas tienen un 25% de posibilidades de ganar porque eso es las probabilidades esperadas de victoria para (6,7)); en cambio, como puedes ser más preciso, mira 10 movimientos profundos como de costumbre con solo esta posición y encuentra todas las posiciones finales posibles. Luego, encuentre el camino correcto (que implique un juego óptimo por ambos lados) a una configuración de 10 movimientos profundos, y seleccione las probabilidades esperadas de esta ruta como las probabilidades esperadas de la posición original.

Creo que este proceso se puede hacer en tiempo polinómico. Mirar k se mueve profundamente para k fijo en el ajedrez es polinomial en el tamaño del tablero, y el número total de torres blancas y negras se expresa en unario (en cierto sentido) porque ese número debe ser menor que el tamaño del tablero.

Si esto suena complicado y difícil de explicar, es porque lo es. Un resumen más conciso de lo que estoy describiendo es: Use la recursividad y las estadísticas básicas para calcular las probabilidades de victoria para las blancas M en las torres blancas y las N torres negras en el tablero. A continuación, utilizar estos valores para mirar k se mueve profundamente y determinar las probabilidades de que White va a ganar en la posición original.

Comentario final: creo que este problema también es interesante para juegos que no son EXPTIME-complete, como el tic-tac-toe, que según Wikipedia es PSPACE-complete. Además, creo que un proceso como el que describí anteriormente también podría ser útil allí, aunque obviamente sería imposible tener una ventaja "material" en tic-tac-toe; Tendría que haber alguna otra base para juzgar la superioridad de la posición de X u O.