Python. Напишем морской бой с достойным соперником-ИИ

Всем привет! В предыдущей статье мы написали игру в спички с ИИ. Как оказалось некоторые из вас даже открывали эту сатью, а некоторые из тех кто открывал даже поставили лайк. Спасибо! Сегодня будем писать морской бой в таком же «терминальном» стиле. На этот раз игра будет больше, а алгоритм стоящий за ходом противника — сложнее.

Ознакомиться с полным кодом приложения и запустить прямо в браузере можно как всегда в конце статьи по ссылке.

Вот предыдущая статья про спички если кому-то интересно:

dtf.ru

Python. Напишем игру в спички с хардкорным ИИ — Офтоп на DTF

Возможно многие из вас играли в детстве в игру "спички" или "палочки" где игроки по очереди убирают с поля от 1 до 3 спичек. Проигравшим считается тот кто возьмет последнюю спичку. Игра достаточно примитивная, поэтому меня заинтересовала возможность написать для нее ИИ. Ну и соответственно саму игру в довесок :)

Прошлое приложение заняло 130 строк кода и я таки умудрился расписать его целиком в рамках поста, а вот морской бой уже получился на все 470+ строк. Всё расписать не получится. Будут расширеные комментарии внутри самого кода по ссылке. Как всегда начнём с самого морского боя, а ИИ (я буду называть это ИИ) оставим на вторую половину.

Сама игра не такая уж и сложная, но в ней хватает нюансов и если писать всё более-менее аккуратно, то получается много кода. В основном это связано с различными проверками при расстановке кораблей, доступности хода, проверками целости кораблей и прочее.

Начнём пожалуй с описания основных классов, которые нам понадобятся для реализации:

Game - сама игра. Этот класс будет группировать и манипулировать остальными классами.

Player — игрок. Будет иметь своё поле, будет совершать ходы.

Field - поле. Будет состоять из двух частей: основная карта и радар. Поле будет проверять возможность расположения кораблей, расставлять корабли, уничтожать их.

Ship - корабль. Можно было обойтись без него на самом деле, но с ним проще. В основном корабль будет хранить координаты и свои HP.

Кроме основных классов так же были написаны вспомогательные FieldPart — чтобы было проще обращаться к конкретной части поля (карта/радар). Color — чтобы было проще и нагляднее задавать цвет элементам. Cell — чтобы описать все возможные состояния клетки поля в одном месте (пустая, сыграная, корабль, уничтоженый корабль, поврежденный корабль).

class Game(object): letters = ("A", "B", "C", "D", "E", "F", "G", "H", "I", "J") ships_rules = [1, 1, 1, 1, 2, 2, 2, 3, 3, 4] field_size = len(letters) def __init__(self): self.players = [] self.current_player = None self.next_player = None self.status = 'prepare' # просто названия функций входящих в Game # сами функции с детальным описанием можно найти в полном коде def start_game(self) def status_check(self) def add_player(self, player) def ships_setup(self, player) def draw(self) def switch_players(self) def clear_screen()

В классе Game мы опишем буквы используемые для отображения координат. Понятное дело внутри самой игры всё задаётся исключительно цифровыми координатами [0][4], [5][1] … но игрок должен во-первых видеть буквы на поле, а во-вторых делать свои ходы используя буквенные обозначения. Поэтому без букв никак. ships_rules - в эту переменную поместим «правила» по кораблям, какие корабли игрок должен выставить до начала боя (здесь можно немного поэкспериментировать при желании: ). field_size - величина поля. Сделаем зависимость от величины списка letters. Поле ведь квадратное, а значит сколько букв — такие и габариты.

Игра будет хранить игроков в cписке players. Но зачем мучиться с коэффициентами при обращении к игрокам, если можно завести две переменные current_player и next_player,которые ссылаются на элементы списка players. Так мы всегда понимает как обратиться к текущему и следующему игроку. А в конце хода мы просто меняем значения этих переменных местами. Ну и я решил добавить такое понятие как status. У игры не то чтобы много статусов, но таким образом можно организовать более наглядный переход из одного состояния в другое в самом игровом цикле. Статусы будут примерно такие: prepare, in_game, game_over.

Функции у игры следующие:

start_game - просто объявляем текущего игрока и следующего.

status_check - игра каждый ход проверяет статусы и меняет их при достижении условий.

add_player - функция используется когда у игры статус prepare для добавления игроков и назначени им полей.

ship_setup - так же используется на старте игры. Передаём в функцию ссылку на игрока и игра просит его расставить корабли или расставляет автоматически. draw — рисует каждый ход поле и доп.инфу. switch_players — просто переключает текущего игрока и следующего, юзается в конце хода. clear_screen — чистит экран.

class Player(object): def __init__(self, name, is_ai, skill): self.name = name self.is_ai = is_ai self.auto_ship_setup = True self.skill = skill self.message = [] self.ships = [] self.enemy_ships = [] self.field = None # просто названия функций входящих в Player # сами функции с детальным описанием можно найти в полном коде def get_input(self, input_type) def make_shot(self, target_player) def receive_shot(self, shot)

Кратенько по игроку. name - просто имя. is_ai - является игрок ИИ или нет, в зависимости от этого меняет некоторая логика хода. auto_ship_setup - автоматически расставлять корабли для игрока или вручную. Опция для нетерпеливых. skill - относится к ИИ пока пропустим описание. ships наполняется имеющимися у игрока кораблями. enemy_ships - здесь будем считать какие корабли остались у противника — человек конечно и сам может посчитать, но для ИИ очень полезно. field - поле игрока (поле будет описано ниже)

Функции у игрока: get_input — запросить ввод. здесь мы передаем тип инпута либо 'ship_setup' либо 'shot'. Всё зависит от статуса игры. Много логики внутри, тут лучше почитать код с комментами. make_shot - делаем выстрел по указанному игроку. В этой функции как раз и вызывается get_input с параметром 'shot'. receive_shot - соответственно игрок принимает выстрел по координатам. На самом деле если чётко расписать действия игроков на бумаге и чем они оперируют в ходе игры всё становится гораздо очевиднее. receive_shot возвращает на выходе либо 'miss' (прмах) либо 'get' (ранил) либо ссылку на объект Ship (убил). Если убил логично вернуть весь корабль т.к. тогда проще закрасить на радаре клетки вокруг. Да, это конечно дерзко возвращать данные разных типов, но что поделать.

class Field(object): def __init__(self, size): self.size = size self.map = [[Cell.empty_cell for _ in range(size)] for _ in range(size)] self.radar = [[Cell.empty_cell for _ in range(size)] for _ in range(size)] self.weight = [[1 for _ in range(size)] for _ in range(size)] # просто названия функций входящих в Field # сами функции с детальным описанием можно найти в полном коде def draw_field(self, element) def check_ship_fits(self, ship, element) def mark_destroyed_ship(self, ship, element) def add_ship_to_field(self, ship, element) def get_max_weight_cells(self) def recalculate_weight_map(self, available_ships)

С полем всё просто: size - размер поля. map - основная карта поля по факту просто список списков изначально заполняемый пустыми клетками (Cell.empty_cell). radar - так же. weight уже по интереснее. Это относится к ИИ, поэтому обсудим чуть ниже.

Функции. draw_field - отрисовка поля. Здесь и далее параемтр element это часть поля с которой необходимо работать. либо Map либо Radar либо Weight. Check_ship_fits - прверяем что корабль помещается на ту или иную позицию. Используется при расстановке кораблей а так же для некоторых манипуляций с ИИ. mark_destroyed_ship - помечаем что корабль уничтожен. Ставим на нем кресты, вокруг — точки. add_ship_to_field - добавление корабля. тут все понятно. get_max_weight_cells и recalculate_weight_map относится к ИИ, это рассмотрим чуть ниже.

class Ship: def __init__(self, size, x, y, rotation): self.size = size self.hp = size self.x = x self.y = y self.rotation = rotation

Тут вообще всё до безобразия просто: x, y — координаты начала корабля. size - размер. rotation — в какую сторону повёрнут (от 0 до 4). hp — текущее хп корабля. Конкретные поврежденные клетки не отслеживаются т.к. по факту за контроль отрисовки поля отвечает класс Field.

Последнее что мы рассмотрим перед написанием ИИ это основной цикл игры:

if __name__ == '__main__': players = [] players.append(Player(name='Username', is_ai=False, auto_ship=True, skill=1)) players.append(Player(name='IQ180', is_ai=True, auto_ship=True, skill=1)) game = Game() while True: game.status_check() if game.status == 'prepare': game.add_player(players.pop(0)) if game.status == 'in game': Game.clear_screen() game.current_player.message.append("Ждём приказа: ") game.draw() game.current_player.message.clear() shot_result = game.current_player.make_shot(game.next_player) if shot_result == 'miss': game.next_player.message.append('На этот раз {}, промахнулся! '.format(game.current_player.name)) game.next_player.message.append('Ваш ход {}!'.format(game.next_player.name)) game.switch_players() continue elif shot_result == 'retry': game.current_player.message.append('Попробуйте еще раз!') continue elif shot_result == 'get': game.current_player.message.append('Отличный выстрел, продолжайте!') game.next_player.message.append('Наш корабль попал под обстрел!') continue elif shot_result == 'kill': game.current_player.message.append('Корабль противника уничтожен!') game.next_player.message.append('Плохие новости, наш корабль был уничтожен :(') continue if game.status == 'game over': Game.clear_screen() game.next_player.field.draw_field(FieldPart.main) game.current_player.field.draw_field(FieldPart.main) print('It was the last ship of {}'.format(game.next_player.name)) print('{} win the match! Congrats!'.format(game.current_player.name)) break print('Thanks for playing!') input('')

Все достаточно просто. В цикле бесконечно проверяется статус игры и в зависимости от этого выполняются те либо иные действия. В статусе 'in game' происходят основные события игры. Получение данных о выстреле игрока, добавление подходящего сообщения для обоих игроков, передача хода другому игроку при промахе и прочее.

Если наступает статус 'game over' — выводим основные поля обоих игроков. Пишем кто выиграл, кто проиграл.

Как всегда я сел и стал прикидывать какой логикой оперирует человек при игре в морской бой.

Первый ход случайный.
Если попал и убил — обрисовал точками вокруг
Если попал и не убил — стреляем в клетки сверху/снизу/слева/справа
По диагоналям от клетки «попал» не может быть кораблей
Прикидываем если остались только большие корабли — затираем мелкие скопления пустых клеток

Более глубокой логики поведения человека я придумать не смог. Дальше начал думать как перенести всё это на какие-то условия. Надо бы держать в уме предыдущий ход, а еще лучше предыдущий удачный ход. И если ты «попал», то следующий выстрел по сторонам. Если второй выстрел не попал, то вернуться к предыдущему ходу и выстрел в другую сторону рядом. Но дальше начинаютя сложности. Так как нужно понимать, что корабль прямой. Значит надо, чтобы ИИ понимал направление корабля и ходил после повторного попадания уже не по четырём направлениям, а в общем-то по одному. И опять-таки приходим к тому, что нужно помнить откуда начался этот корабль. Но это всё просто по сравнению с последним пунктом. Дойдя до него я понял: прежде чем стрелять по клетке — проверь, а помещается ли какой-нибудь корабль хоть как-то в нее.

И тут рассуждения увели меня чуть в сторону и стала вырисовываться идея коэффициентов: назначаем клеткам коэффициенты и стреляем по наиболее весомой. Если корабль помещается в какие-то клетки — прибавляем им коэффициенты. Если нет — коэффициент останется нулевым. Функция check_ship_fits уже была готова т.к. использовалась для расстановки кораблей до начала игры. Отлично.

Я начал развивать идею с коэффициентами. Решил так: изначально каждую клетку поля проверяем на возможность начала с нее корабля. Причем в любую из четырёх сторон. Итого клетка за каждый корабль может получить 4 балла. Естественно речь про поле-радар, единственно доступная информация о кораблях противника расположена на нем. Со временем поле будет заполнятья убитыми кораблями и промахами а коэффициенты этих клеток будут автоматически иметь 0.

Далее в систему коэффициентов нужно как-то вписать все пункты алгоритма:

«Первый ход случайный» — с введением коэффициентов это понятие немного изменится. Теперь каждый ход будет набираться список клеток с самым высоким коэффицентом, а уже из него будет случайным образом выбираться точка обстрела. Зачастую будет получатья так, что список будет состоять из одной единственной клетки которая методом подсчета получила максимальный коэффициент. Так что в целом становитя не важно первый это ход или нет.

«Если попал и убил» — тоже просто. В таких случаях клетке сразу ставится коэффициент 0 как и всем клеткам вокруг нее.

здесь и далее приведен небольшой кусочек поля

«Если попал и не убил» — мы усиливаем вес клеток по всем четырём направлениям т.к. корабль может иметь продолжение только в 4 стороны. По диагоналям от попадения — нули. Тут есть хитрость. Мы не просто выставляем коэффицинет всем вокруг мы умножаем имеющийся, а значит защищаем себя от возможности случайно увеличить нулевой кэффициент

первое попадание. увеличиваем коэффициенты

Ну и последний пункт — если остались только большие корабли — затираем мелкие скопления пустых клеток. Это будет выполняться на основе начального вычисления коэффициентов. Для каждой клетки будут браться оставшиеся корабли и будет совершаться попытка их вписать. Пример:

остался только трехпалубный корабль и как бы мы ни старались он не может проходить через клетку с «?» значит эта клетка не получит увеличения коэффицинета. И как результат коэффициент там будет 0. То же справедливо и для двух незанятых клеток чуть ниже.

Теперь осталось всего лишь написать это:

# пересчет веса клеток def recalculate_weight_map(self, available_ships): # Для начала мы выставляем всем клеткам 1. # нам не обязательно знать какой вес был у клетки в предыдущий раз: # эффект веса не накапливается от хода к ходу. self.weight = [[1 for _ in range(self.size)] for _ in range(self.size)] # Пробегаем по всем полю. # Если находим раненый корабль - ставим клеткам выше ниже и по бокам # коэффициенты умноженые на 50 т.к. логично что корабль имеет продолжение в одну из сторон. # По диагоналям от раненой клетки ничего не может быть - туда вписываем нули for x in range(self.size): for y in range(self.size): if self.radar[x][y] == Cell.damaged_ship: self.weight[x][y] = 0 if x - 1 >= 0: if y - 1 >= 0: self.weight[x - 1][y - 1] = 0 self.weight[x - 1][y] *= 50 if y + 1 < self.size: self.weight[x - 1][y + 1] = 0 if y - 1 >= 0: self.weight[x][y - 1] *= 50 if y + 1 < self.size: self.weight[x][y + 1] *= 50 if x + 1 < self.size: if y - 1 >= 0: self.weight[x + 1][y - 1] = 0 self.weight[x + 1][y] *= 50 if y + 1 < self.size: self.weight[x + 1][y + 1] = 0 # Перебираем все корабли оставшиеся у противника. # Это открытая инафа исходя из правил игры. Проходим по каждой клетке поля. # Если там уничтоженый корабль, задамаженый или клетка с промахом - # ставим туда коэффициент 0. Больше делать нечего - переходим следующей клетке. # Иначе прикидываем может ли этот корабль с этой клетки начинаться в какую-либо сторону # и если он помещается прбавляем клетке коэф 1. for ship_size in available_ships: ship = Ship(ship_size, 1, 1, 0) # вот тут бегаем по всем клеткам поля for x in range(self.size): for y in range(self.size): if self.radar[x][y] in (Cell.destroyed_ship, Cell.damaged_ship, Cell.miss_cell) \ or self.weight[x][y] == 0: self.weight[x][y] = 0 continue # вот здесь ворочаем корабль и проверяем помещается ли он for rotation in range(0, 4): ship.set_position(x, y, rotation) if self.check_ship_fits(ship, FieldPart.radar): self.weight[x][y] += 1

У нас есть поле с выставленными коэффициентами. Надо бы дописать функцию get_max_weight_cells которая будет возвращать список координат с максимальным коэффициентом.

def get_max_weight_cells(self): weights = {} max_weight = 0 for x in range(self.size): for y in range(self.size): if self.weight[x][y] > max_weight: max_weight = self.weight[x][y] weights.setdefault(self.weight[x][y], []).append((x, y)) return weights[max_weight]

Занесем координаты всех клеток в словарь weights. Ключом будет вес клеток. Значением — список содержащий пары координат.

Пробегаем по всем клеткам и заносим их в словарь. Заодно запоминаем максимальное значение веса. Далее просто берём из словаря список координат с ключом максимальным заначением веса: weights[max_weight]

Всё что осталось сделать ИИ, для совершения адекватного хода, это из полученного списка координат выбрать случайную:

x, y = choice(self.field.get_max_weight_cells())

Вот вроде бы и всё. Здесь не описал многие детали реализации, но, как я писал выше, комментарии есть еще в коде.

Строку 335 можно раскомментировать, чтобы получить доступ к отладочному полю с коэффициентами и видеть их распределение.

https://repl.it/@RSTakaROBO/MisguidedFearfulAddons
Вы можете опробовать морской бой прямо здесь, а так же прочитать дополнительные комментарии

Если хотите еще статью похожей тематики — ставьте лайк и предлагайте идеи.

В следующих раз можем попробовать написать например телеграмм-бот тамагочи: )

Python. Напишем морской бой с достойным соперником-ИИ

Морской бой

Class Game(object)

Class Player(object)

Class Field(object)

Class Ship(object)

Алгоритм поведения ИИ