0,0
рейтинг
16 января 2015 в 11:56

Разработка → Морской бой за 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. Буду признателен за любые интересные идеи.

Спасибо.

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 игрока играют между собой на вылет).
image

Основные выводы:
Стратегии расстановки однопалубных кораблей 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!
Владимир Сидоров @balamut108
карма
5,2
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (28)

  • 0
    А есть эвристика для такой штуки, например:
    * * *...... *
    0123456789
    * — звёздочка — простреленные клетки
    . — непростреленные клетки
    И известно, что остался четырёхпалубный корабль. тогда есть смысл стрелять в 5 и 6, и мы попадём в четырёхпалубный.

    Или, например:
    х — простреленный
    o — мимо
    *.. o x x..
    0123 4 5 67
    и смысла стрелять в 2 меньше, чем в 6.
  • –2
    Сделать турнир между игроками, скажем, где будет 1000 игроков. По идее, с учётом текущего времени выполнения весь турнир должен занять примерно 30 сек.

    А вы как считали? Для 1000 игроков получится, что каждый бот стрельнет в противников 999 раз за свой ход (по крайней мере должен так стрелять, т.к. если стрелять лишь раз в абы кого по рандому или только в следующего по кругу — как-то нечестно по отношению даже к самому себе).
    И тогда получается, что турнир с 1000 морских ботиков займет далеко не 30сек.
    В любом случае ждем рассказ о таком мясе :)
    • 0
      Ну они не одновременно же все играть будут.
  • +7
    Ну и интересней было бы сделать разнообразные подключаемые эвристики расстановки кораблей и атак, и проводить турниры между разными ИИ (различные комбинации эвристика). Вот это реально будет интересно. А бой между 1000 одинаковых ботов сводится к вероятностным флуктуациям.
    • +4
      Ну и совсем круто будет сделать все это на нейросетях :)
      • +3
        И для полного эпика — боты собираются в кланы и эволюционируют через генетические алгоритмы. А последний оставшийся сражается с человеком.
        • +2
          А с человеком он сражается на бумаге или уже вживую?
          • 0
            Через нейроинтерфейс. Главное, чтобы не раскусил, что такое азарт, и на душу контроль над мозгом играть не начал, бесовское поделие.
          • 0
            Хех, Хабра среди трёх случайных постов внизу выдала это. Она явно что-то знает! :-)
        • 0
          Интересная идея, между прочим. Раз мощности современного ширпотребного компьютера уже с китовой головой хватает для такой задачи, можно смоделировать реальную эволюцию. Причём можно даже не вносить специально случайные мутации из внешней программной среды — достаточно запустить всё это дело на хардвари, не защищённой троекратным подсчётом (который присутствует практически во всей современной вычтехнике, дабы мимокрокоэлектроны не свели её надёжность до уровня ламповых компьютеров, так что железки придётся искать долго или вообще на заказ делать). Порезвятся, глядишь — и вирус сам появится, а если его выпустить — так вообще в ИИ переродится и будет троллить нубов, забывших про недобитый корабль :3 Хороший способ немного присмирить научных креационистов. Может, было уже?
          • 0
            Было. Скайнет называлось.
            • 0
              Куда делось? :-)
              • 0
                Это был opensource — его забросили :)
                • 0
                  Возможность свободного саморазвития — это куда больше, чем opensource. Впрочем, тут и source не нужен, ибо костыль для человеков и в некотором роде — для кроссплатформенности… И кстати говоря — почему радетели GNU GPL и прочих зашквар-лицензий пекутся о свободе распространения и модификации сырцов, но почти не заморачиваются тем же по отношению к бинарникам? Ведь любую программу при должном умении и достаточном времени можно модифицировать без обращения к каким-то промежуточным текстам, собираемость которых ещё нужно доказать (всякие компрессоры да обфускаторы не аргумент — усложнить понимание запросто можно и у сырцов, тонны пожатого JS в вебе тому отличный пример). Понятно, что с достижением их главной цели — мира во всём мире распространения сырцов любой программы проблемы бинарников вроде бы уходят на второй план, ведь всему можно будет подредактировать сырцы и пересобрать — но ведь конечному пользователю куда удобнее пропатчить бинарник, чем обзаводиться софтом для сборки, нужными хедерами и тратить время и ресурсы на сборку бинарника (что особо критично, если программа увесистая). Но бинарные патчи никто не защищает — а ведь, например, для проприетарных виндопрограмм их полно, и это не только кряки :-) при этом пользовательское соглашение зачастую модификацию бинарей запрещает. Необходимость выпуска нового патча для каждой версии бинарника — тоже не столь большая проблема, ибо обычно меняются только оффсеты.
    • +3
      Так оптимальная стратегия вроде известна. Все корабли похоронить на одной половине поля, кроме однопалубника. Тогда минимизируем эффект от вычисления клеток. Смотрите, когда топят однопалубник, который стоит среди пустого пространства — вокруг него образуется мертвая зона в 8 клеток. Одно попадание и на 9 клеток меньше щупать. Теперь передвинем его вплотную в угол. Чувствуете разницу? В результате противник вынесет в один ход 99% ваших кораблей, а потом будет тупо по вероятностному закону долбить вторые пустые пол-поля в поисках однопалубника. Это даст гораздо больше вероятностных промахов/переходов хода.
      • 0
        Спасибо! Только что реализовал добавление ореола к списку пробитых координат и среднее количество ходов сократилось до 60.
  • +3
    Е.Я. Гик «Занимательные математические игры», 1987г.
    http://habrahabr.ru/post/180995/
    http://geektimes.ru/post/82221/

  • +3
    Высокочастотный морской бой )
  • +1
    Автор, а вы эту статью читали? Чтобы хорошо стрелять, нужно много вычислять.

    Вот еще материалы по теории игры: zx-pk.ru. Там по расстановке кораблей методом выбора равномерно по всем возможным их расположениям.
    • 0
      Благодарю Вас за интересные ссылки. Обязательно ознакомлюсь. А вообще всё-таки цель статьи была в реализации на Python. Понятное дело, что в теории можно много чего придумать, а вот другое дело реализовать это (для меня сейчас более актуальна практика нежели правильная и красивая теория).
      • 0
        Еще можно взглянуть на игру с другого ракурса, как на покер например.
        В покере две составляющих:
        -математическая (просчет вероятности победы, поражения, все ясно думаю)
        -человеческая (анализ реакции игроков, поведение, блеф и т.д.)

        И если с математической составляющей все довольно просто и много раз описано то с человеческой точки зрения не все так однозначно.
        Так как в морской бой играют между собой два человека и расположение противника заведомо неизвестно то никто не мешает жульничать :)
        Например есть игрок А и игрок Б. Игрок А выстрелил и ранил корабль игрока Б. Игрок Б в свою очередь может сказать правду, сознаться в ранении корабля, либо проанализировав карту сказать что игрок А промахнулся и переместить корабль в другое свободное место. Возможен и другой вариант, игрок А ранил корабль игрока Б большой длины и начинает обстреливать клетки вокруг для определения направления корабля. Опять же игрок Б может анализировать свою карту и поворачивать корабль, конечно если это не нарушает правил игры.
        При игре двух компьютерных игроков такая игра может продолжаться практически до заполнения всего поля :) при игре компьютера с человеком можно использовать например несколько уровней сложности, допустим компьютер не может двигать корабли, может двигать только один раз, два, три и т.д. Причем для человека тоже можно дать такую возможность мухлежа :) Мне кажется именно возможность мухлежа сделает игру более интересной и приближенной к человеческой игре нежели обычный обстрел по данным матстатистики.
        • 0
          Я надеюсь, что когда реализую все озвученные мной улучшения у меня останется желание реализовать что-нибудь эдакое. Спасибо за идею!
        • +2
          И если с математической составляющей все довольно просто и много раз описано

          Я бы не сказал, что в «морском бое» все так просто. Те статьи, на которые я сослался, впервые за всю историю «Морского боя» приводят более-менее глубоко разработанную теорию этой игры, а первая ссылка — еще и пригодный практически метод расчетов по ней.

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

          Метод оптимального обстрела, разработанный по статьям в ссылках, обеспечивает максимально быстрый поиск кораблей противника исходя из их случайного размещения по множеству всех возможных размещений. В чем-то это работает подобно игре «угадай число от 1 до 100». Оптимальный метод угадывания в ней — двоичный поиск. Двоичный поиск использует 7 попыток в наихудшем случае, однако большинство чисел угадывается быстрее, чем за 7 попыток. Загадывающий не может увеличить максимальное число попыток угадывающего, но он может всегда реализовать наихудший случай. Если игроки соревнуются, кто из них быстрее угадает число другого, то загадавший более «трудное» число выиграет, т.к. реализует для противника наихудший случай.

          Однако, если противник знает, что мы будем загадывать такие числа, для которых реализуется наихудший случай в методе двоичного поиска — то он может изменить алгоритм отгадывания, чтобы быстрее угадывать именно такие числа. Если загадывающий поймет, что стратегия угадывающего изменилась, и его прежний трюк больше не работает — то он может сам поменять стратегию загадывания своих чисел, чтобы снова реализовать наихудший случай соперника. И т.д.

          В «Морском бое» все эти соображения тоже применимы. Против описанного метода оптимального обстрела нельзя выстоять совсем: рано или поздно противник потопит все ваши корабли. Но, зная метод обстрела, можно размещать свои корабли так, чтобы реализовался наихудший случай для обстрела, чтобы противник много мазал. При этом, однако, появятся возможности изменить алгоритм обстрела, отклонить его где-то от оптимума, чтобы избежать реализации наихудших случаев. Это уже теория игр неслабая получается. Может быть, займусь этим, когда дойдут руки оптимизировать и доделать исходную реализацию обстрела.
  • 0
    Если вы ещё не используете pypy, попробуйте. Есть ненулевая вероятность, что скорость работы повысится в несколько раз.
    • –3
      Долго пытался понять, что за рура. Разработчики явно хотят утащить пару листочков с лавров Pidora. А у скомпилированных питонопрограмм вообще расширение .pyc…
      • 0
        Возможно, вы не знали, но самая распространенная версия Python зовётся CPython — потому что реализация на Си. Как нетрудно после этого догадаться, JPython — это Python на Java, а PyPy — это Python на Python. PyPy использует JIT, и поэтому часто работает быстрее, чем CPython; на моих типичных задачах прирост производительности раза в три-четыре.
        • 0
          Знать-то знали, а распознать среди русского текста не так-то просто, тем более в нижнем регистре.
  • 0
    Интересно, я вот тоже совсем недавно для интереса завершил морской бой (одиночная игра и сетевая версия). Для компьютера не стал сильно «заморачиваться» и логика простая на рандоме (за исключением момента после попадания в корабль, где вычисляется клетка следующего выстрела). Так вот, даже с такой простой логикой компа победить достаточно не просто. Представляю какой он злой будет если «заморочиться» больше.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.