El algoritmo de búsqueda Expectimax es un algoritmo de teoría de juegos utilizado para maximizar la utilidad esperada. Es una variación del algoritmo Minimax . Mientras que Minimax asume que el adversario (el minimizador) juega de manera óptima, Expectimax no lo hace. Esto es útil para modelar entornos donde los agentes adversarios no son óptimos o sus acciones se basan en el azar.
Expectimax vs Minimax
Considere el siguiente árbol Minimax:
Como sabemos que el agente adversario (minimizador) juega de manera óptima, tiene sentido ir a la izquierda. Pero, ¿qué pasa si existe la posibilidad de que el minimizador cometa un error (o no juegue de manera óptima)? Por lo tanto, ir a la derecha puede sonar más atractivo o puede resultar en una mejor solución.
En el siguiente árbol de Expectimax, hemos reemplazado los Nodes minimizadores por Nodes aleatorios.
Los Nodes Chance toman el promedio de todas las utilidades disponibles y nos dan la ‘utilidad esperada’. Por tanto, las utilidades esperadas para los subárboles izquierdo y derecho son (10+10)/2=10 y (100+9)/2=54,5. El Node maximizador elige el subárbol correcto para maximizar las utilidades esperadas.
Ventajas de Expectimax sobre Minimax:
- El algoritmo Expectimax ayuda a aprovechar los oponentes no óptimos.
- A diferencia de Minimax, Expectimax ‘puede correr un riesgo’ y terminar en un estado con una mayor utilidad ya que los oponentes son aleatorios (no óptimos).
Desventajas:
- Expectimax no es óptimo. Puede llevar a que el agente pierda (terminar en un estado con menor utilidad)
- Expectimax requiere que se explore el árbol de búsqueda completo. No se puede hacer ningún tipo de poda, ya que el valor de una única utilidad inexplorada puede cambiar drásticamente el valor de expectimax. Por lo tanto, puede ser lento.
- Es sensible a las transformaciones monótonas en los valores de utilidad.
Para minimax, si tenemos dos estados S 1 y S 2 , si S 1 es mejor que S 2 , las magnitudes de los valores de la función de evaluación f(S 1 ) y f(S 2 ) no importan mientras f( S 1 ) > f(S 2 ) .
Para expectimax, las magnitudes de los valores de la función de evaluación son importantes.
Algoritmo: Expectimax se puede implementar usando un algoritmo recursivo de la siguiente manera,
- Si la llamada actual es un Node maximizador, devuelve el máximo de los valores de estado de los Nodes sucesores.
- Si la llamada actual es un Node aleatorio, devuelve el promedio de los valores de estado de los Nodes sucesores (suponiendo que todos los Nodes tienen la misma probabilidad). Si diferentes Nodes tienen diferentes probabilidades, la utilidad esperada de allí está dada por ∑ i x i p i
- Llamamos a la función recursivamente hasta llegar a un Node terminal (el estado sin sucesores). Luego devuelva la utilidad para ese estado.
Implementación:
C++
// C++ program to illustrate
// Expectimax Algorithm
#include <iostream>
using namespace std;
// Structure to declare
// left and right nodes
struct Node {
int value;
struct Node *left, *right;
};
// Initializing Nodes to NULL
Node* newNode(int v)
{
Node* temp = new Node;
temp->value = v;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// Getting expectimax
float expectimax(Node* node, bool is_max)
{
// Condition for Terminal node
if (node->left == NULL
&& node->right == NULL) {
return node->value;
}
// Maximizer node. Chooses the max from the
// left and right sub-trees
if (is_max) {
return max(
expectimax(
node->left, false),
expectimax(node->right, false));
}
// Chance node. Returns the average of
// the left and right sub-trees
else {
return (
expectimax(node->left, true)
+ expectimax(node->right, true))
/ 2.0;
}
}
// Driver code
int main()
{
// Non leaf nodes.
// If search is limited
// to a given depth,
// their values are
// taken as heuristic value.
// But because the entire tree
// is searched their
// values don't matter
Node* root = newNode(0);
root->left = newNode(0);
root->right = newNode(0);
// Assigning values to Leaf nodes
root->left->left = newNode(10);
root->left->right = newNode(10);
root->right->left = newNode(9);
root->right->right = newNode(100);
float res = expectimax(root, true);
cout << "Expectimax value is "
<< res << endl;
return 0;
}
Java
// Java program to illustrate
// Expectimax Algorithm
class GFG{
// Structure to declare
// left and right nodes
static class Node {
int value;
Node left, right;
};
// Initializing Nodes to null
static Node newNode(int v)
{
Node temp = new Node();
temp.value = v;
temp.left = null;
temp.right = null;
return temp;
}
// Getting expectimax
static float expectimax(Node node, boolean is_max)
{
// Condition for Terminal node
if (node.left == null
&& node.right == null) {
return node.value;
}
// Maximizer node. Chooses the max from the
// left and right sub-trees
if (is_max) {
return Math.max(
expectimax(
node.left, false),
expectimax(node.right, false));
}
// Chance node. Returns the average of
// the left and right sub-trees
else {
return (float) ((
expectimax(node.left, true)
+ expectimax(node.right, true))
/ 2.0);
}
}
// Driver code
public static void main(String[] args)
{
// Non leaf nodes.
// If search is limited
// to a given depth,
// their values are
// taken as heuristic value.
// But because the entire tree
// is searched their
// values don't matter
Node root = newNode(0);
root.left = newNode(0);
root.right = newNode(0);
// Assigning values to Leaf nodes
root.left.left = newNode(10);
root.left.right = newNode(10);
root.right.left = newNode(9);
root.right.right = newNode(100);
float res = expectimax(root, true);
System.out.print("Expectimax value is "
+ res +"\n");
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to illustrate
# Expectimax Algorithm
# Structure to declare
# left and right nodes
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# Initializing Nodes to None
def newNode(v):
temp = Node(v);
return temp;
# Getting expectimax
def expectimax(node, is_max):
# Condition for Terminal node
if (node.left == None and node.right == None):
return node.value;
# Maximizer node. Chooses the max from the
# left and right sub-trees
if (is_max):
return max(expectimax(node.left, False), expectimax(node.right, False))
# Chance node. Returns the average of
# the left and right sub-trees
else:
return (expectimax(node.left, True)+ expectimax(node.right, True))/2;
# Driver code
if __name__=='__main__':
# Non leaf nodes.
# If search is limited
# to a given depth,
# their values are
# taken as heuristic value.
# But because the entire tree
# is searched their
# values don't matter
root = newNode(0);
root.left = newNode(0);
root.right = newNode(0);
# Assigning values to Leaf nodes
root.left.left = newNode(10);
root.left.right = newNode(10);
root.right.left = newNode(9);
root.right.right = newNode(100);
res = expectimax(root, True)
print("Expectimax value is "+str(res))
# This code is contributed by rutvik_56
C#
// C# program to illustrate
// Expectimax Algorithm
using System;
class GFG{
// Structure to declare
// left and right nodes
class Node {
public int value;
public Node left, right;
};
// Initializing Nodes to null
static Node newNode(int v)
{
Node temp = new Node();
temp.value = v;
temp.left = null;
temp.right = null;
return temp;
}
// Getting expectimax
static float expectimax(Node node, bool is_max)
{
// Condition for Terminal node
if (node.left == null
&& node.right == null) {
return node.value;
}
// Maximizer node. Chooses the max from the
// left and right sub-trees
if (is_max) {
return Math.Max(
expectimax(
node.left, false),
expectimax(node.right, false));
}
// Chance node. Returns the average of
// the left and right sub-trees
else {
return (float) ((
expectimax(node.left, true)
+ expectimax(node.right, true))
/ 2.0);
}
}
// Driver code
public static void Main(String[] args)
{
// Non leaf nodes.
// If search is limited
// to a given depth,
// their values are
// taken as heuristic value.
// But because the entire tree
// is searched their
// values don't matter
Node root = newNode(0);
root.left = newNode(0);
root.right = newNode(0);
// Assigning values to Leaf nodes
root.left.left = newNode(10);
root.left.right = newNode(10);
root.right.left = newNode(9);
root.right.right = newNode(100);
float res = expectimax(root, true);
Console.Write("Expectimax value is "
+ res +"\n");
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program to illustrate Expectimax Algorithm
// Structure to declare
// left and right nodes
class Node
{
constructor(v) {
this.left = null;
this.right = null;
this.value = v;
}
}
// Initializing Nodes to null
function newNode(v)
{
let temp = new Node(v);
return temp;
}
// Getting expectimax
function expectimax(node, is_max)
{
// Condition for Terminal node
if (node.left == null
&& node.right == null) {
return node.value;
}
// Maximizer node. Chooses the max from the
// left and right sub-trees
if (is_max) {
return Math.max(
expectimax(
node.left, false),
expectimax(node.right, false));
}
// Chance node. Returns the average of
// the left and right sub-trees
else {
return ((
expectimax(node.left, true)
+ expectimax(node.right, true))
/ 2.0);
}
}
// Non leaf nodes.
// If search is limited
// to a given depth,
// their values are
// taken as heuristic value.
// But because the entire tree
// is searched their
// values don't matter
let root = newNode(0);
root.left = newNode(0);
root.right = newNode(0);
// Assigning values to Leaf nodes
root.left.left = newNode(10);
root.left.right = newNode(10);
root.right.left = newNode(9);
root.right.right = newNode(100);
let res = expectimax(root, true);
document.write("Expectimax value is " + res);
// This code is contributed by mukesh07.
</script>
Producción:
Expectimax value is 54.5
Complejidad temporal : O(b m )
Complejidad espacial : O(b*m), donde b es el factor de ramificación y m es la profundidad máxima del árbol.
Aplicaciones: Expectimax se puede utilizar en entornos donde las acciones de uno de los agentes son aleatorias. Los siguientes son algunos ejemplos,
- En Pacman , si tenemos fantasmas aleatorios, podemos modelar Pacman como el maximizador y los fantasmas como Nodes aleatorios. Los valores de utilidad serán los valores de los estados terminales (ganar, perder o empatar) o el valor de la función de evaluación para el conjunto de estados posibles a una profundidad dada.
- Podemos crear una IA de buscaminas modelando al agente del jugador como el maximizador y las minas como Nodes de oportunidad.