Морской бой за 25 мс

в 8:56, , рубрики: python, Алгоритмы, Морской бой, обучение программированию, Программирование

Предисловие

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

Спасибо.

Автор: balamut108

Источник

Поделиться

* - обязательные к заполнению поля