• ,

Реализация стратегии.

Судя по записям задач поиска контуров, brainfuck кодирования многим интересна алгоритмика, как одна из сторон программирования.
Предлагаю вам реализовать «мозги» следующей игры.
И если, авторов решения будет несколько, можно устроить «соревнование».
]1) Поле игры — матрица 10х10, элементы которой целые числа от 0 до 100 размещены на ней случайным образом.
2) Количество игроков может быть от 2х до 10-ти, но сделаем упрощение — пусть их будет двое.
3) Каждый игрок начинает с суммой очков = 0.
4) Игроки ходят по очереди и выбирают число на матрице. Выбранное игроком число прибавляется к его сумме очков и в матрице игры выбранное число зануляется.
5) Если игрок не выбрал число, то на данном ходу он добавляет к своей сумме ноль и ход переходит к следующему игроку.
6) Игрок может выбрать число на матрице только в строке или колонке выбранного на предыдущем ходе числа.
7) Выбор направления поиска текущего хода- строка или колонка матрицы попеременно:
если предыдуший поиск происходил в строке, то текуший должен происходить в колонке,
и наоборот:
если предыдуший поиск происходил в колонке, то текуший должен происходить в строке.
8) Время поиска хода ограничено.
9) Игра останавливается, если игрок не может выполнить очередной ход (либо все числа матрицы выбраны, либо в процессе игры у текушего игрока нет выбора).
10) Выигрывает игрок, набравший большее количество очков.
11) Для упрощения, первый ход делается в левом верхнем углу (координаты (0,0) матрицы).

Для наглядности, примеры первых ходов:


Я накидал код реализации игры с выдачей результатов на консоль.
Исходники на 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) для
ограничения времени работы любого метода (который не знает что его время выполнения лимитировано).">

3 комментария

JuriMik
Почти неделя без комментов. Мне кажется, достаточно объемное задание по времени. Да и по сложности не для джунов (ИМХО, разумеется). Это так, на первый взгляд. Я попробовал бы заняться, т.к. реально интересная задача для меня, но занят на работе, свободного времени пока нет
DefNeo
Типа героев что ли?))
shersh1k
Если правильно понимаю то проще всего когда твой ход то по каждой возможной строке/столбцу(в зависимости от хода) брать разность числа которое выпадает тебе и максимального числа на этой строке и где она максимальна(в твою пользу) туда и ходить и все)первое что в голову пришло
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.