Игра «Крестики-нолики» · Шаг 5 из 5
Непобедимый бот
В крестиках-ноликах всего несколько тысяч позиций — компьютер успевает перебрать их все. Бот, который заглядывает до конца партии за себя и за соперника, не проигрывает никогда; лучший ваш результат против него — ничья.
Что сделать
Сделайте бота, который не проигрывает никогда, — перебором всех продолжений партии.
Что приходит
pole— поле, список рядовznak— каким знаком играет ботlinii— список линий из шага 2
Что вернуть
Клетку (ряд, столбец) с лучшей оценкой для бота; при равенстве — первую по рядам; свободных нет — None; как оценивать — в «Подробных правилах».
Допишите функцию luchshiy_hod в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
В игре
Игра зовёт luchshiy_hod на каждый ход бота. Решите шаг — и бот станет непобедимым: лучшее, что вы сможете, — ничья.
Без этого шага: непобедимого бота нет — None, и оболочка зовёт простого из шага 4.
Вы поставили крестик в середину. Бот («O») перебирает все продолжения: ход на сторону проигрывает при точной игре, ход в угол — ничья. Лучшая оценка у всех четырёх углов, и бот берёт первый из них по порядку — (0, 0).
L в проверке — восемь линий поля 3×3, как их строит второй шаг.
L = [[(0, 0), (0, 1), (0, 2)], [(1, 0), (1, 1), (1, 2)], [(2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0)], [(0, 1), (1, 1), (2, 1)], [(0, 2), (1, 2), (2, 2)], [(0, 0), (1, 1), (2, 2)], [(0, 2), (1, 1), (2, 0)]]
luchshiy_hod([[".", ".", "."], [".", "X", "."], [".", ".", "."]], "O", L)
(0, 0)
Функция принимает поле, знак бота и список линий. Возвращает лучший ход бота — клетку (ряд, столбец); если свободных клеток нет — None.
Ход оценивается перебором всех продолжений: соперник отвечает лучшим для себя, бот — лучшим для себя, и так до конца партии. Конец партии оценивается с точки зрения бота: его победа через k ходов, считая этот, — 10 − k, проигрыш через k ходов — k − 10, ничья — 0. Бот берёт ход с наибольшей оценкой, соперник — с наименьшей. Среди ходов с равной оценкой бот берёт первый по рядам сверху вниз, в ряду слева направо.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.