Бот для гри - Морський бій історія, теорія, практика Архів - Speccy - наш вибір!
Математичний аналіз гри в "Морський бій" займав мене з давніх-давен. Все почалося з 1996 року, коли я замахнувся реалізувати сильного бота для гри в "Морський бій" на сувенірному годиннику з мікропроцесором Z80, причому бота, що грає чесно, не підглядаючи в кораблі супротивника.
Інтернету тоді не було, а де ще можна було знайти подібну теорію, я також не уявляв. Було вирішено розпочати з опитування одногрупників, які були сильні у цій грі. Але опитування показало, що ці люди або приховують, або не мають формального методу найкращої стрілянини. Діють інтуїтивно. Повідомили мені пару прийомів, але опис був такий, який важко піддається алгоритмізації. Залишалося лише діяти самому. І я почав думати.
Взагалі кажучи, сильна гра у морський бій і двох складових: правильне розташування своїх кораблів і правильна стрілянина по кораблям противника. Але в 1996-1997 р я займався тільки стріляниною, а до розташування так і не зрозумів, як підступитися. Тож почнемо і ми зараз розмову зі стрілянини, повернувшись до розташування згодом.
Вихідний пункт моїх роздумів на той момент - це був один гарний прийом, підказаний спектрумістом Андрієм Гетало, під час гри у "Battleships". Там кораблі були більшими, тому цей прийом дуже добре діяв. Наприклад, щоб знайти корабель довжиною в 4 клітини, потрібно в першу чергу стріляти по відкритих довгих лініях, причому з інтервалом у 3 клітини, тобто. так, щоб між пострілами цей корабель було сховатися. Причому кожен постріл в ідеалі повинен максимально скорочувати довгі лінії як по горизонталі, так і по вертикалі.
З іншого боку, оскільки "Морський бій" - гра з випадковістю, то було зрозуміло, що необхідно якимось чином залучати теорію ймовірностей і в неїтермінах, намагатися стріляти туди, де існує максимальна можливість вразити корабель супротивника.
Сформулювати завдання стрілянини в рамках теорвера – справа непроста, тим більше для мене на 2-му курсі, коли теорвер тільки почали проходити. Але все ж таки я тоді додумався до наступної ідеї, яка виявилася дуже близькою до оптимуму. Я почав обчислювати для кожної вільної клітини величину, яку я назвав число можливостей розміщення. Що це таке?
Уявімо чисте (необстріляне) поле супротивника і якусь клітину в центрі поля. Розглянемо корабель завдовжки 4 клітини. Скільки існує можливостей розмістити цей корабель, щоб він однією зі своїх частин опинився у цій клітці? Відповідь проста. Корабель можна розмістити по горизонталі чотирма способами, щоб одна з його клітин потрапила до шуканої, і ще чотирма по вертикалі. Усього 8.
Тепер представимо ту саму ситуацію, але клітка праворуч від шуканої вже обстріляна (там "мимо"). Скількими способами можна розмістити 4-палубний корабель, щоб одна з його частин потрапила в клітину? Очевидно, що ніяка частина корабля тепер не може опинитися в тій клітці, де мимо. Отже, по горизонталі 4-палубний корабель може бути розміщений тільки одним способом: так, щоб крайня права клітина була в аналізованої, а інші зліва. По вертикалі кількість можливостей розміщення залишається недоторканим, тобто. 4, а лише 5 можливостей розміщення.
Число можливостей розміщення пов'язане з ймовірністю знаходження корабля в цій клітині. Чому? Відповідь можна довести суворо. Корабель довжиною 4 клітини може бути розміщений на полі кінцевим числом способів - назвемо це число m. З них n припадає на клітину, яку ми розглядаємо. Якщо всі розміщення корабля на полі є рівноймовірними (а у наспоки немає причин вважати інакше) - то ймовірність знаходження корабля в даній клітині буде n/m, де n - кількість можливостей розміщення, як я визначив це число вище. Таким чином, ймовірність знаходження корабля у клітині пропорційна числу можливостей його розміщення у ній. Важливо: наведене вище міркування справедливе тільки для випадку, коли на полі немає інших кораблів. Коли є інші кораблі, ситуація значно ускладнюється, і ймовірність більше залежить так явно від кількості можливостей розміщення.
Отримати деяке число, що відповідає ймовірності, для випадку багатьох кораблів, на 1996 р. мені не вдалося, тому я обмежився наступним алгоритмом стрільби: 1) для кожної вільної клітини обчислити кількість можливостей розміщення в ній найдовшого корабля супротивника, який ще залишається на полі . 2) Знайти всі клітини, де кількість можливостей розміщення досягає максимуму. 3) Вистрілити випадковим чином одну з цих клітин з максимумом.
Наприклад, для чистого (необстріляного) поля кількість можливостей розміщення 4-палубного корабля виглядає так для кожної клітини:
2 3 4 5 5 5 5 4 3 2 3 4 5 6 6 6 6 5 4 3 4 5 6 7 7 7 7 6 5 4 5 6 7 8 8 8 8 7 6 5 5 6 7 8 8 8 8 7 6 5 5 6 7 8 8 8 8 7 6 5 5 6 7 8 8 8 8 7 6 5 4 5 6 7 7 7 6 5 4 3 4 5 6 6 6 6 5 4 3 2 3 4 5 5 5 5 4 3 2
Після пострілу в клітину з максимальним числом можливостей розміщення (наприклад, Г-4) карта змінювалася таким чином:
2 3 4 4 5 5 5 4 3 2 3 4 5 4 6 6 6 5 4 3 4 5 6 4 7 7 7 6 5 4 4 4 4 0 5 6 7 7 6 5 5 6 7 5 8 8 8 7 6 5 5 6 7 6 8 8 8 7 6 5 5 6 7 7 8 8 8 7 6 5 4 5 6 7 7 7 7 6 5 4 3 4 5 6 6 6 6 5 4 3 2 3 4 5 5 5 5 4 3 2
Як видно, навіть один постріл суттєво змінює картину розподілуможливостей розміщення 4-палубного корабля. Постріл у клітину з максимальною кількістю таких можливостей як обнуляв це число у самій клітині, а й максимально зменшував його значення переважають у всіх інших клітинах. Число клітин з максимумом у прикладі впало з 16 до 9, скорочуючи вибір можливостей для наступного пострілу. Зрештою, до підбиття 4-палубного корабля, поле супротивника покривалося "візерунок" зі пострілів, який приймав різні форми, але завжди в ньому дотримувалося одна властивість: відстань між сусідніми пострілами по горизонталі та вертикалі не перевищувала 3, що не дозволяло 4- палубнику "проскочити" цей візерунок.
Підбиття 4-палубника виводило з гри відразу безліч клітин (адже інші кораблі не могли розміщуватися впритул до нього). Це скорочувало подальше поле пошуків. Після підбиття 4-палубника обчислення можливостей розміщення проводилося для 3-палубних кораблів тощо. Для однопалубних кораблів, очевидно, цей алгоритм не дає жодних переваг. Тому у реалізації 1997 р я виключив їх із гри.
Коли підбивався якийсь корабель, алгоритм стрілянини переходив у режим добивання корабля. Тут я не зміг на той момент знайти будь-яких критеріїв підвищення ймовірності поразки, тому стріляв у будь-яку з клітин навколо тієї, яка підбита, якщо по цій лінії міг бути розміщений корабель супротивника мінімальної довжини з тих, що залишилися. Після підбиття другої клітини корабля супротивника стрілянина проводилася лише вздовж лінії, де розташований цей корабель. Добивання корабля супротивника всіма гравцями, у тому числі моїм алгоритмом, вважається пріоритетним перед пошуком кораблів, що залишилися. Обгрунтування просте: підбиття корабля виключає з гри не лише обстріляні клітини, а й клітини навколо підбитого корабля, тим самимзначно зменшуючи можливості розміщення інших кораблів, і навіть змінюючи картину максимумів числа можливостей цього розміщення.
Розміщення своїх кораблів на полі на 1997 р. проводилося мною за наступним методом. Спочатку на полі розміщувався корабель максимальної довжини випадковим чином. Потім була спроба розмістити наступний корабель випадковим чином. Якщо згенеровані випадкові числа потрапляли так, що новий корабель не може бути розміщений (він потрапляє в вже наявний корабель або його "ореол") - то спроба повторювалася, і так до переможного кінця. Таким чином, на той момент я не намагався розмістити кораблі таким чином, щоб противнику було важче їх знайти. Це зумовило слабку гру мого робота 1997г.
Викладені вище концепції я спочатку реалізував у програмі на Паскалі – seaboy.pas. Так було простіше проводити налагодження, я мав компілятор Turbo Pascal під CP/M. Коли алгоритм на Паскалі був налагоджений, я розпочав його переклад на асемблер.
Алгоритм стрілянини діяв дуже ефективно. Застосовуючи його під час гри проти людей, я зміг досягти істотних успіхів. Звичайно, я не міг сам розрахувати всі ці числа – можливості розміщення – в умі, але намагався приблизно вгадати, де вони максимальні.
Алгоритм стрілянини має, однак, один важливий недолік. Він насамперед обстрілює середину поля, а межі його – в останню чергу. Отже, якщо розміщувати кораблі вздовж меж поля - то мій алгоритм стрілянини 1997 дуже нескоро їх знайде. Звідси видно, що алгоритм стрілянини можна поліпшити. Про це та про інші алгоритми сильної гри йтиметься в наступних повідомленнях.