Computer Arimaa se refiere al juego de mesa Arimaa mediante programas de computadora .
En 2002, el ingeniero informático indio-estadounidense Omar Syed publicó las reglas para Arimaa y anunció un premio de 10.000 dólares, disponible anualmente hasta 2020, para el primer programa informático (que se ejecute en hardware estándar disponible en el mercado) capaz de derrotar a cada uno de los tres mejores. -Jugadores humanos clasificados en una serie de tres juegos. [1] El premio se reclamó en 2015, cuando un programa de ordenador jugó 7:2 contra tres jugadores humanos. [2] El juego ha sido objeto de varios artículos de investigación.
El número de formas diferentes en que cada jugador puede colocar sus piezas al comienzo del juego es:
El jugador puede colocar 8 conejos en 16 casillas posibles, seguidos de 2 gatos en las 8 casillas restantes, 2 perros en las 6 casillas restantes, 2 caballos en las cuatro casillas restantes, un camello en una de las dos casillas restantes y el elefante. en la última casilla no utilizada.
Debido a que cada jugador puede comenzar el juego con una de las 64.864.800 configuraciones de apertura, el espacio de estado total para la apertura es:
Como dijo Christ-Jan Cox en su tesis de maestría, debido a que el número de posibles estados iniciales es tan grande, "se deduce que es muy difícil desarrollar bases de datos completas de movimientos de apertura". [3] [4]
Es importante que la computadora pueda evaluar el valor de las piezas en el tablero para poder evaluar si sería deseable o no una captura o un intercambio. La evaluación del valor relativo de las piezas es un área de investigación en curso en Arimaa. Algunos sistemas utilizados actualmente son DAPE y FAME.
Algunos o todos los programas de inteligencia artificial que juegan Arimaa utilizan las siguientes técnicas:
Varios aspectos de Arimaa dificultan que los programas informáticos venzan a buenos jugadores humanos. Debido a que se ha invertido tanto esfuerzo en el desarrollo de software potente para jugar ajedrez , es particularmente relevante comprender por qué las técnicas aplicables al ajedrez son menos efectivas para Arimaa.
Los programas de ajedrez más simples utilizan búsqueda de fuerza bruta junto con una evaluación de posición estática dominada por consideraciones materiales. Examinan muchos, muchos movimientos posibles, pero no son buenos (en comparación con los humanos) para determinar quién gana al final de una serie de movimientos, a menos que un lado tenga más piezas que el otro. Lo mismo ocurre con los programas de Arimaa, pero sus resultados no son tan buenos en la práctica.
Cuando se aplica la búsqueda de fuerza bruta a Arimaa, la profundidad de la búsqueda está limitada por la gran cantidad de opciones que tiene cada jugador en cada turno. Computacionalmente, la cantidad de opciones que un jugador tiene disponibles determina la cantidad de caminos diferentes que puede seguir el juego. Esto se conoce como factor de ramificación . El factor de ramificación promedio en una partida de ajedrez es de aproximadamente 35, [5] mientras que en Arimaa es de aproximadamente 17.000. [6]
Estos diferentes factores de ramificación implican que una computadora que puede buscar en una profundidad de ocho turnos para cada jugador en ajedrez, sólo puede buscar alrededor de tres turnos en profundidad para cada jugador en Arimaa:
La profundidad de búsqueda de fuerza bruta, para el software de ajedrez, casi se duplica mediante la poda alfa-beta , que permite al software concluir que un movimiento es mejor que otro sin examinar cada posible continuación del movimiento más débil. Si el oponente puede aplastar un determinado movimiento con una respuesta, no es necesario examinar otras respuestas, lo que aumenta drásticamente la velocidad de búsqueda. En Arimaa, sin embargo, el lado a mover cambia solo cada cuatro pasos, lo que reduce la cantidad de cortes disponibles en una búsqueda basada en pasos.
Además, la utilidad de la poda alfa-beta depende en gran medida del orden en que se consideran los movimientos. Los buenos movimientos deben considerarse antes que los malos para que los malos sean descuidados. En particular, verificar y capturar movimientos son clave para la poda, porque a menudo son mucho mejores que otros movimientos. En el software Arimaa, la aceleración proporcionada por la poda alfa-beta es menor porque las capturas son más raras. En las partidas puntuadas que se juegan en arimaa.com, sólo el 3% de los pasos resultan en captura, en comparación con aproximadamente el 19% de los movimientos de ajedrez que resultan en captura.
En la mayoría de las posiciones de Arimaa, especialmente al comienzo del juego cuando el tablero todavía está lleno, un jugador competente puede evitar perder piezas en los dos turnos siguientes. En comparación con el ajedrez, Arimaa permite a cualquiera de los jugadores retrasar las capturas por más tiempo. De hecho, el número de movimiento medio de la primera captura en ajedrez es el turno 6, mientras que en Arimaa es el turno 12. La lucha es inicialmente más posicional en Arimaa y gira en torno a hacer que las capturas sean inevitables en algún momento en el futuro. Esto magnifica la importancia de juzgar correctamente quién está ganando terreno en formas no materiales. Así, la fortaleza de los programas informáticos (que examinan millones de posiciones) no es tan significativa como su debilidad (juzgar la posición independientemente de quién tiene más piezas).
La debilidad de los programas de Arimaa en las fases iniciales se magnifica aún más en la fase de preparación. En ajedrez todas las partidas empiezan desde la misma posición. Al compilar antes de la partida una lista de respuestas estándar a todos los movimientos de apertura estándar, los programas de ajedrez a menudo pueden realizar una docena o más de movimientos excelentes antes de empezar a "pensar". Los humanos hacen lo mismo, pero tienen una memoria más pequeña y menos confiable de las aperturas, lo que los coloca en relativa desventaja en el ajedrez. Arimaa, por el contrario, tiene millones de formas posibles de colocar las piezas incluso antes de que se mueva la primera. Esto evita que los programas tengan un libro de apertura significativo.
A medida que avanza el juego, los intercambios y el avance de los conejos tienden a hacer que la posición sea más abierta y táctica. Los programas de Arimaa suelen jugar mejor en este tipo de posición, porque ven tiros tácticos que los humanos pasan por alto. Sin embargo, generalmente es posible para los humanos evitar posiciones muy abiertas mediante un juego conservador y buscar posiciones estratégicas en las que a las computadoras les va peor. Contra un oponente conservador es casi imposible abrir la posición en Arimaa, mientras que en ajedrez es sencillamente difícil. Hay que vencer el juego defensivo mediante la acumulación de pequeñas ventajas a largo plazo, algo que los programas no logran muy bien.
Una técnica adicional del ajedrez por ordenador que no se aplica a Arimaa son las tablas de finales . Los juegos de ajedrez de nivel maestro a veces desembocan en finales poco claros con sólo unas pocas piezas, por ejemplo, rey y caballo contra rey y torre. Es posible construir, mediante análisis retrógrado , una tabla exhaustiva del movimiento correcto en todas esas posiciones. Los programas sólo tienen que consultar una tabla pregenerada en dichas posiciones, en lugar de "pensar" de nuevo, lo que les da una ventaja relativa sobre los humanos. Arimaa, por el contrario, rara vez llega a un final. Los intercambios iguales de piezas son menos comunes que en el ajedrez, por lo que es raro que una partida de Arimaa "cambie hacia abajo" y aún así no quede clara. Una partida promedio de Arimaa tiene solo ocho capturas (en comparación con las diecisiete del ajedrez), y los mejores humanos a menudo pueden derrotar a los mejores programas en Arimaa sin perder una sola pieza, por ejemplo, la segunda partida del desafío 2014. Otro ejemplo de baja densidad de captura es este juego de semifinales del Campeonato Mundial de 2012, en el que solo se realizó una captura, un sacrificio de elefante que obligaba a marcar un gol.
Omar Syed espera que, debido a que las técnicas tradicionales de inteligencia artificial son sólo moderadamente efectivas para Arimaa, los programadores se verán obligados a utilizar nuevas técnicas de inteligencia artificial para crear un programa potente para jugar a Arimaa. La búsqueda exitosa de construir un programa de ajedrez con calibre de campeonato mundial ha producido muchas técnicas para jugar con éxito, pero no ha contribuido esencialmente en nada a un razonamiento más general; de hecho, las técnicas de los programas de juego de ajedrez han sido excluidas de algunas definiciones de inteligencia artificial ; Un objetivo para Arimaa es que las técnicas involucradas en su juego ayuden a alcanzar los objetivos más amplios de la inteligencia artificial.
La estructura del desafío hombre contra máquina de Syed se centra en recompensar los avances en el software de inteligencia artificial y no los avances en el hardware. En el desafío anual, los programas se ejecutan en máquinas elegidas y proporcionadas por el propio Syed, bajo el criterio de que sea una computadora doméstica típica, económica y disponible en el mercado. El desafío no estaría abierto a nadie que requiera costosas máquinas multiprocesador como las que se utilizan para desafiar a los jugadores de ajedrez de alto nivel, y mucho menos algo como la supercomputadora Deep Blue hecha a medida , a pesar de que fue el éxito de este enfoque intensivo en hardware. que inspiró el invento de Arimaa. Syed cree que incluso la computadora utilizada en el desafío de 2004 (un sistema Pentium 4 de 2,4 GHz con 512 MB de RAM) tenía suficiente hardware para ganar el premio del desafío si tan solo estuviera ejecutando el software adecuado. Es posible que las supercomputadoras ya tengan el poder de conquistar Arimaa por fuerza bruta utilizando software de inteligencia artificial convencional, y eventualmente las computadoras personales también lo tendrán, si el hardware continúa avanzando al ritmo actual. Es por eso que el premio del desafío Arimaa se ofreció originalmente solo hasta el año 2020.
La interfaz del motor Arimaa, desarrollada por Brian Haskin, define un protocolo que permite que un motor Arimaa se comunique con un controlador.
Según la documentación: "Un motor es un programa capaz de tomar el estado de un juego de Arimaa y seleccionar un movimiento legal a realizar. Un controlador es cualquier cosa que quiera comunicarse con un motor y controlarlo. Esto podría ser cualquier cosa, desde un simple script hacer que el motor analice una sola posición para un programa GUI que permita jugar juegos con humanos u otros motores". [7]
La interfaz del motor Arimaa incluye una implementación de un motor y un controlador, documentación y varios scripts para controlar el motor y jugar en cualquier sitio web que admita el protocolo, incluido el sitio web oficial de Arimaa. [8] [9]
