Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Minimax y Poda Alfa-beta

No description
by

jenny ruiz

on 23 January 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Minimax y Poda Alfa-beta

María Camila Millán Villalba
Ana Liliana Pérez Cortés
Jenny Marcela Ruiz Duarte Algoritmos Minimax y Poda Alfa-Beta Minimax Definición Funcionamiento Aclaraciones Factores de evaluación Función de evaluación 1 Funciòn de evaluaciòn 2 El algoritmo MiniMax es el algoritmo más conocido para juegos de 2 adversarios, movimientos alternos.
En teoría de juegos, Minimax es un método de decisión para minimizar la pérdida máxima esperada en juegos con adversario; este cálculo se hace de forma recursiva. Identificaremos a cada jugador como el jugador MAX y el jugador MIN.
MAX será el jugador que inicia el juego (nosotros), y nuestro objetivo es encontrar el conjunto de movimientos que proporcionen la victoria independientemente de lo que haga el jugador MIN.
Deberá existir una función de evaluación heurística que devuelva valores elevados para indicar buenas situaciones, y valores negativos para indicar situaciones favorables al oponente. Pasos del Algoritmo Generación del árbol de juego. Se generarán todos los nodos hasta llegar a un estado terminal.
Cálculo de los valores de la función de utilidad para cada nodo terminal
Calcular el valor de los nodos superiores a partir del valor de los inferiores. Alternativamente se elegirán los valores mínimos y máximos representando los movimientos del jugador y del oponente, de ahí el nombre de Minimax.
Elegir la jugada valorando los valores que han llegado al nivel superior. Aplicación en el juego del triqui Dos jugadores
Los jugadores colocan fichas en un tablero de 3x3
El jugador uno usa las fichas
El jugador dos usa las fichas Reglas Inicialmente el tablero esta vacío
El jugador 1 empieza y se alternan los movimientos
El jugador 1 gana si obtiene una línea de 3
El jugador 2 gana si obtiene una línea de 3
Existe la posibilidad de empate Los estados finales se evalúan así:
1: si gana el jugador uno
0: si empatan
-1: si gana el jugador el dos Si s no es ganadora para cualquiera de los jugadores:
f(s)=Nùmero de filas, columnas o diagonales abiertas para jugador 1 menos el nùmero de filas, columnas o diagonales abiertas para el jugador 2.

esto es:

f(s)= Nùmero de lìneas que no contienen una
menos nùmero de lìneas que no contienen una Poda Alfa-Beta La poda alfa beta es una tècnica de bùsqueda que reduce el nùmero de nodos evaluados en un àrbol de juego por el algoritmo minimax. La tècnica de poda alfa-beta trata de eliminar partes grandes del àrbol, aplicàndolo a un àrbol minimax estàndar, de forma que se devuelva el mismo movimiento que devolverìa este gracias a que la poda de dichas ramas no influye en la decisiòn final. Desarrollo del algoritmo La poda alfa-beta toma dicho nombre de la utilizaciòn de dos paràmetros que describen los lìmites sobre los valores hacia atràs que aparecen a lo largo de cada camino.

ALFA es el valor de la mejor opciòn hasta el momento a lo largo del camino para MAX, esto implicarà por lo tanto la elecciòn del valor màs alto.

BETA es el valor de la mejor opciòn hasta el momento a lo largo del camino para MIN, esto implicarà por lo tanto la elecciòn del valor mas bajo.
Full transcript