close

Вход

Забыли?

вход по аккаунту

...№3746 - Коммерческое предложение для БТС;doc

код для вставкиСкачать
Методы проектирования и анализа алгоритмов
Урок 6: Минимакс (необязательное задание)
Задание Реализовать выбор ходов компьютером для указанной игры с помощью алгоритма минимакс. Для сокращения числа возможных ходов для рассмотрения использовать алгоритм альфа­бета отсечения (метод ветвей и границ). Предусмотреть два режима игры: человек­компьютер (интерактивный) и компьютер­компьютер (автоматический). Реализовать графическое или текстовое приложение, позволяющее задавать следующий ход (в интерактивном режиме) и следить за ходом игры. Дополнительный плюс: использовать многопоточное программирование для ускорения построения и анализа дерева в алгоритме минимакс (разные потоки строят и анализируют разные поддеревья). Число потоков задается перед стартом или в ходе выполнения программы. Дополнительный плюс: ввести предел (в миллисекундах) для времени на обдумывание компьютером каждого хода. По истечении этого времени алгоритм минимакс должен прерывать свое исполнение и выдавать один из найденных ходов в качестве результата. Если ход удается найти раньше указанного времени, он совершается и игра продолжается. Для каждого хода компьютера выводить время, затраченное им на обдумывание этого хода. Варианты игр: 1. Пять в ряд. Крестики­нолики на поле из NxN клеток (обычно N равно 15 или 19; можно использовать произвольное значение). В начале игры поле пустое. Начинает любой из игроков. На каждом ходу игроки поочередно ставят свою фигуру (крестик или нолик; вариант ­ черную или белую фишку) в пустую клетку поля. Игрок побеждает, если ему удалось выстроить ряд из пяти или более своих фигур по вертикали, горизонтали или диагонали. Если клетки поля заканчиваются и никому из игроков не удалось построить такой ряд, игра завершается ничьей. 2. Гомоку. Аналог пяти в ряд (см. предыдущий пункт). Игрок побеждает, если ему удалось выстроить ряд из ровно пяти своих фигур по вертикали, горизонтали или диагонали. Ряд из более чем пяти фигур возможен, но не приносит победу. 3. Реверси. Игра производится на поле из 8x8 клеток (можно использовать поле другого размера). Игроки играют фишками с черной и белой сторонами (каждый игрок играет за свой цвет). В начале игры в центр поля помещаются четыре фишки (см. рисунок). Игрок с черными фишками ходит первым. Игроки поочередно ставят новую фишку на пустую клетку поля, своим цветом вверх, таким образом, чтобы между поставленной фишкой и уже находящейся на доске своей фишкой образовался ряд из одной и более фишек противника, по вертикали, горизонтали или диагонали. Все фишки противника в таком ряду переворачиваются (меняют цвет) и переходят к игроку; если удалось построить несколько таких рядов одновременно, фишки переворачиваются во всех рядах. Если не удается поставить фишку, чтобы построить ряд, ход переходит к следующему игроку. Игра завершается, когда все клетки поля заняты или ни один из игроков не может сделать ход. Побеждает игрок с большим количеством своих фишек на поле, при равенстве фишек присуждается ничья. 4. Шашки. Игра производится на поле из 8x8 черных и белых клеток (можно использовать поле другого размера, с соответствующим изменением числа фишек). Игроки играют фишками (шашками) черного и белого цвета, которые делятся на обычные и дамки. В начале игры у каждого игрока по 12 обычных шашек, которые расставляются на поле специальным образом (см. рисунок). Игрок с белыми шашками ходит первым. Игроки по очереди двигают одну из своих шашек на свободную клетку поля, по правилам: ­ Простая шашка ходит вперед по диагонали на одну клетку. При достижении любого поля последней горизонтали (противника), она превращается в дамку. ­ Дамка ходит по диагонали на любое свободное поле вперед или назад. Игроки могут своими шашками брать (убирать с доски) шашки противника. Если есть выбор между обычным ходом и взятием, игрок обязан выполнить взятие. Если есть несколько вариантов взятия, игрок может выбрать любой из них. Правила взятия: ­ Обычная шашка может взять шашку противника, если находится рядом с ней по диагонали и за этой шашкой есть свободное поле. После взятия шашка перемещается на это свободное поле. Можно произвести несколько взятий за один ход, если после каждого перемещения выполняется условие взятия (но нельзя брать одну и ту же шашку несколько раз). Если во время серии взятий шашка оказалась на последней горизонтали, она становится дамкой и может продолжать взятия как дамка. После окончания серии взятий взятые шашки убираются с доски. ­ Дамка может взять шашку, если находится рядом с ней на одной диагонали и за этой шашкой есть свободное поле. После взятия дамка может переместиться на любое свободное поле за взятой шашкой. Правила серии взятий аналогичны для дамки. Выигрывает тот игрок, которому удалось уничтожить или заблокировать все шашки противника. В отчет включить: ● Описание использованных алгоритмов ● Текст программы ● Результаты тестов Мой номер варианта задания = Мой номер в списке группы % Количество вариантов Варианты заданий: 1. Пять в ряд 2. Гомоку 3. Реверси 4. Шашки 
1/--страниц
Пожаловаться на содержимое документа