Juego Conecta 4: Paso a Paso (5) El módulo de Inteligencia Artificial. Algoritmo Negamax

Juego Conecta 4:

 Paso a Paso (5) 

El módulo de Inteligencia Artificial. Algoritmo Negamax

La inteligencia artificial de este programa consiste en evaluar las posiciones que se producen con las distintas jugadas (tantos las de un jugador como las del otro,  ordenandolas por niveles) y elegir la que más nos beneficie. Basicamente, consiste, en ver cuales jugadas puedo hacer, evaluar las que podria hacer el contrario, volver a evaluar mi respuesta a la del contrario, y asi hasta cierto nivel o profundad.

Por lo tanto vemos que hay dos partes bien diferenciada:

-La parte de evaluar el "arbol" de las distintas jugadas y sus respuestas, y elegir entre ellas la que más nos beneficie.

-La evaluación de la jugada, osea del tablero que queda cuando ejecuto esa jugada.
Código del negamax

Cosas que hace este código por orden:
1) Obtiene el numero de jugadas posibles del tablero que recibe
2) Crea un tablero auxiliar que es copia del que recibe
3) Entra en un bucle que se repite tantas veces como numero de jugadas posibles se puedan hacer
4) Hace una jugada (inserta una ficha en el tablero auxiliar)
5) Comprueba si es GamerOver o la profundidad del análisis es 0,
5.1) Si es así, evalúa la jugada y retorna su valor.
5.2) Sino:
5.2.1) vuelve a llamar a la funcion negamax, pasandole el nuevo tablero, el jugador contrario (lo multiplica por -1), una profundidad menor, y dos valores -beta, y -alfa_local, que sirven para "podar el arbol de opciones"
5.2.2) Evalúa la puntuación que se obtiene
5.2.2.1) Si es mayor su puntuación a la máxima puntuación, la jugada es elegida como posible mejor jugada
5.2.2.2) Sino, si es igual, de elige aleatoriamente a una de ellas. Esto se hace para que el juego sea un poco aleatorio, al no elegir siempre la misma jugada que tenga la misma puntuación que otras.
5.2.3) Hace una poda alfa-beta, para dejar de revisar jugadas, si superan el valor de beta.

Código del EvaluaJugadaMov

Evaluar una posición de las fichas del  tablero producido por una jugada, consiste en averiguar cuantas veces se han formado grupos de 2, 3 o 4 fichas del mismo color en horizontal, vertical o diagonal (esto se hace usando el método comprueba_linea del objeto tablero).
En principio el valor viene dado por la formula:
 valor_jugada = (4 * n2 + 9 * n3 + 100000 * n4)
Siendo:
n2: numero de grupo de 2 fichas del mismo color en horizonta, vertical o diagonal
n3: numero de grupo de 2 fichas del mismo color en horizonta, vertical o diagonal
n4: numero de grupo de 2 fichas del mismo color en horizonta, vertical o diagonal

Se ha simplificado un poco el algoritmo de cálculo, ya que si se forma un grupo de 4 fichas,  es un tablero ganador, y por lo tanto, no hace falta calcular los otros grupos (n2 ni n3).

En la próxima entradas explicaremos como se ha realizado los formularios (el modo gráfico)