¿Cuál sería el mejor algoritmo para usar si estoy creando un tictactoe ai de 5x5 usando 4 en fila? El algoritmo original que se suponía que debíamos usar era el minimax, pero solo nos dan 10 segundos por turno.

1
Jorge 14 dic. 2016 a las 08:53

2 respuestas

La mejor respuesta

Si desea crear un reproductor de alta calidad, hay muchas mejoras importantes que puede implementar.

Primero, por supuesto, está la poda alfa-beta, pero hay varias otras técnicas que harán que la poda alfa-beta sea aún más efectiva.

En segundo lugar, dado que el límite de tiempo es importante, debe agregar una profundización iterativa. Es decir, busca primero a la profundidad 1, luego a la profundidad 2, etc. Cuando se acaba el tiempo, toma el mejor movimiento de la iteración completada anteriormente. Debido a que el árbol crece exponencialmente, realmente no pierde nada de sus iteraciones anteriores. (Con un factor de ramificación de 2, la sobrecarga es un factor de 2, pero a medida que el factor de ramificación aumenta más, esta sobrecarga se reduce a cero).

En tercer lugar, utilice la heurística de historial para ordenar su buscar. En las iteraciones pequeñas, aprenderá un mejor orden de los estados para acercarse al orden óptimo (para la poda alfa-beta) en las iteraciones posteriores.

En cuarto lugar, use una tabla de transposición para evitar estados duplicados. Hay muchas transposiciones que ocurren al buscar en el árbol, y detectarlas temprano resultará en ahorros significativos. (Esto probablemente tendrá un impacto mayor que la heurística histórica).

Finalmente, cree la mejor función de evaluación posible. Cuanto mejor seas evaluando estados, mejor jugarás. (En el límite, una evaluación perfecta solo requeriría una búsqueda de 1 capa para jugar perfectamente).

Por supuesto, si puedes resolver el juego, hazlo. Solo hay 3 ^ 25 (847,288,609,443) estados posibles en 5x5 tic-tac-toe, por lo que con una máquina con una potencia decente puede resolver el juego, lo que le brinda la función de evaluación perfecta.

0
Nathan S. 14 dic. 2016 a las 06:53

Como mencionaste sobre el algoritmo minimax, quiero sugerirte una variante un poco complicada de minimax que se llama poda alfa-beta. La poda alfa-beta evita una parte del espacio de búsqueda que se denomina poda. Le animo a leer este artículo.

Puede caminar a través del árbol de búsqueda hasta la profundidad 5 o lo que su tiempo le permita. Por favor, no eso, no estoy diciendo que la poda alfa-beta sea la mejor, pero sugiero que la técnica de poda podría darte una ventaja sobre minimax en términos de complejidad de tiempo.

Recursos adicionales:

0
Wasi Ahmad 14 dic. 2016 a las 06:01