Судя по записям задач поиска контуров, brainfuck кодирования многим интересна алгоритмика, как одна из сторон программирования.
Предлагаю вам реализовать "мозги" следующей игры.
И если, авторов решения будет несколько, можно устроить "соревнование".
Я накидал код реализации игры с выдачей результатов на консоль.
Исходники на https://github.com/maratsr/MatrixGame
Для реализации своего алгоритма необходимо создать реализацию интерфейса IGameStrategy и реализовать в нем:
1) метод getTurn(). Где собственно и происходит поиск оптимального хода
2) метод toString(). Просто вывод информации о вашем методе.
Достаточно:
1) добавить код в getTurn() класса MyGameStrategy, где прописать алгоритм. Весь упор именно на алгоритмику, а не собственно знание Java.
2) добавить его одним из игроков в метод static main класса Game для игры.
Всего то пару десятков строк реализации...
Для облегчения написания собственного алгоритма я привел примеры реализаций (как заготовки):
NonZeroFirstValueGameStrategy - Поиск первого доступного элемента
MaxValueGameStrategy - Поиск максимального значения в строке или колонке
RandomValueGameStrategy - Случайный ход
Для тестирования вашего алгоритма можете посоревноваться с ними. Можете также изменить кол-во игроков, размер начальной матрицы и т.п.
Game - основной класс, реализующий игру:
- Генерирует поле игры.
- Создает игроков с их стратегиями.
- В процессе игры передает ход стратегиям и ограничивает время принятия решения (в случае его превышения, прерывает стратегию).
- Выводит в консоль ход игры и ее результат.
Вариантов реализации прочих стратегий вагон:
Перебор на первые 2,3,4... хода с выбором лучшего ("ветви и границы"). Можете по ходу нахождения хода присваивать его аргументу функции move,
процесс перебора программа прервет и в качестве решения возьмет ход, найденный до этого момента.
Подсчет сумм элементов колонок или строк матрицы + поиск с учетом этого...
Можно добавить элементы случайности...
и т.п. и т.д.
P.S. Буду также благодарен, если кто подскажет более правильный способ (чем Executor + Future) для
ограничения времени работы любого метода (который не знает что его время выполнения лимитировано).">
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
это если у каждого игрока свое поле.
если же на одном поле играет одновременно сразу несколько игроков — тогда придется строить такой граф на каждом ходе. точнее, «вычеркивать» невозможные ходы. при поле 10*10 я думаю построение графа займет несколько секунд максимум. это если работать с примитивами, конечно же)) редактирование — значительно быстрее (просто выкидываем из деревьев ненужные ветки).
ну или если совсем просто — тогда обычный жадный алгоритм. который, в принципе, можно улучшить введя «пропуск хода», если есть реальная возможность на следующем ходу получить число значительно большее, чем на этом (например, ход доступен для поиска по рядку, в рядке остались цифры 1, 3, 7, 9. но если пропустить ход — станет доступен поиск по столбцу, где цифры 81, 94, 97, 99). но если его еще улучшить — тогда надо смотреть на два шага вперед, а если еще улучшить — то на три, итд. в итоге снова же задача сводится к построению дерева))
так что я думаю, основная задача тут — выбрать такую структуру данных, которая бы давала хороший результат именно в момент обновления весов в графе/дереве, а это уже дискретка и всякий матан)) так что кто знает такую структуру — пишите))
например, строим дерево не на все доступные хода, а просчитываем только 10 ходов вперед и выбираем для этого шага тот, который даст наибольший результат.
но против такого противника может быть легко играть)) сам просчитываешь его дерево шагов, получаешь тот, по которому противник «идет» и «выбиваешь» ему оттуда цифры)) ну это когда у самого уже есть большое преимущество. ну или наоборот, когда сильно отстаешь и выиграть уже нет возможности и можно просто не дать противнику набрать рекордные суммы)) но насколько я знаю, то согласно теории игр, обычно более эффективными оказываются «добрые» алгоритмы))
в общем, тут уже все зависит от времени, которое выделяется на каждый шаг.