Отново морска битка
Тъй като седмицата на "Морски бой" на Хабре продължава, ще добавя моите две цента. Когато се опитваме да намерим оптималната стратегия за игра на компютъра, бързо стигаме до това приближение:
Да приемем, че вече знаем състоянието на някои клетки и искаме да направим ход, който ни доближава възможно най-близо до победата. В този случай има смисъл да изберете клетка, която е заета от вражески кораб в най-големия брой възможни разположения на кораби, които не противоречат на наличната информация
Наистина. Ако има само една възможна конфигурация, тогава приключваме играта в един ход, стреляйки по неговите кораби един по един (в края на краищата знаем конфигурацията!) Ако има повече конфигурации, тогава трябва да намалим броя им възможно най-много, като по този начин увеличим количеството информация, която имаме. Ако ударим кораба, няма да загубим нищо (все пак имаме ход!), а ако пропуснем, тогава броят на оставащите комбинации ще бъде минимално възможен след този ход.
Ясно е, че това е само приближение до оптималната стратегия. Ако врагът знае за нашия план, той ще се опита да постави корабите така, че да не попаднат в клетките, където ще стреляме в началото на играта. Вярно, това няма да му помогне много - все пак ще го притиснем в ъгъла накрая - но е възможно известна гъвкавост да не ни навреди. Освен това е възможно една добре обмислена поредица от ходове, първият от които не е оптимален, да доведе до по-добър резултат. Но нека засега не усложняваме и без това трудната задача, а се опитайте да изчислите всички конфигурации и да изградите вероятностна карта за попълване на полето.
Какво друго да опитам? Всеки ученик на олимпиада веднага ще отговори - динамично програмиране. Нокак да го организирам?
Вървим отгоре надолу. От каква информация се нуждаем?
Така че нека да отидем отгоре надолу. Да приемем, че полето е разделено на две части - част A се състои от първите k реда, а част B се състои от всички останали. Запълване на част от поле е всяко двуцветно оцветяване на неговите клетки. Попълването на цялото поле се счита за правилно, ако черните клетки образуват набор от кораби, който отговаря на правилата (корабите са прави, не се допират, дължините им образуват необходимия набор). Ще наречем две запълвания S1 и S2 на част A еквивалентни, ако за всяко попълване T на част B, комбинираните запълвания на цялото поле S1T и S2T са правилни или неправилни едновременно.
За да решим проблема, имаме нужда само от:
- Опишете всички класове на еквивалентност на попълване за част А
- За всеки клас изчислете броя на различните пълнежи и за всяка клетка от област А посочете броя пълнежи, в които е била черна (нека наречем тази информация карта на този клас)
- Опишете преизчисляването на класове и техните карти при добавяне на нов ред към област A.
Да предположим, че имаме неизвестно запълване S на площ A и известно запълване T на област B. Какво трябва да знаем за S?
Първо, хубаво е да имате пълното състояние на последния ред. Само в този случай ще можем да определим кои клетки от първия ред на област B все още могат да бъдат заети и кои не.
Второ, трябва да знаете колко и кои готови кораби вече има в зона А. Наричаме кораб завършен, ако вече не може да бъде разширен до зона 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.
- Има изолирана 1 както в последния ред на S, така и в новия ред. Така че вертикалният кораб продължава и дължината му се увеличава с 1.
Сега нека проверим дали наборът от дължини е валиден. Нека s1, s2, s3, s4 са броят на завършените кораби с дължина съответно 1, 2, 3, 4, а n1, n2, n3, n4 е броят на незавършените кораби със съответните дължини. За да не противоречи комплектът на условията е необходимо следното:
Информацията за новия клас е готова. За да създадете карта за нея, просто копирайте първите редове на старата карта и въведете добавения битов низ, умножен по броя на комбинациите, в следващия ред. Картите от един и същи клас, получени от различни конфигурации, се добавят заедно.
След като добавихме 10 реда към оригиналната празна конфигурация, получихме списък от 1053612 класа, всеки със собствена карта. За да получим карта на всички конфигурации на полето, трябва да преминем през всички тези класове, да „завършим“ незавършените кораби, да преброим броя на корабите от всеки получен размер и ако е правилен, тогава да добавим картата на класа към общата сума.
За празно поле 10x10 се оказа 1855545978831780конфигурации и картата за запълване изглежда така (всички числа разделени на 10 9):
Фактът, че е симетричен косвено потвърждава, че няма груби грешки в програмата :) Най-запълнената клетка е C1, най-незапълнената е B2. След преминаването към C1, картата ще изглежда така:
Поредицата от „най-добри ходове“ с постоянни пропуски изглежда така (вижте снимката): 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. Разликата е малка. Ще бъде необходимо да се организира турнир между тези алгоритми, за да се разбере колко значим е той.