Computadora Arimaa

El número de formas diferentes en que cada jugador puede colocar sus piezas al comienzo del juego es:

${\displaystyle {\dbinom {16}{8}}\cdot {\dbinom {8}{2}}\cdot {\dbinom {6}{2}}\cdot {\dbinom {4}{2}}\cdot {\dbinom {2}{1}}\cdot {\dbinom {1}{1}}=64{,}864{,}800}$

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 sin usar.

Dado que cada jugador puede comenzar el juego con una de las 64.864.800 configuraciones iniciales, el espacio de estados total para la apertura es:

${\displaystyle 64{,}864{,}800^{2}\approx 4.2\cdot 10^{15}}$

Como dijo Christ-Jan Cox en su tesis de maestría, debido a que el número de estados iniciales posibles es tan grande, "[e]s deduce que es muy difícil desarrollar bases de datos completas de movimientos de apertura". ^{[ 3 ] [ 4 ]}

Es importante que el ordenador pueda evaluar el valor de las piezas en el tablero para determinar si conviene capturarlas o intercambiarlas. La evaluación del valor relativo de las piezas es un área de investigación actual de Arimaa. Algunos sistemas que se utilizan actualmente son DAPE y FAME.

Algunos o todos los programas de inteligencia artificial que juegan a Arimaa utilizan las siguientes técnicas:

• Tableros de bits
• Tablas de transposición
• Hashing de Zobrist
• Poda Minimax y Alfa Beta
• Movimientos letales y tablas de refutación
• Función de evaluación estática
• Búsqueda de quiescencia
• Búsqueda de árboles de Montecarlo
• UCT

• Libro de apertura
• Tabla de final de juego

Los programas de ajedrez más sencillos utilizan la búsqueda por fuerza bruta combinada con la evaluación estática de posiciones, donde la ventaja material es primordial. Analizan muchísimos movimientos posibles, pero no son tan buenos (en comparación con los humanos) para determinar quién gana al final de una serie de movimientos, a menos que un bando tenga más piezas que el otro. Lo mismo ocurre con los programas Arimaa, pero sus resultados no son tan buenos en la práctica.

Cuando se aplica la búsqueda por fuerza bruta a Arimaa, la profundidad de la búsqueda está limitada por la enorme cantidad de opciones que cada jugador tiene en cada turno. Desde el punto de vista computacional, la cantidad de opciones disponibles para un jugador 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 hasta una profundidad de ocho turnos para cada jugador en ajedrez, solo puede buscar hasta una profundidad de tres turnos para cada jugador en Arimaa:

${\displaystyle 35^{8}\approxeq 17000^{3}}$

La profundidad de búsqueda por fuerza bruta en el software de ajedrez prácticamente se duplica gracias a la poda alfa-beta , que permite al software concluir que un movimiento es mejor que otro sin examinar todas las posibles continuaciones del movimiento más débil. Si el oponente puede anular un movimiento determinado con una sola respuesta, no es necesario examinar otras respuestas, lo que aumenta drásticamente la velocidad de búsqueda. Sin embargo, en Arimaa, el bando que mueve cambia solo cada cuatro pasos, lo que reduce el número de cortes disponibles en una búsqueda por pasos.

Furthermore, the usefulness of alpha-beta pruning is heavily dependent on the order in which moves are considered. Good moves must be considered before bad ones in order for the bad ones to be neglected. In particular, checking and capturing moves are key for pruning, because they are often much better than other moves. In Arimaa software the speedup provided by alpha-beta pruning is less, because captures are rarer. In rated games played on arimaa.com, only 3% of steps result in capture, compared to about 19% of chess moves that result in capture.

In most Arimaa positions, particularly toward the beginning of the game when the board is still crowded, a competent player can avoid losing any pieces within the next two turns. Compared to chess, Arimaa allows either player to delay captures for longer. Indeed, the median move number of the first capture in chess is turn 6, whereas in Arimaa it is turn 12. The struggle is initially more positional in Arimaa, and revolves around making captures unavoidable at some point in the future. This magnifies the importance of correctly judging who is gaining ground in non-material ways. Thus the strength of computer programs (examining millions of positions) is not as significant as their weakness (judging the position apart from who has more pieces).

The weakness of Arimaa programs in the opening phases is further magnified by the setup phase. In chess every game starts from the same position. By compiling before the game a list of stock replies to all standard opening moves, chess programs may often make a dozen or more excellent moves before starting to "think". Humans do the same, but have a smaller and less reliable memory of openings, which puts humans at a relative disadvantage in chess. Arimaa, in contrast, has millions of possible ways to set up the pieces even before the first piece moves. This prevents programs from having any meaningful opening book.

As the game progresses, exchanges and the advancement of rabbits tend to make the position more open and tactical. Arimaa programs typically play better in this sort of position, because they see tactical shots which humans overlook. However, it is usually possible for humans to avoid wide-open positions by conservative play, and to angle for strategic positions in which computers fare worse. Against a conservative opponent it is almost impossible to bust open the position in Arimaa, whereas in chess it is merely difficult. One must beat defensive play by the accumulation of small, long-term advantages, which programs do not do very well.

Una técnica adicional del ajedrez por computadora que no se aplica a Arimaa son las tablas de finales . Las partidas de ajedrez de nivel maestro a veces terminan en finales inciertos con solo 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 solo tienen que consultar una tabla pregenerada en tales posiciones, en lugar de "pensar" de nuevo, lo que les da una ventaja relativa sobre los humanos. Arimaa, en cambio, 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 "termine" y aún así sea incierta. Una partida promedio de Arimaa tiene solo ocho capturas (en comparación con diecisiete en 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 encuentro Challenge de 2014 . Otro ejemplo de baja densidad de capturas es este partido de semifinales del Campeonato Mundial de 2012 , que presenta una sola captura: el sacrificio de un elefante que forzó un gol.

Omar Syed espera que, dado que las técnicas tradicionales de inteligencia artificial solo son moderadamente efectivas para Arimaa, los programadores se vean obligados a utilizar nuevas técnicas para crear un programa de ajedrez potente. La exitosa búsqueda de un programa de ajedrez de nivel mundial ha generado muchas técnicas para jugar partidas con éxito, pero prácticamente no ha contribuido al razonamiento general; de hecho, las técnicas de los programas de ajedrez han sido excluidas de algunas definiciones de inteligencia artificial . Uno de los objetivos de Arimaa es que las técnicas empleadas en su uso contribuyan a los objetivos más amplios de la inteligencia artificial.

La estructura del desafío de Syed, que enfrenta al hombre contra la máquina, se centra en premiar los avances en software de IA, no en hardware. En el desafío anual, los programas se ejecutan en máquinas elegidas y proporcionadas por el propio Syed, con el criterio de que se trate de un ordenador doméstico típico, económico y comercial . El desafío no estaría abierto a quienes requirieran costosos procesadores múltiples, como los que se utilizan para desafiar a jugadores de ajedrez de alto nivel, y mucho menos a algo como la supercomputadora personalizada Deep Blue , a pesar de que el éxito de este enfoque intensivo en hardware inspiró la invención de Arimaa. Syed cree que incluso el ordenador utilizado en el desafío de 2004 (un sistema Pentium 4 de 2,4  GHz con 512 MB de RAM) tenía el hardware suficiente para ganar el premio si hubiera ejecutado el software adecuado. Es posible que las supercomputadoras ya tengan la capacidad de vencer a Arimaa por fuerza bruta utilizando software de IA convencional, y eventualmente los ordenadores personales también la tendrán, si el hardware continúa avanzando al ritmo actual. Por este motivo, el premio del desafío Arimaa se ofreció originalmente solo hasta el año 2020.