Пасьянс «махджонг»: научный проект для старшеклассников с элементами искусственного интеллекта

Boris Feliksovich Melnikov; Elena Anatolyevna Melnikova; Svetlana Valentinovna Pivneva

doi:10.32603/2071-2340-2018-5-41-51

Boris Feliksovich Melnikov Университет МГУ-ППИ в Шэнчжэне, Шэньчжэн, Китайская Народная Республика
Elena Anatolyevna Melnikova Российский государственный социальный университет, Москва, Россия
Svetlana Valentinovna Pivneva Российский государственный социальный университет, Москва, Россия

DOI: https://doi.org/10.32603/2071-2340-2018-5-41-51

Аннотация

Проект, описываемый в настоящей статье, предназначен для исполнения старшеклассниками (а возможно - студентами младших курсов в качестве курсовой работы). Важно отметить, что реализация первой части проекта (компьютерной программы, решающей конкретную раскладку пасьянса) представляет собой весьма незначительную часть работы, предлагаемой для выполнения в этом проекте. Однако и эта часть - создание компьютерной программы для решения конкретной раскладки - тоже является задачей, относящейся к искусственному интеллекту.
В качестве основного критерия качества программы-решателя мы предлагаем использовать процент решения ею случайно сгенерированных раскладок, причём решение должно быть осуществлено без возможности взятия хода назад. Для программирования решения некоторой заданной раскладки мы предлагаем смоделировать процесс решения этой задачи человеком, мышление которого сильно отличается от «мышления» компьютера, в частности, отличатся объёмом запоминаемой информации. Для этого моделирования запрещается, например, программе запоминать фишки, которые уже вышли из игры.
Мы рассматриваем только «заведомо разрешаемые» раскладки. В качестве первого варианта (то есть в качестве начала реализации), мы предлагаем ученику реализовать программу, которая только решает раскладки, полученные случайным заполнением - заполнением пустого поля «с конца». Возможный подход к реализации программы-решателя - применение генетических алгоритмов. Отметим, что даже в этом случае решатель можно назвать небольшой экспертной системой. Мы также кратко описываем в статье некоторые другие области искусственного интеллекта, знание и применение которых возможно в рассматриваемой задаче.
Ранее авторы уже предагали аналогичные проекты студентам младших курсов, было реализовано несколько из них, но бóльшая часть материала, описанного в статье, ещё не реализована, поэтому документ озаглавлен как научный проект для реализации.

Биографии авторов

Boris Feliksovich Melnikov, Университет МГУ-ППИ в Шэнчжэне, Шэньчжэн, Китайская Народная Республика

Мельников Борис Феликсович, доктор физико математических наук, профессор Университета МГУ-ППИ в Шэнчжэне, профессор Российского государственного социального университета, bf-melnikov@yandex.ru

Elena Anatolyevna Melnikova, Российский государственный социальный университет, Москва, Россия

Мельникова Елена Анатольевна, кандидат физико математических наук, доцент Российского государственного социального университета; 129226, Москва, ул. Вильгельма Пика, дом 4, стр. 1, ya.e.melnikova@yandex.ru

Svetlana Valentinovna Pivneva, Российский государственный социальный университет, Москва, Россия

Пивнева Светлана Валентиновна, кандидат педагогических наук, доцент Российского государственного социального университета, tlt-swetlana@yandex.ru

Литература

1. Law M., Deane G. General Card Game Playing. URL: https://www.doc.ic.ac.uk/teaching/
distinguished-projects/2013/m.law.pdf (Retrieved: 06.09.2018).
2. Law M., Russo A., Broda K. The complexity and generality of learning answer set programs // Artificial
Intelligence. 2018. № 259. P. 110–146.
3. Brown N. Sandholm T. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals // Science (American Association for the Advancement of Science). 2017. № 359 (6374).
doi:10.1126/science.aao1733
4. Cyna Games. URL: http://cynagames.com/ (Retrieved: 06.09.2018).
5. Yen Sh.-J., Chen J.-C., Yang T.-N., Hsu Sh.-Ch. Computer Chinese Chess // ICGA journal. 2004. № 27 (1).
P. 3–18.
6. Luger G. Artificial Intelligence: Structures and Strategies for Complex Problem Solving. Boston:
Pearson Education, 2008.
7. Russel S., Norvig P. Artificial Intelligence: A Modern Approach. Prentice Hall, NJ. 2010.
8. Ben-Bassat M., Beniaminy I., Joseph D. Combining Model-Based and Case-Based Expert Systems.
In: Research Perspectives and Case Studies in System Test and Diagnosis. Frontiers in Electronic
Testing // Research Perspectives and Case Studies in System Test and Diagnosis. Frontiers in
Electronic Testing. 1998. Vol. 13. P. 179–199.
9. Weiss M., Indurkhya S. Rule-based Machine Learning Methods for Functional Prediction // Journal of
Artificial Intelligence Research, 1995. № 3. doi:10.1613/jair.199
10. Генетический алгоритм. Просто о сложном. URL: https://habr.com/post/128704/ (дата обращения: 06.09.2018).
11. Мельников Б. Ф., Пивнева С. В., Рогова О. А. Репрезентативность случайно сгенерированных
недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов // Стохастическая оптимизация в информатике. 2010. № 6 (1-1). С. 74–82.
12. Мельников Б. Ф., Сайфуллина Е. Ф. Применение мультиэвристического подхода для случайной генерации графа с заданным вектором степеней // Известия высших учебных заведений.
Поволжский регион. Физико-математические науки. 2013. № 3 (27). С. 70–83.