- Negamax
-
Negamax es una variante del algoritmo minimax donde cada nodo independientemente si fuese MIN o MAX toma el valor máximo de sus hijos (como si todos los nodo fueran MAX), solo que los valores de los nodos MAX se cambian de signo (de ahí su nombre, en vez de tomar máximos y mínimos toma siempre máximos pero con valores cambiados). De esta forma se logra el mismo efecto ya que tomar el mayor valor pero cambiado de signo es en realidad tomar el menor así cuando el algoritmo está en un nivel MIN cuando toma el mayor de sus hijos en realidad está tomando al menor.
La función Negamax podría recibir como parámetro un signo, de esta manera se podría comenzar por niveles MIN o niveles MAX, pero no necesariamente ya se puede establecer niveles estáticos, donde cada nivel está definido por un signo distinto.
Hablando del Minimax: Suponiendo que existe min() que devuelve el menor y max() que devuelve el mayor, Negamax se basa en la siguiente igualdad matemática:
- max(x, y)=-min(-x,-y)
A este algoritmo también se le pueden aplicar podas y heurísticas para acortar su tiempo de ejecución, además existe una mejora de este algoritmo llamado negascout.
Algoritmo Pseudocódigo
int NegaMax(estado) { if(estado_final(estado)) { return evaluacion_heurística(estado); } max=-infinito; while exist movimiento_posible(estado) { val=-NegaMax(mover(mov, estado)); if (val>max) { max=val; } } return(max); }Donde estado_final() verifica si se llegó a un estado de corte de recursión, evaluacion_heurística() devuelve el valor heurístico del nodo, movimiento_posible() es un movimiento dentro del sub-árbol de todos los movimientos posibles, mover() efectúa el movimiento para luego hacer un Backtracking.
Véase también
Enlaces externos
Categorías:- Algoritmos de grafos
- Algoritmos de búsqueda
- Juegos no cooperativos
Wikimedia foundation. 2010.
