Читая в очередной раз Хабр, я заинтересовался статьей «Морской бой с искусственным интеллектом — по-честному» и программой «Интеллектуальный морской бой».
Попробовав сыграть с ней, я обнаружил, что стратегия программы пока оставляет желать лучшего, т.к. счет был 9:1 в мою пользу.
Я решил поделиться своими мыслями со всеми, и в частности с автором(michurin) программы, т.к. проект очень интересный.
Внимание!
После прочтения данной статьи исход игры «Морской бой» перестанет быть для вас случайностью.
Статья писалась простым языком без использования формул.
«Любая формула, включенная в книгу, уменьшает число ее покупателей вдвое» Стивен Хокинг.
Я бы хотел в легкой и доступной форме изложить алгоритм, который я давно прочитал в книге Е.Я. Гика «Занимательные математические игры».
(При написании статьи алгоритм был дополнен)
Вся стратегия будет описана для «Классического» морского боя
(поле 10х10 у каждого игрока по одному четырехтрубнику, два трехтрубника, три двухтрубника и четыре однотрубника).
Корабли не могут изгибаться.
Корабли не могут соприкасаться.
Игрок делает 1 выстрел, если промахивается, то ход переходит сопернику,
если попадает, делает еще выстрелы до первого промаха).
Конечно успех игры, в какой-то мере зависит от везения. Можно беспорядочно наносить удары по неприятельской территории и при этом без промаха уничтожить все его корабли.
Данная стратегия не даст Вам 100% победы, но увеличит вероятность Вашей победы до максимума.
У нас в классе была девочка, так вот она не выставляла до последнего один однотрубный корабль, но здесь будет описана честная стратегия.
Стратегия состоит из 2-х частей.
1) Правильная расстановка кораблей.
2) Правильная стрельба по противнику.
Правильная расстановка кораблей.
Эта идея уже упоминалась в вышеуказанной статье, повторюсь и распишу подробно для тех, кто не знает.
Суть идеи расставить корабли так, чтобы уменьшить вероятность попадания в них.
Сложнее всего попасть в однотрубник, наша задача расставить остальные корабли на минимальной площади, чтобы оставить как можно больше пространства под однотрубники.
Такой расстановкой является расстановка «по краям» или «по периметру».
Таким образом, когда будут потоплены все «большие» корабли, искать однотрубники будет весьма непросто.
Покажу на примере:
Постарался сохранить цветовую схему, как в вышеописанной игре.
Желтый = корабли
Голубой = надстройка (место вокруг корабля, где не может находиться соседний корабль)
Морской волны (cyan) = оставшаяся территория для расстановки однотрубников.
При написании статьи была случайно найдена расстановка, которой не было в рассмотренной в книге.
Расстановки могут также получаться зеркальными отражениями по вертикали и горизонтали, а также поворотом поля на 90, 180, 270 градусов.
Область, оставшаяся для расстановки 4-х однотрубных кораблей, получается 60 клеток. Следовательно, вероятность попадания в однотрубный корабль составляет 4 из 60 или 6,67%. При других расстановках вероятность попадания выше.
Рассмотрим произвольную расстановку, которая была предложена программой.
(однотрубники я убрал, для чистоты эксперимента).
33 клетки для расстановки 4 однотрубных кораблей, это почти в 2 раза меньше,
т.е. вероятность моего выигрыша была почти в 2! раза выше (не учитывая оптимальность стрельбы).
Правильная стрельба по противнику
Идея правильной стрельбы заключается в следующем.
Сначала нужно стараться попасть в самый большой корабль (для классики это 4-х трубник), т.к. попасть в него вероятностно проще, чем в однотрубник.
Разобьем поле на области 4х4 (произвольно). Должно получиться 4 полных квадрата и все, что осталось.
Для этого существует 7 комбинаций, которые могут быть так же расширены путем зеркальных отражений и поворотов. При таком простреле нельзя вписать в квадрат 4х4 четырехтрубник.
Все поле простреливается в любой последовательности, соблюдая комбинацию.
Если мы попадаем в какой-то корабль, то надо его добивать до конца.
После того как корабль подбит, вокруг него рисуется надстройка в одну клетку,
чтобы туда зря не стрелять.
Далее, когда 4-х трубник потоплен, ищем 3-х трубники, простреливаем экономно поля так, чтобы было не поставить 3-х трубник.
Делим поле на квадраты 3х3. Стреляем так, чтобы нельзя было поставить 3-х трубник.
И так далее. Доходим до однотрубников, далее как повезет.
Ну вот, в принципе, и все.
После того как все в классе знали эту стратегию, мы перешли к игре «Морской бой» (на поле 5х5 выставляется 4 однотрубника).
После этого игра стала носить больше психологический характер (кто как повторяется или не повторяется при расстановке), чем математический.
Заключение:
Предлагаю автору(michurin) «Морского боя с интеллектом» взять на вооружение данную стратегию и использовать ее частями в зависимости от выставленного уровня интеллекта программы.
PS При написании данной статьи ни один корабль ВМФ не пострадал =).
PS2 Мои игры с программой:
UPD Картинки исправил(переложил с pict.com на imagehack), но их по прежнему не видно.
UPD2 Переложил все на habrastorage.org вроде все видно.
Попробовав сыграть с ней, я обнаружил, что стратегия программы пока оставляет желать лучшего, т.к. счет был 9:1 в мою пользу.
Я решил поделиться своими мыслями со всеми, и в частности с автором(michurin) программы, т.к. проект очень интересный.
Внимание!
После прочтения данной статьи исход игры «Морской бой» перестанет быть для вас случайностью.
Статья писалась простым языком без использования формул.
«Любая формула, включенная в книгу, уменьшает число ее покупателей вдвое» Стивен Хокинг.
Я бы хотел в легкой и доступной форме изложить алгоритм, который я давно прочитал в книге Е.Я. Гика «Занимательные математические игры».
(При написании статьи алгоритм был дополнен)
Вся стратегия будет описана для «Классического» морского боя
(поле 10х10 у каждого игрока по одному четырехтрубнику, два трехтрубника, три двухтрубника и четыре однотрубника).
Корабли не могут изгибаться.
Корабли не могут соприкасаться.
Игрок делает 1 выстрел, если промахивается, то ход переходит сопернику,
если попадает, делает еще выстрелы до первого промаха).
Конечно успех игры, в какой-то мере зависит от везения. Можно беспорядочно наносить удары по неприятельской территории и при этом без промаха уничтожить все его корабли.
Данная стратегия не даст Вам 100% победы, но увеличит вероятность Вашей победы до максимума.
У нас в классе была девочка, так вот она не выставляла до последнего один однотрубный корабль, но здесь будет описана честная стратегия.
Стратегия состоит из 2-х частей.
1) Правильная расстановка кораблей.
2) Правильная стрельба по противнику.
Правильная расстановка кораблей.
Эта идея уже упоминалась в вышеуказанной статье, повторюсь и распишу подробно для тех, кто не знает.
Суть идеи расставить корабли так, чтобы уменьшить вероятность попадания в них.
Сложнее всего попасть в однотрубник, наша задача расставить остальные корабли на минимальной площади, чтобы оставить как можно больше пространства под однотрубники.
Такой расстановкой является расстановка «по краям» или «по периметру».
Таким образом, когда будут потоплены все «большие» корабли, искать однотрубники будет весьма непросто.
Покажу на примере:
Постарался сохранить цветовую схему, как в вышеописанной игре.
Желтый = корабли
Голубой = надстройка (место вокруг корабля, где не может находиться соседний корабль)
Морской волны (cyan) = оставшаяся территория для расстановки однотрубников.
При написании статьи была случайно найдена расстановка, которой не было в рассмотренной в книге.
Расстановки могут также получаться зеркальными отражениями по вертикали и горизонтали, а также поворотом поля на 90, 180, 270 градусов.
Область, оставшаяся для расстановки 4-х однотрубных кораблей, получается 60 клеток. Следовательно, вероятность попадания в однотрубный корабль составляет 4 из 60 или 6,67%. При других расстановках вероятность попадания выше.
Рассмотрим произвольную расстановку, которая была предложена программой.
(однотрубники я убрал, для чистоты эксперимента).
33 клетки для расстановки 4 однотрубных кораблей, это почти в 2 раза меньше,
т.е. вероятность моего выигрыша была почти в 2! раза выше (не учитывая оптимальность стрельбы).
Правильная стрельба по противнику
Идея правильной стрельбы заключается в следующем.
Сначала нужно стараться попасть в самый большой корабль (для классики это 4-х трубник), т.к. попасть в него вероятностно проще, чем в однотрубник.
Разобьем поле на области 4х4 (произвольно). Должно получиться 4 полных квадрата и все, что осталось.
Для этого существует 7 комбинаций, которые могут быть так же расширены путем зеркальных отражений и поворотов. При таком простреле нельзя вписать в квадрат 4х4 четырехтрубник.
Все поле простреливается в любой последовательности, соблюдая комбинацию.
Если мы попадаем в какой-то корабль, то надо его добивать до конца.
После того как корабль подбит, вокруг него рисуется надстройка в одну клетку,
чтобы туда зря не стрелять.
Далее, когда 4-х трубник потоплен, ищем 3-х трубники, простреливаем экономно поля так, чтобы было не поставить 3-х трубник.
Делим поле на квадраты 3х3. Стреляем так, чтобы нельзя было поставить 3-х трубник.
И так далее. Доходим до однотрубников, далее как повезет.
Ну вот, в принципе, и все.
После того как все в классе знали эту стратегию, мы перешли к игре «Морской бой» (на поле 5х5 выставляется 4 однотрубника).
После этого игра стала носить больше психологический характер (кто как повторяется или не повторяется при расстановке), чем математический.
Заключение:
Предлагаю автору(michurin) «Морского боя с интеллектом» взять на вооружение данную стратегию и использовать ее частями в зависимости от выставленного уровня интеллекта программы.
PS При написании данной статьи ни один корабль ВМФ не пострадал =).
PS2 Мои игры с программой:
UPD Картинки исправил(переложил с pict.com на imagehack), но их по прежнему не видно.
UPD2 Переложил все на habrastorage.org вроде все видно.
