Как создать статистически вероятные места для кораблей в броненосце

Я сделал оригинальный броненосец, и теперь я хочу обновить свой ИИ от случайного догадки, догадавшись, насколько это возможно. У меня проблемы с поиском алгоритмов в сети, поэтому мой вопрос в том, какие алгоритмы уже существуют для этого приложения? И как я могу реализовать один?

Корабли: 5, 4, 3, 3, 2

Поле: 10X10

Совет:

OCEAN = "O"
FIRE = "X"
HIT = "*"
SIZE = 10
SEA = [] # Blank Board
for x in range(SIZE):
    SEA.append([OCEAN] * SIZE)

Если вы хотите увидеть остальную часть кода, я разместил его здесь: (https://github.com/Dbz/Battleship/blob/master/BattleShip.py); Я не хотел загромождать вопрос с помощью большого количества нерелевантного кода.

Ответ 1

Высшим наивным решением было бы пройти все возможные размещения кораблей (легально, учитывая, какая информация известна) и подсчитывать количество раз, когда каждый квадрат заполнен.

очевидно, на относительно пустой доске это не сработает, так как слишком много перестановок, но хорошим началом может быть:

для каждого квадрата на борту: пройдите через все корабли и подсчитайте, сколько разных способов он подходит в этом квадрате, т.е. для каждого квадрата длины судна проверяет, подходит ли он горизонтально и вертикально.

улучшение может состоять в том, чтобы также проверить каждое возможное размещение судна, если остальные суда могут быть размещены на законных основаниях, охватывая все известные "хиты" (места, которые, как известно, содержат судно).

для повышения производительности, если только одно судно может быть помещено в заданное место, вам больше не нужно проверять его на других местах. также, когда есть много "хитов", возможно, сначала можно будет охватить все известные "хиты" и для каждого возможного покрытия пройти через остальные.

edit: вы можете посмотреть в DFS.

Изменить: Разработка в OP (@Dbz) предложения в комментариях: удерживайте набор уволенных мест размещения ( "dismissed" ) кораблей (может быть представлен как строка, например "4V5x3" для размещения длины 4 корабля в 5x3, 5x4, 5x5, 5x6), после угадывания вы добавляете все места размещения угадывайте увольнения, тогда для каждого квадрата удерживайте множество мест размещения, которые пересекаются с ним ( "места размещения [x, y]" ), тогда вероятность будет: 34-|intersection(placements[x,y], dissmissed)|/(3400-|dismissed|)

Чтобы добавить к уволенному списку:

если угадать (X, Y) является пропуском add placements[x,y]
если угадать (X, Y) является хитом:
- добавить соседние места размещения (при условии, что суда не могут быть размещены рядом), то есть добавить:
  - <(2,3a,3b,4,5)>H<X+1>x<Y>, <(2,3a,3b,4,5)>V<X>x<Y+1>
  - <(2,3a,3b,4,5)>H<X-(2,3,3,4,5)>x<Y>, <(2,3a,3b,4,5)>V<X>x<Y-(2,3,3,4,5)>
  - 2H<X+-1>x<Y+(-2 to 1)>, 3aH<X+-1>x<Y+(-3 to 1)>...
  - 2V<X+(-2 to 1)>x<Y+-1>, 3aV<X+(-3 to 1)>x<Y+-1>...
- if |intersection(placements[x,y], dissmissed)|==33, т.е. возможно только одно место размещения (см. ниже)
проверьте, есть ли у какого-либо из просмотров предварительного просмотра только одно возможное место размещения, если это так, добавьте корабль
проверьте, есть ли у любого из кораблей только возможное размещение, если да, добавьте корабль

добавление корабля:

добавить все другие места размещения этого корабля к увольнению
для каждого (x, y) размещения кораблей добавьте placements[x,y] без фактического размещения
для каждого (x, y) знака размещения корабля как угадайте (если еще не известно) этап выполнения
для каждого (x, y), соседнего с маркой размещения кораблей, как угадать (если еще не известно) этап выполнения
выполните этап 3 и 4.

Возможно, я усложнил это, могут быть некоторые избыточные действия, но вы получите точку.

Ответ 2

Хороший вопрос, и мне нравится ваша идея статистического подхода.
Я думаю, что я бы попробовал машинное обучение для этой проблемы следующим образом:

Сначала создайте свою проблему как проблему .
Задача классификации: учитывая квадрат (x,y) - вы хотите рассказать о вероятности наличия корабля на этой площади. Пусть эта вероятность будет p.

Затем вам нужно разработать некоторые "функции". Вы можете использовать окружение (x,y) [поскольку у вас могут быть частичные знания об этом] в качестве ваших функций.

Например, функции середины следующей мини-платы (+ указывает квадрат, который вы хотите определить, есть ли корабль или нет):

OO*
O+*
?O?

может быть что-то вроде:

f1 = (0,0) = false
f2 = (0,1) = false
f3 = (0,2) = true
f4 = (1,0) = false
**note skipping (1,1)
f5 = (1,2) = true
f6 = (2,0) = unknown
f7 = (2,1) = false
f8 = (2,2) = unknown

Я бы использовал функции относительно точки начала (в данном случае - (1,1)), а не как абсолютное местоположение на борту (поэтому квадрат до (3,3) также будет f2).

Теперь создайте тренировочный набор. Учебный набор представляет собой "помеченный" набор функций, основанный на некоторых реальных платах. Вы можете создать его вручную (создать много плат), автоматически с помощью случайного генератора мест размещения или с помощью некоторых других данных, которые вы можете собрать.

Подайте обучающий набор на алгоритм обучения. Алгоритм должен иметь возможность обрабатывать "неизвестные" и быть в состоянии дать вероятность "истинного", а не только логического ответа. Я думаю, что вариация Наивный Байес может хорошо поместиться здесь.

После того, как у вас есть классификатор - используйте его с вашим AI.
Когда ваша очередь, выберите огонь на квадрат, который имеет максимальное значение p. Сначала снимки будут случайными - но с большим количеством выстрелов вы стреляете, у вас будет больше информации на доске, и ИИ будет использовать ее для лучшего прогноза.

Обратите внимание, что я дал функции, основанные на квадрате размера 1. Вы можете, конечно, выбрать любой k и найти функции на этом большом квадрате - это даст вам больше возможностей, но каждый может быть менее информативным. Нет правильного правила, которое будет лучше - и оно должно быть проверено.

Ответ 3

Главный вопрос: как вы собираетесь найти статистически вероятные местоположения. Они уже известны или вы хотите их выяснить? В любом случае, я бы просто сделал сетку взвешенной. В вашем случае начальный вес для каждого слота будет 1,0/(SIZE ^ 2). Сумма весов должна быть равна 1. Затем вы можете настроить весы на основе статистики, собранной из N последних играемых игр. Теперь, когда ваш ИИ делает выбор, он выбирает координату, попадающую на основе взвешенных вероятностей. Быстрый и простой способ сделать это:

Создать случайное число R в диапазоне [0..1]
Начните с слота (0, 0), добавляя веса, т.е. S = W (0, 0) + W (0, 1) +.... где W (n, m) - вес соответствующий слот. Как только S >= R, вы получите координату.

Это может быть оптимизировано путем предварительного вычисления совокупных весов для каждой строки, получайте удовольствие:)

Ответ 4

Узнайте, какие корабли все еще живы: alive = [2,2,3,4] # длина живых судов
Найдите места, где вы не снимали, например, с помощью numpy.where()
Прокрутите точки, где вы можете снимать.
Проверьте стороны данного положения. Идите влево и вправо, сколько пробелов? Идите вверх и вниз, сколько пробелов? Если вы можете поместить лодку в таком количестве мест, вы можете поместиться на любую маленькую лодку, поэтому этот цикл я бы сделал с самого большого корабля вниз, и я бы добавил к подсчетам в этой позиции столько же, сколько кораблей меньших чем тот, который подходит.
Как только вы все это сделали, позиция с большим количеством очков должна быть наиболее вероятной для атаки и удара.

Конечно, он может стать настолько сложным, насколько вам хочется. Вы также можете спросить себя, а не мой следующий хит, какие комбинации хитов дадут мне победу в меньшем количестве ударов или любой другой комбинации/параметризации проблемы. Удачи!