morpion.py

import random
import time

class Node:
    def __init__(self, parent, grid, depth):
        self.parent = parent
        self.grid = grid
        self.depth = depth
        self.children = []
        self.outcome = None

    def add_child(self, child):
        self.children.append(child)

    def build(self):
        if self.grid.get_winner() is not None: return
        for i in range(3):
            for j in range(3):
                if self.grid[i, j] is None:
                    child_grid = self.grid.copy()
                    child_grid[i, j] = 'X' if self.depth % 2 == 0 else 'O'
                    child = Node(self, child_grid, self.depth + 1)
                    self.add_child(child)
                    child.build()

    def get_children(self):
        """ Return all children nodes recursively """
        children = []
        for child in self.children:
            children.append(child)
            children += child.get_children()
        return children

    def get_only_moves(self):
        """ Return None if the node leads to different outcomes, else return the outcome """
        if not self.children:
            self.outcome = self.grid.get_winner()
        else:
            outcomes = set(child.get_only_moves() for child in self.children)
            if len(outcomes) == 1:
                self.outcome = outcomes.pop()
        return self.outcome

    def is_higher_only_move(self):
        return self.parent is None or self.parent.outcome is None


class Tree:
    def __init__(self, grid):
        self.root = Node(None, grid, 1)
        self.nodes = [self.root]

    def construct(self):
        self.root.build()
        self.nodes = [self.root]+self.root.get_children()

    def get_only_moves(self):
        self.root.get_only_moves()
        dic = {}
        for node in self.nodes:
            if node.outcome is not None and node.is_higher_only_move():
                if node.outcome in dic.keys(): dic[node.outcome].append(node)
                else: dic[node.outcome] = [node]
        return dic

    def __iter__(self):
        return iter(self.nodes)

class Analyzer:
    pass

class Grid:
    def __init__(self, grid=None):
        if grid is None:
            grid = [[None for _ in range(3)] for _ in range(3)]
        self.grid = grid

    def get_winner(self):
        win_patterns = [
                           # Rows
                           [(i, j) for j in range(3)] for i in range(3)
                       ] + [
                           # Columns
                           [(j, i) for j in range(3)] for i in range(3)
                       ] + [
                           # Diagonals
                           [(i, i) for i in range(3)],
                           [(i, 2 - i) for i in range(3)]
                       ]

        for pattern in win_patterns:
            values = [self.grid[i][j] for i, j in pattern]
            if all(values) and len(set(values)) == 1:
                return values[0]

        if all(all(cell for cell in row) for row in self.grid):
            return 'draw'
        return None

    def copy(self):
        return Grid([[cell for cell in row] for row in self.grid])

    def __setitem__(self, key, value):
        if type(key) == tuple:
            self.grid[key[0]][key[1]] = value
            return
        raise ValueError('Invalid key')

    def __getitem__(self, key):
        if type(key) == tuple:
            return self.grid[key[0]][key[1]]
        raise ValueError('Invalid key')

    def __str__(self):
        return '\n'.join('|'.join(cell or '.' for cell in row) for row in self.grid)

def print_tree(node, prefix="", is_last=True):
    """ Affiche l'arbre de décision sous forme ASCII """
    connector = "└── " if is_last else "├── "
    print(prefix + connector + f"[{node.depth}] Grid: {node.grid.grid or '?'}")

    prefix += "    " if is_last else "│   "

    child_count = len(node.children)
    for i, child in enumerate(node.children):
        print_tree(child, prefix, i == child_count - 1)

if __name__ == "__main__":

    grid = Grid()
    tree = Tree(grid)
    start = time.time()
    tree.construct()
    print(f"Time: {time.time()-start}s")

    print(len(tree.nodes))
    only_moves = tree.get_only_moves()
    # stats
    for name, value in only_moves.items():
        value = [node for node in value if node.grid.get_winner() is None]
        print('')
        print(f"{name}: {len(value)}")
        min1 = min(node.depth for node in value)
        print(f"Less depth {min1}")
        print("Avg children: ", sum(len(node.children) for node in value)/len(value))
        random_node = random.choice([i for i in value if i.depth == min1])
        print(random_node.grid)
        print_tree(random_node)