Как написать игру морской бой на python - Правописание и грамматика

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

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

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

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

Морской бой

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

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

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

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

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

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

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

Class Game(object)

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)

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)

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(object)

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 можно раскомментировать, чтобы получить доступ к отладочному полю с коэффициентами и видеть их распределение.

Вы можете опробовать морской бой прямо здесь, а так же прочитать дополнительные комментарии

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

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

Источник

Время на прочтение
9 мин

Количество просмотров 62K

Предисловие

Несколько месяцев назад я решил изучить 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. Буду признателен за любые интересные идеи.

Спасибо.

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 за идею.

UPDATE3(17.01.2015)

Реализовал новые стратегии размещения кораблей (там где 60 клеток под однопалубные). В итоге получилось следующее, если каждый из игроков использует одну и туже стратегию, то разницы между проигравшими и победителями нет, а вот если кажому игроку стратегия расстановки присваивается случайно, то явно видно, что прогиравших с моей стратегией больше (квадрат 6х6 в центре), т.е. если мою стратегию выбросить, то все будут играть примерно одинаково. Это тоже не интересно. Теперь буду реализывать различные стратегии ходов (может найдётся, что-то сверхоптимальное).

Данные

left,right, top,bottom и т.п. — это всё вариации размещения 60 координат на поле.
[2015-01-17 19:14:07,780] Статистика:
1. Среднее количесво ходов (всех игроков): 63.18,
2. Среднее количество ходов выйгравших игроков: 64.82,
3. Среднее количество ходов проигравших игроков: 61.54,
4. Среднее количество очков, которое набрали проигравшие: 16.24
[2015-01-17 19:14:07,783] Стратегия: for_1_ship_left loosers: 508
[2015-01-17 19:14:07,783] Стратегия: for_1_ship_left winners: 515

[2015-01-17 19:20:27,526] Статистика:
1. Среднее количесво ходов (всех игроков): 62.58,
2. Среднее количество ходов выйгравших игроков: 64.23,
3. Среднее количество ходов проигравших игроков: 60.93,
4. Среднее количество очков, которое набрали проигравшие: 16.23
[2015-01-17 19:20:27,529] Стратегия: for_1_ship_right loosers: 498
[2015-01-17 19:20:27,529] Стратегия: for_1_ship_right winners: 525

[2015-01-17 19:21:40,153] Статистика:
1. Среднее количесво ходов (всех игроков): 58.94,
2. Среднее количество ходов выйгравших игроков: 61.02,
3. Среднее количество ходов проигравших игроков: 56.87,
4. Среднее количество очков, которое набрали проигравшие: 15.35
[2015-01-17 19:21:40,155] Стратегия: for_1_ship_36 loosers: 518
[2015-01-17 19:21:40,157] Стратегия: for_1_ship_36 winners: 505

[2015-01-17 19:23:37,322] Статистика:
1. Среднее количесво ходов (всех игроков): 62.85,
2. Среднее количество ходов выйгравших игроков: 64.55,
3. Среднее количество ходов проигравших игроков: 61.16,
4. Среднее количество очков, которое набрали проигравшие: 16.15
[2015-01-17 19:23:37,323] Стратегия: for_1_ship_bottom loosers: 526
[2015-01-17 19:23:37,325] Стратегия: for_1_ship_bottom winners: 497

[2015-01-17 19:33:07,933] Статистика:
1. Среднее количесво ходов (всех игроков): 61.59,
2. Среднее количество ходов выйгравших игроков: 63.37,
3. Среднее количество ходов проигравших игроков: 59.81,
4. Среднее количество очков, которое набрали проигравшие: 15.95
[2015-01-17 19:33:07,934] Стратегия: for_1_ship_center_vertical loosers: 512
[2015-01-17 19:33:07,934] Стратегия: for_1_ship_center_vertical winners: 511

[2015-01-17 19:36:03,585] Статистика:
1. Среднее количесво ходов (всех игроков): 61.03,
2. Среднее количество ходов выйгравших игроков: 62.89,
3. Среднее количество ходов проигравших игроков: 59.18,
4. Среднее количество очков, которое набрали проигравшие: 15.78
[2015-01-17 19:36:03,589] Стратегия: for_1_ship_36 loosers: 148
[2015-01-17 19:36:03,589] Стратегия: for_1_ship_36 winners: 109
[2015-01-17 19:36:03,591] Стратегия: for_1_ship_bottom loosers: 34
[2015-01-17 19:36:03,591] Стратегия: for_1_ship_bottom winners: 50
[2015-01-17 19:36:03,591] Стратегия: for_1_ship_center_horisontal loosers: 129
[2015-01-17 19:36:03,591] Стратегия: for_1_ship_center_horisontal winners: 120
[2015-01-17 19:36:03,592] Стратегия: for_1_ship_center_vertical loosers: 96
[2015-01-17 19:36:03,592] Стратегия: for_1_ship_center_vertical winners: 94
[2015-01-17 19:36:03,592] Стратегия: for_1_ship_left loosers: 28
[2015-01-17 19:36:03,592] Стратегия: for_1_ship_left winners: 44
[2015-01-17 19:36:03,592] Стратегия: for_1_ship_right loosers: 40
[2015-01-17 19:36:03,594] Стратегия: for_1_ship_right winners: 48
[2015-01-17 19:36:03,594] Стратегия: for_1_ship_top loosers: 35
[2015-01-17 19:36:03,594] Стратегия: for_1_ship_top winners: 48

UPDATE4(20.01.2015)

Добавил различные варианты совершения ходов: random — случайно из свободных клеток, cross — крест на крест, linear — линейно в 4 ряда через одну (как в хвалёных статьях). Важный момент: стратегия расстановки кораблей выдаётся на весь турнир, а вот стратегия ходов выдаётся на каждую игру.

Собрал статистку (напомню речь идёт о турните, где 1024 игрока играют между собой на вылет).

Основные выводы:
Стратегии расстановки однопалубных кораблей random_12 (выбирается 12 случайных клеток и в них расставляем корабли) и for_1_ship_36 (поле 6х6 в центре) явно наименее эффективные.

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

Количество ходов с реализацией дополнительных стратегий ходов не уменьшилось, а вот время турнира увеличилось с 25 до 50 секунд:
1. Среднее количесво ходов (всех игроков): 61.43,
2. Среднее количество ходов выйгравших игроков: 63.23,
3. Среднее количество ходов проигравших игроков: 59.63,
4. Среднее количество очков, которое набрали проигравшие: 15.93

Буду признателен, если кто-то посмотрит мой код на GitHub и даст свои рекомендации по его улучшению.

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

Спасибо за внимание и да прибудет с вами сила Python!

Источник

from tkinter import * from tkinter import messagebox import time import random tk = Tk() app_running = True size_canvas_x = 500 size_canvas_y = 500 s_x = s_y = 8 # размер игрового поля s_y = 8 step_x = size_canvas_x // s_x # шаг по горизонтали step_y = size_canvas_y // s_y # шаг по вертикали size_canvas_x = step_x * s_x size_canvas_y = step_y * s_y delta_menu_x = 4 menu_x = step_x * delta_menu_x # 250 menu_y = 40 ships = s_x // 2 # определяем максимальное кол-во кораблей ship_len1 = s_x // 5 # длина первого типа корабля ship_len2 = s_x // 3 # длина второго типа корабля ship_len3 = s_x // 2 # длина третьего типа корабля enemy_ships1 = [[0 for i in range(s_x + 1)] for i in range(s_y + 1)] enemy_ships2 = [[0 for i in range(s_x + 1)] for i in range(s_y + 1)] list_ids = [] # список объектов canvas # points1 — список куда мы кликнули мышкой points1 = [[—1 for i in range(s_x)] for i in range(s_y)] points2 = [[—1 for i in range(s_x)] for i in range(s_y)] # boom — список попаданий по кораблям противника boom = [[0 for i in range(s_x)] for i in range(s_y)] # ships_list — список кораблей игрока 1 и игрока 2 ships_list = [] # print(enemy_ships1) def on_closing(): global app_running if messagebox.askokcancel(«Выход из игры», «Хотите выйти из игры?»): app_running = False tk.destroy() tk.protocol(«WM_DELETE_WINDOW», on_closing) tk.title(«Игра Морской Бой») tk.resizable(0, 0) tk.wm_attributes(«-topmost», 1) canvas = Canvas(tk, width=size_canvas_x + menu_x + size_canvas_x, height=size_canvas_y + menu_y, bd=0, highlightthickness=0) canvas.create_rectangle(0, 0, size_canvas_x, size_canvas_y, fill=«white») canvas.create_rectangle(size_canvas_x + menu_x, 0, size_canvas_x + menu_x + size_canvas_x, size_canvas_y, fill=«lightyellow») canvas.pack() tk.update() def draw_table(offset_x=0): for i in range(0, s_x + 1): canvas.create_line(offset_x + step_x * i, 0, offset_x + step_x * i, size_canvas_y) for i in range(0, s_y + 1): canvas.create_line(offset_x, step_y * i, offset_x + size_canvas_x, step_y * i) draw_table() draw_table(size_canvas_x + menu_x) t0 = Label(tk, text=«Игрок №1», font=(«Helvetica», 16)) t0.place(x=size_canvas_x // 2 — t0.winfo_reqwidth() // 2, y=size_canvas_y + 3) t1 = Label(tk, text=«Игрок №2», font=(«Helvetica», 16)) t1.place(x=size_canvas_x + menu_x + size_canvas_x // 2 — t1.winfo_reqwidth() // 2, y=size_canvas_y + 3) t0.configure(bg=«red») t0.configure(bg=«#f0f0f0») def button_show_enemy1(): for i in range(0, s_x): for j in range(0, s_y): if enemy_ships1[j][i] > 0: color = «red» if points1[j][i] != —1: color = «green» _id = canvas.create_rectangle(i * step_x, j * step_y, i * step_x + step_x, j * step_y + step_y, fill=color) list_ids.append(_id) def button_show_enemy2(): for i in range(0, s_x): for j in range(0, s_y): if enemy_ships2[j][i] > 0: color = «red» if points2[j][i] != —1: color = «green» _id = canvas.create_rectangle(size_canvas_x + menu_x + i * step_x, j * step_y, size_canvas_x + menu_x + i * step_x + step_x, j * step_y + step_y, fill=color) list_ids.append(_id) def button_begin_again(): global list_ids global points1, points2 global boom global enemy_ships1, enemy_ships2 for el in list_ids: canvas.delete(el) list_ids = [] generate_ships_list() # print(ships_list) enemy_ships1 = generate_enemy_ships() enemy_ships2 = generate_enemy_ships() points1 = [[—1 for i in range(s_x)] for i in range(s_y)] points2 = [[—1 for i in range(s_x)] for i in range(s_y)] boom = [[0 for i in range(s_x)] for i in range(s_y)] b0 = Button(tk, text=«Показать корабли Игрока №1», command=button_show_enemy1) b0.place(x=size_canvas_x + 20, y=30) b1 = Button(tk, text=«Показать корабли Игрока №2», command=button_show_enemy2) b1.place(x=size_canvas_x + 20, y=70) b2 = Button(tk, text=«Начать заново!», command=button_begin_again) b2.place(x=size_canvas_x + 20, y=110) def draw_point(x, y): # print(enemy_ships1[y][x]) if enemy_ships1[y][x] == 0: color = «red» id1 = canvas.create_oval(x * step_x, y * step_y, x * step_x + step_x, y * step_y + step_y, fill=color) id2 = canvas.create_oval(x * step_x + step_x // 3, y * step_y + step_y // 3, x * step_x + step_x — step_x // 3, y * step_y + step_y — step_y // 3, fill=«white») list_ids.append(id1) list_ids.append(id2) if enemy_ships1[y][x] > 0: color = «blue» id1 = canvas.create_rectangle(x * step_x, y * step_y + step_y // 2 — step_y // 10, x * step_x + step_x, y * step_y + step_y // 2 + step_y // 10, fill=color) id2 = canvas.create_rectangle(x * step_x + step_x // 2 — step_x // 10, y * step_y, x * step_x + step_x // 2 + step_x // 10, y * step_y + step_y, fill=color) list_ids.append(id1) list_ids.append(id2) def draw_point2(x, y, offset_x=size_canvas_x + menu_x): # print(enemy_ships1[y][x]) if enemy_ships2[y][x] == 0: color = «red» id1 = canvas.create_oval(offset_x + x * step_x, y * step_y, offset_x + x * step_x + step_x, y * step_y + step_y, fill=color) id2 = canvas.create_oval(offset_x + x * step_x + step_x // 3, y * step_y + step_y // 3, offset_x + x * step_x + step_x — step_x // 3, y * step_y + step_y — step_y // 3, fill=«white») list_ids.append(id1) list_ids.append(id2) if enemy_ships2[y][x] > 0: color = «blue» id1 = canvas.create_rectangle(offset_x + x * step_x, y * step_y + step_y // 2 — step_y // 10, offset_x + x * step_x + step_x, y * step_y + step_y // 2 + step_y // 10, fill=color) id2 = canvas.create_rectangle(offset_x + x * step_x + step_x // 2 — step_x // 10, y * step_y, offset_x + x * step_x + step_x // 2 + step_x // 10, y * step_y + step_y, fill=color) list_ids.append(id1) list_ids.append(id2) def check_winner(x, y): win = False if enemy_ships1[y][x] > 0: boom[y][x] = enemy_ships1[y][x] sum_enemy_ships1 = sum(sum(i) for i in zip(*enemy_ships1)) sum_boom = sum(sum(i) for i in zip(*boom)) #print(sum_enemy_ships1, sum_boom) if sum_enemy_ships1 == sum_boom: win = True return win def check_winner2(): win = True for i in range(0, s_x): for j in range(0, s_y): if enemy_ships1[j][i] > 0: if points1[j][i] == —1: win = False #print(win) return win def add_to_all(event): global points1, points2 _type = 0 # ЛКМ if event.num == 3: _type = 1 # ПКМ # print(_type) mouse_x = canvas.winfo_pointerx() — canvas.winfo_rootx() mouse_y = canvas.winfo_pointery() — canvas.winfo_rooty() # print(mouse_x, mouse_y) ip_x = mouse_x // step_x ip_y = mouse_y // step_y print(ip_x, ip_y, «_type:», _type) if ip_x < s_x and ip_y < s_y: if points1[ip_y][ip_x] == —1: points1[ip_y][ip_x] = _type draw_point(ip_x, ip_y) # if check_winner(ip_x, ip_y): if check_winner2(): print(«Победа!!!!!») points1 = [[10 for i in range(s_x)] for i in range(s_y)] #print(len(list_ids)) if ip_x >= s_x + delta_menu_x and ip_x <= s_x + s_x + delta_menu_x and ip_y < s_y: # print(«ok») if points2[ip_y][ip_x — s_x — delta_menu_x] == —1: points2[ip_y][ip_x — s_x — delta_menu_x] = _type draw_point2(ip_x — s_x — delta_menu_x, ip_y) # if check_winner(ip_x, ip_y): if check_winner2(): print(«Победа!!!!!») points2 = [[10 for i in range(s_x)] for i in range(s_y)] canvas.bind_all(«<Button-1>», add_to_all) # ЛКМ canvas.bind_all(«<Button-3>», add_to_all) # ПКМ def generate_ships_list(): global ships_list ships_list = [] # генерируем список случайных длин кораблей for i in range(0, ships): ships_list.append(random.choice([ship_len1, ship_len2, ship_len3])) # print(ships_list) def generate_enemy_ships(): global ships_list enemy_ships = [] # подсчет суммарной длины кораблей sum_1_all_ships = sum(ships_list) sum_1_enemy = 0 # print(«sum: «, sum_1_all_ships) while sum_1_enemy != sum_1_all_ships: # обнуляем массив кораблей врага enemy_ships = [[0 for i in range(s_x + 1)] for i in range(s_y + 1)] # +1 для доп. линии справа и снизу, для успешных проверок генерации противника for i in range(0, ships): len = ships_list[i] horizont_vertikal = random.randrange(1, 3) # 1- горизонтальное 2 — вертикальное primerno_x = random.randrange(0, s_x) if primerno_x + len > s_x: primerno_x = primerno_x — len primerno_y = random.randrange(0, s_y) if primerno_y + len > s_y: primerno_y = primerno_y — len # print(horizont_vertikal, primerno_x,primerno_y) if horizont_vertikal == 1: if primerno_x + len <= s_x: for j in range(0, len): try: check_near_ships = 0 check_near_ships = enemy_ships[primerno_y][primerno_x — 1] + enemy_ships[primerno_y][primerno_x + j] + enemy_ships[primerno_y][primerno_x + j + 1] + enemy_ships[primerno_y + 1][primerno_x + j + 1] + enemy_ships[primerno_y — 1][primerno_x + j + 1] + enemy_ships[primerno_y + 1][primerno_x + j] + enemy_ships[primerno_y — 1][primerno_x + j] # print(check_near_ships) if check_near_ships == 0: # записываем в том случае, если нет ничего рядом enemy_ships[primerno_y][primerno_x + j] = i + 1 # записываем номер корабля except Exception: pass if horizont_vertikal == 2: if primerno_y + len <= s_y: for j in range(0, len): try: check_near_ships = 0 check_near_ships = enemy_ships[primerno_y — 1][primerno_x] + enemy_ships[primerno_y + j][primerno_x] + enemy_ships[primerno_y + j + 1][primerno_x] + enemy_ships[primerno_y + j + 1][primerno_x + 1] + enemy_ships[primerno_y + j + 1][primerno_x — 1] + enemy_ships[primerno_y + j][primerno_x + 1] + enemy_ships[primerno_y + j][primerno_x — 1] # print(check_near_ships) if check_near_ships == 0: # записываем в том случае, если нет ничего рядом enemy_ships[primerno_y + j][primerno_x] = i + 1 # записываем номер корабля except Exception: pass # делаем подсчет 1ц sum_1_enemy = 0 for i in range(0, s_x): for j in range(0, s_y): if enemy_ships[j][i] > 0: sum_1_enemy = sum_1_enemy + 1 # print(sum_1_enemy) # print(ships_list) # print(enemy_ships) return enemy_ships generate_ships_list() # print(ships_list) enemy_ships1 = generate_enemy_ships() enemy_ships2 = generate_enemy_ships() # print(«****************************») # print(enemy_ships1) # print(«****************************») # print(enemy_ships2) # print(«****************************») while app_running: if app_running: tk.update_idletasks() tk.update() time.sleep(0.005)

Источник

Предисловие

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

Ссылка проект в GitHub.

Основные сложности, которые возникли входе разработки

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 — последний успешный выстрел.

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

Расстановка кораблей

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

Модуль Logging

Прочее

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

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

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

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

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

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

Спасибо.

Автор: balamut108

Источник

Источник

Дима любит играть в морской бой. К сожалению, он очень рассеян и постоянно неправильно отмечает на карте клетки, по которым уже стрелял. Напишите класс, который будет строить за Диму карту.

Класс SeaMap должен иметь следующие методы (sm – экземпляр SeaMap):

sm.shoot(row, col, result) — добавить на карту результат выстрела. row — индекс ряда карты. col — индекс вертикальной колонки карты. result — одна из строк “miss” (промах), “hit” (попадание), “sink” (потопление корабля).

sm.cell(row, col) Возвращает ‘.’, если в клетке с координатами row, col может находится корабль. Возвращает ‘*’, если в клетку уже стреляли или она находится рядом с потопленным кораблём. Возвращает ‘x’ если в клетке было попадание.

Метод cell будет вызываться, только когда все обнаруженные на карте корабли потоплены. То есть, не нужно помечать ‘*’ клетки рядом с кораблём в который попали, но не потопили до конца.

Формат ввода
Каждый тест представляет собой код, в котором будет использоваться ваш класс. Файл c решением не обязательно называть solution.py, он будет переименован автоматически. Тест запускается с вашим классом, а его вывод сравнивается с правильным решением.

Пример 1
Ввод Вывод
from solution import SeaMap

sm = SeaMap()
sm.shoot(2, 0, ‘miss’)
sm.shoot(6, 9, ‘miss’)
for row in range(10):
for col in range(10):
print(sm.cell(row, col), end=»)
print()
……….
……….
*………
……….
……….
……….
………*
……….
……….
……….
Пример 2
Ввод Вывод
from solution import SeaMap

sm = SeaMap()
sm.shoot(2, 0, ‘sink’)
sm.shoot(6, 9, ‘hit’)
for row in range(10):
for col in range(10):
print(sm.cell(row, col), end=»)
print()

……….
**……..
x*……..
**……..
……….
……….
………x
……….
……….
……….
Пример 3
Ввод Вывод
from solution import SeaMap

sm = SeaMap()
sm.shoot(0, 0, ‘sink’)
sm.shoot(0, 9, ‘sink’)
sm.shoot(9, 0, ‘sink’)
sm.shoot(9, 9, ‘sink’)
for row in range(10):
for col in range(10):
print(sm.cell(row, col), end=»)
print()
x*……*x
**……**
……….
……….
……….
……….
……….
……….
**……**
x*……*x

__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь

Источник

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

Главная
Генетические алгоритмы
Примеры реализаций

Расставляем корабли в игре Морской бой

Архив проекта: ga_8.zip

На этом занятии
мы рассмотрим еще один пример использования генетического алгоритма для
расстановки кораблей в игре «Морской бой». Наша цель разместить один
четырехпалубный, два трехпалубных, три двухпалубных и четыре однопалубных
кораблей на игровом поле так, чтобы они не соприкасались между собой:

Вначале нам
нужно определиться с форматом данных в хромосомах. Я закодировал их, следующим
образом:

Здесь x, y – положение
корабля (целое число от 1 до 10); p – ориентация
корабля (0 – по горизонтали; 1 – по вертикали). Общая длина хромосомы
составляет 10*3 = 30 генов.

Идея вычисления приспособленности особи

Следующим важным
шагом является вычисление значения функции приспособленности каждого
индивидуума. Идея расчета в нашем алгоритме будет следующей. Вначале сформируем
матрицу, в которой нули будут описывать игровое поле, а граничные значения 1000
– величину штрафа за расположение корабля за пределами игрового поля:

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

Если, затем,
добавить трехпалубный корабль с наложением на четырехпалубный, то в области
игрового поля будем получать величины больше единицы (см. второй рисунок).

Таким образом,
логика вычисления значения приспособленности особи, следующая. В игровой
области суммируем все величины больше 1, а за его пределами – все значения
более 1000. Общая сумма и будет определять приспособленность индивидуума. Можно
заметить, если корабли располагаются по правилам игры, то значение
приспособленности равно нулю. И возрастает, при увеличении числа ошибочных
расстановок. То есть, в процессе оптимизации нам нужно будет минимизировать
функцию принадлежности.

Реализация алгоритма на Python

Давайте теперь
реализуем этот алгоритм на Python с использованием
пакета DEAP. Вначале
выполним импорт необходимых пакетов и модулей:

from deap import base, algorithms
from deap import creator
from deap import tools
 
import algelitism
from graph_show import show_graph
 
import random
import matplotlib.pyplot as plt
import numpy as np

Затем, определим
глобальные параметры алгоритма и задачи:

POLE_SIZE = 10
SHIPS = 10
LENGTH_CHROM = 3*SHIPS    # длина хромосомы, подлежащей оптимизации
 
# константы генетического алгоритма
POPULATION_SIZE = 50   # количество индивидуумов в популяции
P_CROSSOVER = 0.9       # вероятность скрещивания
P_MUTATION = 0.2        # вероятность мутации индивидуума
MAX_GENERATIONS = 50    # максимальное количество поколений
HALL_OF_FAME_SIZE = 1
 
hof = tools.HallOfFame(HALL_OF_FAME_SIZE)
 
RANDOM_SEED = 42
random.seed(RANDOM_SEED)

Следующим шагом
определим класс FitnessMin для работы со значением
приспособленности и класс Individual представления индивидуумов в
популяции:

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)

Здесь все
стандартно и вес определен как -1, означающий, что нас будет интересовать
минимум функции приспособленности.

Затем, определим
функцию randomShip, которая будет
создавать начальных индивидуумов со случайными значениями генов:

def randomShip(total):
    ships = []
    for n in range(total):
        ships.extend([random.randint(1, POLE_SIZE), random.randint(1, POLE_SIZE), random.randint(0, 1)])
 
    return creator.Individual(ships)

Параметр total – это общее
число кораблей. В цикле для каждого корабля создаются три случайных значения:
координаты x, y и ориентация p.

Далее, мы
регистрируем функцию randomShip для создания индивидуума,
функцию populationCreator – для создания
популяции и создаем начальную популяцию размером POPULATION_SIZE:

toolbox = base.Toolbox()
toolbox.register("randomShip", randomShip, SHIPS)
toolbox.register("populationCreator", tools.initRepeat, list, toolbox.randomShip)
 
population = toolbox.populationCreator(n=POPULATION_SIZE)

Самое сложное в
этом алгоритме оказалось реализовать вычисление значения приспособленности
особи. У меня получилась вот такая функция с применением списков пакета numpy:

def shipsFitness(individual):
    type_ship = [4, 3, 3, 2, 2, 2, 1, 1, 1, 1]
 
    inf = 1000
    P0 = np.zeros((POLE_SIZE, POLE_SIZE))
    P = np.ones((POLE_SIZE+6, POLE_SIZE+6))*inf
    P[1:POLE_SIZE+1, 1:POLE_SIZE+1] = P0 
 
    th = 0.2
    h = np.ones((3, 6)) * th
    ship_one = np.ones((1, 4))
    v = np.ones((6, 3)) * th
 
    for *ship, t in zip(*[iter(individual)] * 3, type_ship):
        if ship[-1] == 0:
            sh = np.copy(h[:, :t+2])
            sh[1, 1:t+1] = ship_one[0, :t]
            P[ship[0] - 1:ship[0] + 2, ship[1]-1:ship[1] + t+1] += sh
        else:
            sh = np.copy(v[:t+2, :])
            sh[1:t+1, 1] = ship_one[0, :t]
            P[ship[0]-1:ship[0] + t+1, ship[1] - 1:ship[1] + 2] += sh
 
 
    s = np.sum(P[np.bitwise_and(P > 1, P < inf)])
    s += np.sum(P[P > inf+th*4])
 
    return s,         # кортеж

В целом, здесь
все просто. Сначала создаем поле P с нулевыми значениями в области
размещения кораблей и величинами 1000 – за пределами игрового поля. Далее идут
вспомогательные матрицы h и v для формирования
масок кораблей, которые, затем, будут добавляться в игровое поле для
формирования числовых значений в соответствии с идеей вычисления
приспособленности особи. В цикле мы перебираем по три значения из хромосомы
индивидуума и по одному значению из списка type_ship. Этот список говорит,
какой тип корабля в данном случае добавляется в игровое поле. Затем, добавляем
маску корабля в соответствии с его ориентацией (вертикальная или
горизонтальная). После расстановки всех кораблей, мы подсчитываем сумму
величин, которые больше 1 и меньше 1000 – это для ошибок в пределах игрового
поля и сумму величин, которые больше 1000 + 0,2∙4 – это величина штрафа
при размещении кораблей за пределами игрового поля. Общая сумма, как раз, и
является значением приспособленности особи.

Дальше, проще.
Объявим еще одну функцию для выполнения мутации хромосомы:

def mutShips(individual, indpb):
    for i in range(len(individual)):
        if random.random() < indpb:
            individual[i] = random.randint(0, 1) if (i+1) % 3 == 0 else random.randint(1, POLE_SIZE)
 
    return individual,

Здесь координаты
могут меняться случайно в пределах от 1 до 10, а ориентация принимает значение
0 или 1.

Затем, регистрируем
все эти функции для выполнения в главном цикле ГА пакета DEAP:

toolbox.register("evaluate", shipsFitness)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", mutShips, indpb=1.0/LENGTH_CHROM)
 
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("min", np.min)
stats.register("avg", np.mean)

В качестве
отбора используется турнирный отбор, а в качестве скрещивания – двухточечное
скрещивание. Также определен экземпляр класса Statistics для сбора
статистики работы ГА.

Наконец,
запускаем алгоритм с помощью нашей функции eaSimpleElitism(), которая
реализует принцип элитизма – сохранения лучших индивидуумов в каждом поколении.
И в конце, считываем статистику, отображаем лучшего индивидуума и графики:

population, logbook = algelitism.eaSimpleElitism(population, toolbox,
                                        cxpb=P_CROSSOVER,
                                        mutpb=P_MUTATION,
                                        ngen=MAX_GENERATIONS,
                                        halloffame=hof,
                                        stats=stats,
                                        verbose=True)
 
maxFitnessValues, meanFitnessValues = logbook.select("min", "avg")
 
best = hof.items[0]
print(best)
 
plt.plot(maxFitnessValues, color='red')
plt.plot(meanFitnessValues, color='green')
plt.xlabel('Поколение')
plt.ylabel('Макс/средняя приспособленность')
plt.title('Зависимость максимальной и средней приспособленности от поколения')
plt.show()

После запуска
программы увидим, следующий график:

Как видим,
решение находится мгновенно. И это не удивительно, так как на поле 10х10
расставить корабли очень просто. Давайте усложним задачу и уменьшим поле до
размеров 7х7:

Здесь лучшего
решения достигнуто не было. Но, если увеличить размер популяции до 200 особей:

то решение
находится на 17-й итерации.

Отображение расположения кораблей

Графики кривых –
это, конечно, хорошо, но куда лучше было бы увидеть полученную расстановку. Для
этого в модуль graph_show.py я добавил
следующую функцию:

v_ship = np.array([0, 1, 2, 3])
h_ship = np.array([0, 0, 0, 0])
type_ship=[4, 3, 3, 2, 2, 2, 1, 1, 1, 1]
colors=['g', 'b', 'm', 'y']
 
def show_ships(ax, best, pole_size):
    rect = Rectangle((0, 0), pole_size+1, pole_size+1, fill=None, edgecolor='r')
 
    t_n = 0
    for i in range(0, len(best), 3):
        x = best[i]
        y = best[i+1]
        r = best[i+2]
        t = type_ship[t_n]
        t_n += 1
 
        if r == 1:
            ax.plot(v_ship[:t] + x, h_ship[:t] + y, ' sb', markersize=18, alpha=0.8, markerfacecolor=colors[t-1])
        else:
            ax.plot(h_ship[:t] + x, v_ship[:t] + y, ' sb', markersize=18, alpha=0.8, markerfacecolor=colors[t-1])
 
    ax.add_patch(rect)

Далее, мы ее
импортируем в основном модуле программы:

from graph_show import show_graph, show_ships

И будем вызывать
на каждой итерации работы ГА, чтобы видеть лучший вариант расстановки. Вначале
определим уже знакомую нам функцию:

def show(ax):
    ax.clear()
    show_ships(ax, hof.items[0], POLE_SIZE)
 
    plt.draw()
    plt.gcf().canvas.flush_events()

Включим
интерактивный режим отображения данных, сформируем окно и координатные оси, а
также установим размер окна и границы осей:

plt.ion()
fig, ax = plt.subplots()
fig.set_size_inches(6, 6)
 
ax.set_xlim(-2, POLE_SIZE+3)
ax.set_ylim(-2, POLE_SIZE+3)

В функции eaSimpleElitism() укажем
параметр callback с функцией show и аргументом ax:

population, logbook = algelitism.eaSimpleElitism(population, toolbox,
                                        cxpb=P_CROSSOVER,
                                        mutpb=P_MUTATION,
                                        ngen=MAX_GENERATIONS,
                                        halloffame=hof,
                                        stats=stats,
                                        callback=(show, (ax, )),
                                        verbose=True)

После выполнения
ГА выключим интерактивный режим и оставим окно с последним вариантом
расстановки кораблей на экране:

После выполнения
программы увидим следующий конечный результат:

Конечно, это
всего лишь пример того, как можно реализовать эту задачу с помощью ГА. Надеюсь,
после примеров с расстановкой кораблей и определением кратчайшего маршрута в
графе, вы стали лучше понимать, как конструируются генетические алгоритмы для
решения тех или иных задач.

Видео по теме

Источник