AO*

 class Node:

    def __init__(self, name, is_goal=False):

        self.name = name

        self.is_goal = is_goal

        self.children = []  # Children nodes (can be OR/AND groups)

        self.cost = float('inf')  # Cost initialized as infinity

        self.solved = False  # If this node is part of the solution

    def add_or_child(self, child):

        self.children.append([child])  # OR group: a single child

    def add_and_children(self, children):

        self.children.append(children)  # AND group: multiple children

def ao_star(node):

    """

    AO* algorithm to solve an AND-OR graph.

    :param node: The root node of the graph/tree.

    :return: Solution path and cost.

    """

    def recursive_ao_star(n):

        if n.is_goal:

            n.cost = 0

            n.solved = True

            return True

        if not n.children:  # Dead-end

            return False

        # Evaluate each child group (OR or AND group)

        for group in n.children:

            group_cost = 0

            all_solved = True

            for child in group:

                if not child.solved:

                    if not recursive_ao_star(child):

                        all_solved = False

                group_cost += child.cost

            # Update the cost and solved status

            if all_solved and group_cost < n.cost:

                n.cost = group_cost

                n.solved = True

                n.best_group = group

        return n.solved

    recursive_ao_star(node)

    # Reconstruct the solution path

    solution_path = []

    def extract_solution_path(n):

        if n.is_goal:

            solution_path.append(n.name)

            return

        solution_path.append(n.name)

        for child in getattr(n, 'best_group', []):

            extract_solution_path(child)

    extract_solution_path(node)

    return solution_path, node.cost

# Example Game Tree

# Constructing the graph

A = Node('A')  # Root

B = Node('B')

C = Node('C')

D = Node('D', is_goal=True)  # Goal node

E = Node('E', is_goal=True)  # Goal node

F = Node('F', is_goal=True)  # Goal node

G = Node('G')

# Building the AND-OR tree

A.add_or_child(B)

A.add_or_child(C)

B.add_and_children([D, E])

C.add_or_child(F)

C.add_or_child(G)

# Assigning costs to leaf nodes

D.cost = 2

E.cost = 3

F.cost = 1

G.cost = 5

# Running AO* on the tree

solution, cost = ao_star(A)

print("Solution Path:", solution)

print("Solution Cost:", cost)