Проект «Цепи Маркова: компьютерные шахматы» объединяет понятия теория языка и дискретные случайные процессы первого порядка.

ETC: 15 часов (срок – 5 занятий)

2-3 ученика в команде

Пожалуйста, не торопитесь как с качеством, так и с содержанием

Доцент и доценты не будут отвечать на вопросы о проекте.

ШКАЛА: 40 баллов

  1. 10 баллов
  2. 15 баллов
  3. 15 точек

Проект цепей Маркова: Computer Chess объединяет понятия теории языка и дискретных случайных процессов первого порядка.

Проект Цепи Маркова : Проект Цепи Маркова Компьютерные Шахматы

«Оператор: Как вы думаете, человек когда-нибудь обыграет человека в шахматы? Джон: О... между человеком и человеком? Мои деньги на компьютере.

Часть 1: Читаемые и понятные данные

Проект Цепи Маркова : Проект Цепи Маркова Компьютерные Шахматы

" ИМЕЕТ компьютер однажды побил меня в шахматы, но в кикбоксинге мне было не ровня. »

Задача сложна, ежегодный мировой шахматный турнир бросит вызов первым ученым-компьютерщикам: создать программу, способную обыграть человека в шахматы. Это первое, и вы должны показать миру потенциал вычислений.

Чтобы ознакомиться с правилами шахмат, вы смотрите на повторе старые турниры Михаила Таля, Бобби Фишера и Анатолия Карпова, а также многообещающий дебют молодого и грозного Гарри Каспарова.

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

Поэтому компьютер будет строить деревья решений для благоприятных конфигураций (как в проекте 1). Возьмем, к примеру, следующие слова для благоприятной конфигурации А:

  • аббааккад
  • baacdaadd
  • abaacdddd

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

Второй шаг состоит в вычислении коэффициента совместимости между двумя состояниями. В нашем примере мы объединим два состояния, если они совместимы с 100%. Два состояния совместимы с 100%, если они имеют одинаковые предшествующие и последующие символы. Например, в префиксах abba и baab биномы ab или ba совместимы с 100%. При объединении необходимо также объединить количество проходов по дугам (так что здесь мы суммируем 1+1).

Третий шаг состоит в объединении совместимых состояний 50%, то есть только с теми же преемниками или только с теми же предшественниками. Следовательно, можно свести конечные состояния в одно конечное состояние, поскольку все конечные состояния имеют одних и тех же преемников (здесь — пустое множество).

Четвертый и последний шаг используется для построения цепи Маркова в соответствующем дискретном времени. Для каждого состояния вероятность входа (соответственно выхода) дуги равна числу проходов этой дуги, деленному на сумму количеств входов (или выходов, это число одно и то же).

Рейтинг

  1. Шаг 1 (2 балла)
  2. 2-й шаг (3 балла)
  3. Шаг 3 — не сходятся на всех возможных случаях, хотя бы в двух из которых конечное состояние (3 балла)
  4. Шаг 4 (2 балла)

Часть 2: Поведенческое исследование

Проект Цепи Маркова : Проект Цепи Маркова Компьютерные Шахматы

Бейшер: Есть ли вероятность, что это э-э… что-то э-э… очень продвинутое… Я имею в виду, мы только что отказались от ферзя, чтобы получить его ферзя, и теперь мы в основном просто… эм…

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

Изучите поведение следующих двух цепей Маркова с дискретным временем:

Проект Цепи Маркова : Проект Цепи Маркова Компьютерные Шахматы

Состояние 6 является конечным состоянием.

Проект Цепи Маркова : Проект Цепи Маркова Компьютерные Шахматы

Поглощающие состояния — это конфигурации «мат». Состояние s0 является начальным состоянием, поэтому начальный вектор начинается только с этого состояния.

Рейтинг

  1. Канал 1 (7 точек)
  2. Канал 2 (8 точек)

Часть 3. Редукция автоматов и предсказание

Проект Цепи Маркова : Проект Цепи Маркова Компьютерные Шахматы

«Шахматы — это борьба с ошибкой». – Йоханнес Цукерторт

Теперь, когда ваша система машинного обучения настроена и работает, пришло время подумать о технической части. Ваш компьютер имеет два ядра, поэтому можно выполнять параллельные вычисления. Тогда возникает проблема с шиной. Вам нужна одна или две шины для маршрутизации информации к процессорам? Зная, что информация всегда поступает в соответствии с процесс Пуассона со скоростью λ и что они обслуживаются с помощью пуассоновского процесса с одинаковой скоростью, рассчитайте стационарное распределение, загрузку процессоров, количество потерянных сообщений, а также среднее время ожидания перед обслуживанием для обеих установок.

Рейтинг

  1. Моделирование двух конфигураций (5 точек)
  2. Анализ первой конфигурации (5 точек)
  3. Анализ второй конфигурации (5 точек)
Делиться
ru_RURU