Комментарии 17
Можно добавить варианты крестиков-ноликов на больших досках.
Было бы интересно почитать про антагонистические игры для 3-х и более игроков.
Шашки вроде как уже до конца просчитаны.
только английские и только с начальной позиции
Не беспокойтесь, осталась еще непредсказуемая игра в чапаевцев)
А чего беспокоиться? Пусть для начала столбовые шашки обсчитают
Было бы интересно узнать про маджонг, китайский и японский вариант
Игры с неполной информацией, наверное, совсем не то же самое, что игры с открытой информацией.
я прошу прощения, что не в тему - не ваш запрос был на возможность клонирования прошивки ssd дисков HPE на форуме LINUX.ORG.RU?
Если ваш - хотел бы пообщаться на эту тему.
Продолжение будет, я над этим работаю.
Продолжение готово.
Было бы интересно почитать про настолки, особенно в двух вариантах:
Где влияют только ходы и полученные карты (Ticket To Ride, Свинтус, Uno, Каркассон)
Где влияет поведение игроков (Манчкин, Шакал)
Обожаю сокобан и кубик рубика, спасибо что их тоже упомянули.
На счёт сокобана есть целое соревнование различных солверов. Только недавно они смогли решить базовый набор из 90 классических уровней. Перебор там бесполезен, нужно очень много различных оптимизаций. http://www.sokobano.de/wiki/index.php?title=Solver_Statistics
По кубику рубика тоже все не просто. Солверы существуют только для 2х2 и 3х3. Они способны найти кратчайшее решение для любой исходной позиции. 3х3 решается максимум за 20 поворотов. Но вот для кубиков более высоких порядков задача пока что не решена. http://kociemba.org/cube.htm
В "обожании" Кубика Рубика несомненно присутствует нечто религиозное – головоломка совершенно монструозная, безусловно любопытна, как математическая задача и восхищает формой в которую эта задача заключена её изобретателем, но такая "головоломка" хороша для Герберта Коцембы и ему подобных, человека же менее готового к интеллектуальным напряжениям она должна сводить с ума,– Грэм Паркер, собиравший её 26 лет, являет собой редкий пример удивительного психического здоровья, каким не всякий, взявший в руки Кубик Рубика, обладает. Много более простая головоломка,– сложность которой лишь 8,– зовётся Мгновенное Безумие (Instant Insanity).
"и по рейтингу Эло машины с лихвой перегнали человека. "
где по ссылке рейтинг машин?
Где глянуть рейтинг эло AI + HI.
Мне кажется, что в статье не хватает всё же каких-то более строгих и конкретных утверждений.
Во введении я бы рекомендовал более подробно написать, что исследуется сложность последовательности задач, зависящая от N. И может быть привести какой-то пример. Кроме того, слово "конечный" используется в разных смыслах и не всегда ясно, что имеется в виду.
Как правильно отмечено, в некоторых играх оценивается не сложность поиска выигрышной стратегии, а сложность поиска оптимального хода или стратегии при известной конфигурации. Собственно, хотелось бы более ясно понимать, для какой игры что именно оценивается. Формулировка "сложность игры" неоднозначна.
Амазонки. Не ясно, как устроена игра размера N. Изменяется только размер доски или количество амазонок тоже?
Криптарифмы. Аналогично, совершенно не ясно как устроена задача размера N. А следующая фраза, очевидно, сформулированна некорректно: "Однако при использовании других систем счисления, является NP-полной." (других, это каких? двоичная система счисления подходит? Очевидно, что нет.) Как основание системы счисления должно зависеть от N?
Пятнашки. Тут понятна задача, но совершенно не ясен смысл фразы "Что интересно «не известен ни один алгоритм, находящий кратчайшее решение для обобщённых пятнашек N×N за разумное время»". Что значит "разумное"?
Го и шахматы. Аналогично. Как устроена задача для размера N. Какие фигуры в шахматах N x N?
Вычислительная сложность некоторых игр и головоломок (часть 1)