Todos los motores de ajedrez de los que he oído hablar (incluido todo lo que encontré en la lista de Wikipedia) utilizan la búsqueda de fuerza bruta con una función de evaluación (algoritmo minmax) para decidir su movimiento.
No es así como la mayoría de los humanos se acercan al juego, empleando el reconocimiento de patrones generales, por lo que, en principio, sería posible que las computadoras hicieran lo mismo.
¿Hay algún motor de ajedrez que no se base en el enfoque de fuerza bruta para encontrar sus movimientos?
engines
chess-algorithms
candidate-move
brute-force
usuario57565488
fuente
fuente
Respuestas:
Hubo intentos en la década de 1980 de escribir motores de ajedrez con bases de conocimiento que seleccionaran movimientos candidatos como los humanos, pero no tuvieron éxito. El problema es que la coincidencia de patrones humanos es difícil de expresar con palabras, por lo que crear las reglas para la base de conocimiento fue extremadamente difícil.
El entrenamiento de una red neuronal para elegir movimientos candidatos parece una línea de investigación prometedora. Aquí y aquí podría haber dos documentos pertinentes. (FWIW, no es mi campo de Comp Sci)
fuente
Puede echar un vistazo a Giraffe, que apareció recientemente en las noticias:
https://thestack.com/iot/2015/09/14/neural-network-chess-computer-abandons-brute-force-for-selective-human-approach/
La exageración es que en 3 días aprendió el juego y alcanzó el nivel IM. Por otro lado, la investigación está en
http://arxiv.org/abs/1509.01549
fuente
Me gustaría agregar detalles a la respuesta de @ Ian_Bush sobre Giraffe.
En la respuesta de @ Ian_Bush, se observa que Giraffe no usa el cálculo de fuerza bruta. Esto no está bien , porque Giraffe sigue siendo un motor alfa-beta (nega-max). La única diferencia con un motor estándar es que la función de evaluación se ajusta automáticamente mediante el aprendizaje profundo. Por lo tanto, el motor aprende a jugar solo.
Tradicionalmente, el programador del motor ajusta los parámetros en un motor. Yo mismo he hecho mucho. Por ejemplo, ¿cuánto peso deberías darle a un obispo y a un caballero? 3.0? 3.1? 3.2? Es difícil de contar.
Giraffe aborda el problema de una manera mucho más inteligente. Comienza con algunos valores iniciales. El motor utiliza el algoritmo de ascenso de gradiente para ajustar esos valores. No tenemos que codificar explícitamente cuánto peso debe tener una reina en el código. Esto es lo que queremos decir "aprender". No significa que el motor pueda jugar ajedrez sin buscar.
EDITAR : Giraffe modela los nodos del árbol como probabilidad de que caigan en la variación principal. Consulte el documento para más detalles. Personalmente, no creo en este enfoque, y el documento muestra poca evidencia de lo útil que sería.
fuente
We evaluated board representations by training neural networks to predict the output of Stock- fish’s evaluation function in a supervised fashion, given 5 million positions as input, in the board representation under evaluation.Entonces, esto no es aprender por autoimpresión IMO.Es discutible si se puede llamar una búsqueda basada en heurística y evaluar el enfoque como fuerza bruta. La mayoría de los motores de ajedrez de primer nivel siguen un enfoque basado en reglas para evaluar una posición y una función de búsqueda basada en reglas para podar movimientos.
En realidad, esto no garantiza la elección del movimiento "óptimo global", sin embargo, estos movimientos son lo suficientemente buenos para su propósito. En este sentido, la mayoría de los motores de ajedrez están utilizando una aproximación al óptimo global y, de hecho, lo están logrando.
Hasta la fecha, no tenemos muchos motores de ajedrez que tengan éxito en el nivel superior con un enfoque diferente, al menos no en hardware barato.
fuente
Claude Shannon propuso dos tipos de algoritmos para crear motores de ajedrez. Un motor "tipo A" examina todos los movimientos posibles hasta cierta profundidad finita, minimiza el árbol y luego juega el movimiento con la evaluación más alta del árbol minimizado (también conocido como fuerza bruta). Los motores de tipo B limitan su búsqueda a solo un subconjunto de movimientos posibles según algunos criterios. Creí que favorecía al Tipo B como más prometedor.
Los motores que se crearon en la década de 1970 (por ejemplo, Hitech, Kaissa) tendían a ser pura fuerza bruta sin poda o solo alfa-beta, pero la gente pronto vio el valor de podar el árbol de movimientos y líneas que probablemente no demostrarían ser fuertes. . Casi todos los motores recientes podan el árbol de líneas que son claramente más débiles (alfa-beta), y la mayoría de los motores también usan varios tipos de poda hacia adelante (futilidad, reducción de movimiento tardío, movimiento nulo, maquinilla de afeitar). En ese sentido, ya no hay muchos motores que usen fuerza bruta pura.
En la década de 1970, Botvinnik estaba trabajando en un motor llamado Pioneer concebido en torno a la noción de caminos de ataque que habrían sido guiados por la evaluación. Nunca llegó al punto en el que podía jugar una partida completa de ajedrez.
En la década de 1990, Chris Wittington se pronunció a favor de utilizar la incorporación de más conocimientos de ajedrez, y creó un programa llamado Chess System Tal que fue bastante fuerte para su época.
Kasparov, Anand y Tord Romstad han notado que Hiarcs parece tener una evaluación más detallada que muchos de los principales motores cuya fuerza proviene de una búsqueda rápida.
fuente
Básicamente todos ellos!
Los motores de ajedrez realmente solo usan la fuerza bruta cuando:
De lo contrario, tienen una "búsqueda selectiva", esto considerará todos los movimientos posibles para un diseño de tablero determinado, pero solo explorará un puñado de ellos. Sin embargo, un motor puede cambiar a fuerza bruta si califica dos movimientos de manera muy similar (más de un movimiento fuerte) o si no puede encontrar un movimiento que le guste (sin movimientos fuertes).
También tienden a la fuerza bruta como última línea de defensa, si has visto un jaque mate, es probable que lo vea venir y querrá esforzarse mucho para dibujar, y no puede encontrar una salida (el "efecto Horizon "es un problema con los motores, supongamos que va a perder a su reina, y tiene un límite de solo 4 jugadas profundas; si puede intercambiar peones y posponer esa pérdida de la reina por 4 movimientos, pensará que ha salvado a la reina , en el proceso, perderá al menos 1 peón (ya que el próximo movimiento acerca el horizonte desde antes) y el peso que pone en salvar a la reina puede significar que sacrifica algo de defensa, por nada si la muerte pasa por el horizonte) .
También tendrá fuerza bruta cuando la búsqueda selectiva no sea muy útil. Esta es la razón por la cual los motores tardan más cuando les quedan 3 piezas. Tienen que aplicar fuerza bruta porque el algoritmo de selección no puede calificar un movimiento. El algoritmo de selección es excelente durante el medio juego porque puede ser como "Oohh, hacer esto con el peón bloquea su [lo que sea] y respalda mi [lo que sea] y [lo que sea] que tengo un número menor defendiendo que atacando - por ejemplo .
Si tienes un rey en el medio del tablero, hay 8 movimientos, la búsqueda selectiva será como "Ninguno de estos hace nada útil, no puedo decirlo".
Puede pensar que la búsqueda selectiva tiene dos partes, es táctica en el sentido de que intentará detectar movimientos tácticos, ignorará el peso de las piezas involucradas, generalmente porque una reina que no es parte de ninguna estrategia no vale la pena. más que un peón vital para ello. También es estratégico, ya que explorará movimientos que refuerzan una defensa y se abrirán más tarde a posibles ataques.
El motor hace lo mismo desde su punto de vista, y de un lado a otro.
Algo llamado tabla de transposición es una gran lista de cosas en las que ha pensado, de esa manera si termina considerando algo que ya ha hecho, lo sabe y no tiene que volver a evaluarlo.
A MENOS (selectivo :)) llega allí de una manera diferente, o quiere explorar más a fondo. Supongamos, por ejemplo, que descubre que su ... torre es esencial para un ataque inminente, el motor puede reevaluar una línea cuando descubre esto. El peso anterior que le puso a esa torre (por ejemplo, 5 puntos, lo importante que es para usted) podría ser una subestimación.
La búsqueda selectiva también puede dar marcha atrás, por ejemplo, considerando que un obispo se mueve directamente al territorio enemigo, al selector de movimiento no es importante que se pueda tomar fácilmente. ¡Digamos que descubre eso estratégicamente que es un movimiento excelente! Entonces puede dar marcha atrás para tratar de encontrar una manera de proteger esa casilla para llevar al obispo allí. Supongamos que implica un peón para hacerlo.
El método de fuerza bruta consideraría la línea que involucra ese movimiento de peón, y (por fuerza bruta) el alfil también se mueve, y lo mismo que califica la posición del tablero (la búsqueda selectiva en sí) dirá "esto es bueno", entonces el tablero califica esa variación altamente, ambos lo encuentran.
Es muy difícil calificar una posición usando el método de fuerza bruta, por eso la búsqueda selectiva funciona tan bien.
La fuerza bruta desde la posición inicial podría encontrar ese famoso compañero en 4 que involucra a una reina f7 cubierta por un obispo, y si tuviera que calificar eso altamente (¡HE ENCONTRADO UN CHECKMATE! ¡TRABAJO HECHO! ¡JUEGO!) estaría equivocado porque el negro obviamente contrarrestará. La búsqueda selectiva califica una posición (para una evaluación adicional) porque parece ser buena. Esto significa que cuando considera su respuesta, puede decidir qué sería bueno para usted ...
Por lo tanto, la fuerza bruta usa todo lo que la búsqueda selectiva usa para calificar las cosas porque "encontró un jaque mate que involucra este movimiento" no es suficiente para decir que el movimiento es bueno.
Por lo tanto, ¿cuáles son los primeros movimientos elegidos (Blanco), por los motores de ajedrez de fuerza bruta?
fuente