Representación eficiente de la memoria de las posibilidades en el análisis de juegos

Question

Motivado por la pregunta reciente sobre la estrategia óptima en el juego de bolas de strike, quería indagar sobre cuáles son los enfoques pragmáticos que uno podría utilizar para resolver tales problemas en la práctica. Voy a intentar definir un problema generalizado

1. Hay un gran conjunto discreto de estados enumerados $S$ .
2. Hay un desconocido valor función $v: S \rightarrow Bool$ definido sobre los elementos de este conjunto, que es verdadero para un elemento y falso para todos los demás. Llamamos elemento "secreto" al elemento para el que la función es verdadera
3. Se sabe que hay un distancia función $d: S^2 \rightarrow \mathbb{N}^{0+}$ definido para un par de elementos. La distancia es un número entero positivo si los elementos son distintos, y cero si son iguales. Es simétrica con respecto al orden del par. En general, no satisface la desigualdad del triángulo. También se sabe que el conjunto $S$ posee cierto grado de simetría con respecto a $d$ . En un ejemplo de aplicación, los estados podrían ser puntos en un N-simplex de longitud lateral entera, y $d$ podría ser la distancia euclidiana.
4. Es posible pedir al juego la distancia entre el elemento secreto y cualquier otro elemento.
5. El objetivo del juego es determinar el elemento secreto en el menor número posible de preguntas. El número de cálculos mentales, incluido el cálculo de las distancias entre dos elementos conocidos, es esencialmente libre, lo único que cuenta es el número de preguntas sobre el elemento secreto que se hacen.

Estrategia que propongo:

1. Haz una copia $S'$ del conjunto anterior
2. Elige un elemento al azar $r_i\in S'$ del conjunto, pregunte por la distancia $d_i = d(r_i, x)$ al elemento secreto $x$
3. Encontrar todos los elementos $E = \{s \in S' : d(r_i, s) \neq d_i\}$ que no están a la distancia $d_i$ del elemento $r_i$ . Quítelos de $S'$
4. Repite 1-3 hasta que sólo quede un elemento en el conjunto

Problemas con mi estrategia:

1. Aunque siempre hace preguntas que aumentan el conocimiento, no aprovecha que algunas preguntas son potencialmente más útiles que otras.
2. Y lo que es más importante, requiere el almacenamiento y el bucle de todos los estados posibles, lo que puede ser inviable en aplicaciones reales

Pregunta(s) real(es) : ¿Cuáles son los posibles enfoques que uno puede intentar para resolver algorítmicamente tales problemas de una manera más realista en cuanto a la memoria? Si sólo almacenara una lista de preguntas y respuestas recibidas, así como una pequeña cantidad de variables auxiliares, ¿sería posible determinar eficientemente al menos un estado que no se pueda excluir que sea el estado secreto basándose en el conocimiento actual? ¿Existen enfoques aproximados que garanticen la convergencia, pero que no necesariamente hagan la cantidad óptima de preguntas, y que tengan poca memoria? Cualquier ejemplo o enlace a la literatura es bienvenido

Editar : Vuelvo a insistir en que la potencia de procesamiento del ordenador es irrelevante para mí. Hay dos objetivos: minimizar el número de preguntas formuladas y minimizar la cantidad de memoria utilizada para resolver el problema. Quiero una estrategia de compromiso

Answer 1

Sólo es necesario mantener en memoria un puñado de elementos mientras se enumera el espacio de estados.

Inicialmente su conjunto de pares memorizados $M$ está vacía. Al añadir un elemento $m$ a $M$ usted almacena $d(m, s)$ junto con ella (donde $s$ es el elemento secreto), costando una consulta.

Entonces, al enumerar $S$ para cada elemento $x$ se comprueba para cada elemento $m \in M$ si $d(m, s) = d(m, x)$ . Si $x = s$ esto debe ser cierto, si esto es falso sabemos $x$ no es el elemento secreto y puede descartarlo inmediatamente. Esto tampoco cuesta una consulta porque ya sabemos $d(m, s)$ y $d(m, x)$ es gratis.

Si $x$ pasa esta comprobación para cada $m \in M$ lo añades a $M$ como se ha dicho anteriormente, con la advertencia de que se puede parar si $d(x, s) = 0$ ya que has encontrado el elemento secreto.

Como ejercicio para el lector, convénzase de que el algoritmo anterior sólo almacena $k$ elementos en $M$ , donde $k$ son los grados de libertad de los elementos de $S$ tener. Por ejemplo, si $S$ es un subconjunto de $\mathbb{R}^2$ sólo almacenará dos elementos en $M$ .

Para visualizar esto, considere hacer una sola pregunta en el $\mathbb{R^2}$ escenario para algún punto $p$ . Ahora puedes dibujar un círculo con radio $d(p, s)$ y saber que $s$ debe estar en ese círculo. El círculo es una esfera para tres grados de libertad, una hiperesfera para cuatro, etc. Cada pregunta que haces reduce los grados de libertad en uno.

Lo que puede considerarse exactamente un grado de libertad depende de la métrica de la distancia.