enfoque estadístico para el ajedrez?

votos
12

Leer acerca de cómo Google soluciona el problema de traducción me hizo pensar. ¿Sería posible construir un motor de ajedrez fuerte mediante el análisis de varios millones de juegos y determinar el mejor movimiento posible basado en gran medida (por completo?) En las estadísticas? Hay varias de estas bases de datos de ajedrez ( este es uno que tiene 4,5 millones de juegos), y uno potencialmente podrían peso se mueve en posiciones idénticas (o espejos o reflejadas) utilizando factores tales como la calificación de los actores involucrados, la edad del juego es (a factor en la mejora de la teoría del ajedrez) etc. Cualquier razones para que esto no iba a ser un enfoque viable para la construcción de un motor de ajedrez?

Publicado el 26/04/2010 a las 23:50
fuente por usuario
En otros idiomas...                            


11 respuestas

votos
21

Algo como esto ya está hecho: es el concepto subyacente de la apertura de los libros .

Debido a la naturaleza del juego, inhibidores de la aromatasa ordenador son muy malos en el principio, cuando hay tantas posibilidades y el objetivo final es todavía muy por delante. Se comienza a mejorar hacia el centro, cuando posibilidades tácticas comienzan a formarse, y puede reproducir perfectamente en el juego final muy superior a la capacidad de la mayoría de los seres humanos.

Para ayudar a la IA hacen buenos movimientos en el principio, muchos motores se basan en la apertura de los libros en su lugar: un diagrama de flujo obtenida por estadística de movimientos, básicamente. Se analizaron muchos juegos entre los jugadores de alta calificación, y las recomendaciones estén codificadas en "el libro", y mientras que las posiciones están todavía en "el libro", la IA no incluso "pensar", y simplemente seguir lo que "el libro " dice.

Algunas personas también pueden memorizar la apertura de los libros (esto es principalmente la razón por Fischer inventó su ajedrez aleatorio variante, por lo que la memorización de las aberturas se convierte en mucho menos eficaz). En parte debido a esto, a veces un movimiento no convencional se hace en un principio, no porque es estadísticamente el mejor movimiento de acuerdo a la historia, sino precisamente lo contrario: no es una posición "conocido", y puede llevar a su oponente (humano o un ordenador) " del libro".

En el extremo opuesto del espectro, hay algo llamado Endgame tablebase , que es básicamente una base de datos de las posiciones de finales analizados previamente. Desde las posiciones previamente se buscaron exhaustivamente, se puede usar esto para permitir un juego perfecto: cualquier posición dada, se puede decidir de inmediato si se trata de ganar, perder o dibujar, y cuál es la mejor manera de lograr / evitar el resultado.

En el ajedrez, algo como esto sólo es factible para la apertura y el final del juego, sin embargo. La complejidad del medio juego es lo que hace el juego interesante. Si uno puede jugar al ajedrez con sólo mirar una tabla, entonces el juego no sería tan emocionante, interesante y profundo como es.

Respondida el 27/04/2010 a las 01:13
fuente por usuario

votos
6

Bueno, 4,5 millones de juegos todavía sólo cubre una muy pequeña (infinitesimal pequeña) fracción de todos los juegos posibles.

Y mientras que tendría un gran número de posiciones de ganar y perder, que dejaría el problema de reducir eso a un conjunto útil de parámetros. Un muy viejo problema, con las redes neuronales como un enfoque estándar. Pero NeuralNets no están ganando torneos de ajedrez.

Respondida el 26/04/2010 a las 23:59
fuente por usuario

votos
3

Esta estrategia general se ha tratado de una variedad de juegos. Muy a menudo, las personas generan una adecuada gran base de datos de juegos haciendo que el ordenador pueda reproducir en sí. Una rápida búsqueda en Internet se convierte en imagen http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/chess-RL.pdf - que se basa en el trabajo previo en el Backgammon. En el ajedrez, la fuerza bruta de preanálisis es muy eficaz para los ordenadores, sin embargo - y en las estadísticas generales es mucho más eficaz cuando se puede mezclar toda la información previamente conocida sobre el problema, en lugar de tratar de volver a aprender de los datos . Tomo nota de que en este enlace de la computadora aprendió lo que equivale a la función de evaluación en la parte inferior de la visión hacia adelante, no todo el proceso.

Respondida el 27/04/2010 a las 06:43
fuente por usuario

votos
2

Hay algo similar que funciona muy bien en equipo Ir - el método de UCT . No utiliza un conjunto conocido de juegos, sino que juega un gran número de juegos de azar, manteniendo las estadísticas que se mueve conducen a proporciones más altas de victorias. Y lo hace a partir de la posición actual.

Las estadísticas se mantienen en un árbol de movimientos (similar al que se utiliza en Minimax) e influyen en la elección del próximo juego de azar para jugar - los movimientos con proporciones más altas de ganar se eligen con más frecuencia. El crecimiento del árbol también se guía por los juegos - por lo general cada juego añade una hoja en el árbol. Esto lleva a los caminos prometedores están explorando más profundamente.

Respondida el 27/04/2010 a las 12:12
fuente por usuario

votos
1

Yo diría que sí, que podría funcionar. Nadie está realmente probado todavía con éxito, pero ¿por qué no busca "patrones" utilizando un enfoque estadístico. No estoy considerando el almacenamiento de toda la junta ya que no hay astronómicamente muchas posiciones en el tablero para guardar, sino simplemente buscar patrones específicos.

La búsqueda de patrones

Un programa de ajedrez típico evalúa y da bonificaciones para los patrones reconocidos como la buena defensa de peón o una línea de torres abiertas y en las otras sanciones mano para como peones doblados.

Tales patrones se podrían programar de manera eficiente en las máscaras de 64 bits. Usted tendría bit-máscaras para las posiciones que importan y mascaras de bits para piezas esperados en esas posiciones. Cada patrón necesita tiempo para que coincida con lo que sería importante encontrar los que marca la diferencia. Ahí es donde se utilizaría enfoque estadístico de Google. Podría funcionar a través de juegos "históricos" y buscar patrones. Después de que encuentre un patrón tendría que calcular un peso al modelo y ver si la evaluación mejorada es mayor que el de arriba.

Creo que esto sería un gran proyecto en lugar de probar, incluso demasiado para una tesis doctoral.

Respondida el 15/02/2016 a las 09:18
fuente por usuario

votos
1

Hay aproximadamente 10 123 árboles de juego en el ajedrez de los cuales tiene alrededor de 4,5 × 10 6 en esa base de datos. Podemos ignorar los árboles de juego, y sólo tienen en cuenta la complejidad de espacio de estados de los que hay en cualquier lugar entre 10 43 y 10 50 estados legales. Vamos a suponer que todos los partidos en esa base de datos tienen movimientos únicos, y que hay 1000 se mueve en promedio por juego, lo que nos da 4,5 x 10 9 estados. Tomando el estimado límite inferior 10 43 de estados posibles, que sólo cubre 4,5 × 10 -34de todos los estados. No sé cuál es el número total de posiciones en el tablero únicos que excluyen rotaciones o reflexiones, pero sólo reducirá por un factor de dos o menos, lo que no es muy útil.

Usted tendría que añadir más conocimiento del dominio en el motor estadístico y averiguar el nivel de similitud entre dos posiciones en el tablero dados ya que hay un 1 en 10 35 probabilidad de que usted no encontrará una posición en el tablero juego (incluyendo reflexiones y rotaciones). Creo que la clave más importante aquí sería encontrar la forma cómo dos posiciones en el tablero dados son similares. Eso va a incorporar un conocimiento mucho más dominio de transformaciones simples.

Es una gran idea, sin embargo, que vale la pena explorar más a fondo, aunque sospecho que se ha intentado antes dada la complejidad del ajedrez y el interés a su alrededor.

Respondida el 27/04/2010 a las 00:55
fuente por usuario

votos
1

Me gusta la idea, pero la analogía [con traducción de texto] parece quedarse corto si se considera que el contexto de una frase en lenguaje natural requiere mucho menos elementos que el contexto de una posición en el tablero de ajedrez (a pesar de que los elementos de tales sentencias, a saber Es decir, pueden provenir de un conjunto más grande que los elementos de un juego de ajedrez, es decir, las piezas del juego, caballero, peón, etc.)
por otra parte, la disponibilidad de corpus multilingüe (documentos de diversa naturaleza, en varios idiomas) supera con creces el número de juegos de ajedrez, que uno puede encontrar en un formato digital , en especial si se considera que para el análisis de ajedrez se necesita todo el partido por el que, para el propósito de la traducción, se puede utilizar cada frase independientemente del resto del texto.

Como resultado de ello, y con la posible excepción de la abertura de la parte de los juegos (cuando las posiciones de la junta no han tenido mucha oportunidad de diferir con respecto a otros juegos), el número de juegos de ajedrez necesarios para introducir un poco de significación estadística tendría que ser astronómico...

Tengo que correr, pero estaré de vuelta con estimaciones específicas sobre el número de posibles juegos de ajedrez (en lo absoluto, y en el subconjunto de posibles juegos), y debe demostrar efectivamente que 4.5 millones de juegos es una muestra relativamente pequeña.

Respondida el 27/04/2010 a las 00:13
fuente por usuario

votos
0

Una cosa que no he visto mencionado es la consideración de las calificaciones de los jugadores en los juegos en su base de datos. Algunas aberturas con buenos porcentajes db son el resultado del mejor jugador que tiende a ganar y decir poco sobre el valor de la abertura.

De hecho, he decidido que las bases de datos son buenos para una sola cosa y que está indicando lo que se mueve son populares. Más allá de que está realmente estirar su interpretación de los datos más allá de lo que merece.

Del mismo modo el análisis informático sólo muestra el mejor resultado para el equipo frente a los juegos de ordenador. Los partidos entre los seres humanos son diferentes y no se debe confiar demasiado en el análisis por ordenador.

Tanto la base de datos y equipo de análisis es interesante, pero que puede ser fácilmente malinterpretado. Tener cuidado.

Respondida el 12/11/2018 a las 10:53
fuente por usuario

votos
0

algoritmo de aprendizaje profundo similar al programa GO que derrotó al jugador amo humano podría ser el asesino. Se requeriría un alto costo sin embargo. Sin embargo, se podría utilizar los patrones de aprendizaje profundas aprendido de GO y aplicarlo a ajedrez.

Respondida el 03/10/2016 a las 14:20
fuente por usuario

votos
0

Máquina de aprendizaje ha hecho grandes progresiones últimamente, sobre todo después de que el equipo de Google vencer al campeón GO utilizando ML. Se ha encontrado ahora también ha demostrado con el ajedrez. Echar un vistazo al artículo en el MIT Technology Review, https://www.technologyreview.com/s/541276/deep-learning-machine-teaches-itself-chess-in-72-hours-plays-at-international-master /

Profundo aprendizaje de ML es una mejora de los viejos autoajuste algoritmos de IA de Redes Neuronales. La demostración de Lai no enseñó la máquina de las reglas básicas del ajedrez o se preocupaba por el resultado de los juegos. Él sólo alimenta la máquina con una gran base de datos de los juegos y la máquina descubrió que el resto y jugó a un nivel razonable "humana".

Asumo dos grandes mejoras serían para que sea más eficiente mediante la enseñanza de que las reglas y luego guiarla alimentándolo con los resultados reales de los juegos. Luego, después de que van entrenar con los actuales campeones de ajedrez, los motores como Bacalao! :-)

Respondida el 27/06/2016 a las 08:26
fuente por usuario

votos
-1

Chinmay,

Sé que esto es un hilo viejo, pero es un tema que he estado explorando últimamente. La mayoría de las personas que respondieron anteriormente realmente no consiguió su pregunta. Creo que sí, que vale la pena analizar numerosos juegos en el pasado para desarrollar movimientos sugeridos. Va a cubrir todos los movimientos posibles? No, obviamente no. Pero cubre todos los movimientos realistas de los juegos reales. Un ser humano (u otro algoritmo informático) tendrían que empezar a jugar muy extraños movimientos de tirar cosas fuera. Por lo tanto, no se puede construir un algoritmo de 'perfecta' que gana todo el tiempo, pero si gana mucho, decir una calificación> 2200 de la FIDE, que no está mal ¿verdad? Y si se incorporan aberturas y Finales, no sólo se basan en el análisis mueven más allá, hace que sea un motor aún mejor.

Hay un número astronómicamente alto de posibles posiciones de la junta, pero es finito, y si se quita las posiciones estúpidos que reduce el número un poco. ¿Es posible tener 4, 5 o 6 de uno de los jugadores peones alineados en el mismo archivo? Sí, tendría que ocurrir en un juego real? Dudo. Incluir un cerebro de ajedrez básico en su lógica para situaciones en las que el oponente va 'libro off'. Micro Max es solamente un par de cientos de líneas de código, por ejemplo. Si el oponente ha jugado estúpida para frustrar sus movimientos, que son probablemente derrotar por un motor simple.

Respondida el 07/03/2011 a las 15:38
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more