# Все выигрышные маски 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))