La búsqueda adversaria es una búsqueda en la que examinamos el problema que surge cuando intentamos planificar por delante del mundo y otros agentes están planeando en nuestra contra.
ubuntu que comando
- En temas anteriores hemos estudiado las estrategias de búsqueda que sólo están asociadas a un único agente que tiene como objetivo encontrar la solución que muchas veces se expresa en forma de una secuencia de acciones.
- Sin embargo, puede haber algunas situaciones en las que más de un agente esté buscando la solución en el mismo espacio de búsqueda, y esta situación suele ocurrir en el juego.
- El ambiente con más de un agente se denomina entorno multiagente , en el que cada agente es oponente de otro agente y juega entre sí. Cada agente necesita considerar la acción de otro agente y el efecto de esa acción en su desempeño.
- Entonces, Las búsquedas en las que dos o más jugadores con objetivos contradictorios intentan explorar el mismo espacio de búsqueda de la solución se denominan búsquedas adversarias, a menudo conocidas como juegos. .
- Los juegos se modelan como un problema de búsqueda y una función de evaluación heurística, y estos son los dos factores principales que ayudan a modelar y resolver juegos en IA.
Tipos de juegos en IA:
| determinista | Movimientos aleatorios | |
|---|---|---|
| Información perfecta | Ajedrez, Damas, vamos, Otelo | Backgammon, monopolio |
| información imperfecta | Acorazados, ciegos, tres en raya | Bridge, póquer, scrabble, guerra nuclear |
Ejemplo: Backgammon, Monopoly, Poker, etc.
Nota: En este tema, analizaremos los juegos deterministas, el entorno totalmente observable, la suma cero y donde cada agente actúa alternativamente.
Juego de suma cero
- Los juegos de suma cero son una búsqueda adversarial que implica pura competencia.
- En el juego de suma cero, la ganancia o pérdida de utilidad de cada agente se equilibra exactamente con las pérdidas o ganancias de utilidad de otro agente.
- Un jugador del juego intenta maximizar un valor único, mientras que el otro jugador intenta minimizarlo.
- Cada movimiento de un jugador en el juego se denomina jugada.
- El ajedrez y el tres en raya son ejemplos de juegos de suma cero.
Juego de suma cero: pensamiento integrado
El juego de suma cero implicaba un pensamiento integrado en el que un agente o jugador intentaba descubrir:
- Qué hacer.
- Cómo decidir la mudanza
- Necesita pensar también en su oponente.
- El oponente también piensa qué hacer.
Cada uno de los jugadores intenta descubrir la respuesta de su oponente a sus acciones. Esto requiere pensamiento integrado o razonamiento inverso para resolver los problemas del juego en la IA.
Formalización del problema:
Un juego se puede definir como un tipo de búsqueda en IA que puede formalizarse con los siguientes elementos:
Árbol de juego:
Un árbol de juego es un árbol donde los nodos del árbol son los estados del juego y los bordes del árbol son los movimientos de los jugadores. El árbol de juego implica el estado inicial, la función de acción y la función de resultado.
Ejemplo: árbol del juego Tic-Tac-Toe:
La siguiente figura muestra parte del árbol de juego del juego de tres en raya. A continuación se detallan algunos puntos clave del juego:
- Hay dos jugadores MAX y MIN.
- Los jugadores tienen un turno alternativo y comienzan con MAX.
- MAX maximiza el resultado del árbol de juego
- MIN minimiza el resultado.
Explicación de ejemplo:
- Desde el estado inicial, MAX tiene 9 movimientos posibles ya que comienza primero. MAX coloca x y MIN coloca o, y ambos jugadores juegan alternativamente hasta llegar a un nodo de hoja donde un jugador tiene tres seguidos o todos los cuadrados están llenos.
- Ambos jugadores calcularán cada nodo, minimax, el valor minimax que es la mejor utilidad posible contra un adversario óptimo.
- Supongamos que ambos jugadores conocen bien el tres en raya y realizan la mejor jugada. Cada jugador hace todo lo posible para evitar que otro gane. MIN actúa contra Max en el juego.
- Entonces, en el árbol del juego, tenemos una capa de Max, una capa de MIN, y cada capa se llama así Capa . Max coloca x, luego MIN pone o para evitar que Max gane, y este juego continúa hasta el nodo terminal.
- En esto, MIN gana, MAX gana o es un empate. Este árbol de juego es todo el espacio de búsqueda de posibilidades en el que MIN y MAX van jugando al tres en raya y turnándose alternativamente.
Por lo tanto, la búsqueda contradictoria del procedimiento minimax funciona de la siguiente manera:
- Su objetivo es encontrar la estrategia óptima para que MAX gane el juego.
- Sigue el enfoque de búsqueda en profundidad.
- En el árbol del juego, el nodo de hoja óptimo podría aparecer en cualquier profundidad del árbol.
- Propague los valores minimax hasta el árbol hasta que se descubra el nodo terminal.
En un árbol de juego determinado, la estrategia óptima se puede determinar a partir del valor minimax de cada nodo, que se puede escribir como MINIMAX(n). MAX prefiere pasar a un estado de valor máximo y MIN prefiere pasar a un estado de valor mínimo entonces:
