Задать вопрос
  • Что можно ускорить в коде решателя игры крестики нолики?

    @nay34
    # Все выигрышные маски 3x3
    WIN_MASKS = [
    0b111000000, # ряд 1
    0b000111000, # ряд 2
    0b000000111, # ряд 3
    0b100100100, # колонка 1
    0b010010010, # колонка 2
    0b001001001, # колонка 3
    0b100010001, # диагональ \
    0b001010100 # диагональ /
    ]

    def is_win(mask: int) -> bool:
    """Проверка выигрыша через битовые маски"""
    return any((mask & w) == w for w in WIN_MASKS)

    memo = {} # кэш результатов

    def solve(xmask: int, omask: int, turn: int) -> int:
    """
    Рекурсивный minimax с мемоизацией
    xmask, omask – битовые маски X и O
    turn – чей ход: 1 (X) или -1 (O)
    Возвращает: 10 (X выиграл), -10 (O выиграл), 0 (ничья)
    """

    key = (xmask, omask, turn)
    if key in memo:
    return memo[key]

    # Проверка выигрыша
    if is_win(xmask):
    return 10
    if is_win(omask):
    return -10

    # Проверка ничьи
    if (xmask | omask) == 0b111111111: # все клетки заняты
    return 0

    # Ходы
    best = -100 if turn == 1 else 100
    free = ~(xmask | omask) & 0b111111111

    while free:
    move = free & -free # берём младший свободный бит
    free -= move
    if turn == 1: # ход X
    score = solve(xmask | move, omask, -1)
    best = max(best, score)
    else: # ход O
    score = solve(xmask, omask | move, 1)
    best = min(best, score)

    memo[key] = best
    return best

    if __name__ == "__main__":
    # Пустое поле: xmask=0, omask=0, ходит X (turn=1)
    result = solve(0, 0, 1)
    print("Оценка стартовой позиции:", result)
    print("Посчитано позиций:", len(memo))
    Ответ написан
    Комментировать