Сапёр

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

Например, в этой 3х3 игре "Сапёр" три значения 1 означают, что у каждой из этих ячеек есть одна соседняя, которая содержит мину. Четыре нулевых значения указывают на то, что у каждой из этих ячеек нет соседней мины.

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

Цель игры - пометить каждую ячейку с миной флажком. Поставить флажок можно, щёлкнув правой кнопкой мыши по ячейке.

Логика высказываний

Вашей целью в этом задании будет создание ИИ, способного играть в "Сапёра". Напомним, что агент, основанный на знаниях, принимает решения, рассматривая свою базу знаний, делая вывод из этих знаний.

Один из способов представления знаний ИИ об игре "Сапёр" - сделать каждую ячейку пропозициональной переменной, которая будет истинной, если ячейка содержит мину, и ложной в противном случае.

К какой информации имеет доступ ИИ? Каждый раз, когда нажимается безопасная ячейка ИИ будет узнавать её число. Рассмотрим следующую доску "Сапёра", где средняя ячейка была открыта, а другие были помечены идентификационными буквами для обсуждения.

Какая информация у нас есть сейчас? Похоже, теперь мы знаем, что в одной из восьми соседних ячеек - мина.


Or(A, B, C, D, E, F, G, H)

Но на самом деле мы знаем больше, чем говорит это выражение. Приведённое выше логическое высказывание выражает идею о том, что по крайней мере одно из восьми высказываний истинно. Но мы можем сделать более сильное утверждение: мы знаем, что ровно одно из восьми высказываний верно. Это даёт нам пропозициональное высказывание приведённое ниже.


Or(
    And(A, Not(B), Not(C), Not(D), Not(E), Not(F), Not(G), Not(H)),
    And(Not(A), B, Not(C), Not(D), Not(E), Not(F), Not(G), Not(H)),
    And(Not(A), Not(B), C, Not(D), Not(E), Not(F), Not(G), Not(H)),
    And(Not(A), Not(B), Not(C), D, Not(E), Not(F), Not(G), Not(H)),
    And(Not(A), Not(B), Not(C), Not(D), E, Not(F), Not(G), Not(H)),
    And(Not(A), Not(B), Not(C), Not(D), Not(E), F, Not(G), Not(H)),
    And(Not(A), Not(B), Not(C), Not(D), Not(E), Not(F), G, Not(H)),
    And(Not(A), Not(B), Not(C), Not(D), Not(E), Not(F), Not(G), H)
)

Это очень сложное выражение! И это просто для того, чтобы выразить, что означает для ячейки число 1 в ней. Если ячейка имеет 2 или 3 или какое-либо другое значение, то выражение будет ещё длиннее.

Для игры с сеткой 8х8 понадобилось бы 64 пропозициональных символа, и 2^64 возможных моделей для проверки, что слишком много для компьютера. Нам надо найти другое представление знаний.

Представление знаний

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


{A, B, C, D, E, F, G, H} = 1

Каждое логическое предложение в этом представлении состоит из двух частей: набора клеток на поле, которые участвуют в предложении и числа, представляющего сколько из них, содержащих мины. Приведённое выше предложение говорит, что из клеток A, B, C, D, E, F, G, H ровно одна содержит мину.

Чем удобно это представление? Рассмотрим игру ниже.

Используя знание левого нижнего числа, мы могли бы записать {D, E, G} = 0, означающее, что 0 клеток из D, E, G содержат мины. Каждый раз, когда у нас есть предложение, счётчик которого равен 0, мы знаем, что все ячейки этого предложения безопасны.

Точно также рассмотрим игру ниже.

Наш ИИ построил бы предложение {E, F, G} = 3. Мы можем сделать вывод, что все E, F, H являются минами. В более общем случае, каждый раз, когда число ячеек равно числу мин, мы знаем, что все ячейки этого предложения должны быть минами.

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

Например, если бы наш ИИ знал предложение {A, B, C}=2, у нас ещё не было бы достаточной информации, чтобы сделать какой-либо вывод. Но если бы нам сказали, что C безопасна, то мы бы вообще удалили C из предложения, оставив {A, B} = 2. Последнее позволяет сделать новые выводы.

Точно так же, если бы наш ИИ знал предложение {A, B, C} = 2, и нам сказали бы, что C - это мина, мы могли бы удалить C из предложения и уменьшить значение счётчика, что даёт {A, B} = 1. Если только две из A, B, C являются минами и мы знаем C мина, тогда среди A, B только одна мина.

Рассмотрим следующие два предложения. Из 1 средней ячейки верхнего ряда наш ИИ построит предложение {A, B, C} = 1. Из средней ячейки нижнего ряда следует предложение {A, B, C, D, E} = 2. Мы могли бы построить новое предложение, что {D, E} = 1. Так только две из A, B, C, D, E являются минами и только одна из A, B, C является миной, тогда это есть причина, что только одна мина D, E.

В более общем случае каждый раз, когда у нас есть два предложения множество1 = счётчик1 и множество2 = счётчкик2, где множество1 является подмножеством множества2, мы можем построить новое предложение множество2 - множество1 = счётчик2 - счётчик1. Рассмотрите пример приведённый выше, чтобы убедиться что вы поняли.

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

Выпишем правила:

Каждый раз, когда у нас есть предложение, счётчик которого равен 0, мы знаем, что все ячейки этого предложения безопасны.
Каждый раз, когда число ячеек равно числу мин, мы знаем, что все ячейки этого предложения должны быть минами.
Каждый раз, когда у нас есть два предложения множество1 = счётчик1 и множество2 = счётчкик2, где множество1 является подмножеством множества2, мы можем построить новое предложение множество2 - множество1 = счётчик2 - счётчик1.

Начало

Загрузите код дистрибутива и распакуйте его.

Пояснение

Файлы game.js, view.js, index.js, index.html были созданы для вас и содержат все необходимое для создания графического интерфейса игры. Файл minesweeper.js нужен для реализации ИИ игры. Когда вы определите все необходимые функции в minesweeper.js, вы сможете запустить игру, запустив http-server.

Откройте файл minesweeper.js, чтобы понять, что там есть. В этом файле определены два класса: Sentence, который реализует логические высказывания, содержащие набор ячеек и количество мин в них; MinesweeperAI, который делает выводы о том, какие действия следует предпринять, основываясь на знаниях.

Каждый объект класса Sentence имеет множество ячеек и счётчик числа мин из них. Класс содержит функции mark_mine и mark_safe для обновления информации о ячейках.

MinesweeperAI реализует ИИ, который может играть в "Сапёра". Класс отслеживает ряд значений. moves_made содержит ячейки на которые уже нажали, поэтому ИИ знает, что не нужно их снова выбирать. mines содержит ячейки, известные как мины. safes содержит ячейки, которые считаются безопасными. knowledge содержит список всех предложений, которые ИИ считает истинными.

mark_mine функция добавляет ячейку к mines, что бы ИИ знал, что это мина. Она также перебирает все предложения известные ИИ, и информирует их о том, что ячейка является миной, чтобы предложение себя изменило соответственно этой информации. make_safe функция делает подобное, но для ячеек безопасных.

Функции add_knowledge, make_safe_move, make_random_move оставлены для вас.

Задание

Закончите определение классов Sentence, MinesweeperAI в файле minesweeper.js.

В классе Sentence завершите реализации known_mines, known_safes, mark_mine и mark_safe.

known_mines функция должна возвращать ячейки из cells, о которых известно, что они являются минами.
known_safe функция должна возвращать все ячейки из cells, которые безопасны.
mark_mine функция должна сначала проверить, является ли ячейка одной из ячеек, включённых в предложение.
- Если ячейка в предложении, функция должна обновить предложение, чтобы ячейка больше не была в предложении, но по-прежнему представляла логически правильное предложение, учитвыаия, что ячейка, как известно, является миной.
- Если ячейки нет в предложении, то никаких действий не требуется.
Функция mark_safe должна сначала проверить, является ли ячейка одной из ячеек, включённых в предложение.
- Если ячейка находится в предложении, функция должна обновить предложение, чтобы ячейка больше не была в предложении, но по-прежнему представляла логически правильное предложение, учитывая, что эта ячейка известна как безопасная.
- Если ячейки нет в предложении, то никаких действий не требуется.

В классе MinesweeperAI завершите реализацию add_knowledge, make_safe_move и make_random_move.

add_knowledge должен принимать ячейку (задаваемую числом) и ее соответствующий счетчик, а также обновлять this.mines, this.safes, this.moves_made и this.knowledge с любой новой информацией, которую ИИ может вывести, учитывая эта ячейка известна как безопасная ячейка с соседними минами.
- Функция должна пометить ячейку как один из сделанных в игре ходов.
- Функция должна пометить ячейку как безопасную, обновив также все предложения, содержащие эту ячейку.
- Функция должна добавить новое предложение в базу знаний ИИ на основании значения ячейки и числа мин в соседних ячейках. Не забудьте включить в предложение только те ячейки, состояние которых ещё не определено.
- Если на основе любого из предложений в this.knowledge новые ячейки могут быть помечены как безопасные или как мины, то функция должна это сделать.
- Если на основе любого из предложений в this.knowledge можно вывести новые предложения (используя метод подмножества, описанный в разделе "Представление знаний"), то эти предложения также следует добавить в базу знаний.
- Обратите внимание, что каждый раз, когда вы вносите какие-либо изменения в знания своего ИИ, можно сделать новые выводы, которые раньше были невозможны. Убедитесь, что эти новые выводы добавлены в базу знаний, если это возможно.
make_safe_move должна возвращать ход, заведомо безопасный.
- Возвращаемый ход должен быть известен как безопасный, а не уже сделанный ход.
- Если безопасное перемещение не может быть гарантировано, функция должна возвращать undefined.
- Функция не должна изменять this.moves_made, this.mines, this.safes или this.knowledge.
make_random_move должен возвращать случайный ход.
- Эта функция будет вызываться, если безопасное перемещение невозможно: если ИИ не знает, куда двигаться, вместо этого он выберет случайное перемещение.
- Ход не должен быть ходом, который уже был сделан.
- Ход не должен быть ходом, который известен как мина.
- Если такие перемещения невозможны, функция должна возвращать undefined.

Добавьте игру на ваш сайт, на github.

Как отправить на проверку

В форме укажите адрес игры на сайте.

http://90.188.117.161:8080