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

Question

[ffff567]

пока что код не внедрен в саму игру крестики нолики пока что просто тестирую скорость
Текущий код решает полным перебором позицию за 0.45 секунды в итоге создает дерево с оценками -10 проигрыш 0 ничья 10 выигрыш всего получается 55648 комбинаций. Нужно еще ускорить чтобы можно было решать крестики нолики на большом поле.

x=[0, 0, 0, 0, 0, 0, 0, 0, 0]

адреса={0:[[0,1,2],[0,4,8],[0,3,6]], 1:[[0,1,2],[1,4,7]], 2:[[0,1,2],[2,4,6],[2,5,8]],
        3:[[0,3,6],[3,4,5]], 4:[[0,3,6],[1,4,7],[0,4,8],[2,4,6],[3,4,5]], 5:[[2,5,8],[3,4,5]],
        6:[[0,3,6],[2,4,6],[6,7,8]], 7:[[6,7,8],[1,4,7]], 8:[[6,7,8],[0,4,8],[2,5,8]]}

словарь={}
словарь2={}

def выигрыш(i): 
    flag=False
    for num, k in enumerate(i):
        if not k:
            cop=i.copy()
            cop[num]=глубина
            for b in адреса[num]:
                if all(cop[ind]%2==очередь and cop[ind] for ind in b):
                    flag=True
                    словарь2[tuple(словарь[tuple(i)]+[num])]=10 if очередь%2 else -10
    if flag: return True
                
def перебор(позиция, hist):
    if выигрыш(позиция): return
    # if глубина!=9:
    #     if перекрытие(позиция): return   
    if глубина==9:
        for num, b in enumerate(позиция):
            if not b:словарь2[tuple(hist+[num])]=0
    else:
        for num, b in enumerate(позиция):
            if not b:
                dd=позиция.copy()
                dd[num]=глубина
                словарь[tuple(dd)]=hist+[num]


for глубина in [1,2,3,4,5,6,7,8,9]:
    очередь = глубина & 1
    if глубина==1:
        for num, b in enumerate(x):
            if not b:
                xx=x.copy()
                xx[num]=глубина
                словарь[tuple(xx)]=[num]
    else:
        for z,z1 in {**словарь}.items():
            перебор(list(z), z1)
            del словарь[z]

Comments

[Everything_is_bad]

Какую букву в игре поле чудес в этом случае лучше всего открыть?
Как написать код по другому или ускорить его?
и тебя кучу раз просили соблюдать хотя бы pep8

[Everything_is_bad]

и тебе уже отвечал что надо делать

Хочешь помощи, пиши нормальный код, почитай про pep8, а то на твой код без боли нельзя смотреть.

Ну и учись самостоятельно оптимизировать, начни с профилирования для поиска тяжелый мест. Хочешь помощи именно по алгоритмам, так сформулируй проблемное место.

https://qna.habr.com/answer?answer_id=2495392#answ...

[GavriKos]

1c в теги

[ffff567]

Everything_is_bad, уже улучшил с 0.68 секунды до 0.46 55648 комбинаций. В коде есть лишняя функция

[Алексей Уколов]

уже улучшил

Ну, теперь заживём.

Answer 1

[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))

Comments

[ffff567]

Что за фигня?
Оценка стартовой позиции: 10
Посчитано позиций: 7

[ffff567]

у меня самый продвинутый код уже улучшено до 0.125 секунды. Количество комбинаций первого хода 9856. А это чушь у тебя какая то