...

пятница, 16 января 2015 г.

[Из песочницы] Морской бой за 25 мс

Предисловие




Несколько месяцев назад я решил изучить Python. В качестве одной из тестовых задач требовалось написать игру «Морской бой». Тогда я не сделал эту задачу, но в голову пришла идея написать «Морской бой», где будут играть два компьютера между собой. Эта мысль не оставляла меня, и я решил дерзнуть. Результат представлен на ваш суд. Буду признателен за любую конструктивную критику.

Общая концепция текущей реализации




Вся игра, по сути, сводится к тому, что два экземпляра класса Player спрашивают друг у друга координаты кораблей и в зависимости от ответа выстраивают свою стратегию ходов.

Стратегия расстановки кораблей следующая: 2-3-4 палубные размещаются по краям карты (2 клетки), 1-палубный в центре (квадрат 6х6).


image



Стратегия ходов, как в игре между людьми: первый ход наобум, если попал, то прорабатываем 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 близлежащих координаты (предварительно отфильтровав их по границам поля и списку координат, по которым мы уже стреляли).


image


Если recomendation_pool не пустой — это значит, что мы попали второй раз и речь уже идёт не о 4 координатах вокруг, а о двух с каждого края.


image


Если текущим выстрелом корабль был потоплен, мы считаем свою задачу выполненной и зачищаем пул рекомендаций и проч. Следующий выстрел будет выполнен случайным образом.


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). Ореол — это набор координат в которые нельзя будет поставить потом корабль (правило: не размещать корабли рядом).


image


3. После чего зачищаем список комбинаций (data_cleaner) из списка который состоит из координат корабля и ореола.


Модуль Logging




Под конец разработки открыл для себя модуль logging из стандартной библиотеки. Поля для вывода настраиваются (logging.basicConfig), а работать с выводом не сложнее, чем с print.

image


Прочее




sevice.rdn_usr_name — генерирует случайные имена игроков из набора букв и цифр от 0 до 999.

Игра заканчивается, если у противника Player.ships_defeat = 10, т.е. потоплены все 10 кораблей. Счётчик обновляется, если корабль отвечает «Убил!».


Список улучшений (TO DO)




1. Сделать турнир между игроками, скажем, где будет 1000 игроков. По идее, с учётом текущего времени выполнения весь турнир должен занять примерно 30 сек.

2. Добавить «базовый алгоритм» хода, например, ходить крест на крест, т.е. пробивать все клетки по диагонали и потом далее. Реализовать несколько таких алгоритмов и далее присваивать случайным образом работу по ним игроку. После чего сравнивать эффективность (например, что даёт больше результата случайные ходы или алгоритм «крест на крест»?)


3. Оптимизировать механизм поиска комбинаций (service.gen_cord), т.к. очевидно, что он избыточен и отнимает много ресурсов.


4. Реализовать различные стратегии размещения кораблей и потом сравнить какая из них наиболее успешна.


P.S. Буду признателен за любые интересные идеи.


Спасибо.


Recommended article: Chomsky: We Are All – Fill in the Blank.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


Комментариев нет:

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