matrix_det_game_tree_traversal.py

import collections
import functools
import time

import numpy as np


State = list[int]
StateImmutable = tuple[int]
Action = tuple[int, int]

def get_next_actions(state: State) -> list[Action]:
    n = len(state)
    is_used = [False] * n
    num_used = 0
    for item in state:
        if item != 0:
            is_used[item - 1] = True
            num_used += 1
    result = []
    if num_used < n:
        for i in range(n):
            if state[i] == 0:
                for item in range(1, n + 1):
                    if not is_used[item - 1]:
                        result.append((i, item))
    return result


@functools.cache
def state_score_cached(state: StateImmutable) -> int:
    n = len(state)
    m = np.sqrt(n).astype(int)
    matrix = np.array(state, dtype=int).reshape(m, m)
    nonzeros = np.count_nonzero(matrix)
    assert nonzeros == n, nonzeros
    det = np.linalg.det(matrix)
    if det > 0:
        return 1
    elif det < 0:
        return -1
    else:
        return 0


def state_score(state: State):
    return state_score_cached(tuple(state))


dfs_cache = {}


def dfs(state: State, depth: int = 0) -> int:
    state_tuple = tuple(state)
    if state_tuple not in dfs_cache:
        time_start = time.perf_counter()

        if depth <= 2:
            print('    ' * depth + str(state))

        actions = get_next_actions(state)
        child_scores = collections.defaultdict(list)
        for i, item in actions:
            state[i] = item
            child_score = dfs(state, depth + 1)
            child_scores[child_score].append((i, item))
            state[i] = 0

            # if child_score == -1:
            #     # Can force a win through this move.
            #     break

        if len(actions) == 0:
            score = state_score(state)
            good_next_states = []
        else:
            if child_scores[-1]:
                # There is a move that forces a win.
                score = 1
                good_next_states = child_scores[-1]
            elif child_scores[0]:
                # There is a move that forces a draw.
                score = 0
                good_next_states = child_scores[0]
            else:
                # All moves lead to a loss.
                assert len(child_scores[1]) == len(actions)
                score = -1
                good_next_states = child_scores[1]

        if depth <= 2:
            branch_time = time.perf_counter() - time_start
            if score == 0:
                outcome = 'draw'
            else:
                if len(actions) == 0:
                    moves_str = '<terminal node>'
                else:
                    moves_str = str(good_next_states) if len(good_next_states) < len(actions) else 'all moves'
                if (score == 1 and depth % 2 == 0) or (score == -1 and depth % 2 == 1):
                    outcome = f'first player wins in {state} through: {moves_str}'
                else:
                    outcome = f'second player wins in {state} through: {moves_str}'
            print('    ' * depth + f'-> [{branch_time:.2f} sec] ' + outcome)

        dfs_cache[state_tuple] = score
    else:
        score = dfs_cache[state_tuple]

    return score


initial_state = [0] * 9
dfs(initial_state)