#! /usr/bin/env python3
# -*- coding: utf-8 -*-

"""Illustrates the best case of alpha-beta vs. minimax. We assume a
uniform tree with alternating moves beginning with MAX, depth DEPTH
and branching factor BRANCHING_FACTOR.

One of the situations where we get the best case is when all terminal
positions have the same value, so we simply use a utility function
that is 0 everywhere. This simplifies the implementation of game
positions: the only thing we need to track is how far into the game we
are (how many moves by either play have been made).

More generally, for the best case it is sufficient that both players
always consider their best move first. If all moves are equally good
as in this example, this happens trivially.
"""

import time
from random import random


DEPTH = 8
BRANCHING_FACTOR = 10

RAND = False


class Statistics:
    def __init__(self):
        self.nodes = 0

    def increment_nodes(self):
        self.nodes += 1

    def __repr__(self):
        return("{} nodes".format(self.nodes))


def init():
    return 0


def is_terminal(p):
    return p == DEPTH


def utility(p):
    if RAND:
        return random()
    return 0


def player(p):
    if p % 2 == 0:
        return "MAX"
    else:
        return "MIN"


def succ(p):
    return (("move_{}".format(i), p + 1)
            for i in range(BRANCHING_FACTOR))


def minimax(p, stats):
    stats.increment_nodes()
    if is_terminal(p):
        return (utility(p), None)
    best_move = None
    if player(p) == "MAX":
        v = float("-inf")
    else:
        v = float("inf")
    for move, p_prime in succ(p):
        v_prime, best_move_prime = minimax(p_prime, stats)
        if (player(p) == "MAX" and v_prime > v or
            player(p) == "MIN" and v_prime < v):
            v = v_prime
            best_move = move
    return v, best_move


def alpha_beta(p, alpha, beta, stats):
    stats.increment_nodes()
    if is_terminal(p):
        return (utility(p), None)
    best_move = None
    if player(p) == "MAX":
        v = float("-inf")
    else:
        v = float("inf")
    for move, p_prime in succ(p):
        v_prime, best_move_prime = alpha_beta(p_prime, alpha, beta, stats)
        if (player(p) == "MAX" and v_prime > v or
            player(p) == "MIN" and v_prime < v):
            v = v_prime
            best_move = move
        if player(p) == "MAX":
            if v >= beta:
                return (v, None)
            alpha = max(alpha, v)
        if player(p) == "MIN":
            if v <= alpha:
                return (v, None)
            beta = min(beta, v)
    return v, best_move


def run_algorithm(name, func):
    stats = Statistics()
    start_time = time.perf_counter()
    result = func(stats)
    elapsed = time.perf_counter() - start_time
    print("{} result: {}".format(name, result))
    print("{} statistics: {}".format(name, stats))
    print("{} time: {:.3f} seconds".format(name, elapsed))


def run_minimax():
    run_algorithm("Minimax", lambda stats: minimax(init(), stats))


def run_alpha_beta():
    run_algorithm("AlphaBeta", lambda stats:
                  alpha_beta(init(), float("-inf"), float("inf"), stats))


def main():
    print("DEPTH = {}, BRANCHING_FACTOR = {}".format(DEPTH, BRANCHING_FACTOR))
    print()
    run_alpha_beta()
    print()
    run_minimax()


if __name__ == "__main__":
    main()

"""Output on dmi-borrow19 (run on 2025-05-19):

$ ./ai_g03_alpha_beta_best_case.py

DEPTH = 8, BRANCHING_FACTOR = 10

AlphaBeta result: (0, 'move_0')
AlphaBeta statistics: 34434 nodes
AlphaBeta time: 0.091 seconds

Minimax result: (0, 'move_0')
Minimax statistics: 111111111 nodes
Minimax time: 107.346 seconds
"""