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:

Información perfecta:Un juego con la información perfecta es aquel en el que los agentes pueden mirar el tablero completo. Los agentes tienen toda la información sobre el juego y también pueden ver los movimientos de los demás. Algunos ejemplos son ajedrez, damas, go, etc.Información imperfecta:Si en un juego los agentes no tienen toda la información sobre el juego y no son conscientes de lo que está sucediendo, este tipo de juegos se denominan juegos con información imperfecta, como tres en raya, acorazado, ciego, puente, etc.Juegos deterministas:Los juegos deterministas son aquellos juegos que siguen un patrón estricto y un conjunto de reglas para los juegos, y no hay aleatoriedad asociada con ellos. Algunos ejemplos son ajedrez, damas, go, tres en raya, etc.Juegos no deterministas:Los no deterministas son aquellos juegos que tienen varios eventos impredecibles y tienen un factor de azar o suerte. Este factor de azar o suerte se introduce mediante dados o cartas. Estos son aleatorios y cada respuesta de acción no es fija. Estos juegos también se denominan juegos estocásticos.
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:

Estado inicial:Especifica cómo se configura el juego al principio.Jugador(es):Especifica qué jugador se ha movido en el espacio de estados.Comportamiento):Devuelve el conjunto de movimientos legales en el espacio de estados.Resultado(s, a):Es el modelo de transición, que especifica el resultado de los movimientos en el espacio de estados.Prueba(s) de terminal:La prueba terminal es verdadera si el juego ha terminado; de lo contrario, es falsa en cualquier caso. El estado donde termina el juego se llama estados terminales.Utilidad(es, p):Una función de utilidad da el valor numérico final de un juego que termina en estados terminales s para el jugador p. También se le llama función de pago. En el ajedrez, los resultados son victoria, derrota o empate y sus valores de pago son +1, 0, ½. Y para el tres en raya, los valores de utilidad son +1, -1 y 0.

Á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: