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

Python

1 ответ

Сейчас ситуация такая: пока что код не внедрен в саму игру крестики нолики пока что просто тестирую скорость
По вводным: текущий код решает полным перебором позицию за 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]

Нужно решить такую задачу?

Опишите проблему, и специалист поможет с настройкой, исправлением ошибки или доработкой сайта. Подберём понятный план работ без лишней переписки.

Заказать помощь

Лучший ответ

Андрей PHP Ответ

Для обычных крестиков-ноликов 3x3 полный перебор за 0.45 секунды уже медленнее, чем должен быть: таких позиций мало, и решатель обычно работает почти мгновенно. Основные ускорения: не копировать списки на каждом ходе без необходимости, хранить позицию компактно, использовать memoization по состоянию, alpha-beta pruning и заранее проверять победу только по линиям последнего хода.

Главная проблема для “большого поля” в том, что полный перебор взрывается комбинаторно. Для 3x3 можно решить всё дерево, для 10x10 уже нельзя. Там нужен minimax с ограничением глубины и эвристической оценкой позиции, а не полный перебор до конца игры.

Для 3x3 минимальная оптимизация - кешировать состояние tuple(board):

WIN_LINES = [
    (0, 1, 2), (3, 4, 5), (6, 7, 8),
    (0, 3, 6), (1, 4, 7), (2, 5, 8),
    (0, 4, 8), (2, 4, 6),
]
 
cache = {}
 
def winner(board):
    for a, b, c in WIN_LINES:
        if board[a] and board[a] == board[b] == board[c]:
            return board[a]
    return 0
 
def solve(board, player):
    key = (tuple(board), player)
    if key in cache:
        return cache[key]
 
    w = winner(board)
    if w:
        return 10 if w == player else -10
    if all(board):
        return 0
 
    best = -100
    next_player = 2 if player == 1 else 1
    for i, cell in enumerate(board):
        if cell == 0:
            board[i] = player
            score = -solve(board, next_player)
            board[i] = 0
            best = max(best, score)
 
    cache[key] = best
    return best

WIN_LINES = [ (0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6), ] cache = {} def winner(board): for a, b, c in WIN_LINES: if board[a] and board[a] == board[b] == board[c]: return board[a] return 0 def solve(board, player): key = (tuple(board), player) if key in cache: return cache[key] w = winner(board) if w: return 10 if w == player else -10 if all(board): return 0 best = -100 next_player = 2 if player == 1 else 1 for i, cell in enumerate(board): if cell == 0: board[i] = player score = -solve(board, next_player) board[i] = 0 best = max(best, score) cache[key] = best return best

Для большого поля добавьте alpha-beta и глубину:

def search(board, depth, alpha, beta, player):
    if depth == 0 or is_terminal(board):
        return evaluate(board, player)
 
    for move in ordered_moves(board):
        make_move(board, move, player)
        score = -search(board, depth - 1, -beta, -alpha, other(player))
        undo_move(board, move)
        alpha = max(alpha, score)
        if alpha &gt;= beta:
            break
    return alpha

def search(board, depth, alpha, beta, player): if depth == 0 or is_terminal(board): return evaluate(board, player) for move in ordered_moves(board): make_move(board, move, player) score = -search(board, depth - 1, -beta, -alpha, other(player)) undo_move(board, move) alpha = max(alpha, score) if alpha >= beta: break return alpha

Еще сильное ускорение дает генерация только “разумных” ходов: рядом с уже занятыми клетками, а не по всему полю. Для 15x15/Gomoku обычно оценивают линии, угрозы, открытые тройки/четверки и глубину 2-6 ходов. Полное дерево для большого поля не решается практически.

Итог: для 3x3 достаточно tuple-cache и проверки победных линий. Для большого поля меняйте подход: эвристика, ограниченная глубина, alpha-beta, ordered moves и генерация ходов около существующих фигур.

Другие ответы (0)

Пока нет других ответов. Будьте первым, кто поможет автору.

Ответить на вопрос

комментарий Отменить ответ

Вам также может быть интересно

VPN Как правильно настроить vless для Android TV? 1 ответ Pyrogram Как правильно зарегистрировать юзер бота в Telegram? 1 ответ печатные-платы Как заставить запускаться программу M3.exe от компании Hanxing AOI в инспекционной машине на Windows 7 Pro? 1 ответ Linux Как диагностировать зависание RK3568 U-boot на Starting kernel? 1 ответ

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

комментарий Отменить ответ

Вам также может быть интересно

Ежедневно, круглосуточно