Морской бой за 25 мс
- суббота, 17 января 2015 г. в 02:10:52
http://habrahabr.ru/post/248061/
Несколько месяцев назад я решил изучить 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 — определяет дальнейшую стратегию в зависимости от результатов текущего хода.
Важные переменные: 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]] — набор координат для корабля.
Важные переменные: 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.basicConfig), а работать с выводом не сложнее, чем с print.
sevice.rdn_usr_name — генерирует случайные имена игроков из набора букв и цифр от 0 до 999.
Игра заканчивается, если у противника Player.ships_defeat = 10, т.е. потоплены все 10 кораблей. Счётчик обновляется, если корабль отвечает «Убил!».
1. Сделать турнир между игроками, скажем, где будет 1000 игроков. По идее, с учётом текущего времени выполнения весь турнир должен занять примерно 30 сек.
2. Добавить «базовый алгоритм» хода, например, ходить крест на крест, т.е. пробивать все клетки по диагонали и потом далее. Реализовать несколько таких алгоритмов и далее присваивать случайным образом работу по ним игроку. После чего сравнивать эффективность (например, что даёт больше результата случайные ходы или алгоритм «крест на крест»?)
3. Оптимизировать механизм поиска комбинаций (service.gen_cord), т.к. очевидно, что он избыточен и отнимает много ресурсов.
4. Реализовать различные стратегии размещения кораблей и потом сравнить какая из них наиболее успешна.
P.S. Буду признателен за любые интересные идеи.
Спасибо.
UPDATE (16.01.2015)
В турнире идёт игра на вылет, т.е. если проиграл на след. ступень уже не попадаешь.
Чтобы турнир был без косяков количество игроков должно быть, чтобы при делении остаток от деления всегда делился на 2 и так до того как число игроков в турнире не будет 1 (т.е. победитель). К таким числам относятся 1024 (512, 256, 128, 64, 32, 16, 8, 4, 2).
Ранее я предполагал, что турнир будет длиться порядка 30 секунд, т.е. время вырастает линейно в зависимости от количества игроков, однако каково же было моё удивление, когда весь турнир для 1024 игроков всего 17 секунд. Почему получается 17 секунд мне не ведомо, возможно начинают работать какие-то механизмы оптимизации. Мои расчеты таковы: 1022 партии длится весь турнир* 25 мс одна партия = 25.55 секунд.
Статистика турнира держится в пределах следующих значений:
1. Среднее количество ходов (всех игроков): 85.06,
2. Среднее количество ходов выигравших игроков: 85.95,
3. Среднее количество ходов проигравших игроков: 84.17,
4. Среднее количество очков, которое набрали проигравшие: 17.75
Выводы можем сделать следующие:
1. Количество ходов, что выигравшие, что проигравшие делают примерно одинаковое.
2. Количество очков почти 18 (для победы нужно 20).
Итог: оба игрока играют примерно одинаково и одинаково неэффективно :) Разница в 2 очка показывает, что победа буквально вырывается из лап соперника на последних ходах.
Вывод: т.к. сейчас каждый игрок руководствуется одной и той же стратегией особого разнообразия в игре нет. Чтобы было поинтересней нужно реализовать различные стратегии как расстановки кораблей, так и выполнения ходов, чем и займусь на досуге в ближайшее время.
Следите за обновлениями статьи.
UPDATE2(16.01.2015)
Реализовал добавление ореола к списку пробитых координат после потопления корабля (в принципе всё честно). Статистика по количеству ходов существенно улучшилась:
1. Среднее количесво ходов (всех игроков): 58.91,
2. Среднее количество ходов выйгравших игроков: 60.98,
3. Среднее количество ходов проигравших игроков: 56.83,
4. Среднее количество очков, которое набрали проигравшие: 15.37
Спасибо Meklon за идею.
Всем спасибо за ссылки и комментарии.
Предисловие
Несколько месяцев назад я решил изучить 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)
2. Добавить «базовый алгоритм» хода, например, ходить крест на крест, т.е. пробивать все клетки по диагонали и потом далее. Реализовать несколько таких алгоритмов и далее присваивать случайным образом работу по ним игроку. После чего сравнивать эффективность (например, что даёт больше результата случайные ходы или алгоритм «крест на крест»?)
3. Оптимизировать механизм поиска комбинаций (service.gen_cord), т.к. очевидно, что он избыточен и отнимает много ресурсов.
4. Реализовать различные стратегии размещения кораблей и потом сравнить какая из них наиболее успешна.
P.S. Буду признателен за любые интересные идеи.
Спасибо.
UPDATE (16.01.2015)
Турнир реализован + сделан небольшой сбор статистики и вот что получается:
В турнире идёт игра на вылет, т.е. если проиграл на след. ступень уже не попадаешь.
Чтобы турнир был без косяков количество игроков должно быть, чтобы при делении остаток от деления всегда делился на 2 и так до того как число игроков в турнире не будет 1 (т.е. победитель). К таким числам относятся 1024 (512, 256, 128, 64, 32, 16, 8, 4, 2).
Ранее я предполагал, что турнир будет длиться порядка 30 секунд, т.е. время вырастает линейно в зависимости от количества игроков, однако каково же было моё удивление, когда весь турнир для 1024 игроков всего 17 секунд. Почему получается 17 секунд мне не ведомо, возможно начинают работать какие-то механизмы оптимизации. Мои расчеты таковы: 1022 партии длится весь турнир* 25 мс одна партия = 25.55 секунд.
Статистика турнира держится в пределах следующих значений:
1. Среднее количество ходов (всех игроков): 85.06,
2. Среднее количество ходов выигравших игроков: 85.95,
3. Среднее количество ходов проигравших игроков: 84.17,
4. Среднее количество очков, которое набрали проигравшие: 17.75
Выводы можем сделать следующие:
1. Количество ходов, что выигравшие, что проигравшие делают примерно одинаковое.
2. Количество очков почти 18 (для победы нужно 20).
Итог: оба игрока играют примерно одинаково и одинаково неэффективно :) Разница в 2 очка показывает, что победа буквально вырывается из лап соперника на последних ходах.
Вывод: т.к. сейчас каждый игрок руководствуется одной и той же стратегией особого разнообразия в игре нет. Чтобы было поинтересней нужно реализовать различные стратегии как расстановки кораблей, так и выполнения ходов, чем и займусь на досуге в ближайшее время.
Следите за обновлениями статьи.
UPDATE2(16.01.2015)
Реализовал добавление ореола к списку пробитых координат после потопления корабля (в принципе всё честно). Статистика по количеству ходов существенно улучшилась:
1. Среднее количесво ходов (всех игроков): 58.91,
2. Среднее количество ходов выйгравших игроков: 60.98,
3. Среднее количество ходов проигравших игроков: 56.83,
4. Среднее количество очков, которое набрали проигравшие: 15.37
Спасибо Meklon за идею.
Всем спасибо за ссылки и комментарии.