Фон
MENACE ( M achine E ducable N oughts й C Rosses E ngine) является рудиментарным неглубоко машина алгоритм обучения для игры крестики и нолики, созданный британским ученый Дональд Мичи в 1960 - е годы. Первоначально он был реализован с 304 спичечными коробками, каждый из которых помечен позицией на доске и содержал цветные шарики (с одним из девяти цветов, представляющих возможные ходы). Мичи подсчитал, что этих 304 спичечных коробок было достаточно для каждой комбинации ходов на доске.
Более математически вы можете понять, что на плате N & C на самом деле существует 19 683 возможных комбинаций нолей, крестов и заготовок; однако он рассчитал способы сократить это число (чтобы ускорить алгоритм и, вероятно, сократить количество спичечных коробок!). Во-первых, он удалил все невозможные ходы, такие как:
-------
|X|0|X|
| |0| |
|X|X| |
-------
(две нолики и четыре креста)
Далее он компенсировал повороты. Например, если на спичечной коробке мы видим:
-------
| |0|0|
|X| |X|
| |0| |
-------
мы можем использовать ту же коробку для
-------
| |X| |
|0| |0|
| |X|0|
-------
Следовательно, вышеупомянутые цветные шарики представляют относительные положения, а не абсолютные. Например, если бы мы сказали, что красная полоска означает верхний левый, то мы взглянем на изображение в верхней части окна и увидим:
-------
| |0|0|
|X| |X|
| |0| |
-------
Таким образом, мы знали бы, что в случае, если это доска, тогда красный шарик будет означать:
-------
|R|0|0|
|X| |X|
| |0| |
-------
Но если это доска:
-------
| |X| |
|0| |0|
| |X|0|
-------
красный шарик будет означать
-------
| |X|R|
|0| |0|
| |X|0|
-------
Эти преобразования применяются для поворотов и инвертирования (во всех направлениях, в том числе и по диагонали). Еще раз, вам нужно сохранить каждую спичечную коробку только один раз таким образом: не создавайте отдельные виртуальные ящики для каждого преобразования!
Еще одно упрощение, которое сделала Мичи, - убедиться, что компьютер работает первым. Таким образом, он мог удалить все ходы первого уровня, убрав примерно пятую часть оставшихся ящиков. Наконец, он удалил все поля для окончания игры (поскольку на этих шагах больше не требовалось никакого «содержимого» или ходов).
Хорошо, теперь на сам алгоритм (это очень просто):
- Во-первых, определитесь с тем, какие цвета представляют бусины. Вам нужно 9 цветов, чтобы представить каждое из мест на доске.
- В начале игры каждая из 304 спичечных коробок содержит бусы. В то время как бусины имеют произвольный цвет (поэтому дубликаты в порядке), они должны быть возможными ходами (поэтому, если изображение состояния доски изображает букву «О» в середине справа, то вы не можете использовать бусину, которая представляет середину верно).
- Каждый раз, когда наступает ход MENACE (X), находите спичечный коробок с напечатанной на нем текущей позицией доски (или каким-либо ее преобразованием).
- Откройте спичечный коробок и выберите любую бусину там в случайном порядке.
- Узнайте, как статус доски был преобразован, чтобы попасть к изображению на спичечной коробке (например, повернуть на 90 градусов против часовой стрелки). Затем примените это преобразование к бусине (например, верхний левый становится левым левым).
- Поместите X в этот квадрат. Удалить выбранный шарик из спичечной коробки. Если в результате коробка останется пустой, поместите три случайных (возможных) шарика в коробку и выберите один из них для хода.
- Повторите 3-6, пока игра не закончится.
- Если MENACE выиграл игру, вернитесь к каждой спичечной коробке, которую взял MENACE. Затем проследите, какой цветной шарик он использовал на этом ходу. Поместите два шарика этого цвета в коробку (так, чтобы был оригинальный шарик + еще один, таким образом увеличивая вероятность того, что MENACE сделает этот ход в следующий раз, когда он достигнет этой позиции)
- Если MENACE проиграл, ничего не делайте ( не заменяйте бусы, которые он вынул).
- Если MENACE нарисовал игру, то замените бусину, которую он использовал в каждом из своих ходов, но не добавляйте дополнительную, чтобы вы остались с тем, что начали.
Это оставляет нам алгоритм, который очень прост, но сложен в реализации. Это составляет основу вашего вызова.
Если вы все еще в замешательстве, посмотрите http://chalkdustmagazine.com/features/menace-machine-educable-noughts-crosses-engine/ - это то, что я прочитал, когда впервые узнал об этом алгоритме
Вызов
Сыграйте в игру в крестики-нолики с компьютером. На каждом шаге выведите содержимое всех спичечных коробок.
входные
- В начале программы число, указывающее, сколько игр вы хотите играть против MENACE
- Затем, после первого хода MENACE, вы вводите свой ход в виде двухсимвольной строки, первая буква которой «L», «R» или «M» (слева, справа или в середине), ссылаясь на ось Y. Затем вы вводите другую букву (снова «L», «R» или «M»), на этот раз ссылаясь на ось X. Повторите для всех ходов и игр.
Выходы
- В начале каждой новой игры выведите «новая игра».
- После каждого хода игрока выведите доску в любом приемлемом формате. Это не должно выглядеть красиво (например, массив массивов, представляющих позиции доски, в порядке).
- После каждого хода игрока MENACE должен сделать ход. Вывести доску после хода MENACE
- После каждой игры выведите содержимое всех 304 спичечных коробок. Бусы могут быть представлены буквой, именем цвета, символом или любой другой строкой или целым числом (без указателей, анонимных функций и т. Д.).
правила
- Это код-гольф , поэтому выигрывает самый короткий ответ в байтах.
- Я должен иметь возможность вводить ходы после просмотра ответа MENACE. Не «пропускайте все свои ходы в эту функцию и смотрите, как проходит игра».
- Доска должна быть очищена между играми.
- В Спичечницах должны не быть очищены между играми (это было бы сбросить машинное обучение)
- Вы должны иметь 304 спичечных коробок. Любой может реализовать этот алгоритм со всеми 19 683 спичечными коробками, но обучение идет медленно (так как требуется много игр, чтобы получить все из них с полезным содержимым).
- Вывод может быть в любом приемлемом формате, и ввод может быть выполнен в соответствии со стандартами PPCG (при условии, что он соответствует правилу 2). Если вам нужно настроить формат ввода (как описано в разделе « Вход »), тогда все в порядке, если это имеет смысл.
- Игра заканчивается, когда игрок выигрывает (получая по три по диагонали, по горизонтали или по вертикали) или, если есть ничья (доска заполнена, а победителя нет)
- В то время как MENACE нужно делать возможные ходы (и иметь только возможные шарики внутри каждой спичечной коробки), для решения задачи вам не нужно проверять ввод пользователя. Если они вводят что-то неправильное, ваша программа может делать что угодно (сойти с ума, выбросить ошибку и т. Д.) - вы можете предположить, что ввод правильный.
источник
[[0, 2, 6], [4, 8, 4, 3, 3], [7, 7, 7, 7, 7, 7, 7, 8], [1], ... [3, 3, 5, 4]]
.Ответы:
R , 839 байт
Попробуйте онлайн!
Довольно длинный ответ, но это не было простой задачей. Ссылка TIO здесь потерпит неудачу, потому что она ожидает интерактивного ввода. Вот версия, которая играет против второго случайного игрока, который просто выбирает место наугад. Выход для этой второй версии - только победитель (1, 2 или 0 для ничьей.) Спичечные коробки инициализируются для всех позиций доски, но используются только для 304 согласно спецификации. Они реализованы в виде копий доски с отрицательными числами, указывающими количество бус на каждой позиции. Я экспериментировал со списком векторов согласно оригинальной спецификации, но он был менее интуитивным.
Это менее понятная версия с комментариями (но все же с короткими именами переменных). Обратите внимание, что он не распечатывает спичечные коробки, потому что они очень длинные. Он может реализовывать интерактивного игрока 2, случайного игрока 2 или ту же стратегию спичечной коробки для игрока 2.
источник