Cómo resolver 8 × 8 Othello

Answer 1

Un descargo de responsabilidad rápido :
Soy más un tipo de teoría de juegos de comportamiento, pero está bien, lo intentaré, pero probablemente ya conozcas las cosas que mencionaré, por lo que esta respuesta puede ser más para otros que el OP.

Aaaand, un poco de historia …
Un juego versus se considera “resuelto” si el resultado puede predecirse, desde cualquier posición, cuando los jugadores juegan perfectamente.

Las soluciones se consideran “ultra-débiles”, “débiles” o “fuertes” si involucran solo una política / estrategia que tiende a ganar o un algoritmo que siempre gana o empata o uno que produce un juego perfecto en todos los casos.

Algunos juegos resueltos incluyen damas, tic-tac-toe y connect 4.
Los juegos parcialmente resueltos incluyen ajedrez, go y reversi. Para aquellos, la investigación continúa.

Es importante tener en cuenta que generalmente podemos resolver juegos de mesa de 5 × 5. En algunos casos podemos resolver juegos de 7 × 7, pero 8 × 8 está empujando los límites de nuestras habilidades actuales.
Los borradores de estilo inglés, por ejemplo, se resolvieron en 4 × 4 o 5 × 5 hace algún tiempo, pero 8 × 8 solo se resolvió débilmente en 2007.

Para darle escala a este concepto, la resolución de los correctores demoró más de 50 computadoras en 18 años.

OTELO
De manera general, Othello se resuelve al crear árboles de juego de todas las “capas” disponibles y buscar a través de ellas para encontrar todos los conjuntos ganadores de jugadas perfectas desde la posición actual. Eso lleva algo de tiempo. Si eres un académico y realmente quieres resolver Othello 8 × 8, así es como se hace.

Si, en cambio, quisiera hacer una máquina de Othello que funcionara con monedas para barras y arcadas, podríamos renunciar a un poco de perfección para hacer que la máquina sea lo suficientemente rápida como para no hacer que la gente se duerma o parezca rota.
Una forma de acelerar las cosas es el uso de un algoritmo ‘negamax’. Es similar al concepto de minimax, pero está optimizado para 2 jugadores, en comparación con los juegos.

Toda una familia de motores de búsqueda adversos han surgido de esta idea.

Luego viene la poda, lo que significa que podemos eliminar de forma segura algunos árboles porque probablemente no producirán resultados ganadores, desde esta posición. La poda de Alphabeta es una opción popular donde descartamos cualquier opción menos buena que la actual. Ahora, combine esos 2 y obtendrá algo como Negascout: para buscar y podar aún más rápido.

A continuación, podemos considerar algunos patrones, como las diferencias en los cuadrados en el centro del tablero, en comparación con el borde o en una esquina. El número de movimientos posibles es obviamente diferente en esos casos literales, de borde.

Estas son realmente las pocas herramientas. Es sobre todo un trabajo duro: rastrear desde 10 hasta la 28a lista de poder de posibles movimientos legales.

Es probable que 8 × 8 Otherllo sea resuelto pronto por personas mucho más inteligentes que yo y probablemente principalmente por la fuerza bruta. Se resolvió 6 × 6 después de examinar unos 3,5 billones de movimientos (favorece ligeramente al jugador uno). Lo extraño es que 10 × 10, que tiene un número astronómico de posibles movimientos, ya muestra una tendencia a favorecer un empate, debido a la longitud y la mayor oportunidad de recuperación del juego imperfecto. Entonces, 8 × 8 puede ser la versión más grande con una solución establecida.

Answer 2

(originalmente un comentario sobre la respuesta de Al).

En cuanto a las funciones de búsqueda / evaluación de juegos de mesa, no estoy contento con podar el árbol de juegos de Othello. Pero, para hacer posible un enfoque de fuerza bruta, en mi opinión, necesitamos una aceleración de órdenes de magnitud en el procesamiento del árbol del juego. Entonces, ¿qué debe hacer un hombre? He estado pensando en este sentido: ¿cómo podemos transformar a Othello en un sistema diferente y posiblemente más simple, que sea más susceptible de análisis?

Advertencia (para otros lectores): si se ofende fácilmente por la pseudociencia, ¡deje de leer ahora!

Una idea con la que he estado jugando, en la línea anterior, es representar el tablero de manera diferente (por ejemplo, a través de polígonos, vectores, líneas, etc.), con la esperanza de que una o más operaciones que traten con el tablero puedan optimizarse significativamente. Ayer, cuando hice mi pregunta en Quora.com, pensé en representar el tablero como una secuencia de serpientes horizontales, verticales y diagonales rectas.

Una serpiente se compone de uno o más cuadrados de tablero contiguos y tiene propiedades a las que se puede acceder en tiempo constante, por ejemplo, tipo, longitud, inicio, finalización. Al comienzo del juego, habría seis serpientes [(x, y) a continuación …]. Los tipos de serpiente son expresiones regulares simples, por ejemplo, _BAAAAAA_, AAAAAA, _BBBBBB.

1) [_] [B] [W] [_] (4,3 – 4,6) [serpiente de doble cabeza]

2) [_] [W] [B] [_] (5,3 – 5,6)

3) [_] [B] [W] [_] (3,4 – 6,4)

4) [_] [W] [B] [_] (3,5 – 6,5)

5) [B] [B] (4,4 – 5,5) [serpiente sin cabeza]

6) [W] [W] (5,4 – 4,5)

1 2 3 4 5 6 7 8 (x)

1 [_] [_] [_] [_] [_] [_] [_] [_]

2 [_] [_] [_] [_] [_] [_] [_] [_]

3 [_] [_] [_] [_] [_] [_] [_] [_]

4 [_] [_] [_] [B] [W] [_] [_] [_]

5 [_] [_] [_] [W] [B] [_] [_] [_]

6 [_] [_] [_] [_] [_] [_] [_] [_]

7 [_] [_] [_] [_] [_] [_] [_] [_]

8 [_] [_] [_] [_] [_] [_] [_] [_]

(y)

Para determinar los movimientos legales para un tablero dado para las negras, equivale a encontrar todas las serpientes _W ^ + B (^ + es el exponente +, que significa ‘al menos una W’). Cuando se realiza un movimiento, es posible que necesitemos combinar, extender, dividir, sumar o restar serpientes. Creo que este enfoque hará que la generación de movimientos legales sea más rápida, sin agregar mucha sobrecarga a los movimientos reales (actualizaciones de serpientes). Pero me pregunto si puede acelerar las búsquedas u otras operaciones. Las serpientes son como vectores, por lo tanto, estaba buscando si hay operaciones matemáticas (como la multiplicación de matrices), que podrían usarse.

Por el momento, todavía necesitamos el tablero, pero ¿tal vez podríamos eliminarlo y solo tener las serpientes?