[Из песочницы] Морской бой за 25 мс
Предисловие Несколько месяцев назад я решил изучить Python. В качестве одной из тестовых задач требовалось написать игру «Морской бой». Тогда я не сделал эту задачу, но в голову пришла идея написать «Морской бой», где будут играть два компьютера между собой. Эта мысль не оставляла меня, и я решил дерзнуть. Результат представлен на ваш суд. Буду признателен за любую конструктивную критику.Общая концепция текущей реализации Вся игра, по сути, сводится к тому, что два экземпляра класса Player спрашивают друг у друга координаты кораблей и в зависимости от ответа выстраивают свою стратегию ходов.Стратегия расстановки кораблей следующая: 2–3–4 палубные размещаются по краям карты (2 клетки), 1-палубный в центре (квадрат 6×6).
Стратегия ходов, как в игре между людьми: первый ход наобум, если попал, то прорабатываем 4 клетки вокруг и далее, если попал повторно, то прорабатываем по две клетки уже на линии (две, т.к. макс. длинна корабля 4 клетки, в 2 уже попал, значит макс. есть ещё 2 клетки).
В статье на Википедии всё достаточно подробно описано, поэтому не буду здесь сильно касаться игровой логики, тем более, что и так все примерно понимают, о чём идёт речь. У меня отличия только такие: начисление очков за каждый ход, нумерация клеток от 0 до 9.
В игре используются три класса: Game, Player, Ship. Использование класса Game в текущей реализации избыточно, так как используется всего один его экземпляр, но это некоторый задел на будущее (см. список улучшений в конце статьи).
Game отвечает за общую игровую логику, Player — за стратегию ходов, Ship — хранит текущее состояние кораблей и их координаты.
Ссылка проект в GitHub.
Основные сложности, которые возникли входе разработки 1. Проектирование. Писать с использованием классов или функций? Какой набор классов использовать? Основной проблемой при проектировании оказалось отслеживание различных состояний в игре. Например, кто сейчас ходит, в каком состоянии корабль (подбит, убит), не закончилась ли игра, кто выиграл и т.п.2. Логика/алгоритмы. Как расставить корабли в соответствии со стратегией, как выбрать координаты для хода?
Обзор наиболее интересных частей кода return_shoot_state — определяет дальнейшую стратегию в зависимости от результатов текущего хода. def return_shoot_state (self, state, crd): »«Стратегия дальнейщих ходов в зависимости от результата текущего хода»« if state == u’Попал!': self.scores += 1 if not self.recomendation_pool: crd_rec = [[crd[0] — 1, crd[1]], [crd[0] + 1, crd[1]], [crd[0], crd[1] — 1], [crd[0], crd[1] + 1]] crd_rec = filter (lambda x: 0 <= x[0] <= 9 and 0 <= x[1] <= 9, crd_rec) crd_rec = filter(lambda x: x not in self.alien, crd_rec) self.succ_shoots.append(crd) self.recomendation_pool.extend(crd_rec) else: crd_s1 = self.recomendation_pool[0] crd_s2 = self.succ_shoots[0] for ind in range(2): if crd_s1[ind] != crd_s2[ind]: if crd_s1[ind] > crd_s2[ind]: crd_rec = [[crd_s1[ind]+1, crd_s1[ind]+2], [crd_s2[ind]-1, crd_s2[ind]-2]] else: crd_rec = [[crd_s1[ind]-1, crd_s1[ind]-2], [crd_s2[ind]+1, crd_s2[ind]+2]] crd_rec = filter (lambda x: 0 <= x[0] <= 9 and 0 <= x[1] <= 9, crd_rec) crd_rec = filter(lambda x: x not in self.alien, crd_rec) self.recomendation_pool.extend(crd_rec) elif state == u'Убил!': self.scores += 1 self.recomendation_pool = [] self.succ_shoots = [] Важные переменные: recomendation_pool — список координат для будущих выстрелов, succ_shoots — последний успешный выстрел.
Если мы попали в корабль, то, во-первых, нужно начислить себе очки за успешный выстрел (scores += 1), а во-вторых, понять, что делать дальше. Мы проверяем recomendation_pool, есть ли там что-то, если нет, то записываем туда 4 близлежащих координаты (предварительно отфильтровав их по границам поля и списку координат, по которым мы уже стреляли).
Если recomendation_pool не пустой — это значит, что мы попали второй раз и речь уже идёт не о 4 координатах вокруг, а о двух с каждого края.
Если текущим выстрелом корабль был потоплен, мы считаем свою задачу выполненной и зачищаем пул рекомендаций и проч. Следующий выстрел будет выполнен случайным образом.
service.gen_cord — генерирует все возможные координаты для каждого типа кораблей. Результатом работы функции будет словарь со следующей структурой: {«S0»:[[[x0, y0],[x1, y2],[xN0, yN1]], [[x3, y3],[x4, y4],[xN2, yN3]], …], «S1»: …}, где S — тип корабля, [[x0, y0],[x1, y2],[xN0, yN1]] — набор координат для корабля.
def gen_cord (): »«Генератор всех возможных комбинаций координат»« all_comb = [[x/10, x % 10] for x in range (100)] for_1_ship = filter (lambda x: x[0] in range (2, 8) and x[1] in range (2, 8), all_comb) for_other_ship = filter (lambda x: x not in for_1_ship, all_comb) cord_comb = {1: [[x] for x in for_1_ship], 2: [], 3: [], 4: []} for ship in filter (lambda x: x!= 1, cord_comb.keys ()): for cord in for_other_ship: hor_direction = [cord] + [[cord[0]+x, cord[1]] for x in range (1, ship)] ver_direction = [cord] + [[cord[0], cord[1]+x] for x in range (1, ship)] for dir_d in [hor_direction, ver_direction]: for cord_d in dir_d: if cord_d not in for_other_ship: break else: cord_comb[ship].append (dir_d) return cord_comb Важные переменные: all_comb — хранит координаты поля в формате [[x0, y0], [x1, y1], …]. for_1_ship — тот самый квадрат 6×6 для однопалубных, for_other_ship — набор координат для всех остальных кораблей. cord_comb — словарь, который хранит все комбинации координат.Расстановка кораблей В момент инициализации экземпляра класса Player также расставляются и корабли. В классе за это отвечает метод create_ships, где происходит следующее:1. Для каждого корабля (ships) из доступной последовательности комбинаций координат (combinations) псевдослучайным образом (random.choice) выбирается набор координат.2. Далее для набора координат генерируется ореол (service.set_halo). Ореол — это набор координат в которые нельзя будет поставить потом корабль (правило: не размещать корабли рядом).
3. После чего зачищаем список комбинаций (data_cleaner) из списка который состоит из координат корабля и ореола.
Модуль Logging
Под конец разработки открыл для себя модуль logging из стандартной библиотеки. Поля для вывода настраиваются (logging.basicConfig), а работать с выводом не сложнее, чем с print.
Прочее sevice.rdn_usr_name — генерирует случайные имена игроков из набора букв и цифр от 0 до 999.Игра заканчивается, если у противника Player.ships_defeat = 10, т.е. потоплены все 10 кораблей. Счётчик обновляется, если корабль отвечает «Убил!».
Список улучшений (TO DO) 1. Сделать турнир между игроками, скажем, где будет 1000 игроков. По идее, с учётом текущего времени выполнения весь турнир должен занять примерно 30 сек.2. Добавить «базовый алгоритм» хода, например, ходить крест на крест, т.е. пробивать все клетки по диагонали и потом далее. Реализовать несколько таких алгоритмов и далее присваивать случайным образом работу по ним игроку. После чего сравнивать эффективность (например, что даёт больше результата случайные ходы или алгоритм «крест на крест»?)
3. Оптимизировать механизм поиска комбинаций (service.gen_cord), т.к. очевидно, что он избыточен и отнимает много ресурсов.
4. Реализовать различные стратегии размещения кораблей и потом сравнить какая из них наиболее успешна.
P.S. Буду признателен за любые интересные идеи.
Спасибо.
