Знову «Морський бій»
Якщо вже тиждень «Морського бою» на Хабрі триває, додам і я свої два центи. При спробі знайти оптимальну стратегію для гри за комп'ютер досить швидко приходимо до такого наближення:
Припустимо, що стан деяких клітин нам уже відомий, і ми хочемо зробити хід, який максимально наближає нас до перемоги. У такому разі має сенс вибирати клітину, яка зайнята кораблем противника у найбільшій кількості можливих розміщень кораблів, що не суперечать наявній інформації.
Справді. Якщо можлива конфігурація лише одна, то ми закінчуємо гру за один хід, розстрілюючи його кораблі по черзі (адже конфігурація нам відома!) Якщо ж конфігурацій більше, то нам потрібно зменшити їх число якнайсильніше, тим самим збільшивши наявну в нас кількість інформації. Якщо ми потрапимо в корабель, то нічого не втратимо (адже хід залишається у нас!), а якщо промахнемося — то кількість комбінацій, що залишилися, буде мінімальною з можливих після цього ходу.
Зрозуміло, що це лише наближення до відпимальної стратегії. Якщо противник знатиме про наш план, він намагатиметься розмістити кораблі так, щоб вони не потрапляли в ті клітини, куди ми стрілятимемо на початку гри. Щоправда, йому це допоможе мало — ми все одно врешті-решт затиснемо його в кут — але можливо, певна гнучкість нам не завадила б. Крім того, не виключено, що продумана серія ходів, перший з яких не є оптимальним, привела б до кращого результату. Але не будемо поки що ускладнювати і без того складне завдання, а спробуємо прорахувати всі конфігурації та побудувати карту ймовірності заповнення поля.
Що ще спробувати? Будь-який олімпіадник відразу відповість — динамічне програмування. Алеяк його організувати?
Ідемо зверху донизу. Яка інформація нам потрібна?
Отже, йтимемо зверху донизу. Припустимо, що поле у нас розділене на дві частини — частина A складається з перших рядків k, а частина B — з усіх інших. Заповненням частини поля назвемо будь-яку розмальовку його клітин у два кольори. Заповнення всього поля називається коректним, якщо чорні клітини утворюють набір кораблів, що відповідає правилам (кораблі прямі, не стикаються, їх довжини утворюють потрібний набір). Два заповнення S1 та S2 частини A ми називатимемо еквівалентними, якщо для будь-якого заповнення T частини B об'єднані заповнення всього поля S1T та S2T будуть коректними або некоректними одночасно.
Для вирішення завдання нам достатньо:
- Описати всі класи еквівалентності заповнень для частини A
- Для кожного класу обчислити кількість різних заповнень, і кожної клітини області A вказати, у якому числі заповнень вона була чорної (назвемо цю інформацію картою даного класу)
- Описати перелік класів та їх карток при додаванні до області A нового рядка.
Нехай у нас є невідоме заповнення області S A і відоме заповнення області T B. Що нам достатньо знати про S?
По-перше, непогано мати повний стан останнього рядка. Тільки в цьому випадку ми зможемо визначити, які клітини першого рядка області B ще можемо займати, а які — ні.
По-друге, треба знати, скільки та яких закінчених кораблів в області A вже є. Закінченим ми називаємо корабель, який вже не можна продовжити в область B. У нашому випадку це або кораблі, які не мають клітин в останньому рядку, або кораблі, що повністю лежать у ній (і займають дві або більше клітини).
По-третє, про кожен корабель, який можна продовжити в область B, нам потрібнознати його поточну довжину. Самі ці кораблі легко впізнати за останнім рядком: вони займають у ній одну чорну клітку, оточену білими полями.
І все. Клас еквівалентності цілком визначається цими даними, причому навіть всі їх комбінації є допустимими. Порахуємо, скільки вийшло:
- Останній рядок: 10 біт, причому не всі варіанти можливі: не може йти більше 4 одиниць поспіль, і не може бути двох груп по 4 одиниці (0111101111). Усього виходить 909 варіантів.
- Вже виставлені кораблі. Від 0 до 4 однопалубних, від 0 до 3 двопалубних, від 0 до 2 трипалубних, 0 або 1 чотирипалубний. Усього 120 варіантів.
- Для кожного ізольованого біта рядки - число клітин у відповідному вертикальному кораблі, що потрапили в A: від 1 до 4. Таких кораблів не більше 5, разом не більше 1024 варіантів.
Додаємо новий рядок
Нехай ми маємо заповнення S, про яке нам відома лише описана вище інформація. Ми хочемо продовжити його ще на один рядок: перерахувати всі заповнення, які можна отримати, визначити класи для них і для кожного нового класу побудувати карту щільності заповнень.
Спочатку подивимося, які рядки ми можемо додавати до нашого заповнення. Основний критерій відомий усім: чорна клітина нового рядка може бути сусідньої по діагоналі з чорною клітиною останнього рядка S. Далі, як ми знаємо, у новому рядку може бути занадто довгих кораблів. І ще, якщо один із вертикальних кораблів має довжину 4, то продовжуватися на новий рядок він теж не може. Інші обмеження пов'язані з наборомкораблів, та їх зручніше перевіряти потім.
Переберемо всі рядки, які можна додати. Якщо рядку є більше однієї одиниці поспіль, всі вони утворюють горизонтальний корабель — його відразу враховуємо в лічильниках закінчених кораблів. Із ізольованими одиницями є три ситуації:
- В останньому рядку S ізольована одиниця була, а в новому рядку тут її немає. Значить, корабель закінчено, і його довжина додається до лічильника.
- У новому рядку ізольована одиниця є, а в останньому рядку S тут її не було. Отже, з'явився новий вертикальний корабель, і його довжина дорівнює 1.
- Ізольована одиниця є і в останньому рядку S, і в новому рядку. Значить, вертикальний корабель продовжується, та його довжина збільшується на 1.
Тепер перевіримо, чи припустимо набір довжин. Нехай s1, s2, s3, s4 – число закінчених кораблів довжини 1,2,3,4 відповідно, а n1, n2, n3, n4 – число незакінчених кораблів із відповідними довжинами. Щоб набір не суперечив умовам, необхідно:
Інформація для нового класу готова. Щоб побудувати для нього карту, достатньо скопіювати перші рядки старої карти, а наступний рядок вписати доданий бітовий рядок, помножений на кількість комбінацій. Карти одного й того класу, отримані з різних змін, складаються.
Після того, як ми додали до вихідної порожньої конфігурації 10 рядків, у нас вийшов список із 1053612 класів, кожен зі своєю карткою. Щоб отримати карту всіх конфігурацій поля, нам треба пройтися по всіх цих класах, «закінчити» незакінчені кораблі, порахувати кількість кораблів кожного розміру, і якщо воно правильне - то додати карту класу до загальної суми.
Для порожнього поля 10x10 вийшло 1855545978831780конфігурацій, а карта заповнення виглядає так (усі числа поділені на 109):
Те, що вона симетрична, побічно підтверджує, що грубих помилок у програмі немає :) Найбільша заповнена клітина - С1, найзаповнена - B2. Після ходу в С1 карта набуде такого вигляду:
Послідовність кращих ходів при постійних промахах виглядає так (див. малюнок): C1, J8, A8, H1, A4, J4, D10, G10, E1, D2, B3, A2, C9, B10, H9, I10, I7, J6, I5, H6, J2, I3, H4, G5, G2, F3, E4, B7, A6, B5, C6, C3, D4, D5, F6. Видно, що програма не поспішає ловити лінкори. До 24-го ходу, коли «діагонального» алгоритму залишився б останній хід до гарантованого попадання, кількість розташувань кораблів, що залишилися, становить приблизно 240*10 9 , а у «діагонального» алгоритму воно становить 260*10 9 . Різниця невелика. Треба буде влаштувати турнір між цими алгоритмами, щоб з'ясувати, наскільки вона є суттєвою.