Морський бій за 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()):
cord for 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. Буду вдячний за будь-які цікаві ідеї.

Спасибі.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.