Комментарии 57
Интересно, сколько читателей всё-таки осилили статью полностью )
«Искусственный интеллект: стратегии и методы решения сложных проблем»
Джордж Ф. Люгер
Рекомендую для более глубокого ознакомления.
Видел ее в books.google.com.
Джордж Ф. Люгер
Рекомендую для более глубокого ознакомления.
Видел ее в books.google.com.
Однако число позиций столь велико, что полный анализ игры практически невозможен (за исключением классических крестиков-ноликов 3х3 и аналогичных по богатству стратегий игр).
вообщето шашки на 8х8 доске перебрали
вообщето шашки на 8х8 доске перебрали
> Мои студенты после 2 курса втроем за три недели сваяли вот эти шахматы.
Глюк там в программке, компьютер почему-то стал ходить конем по прямой, да еще и моим конем :)
Глюк там в программке, компьютер почему-то стал ходить конем по прямой, да еще и моим конем :)
Всё правда, всё про нас.
Минимакс в универе преподают.
Ждём статью про оценочные функции =)
Минимакс в универе преподают.
Ждём статью про оценочные функции =)
дерево ходов на самом деле выглядет не так, в нём есть приоритетные ветки, подветки, ветки с вопросом, с равенством,…
В статье описано это, насколько я понял. Тут и далее по тексту:
3. Выполняется некоторый в меру интеллектуальный анализ дерева возможных ходов, в процессе которого отсекаются заведомо неоптимальные ветки и глубоко просчитываются более перспективные. Как раз тут и выполняется знаменитая альфа-бета-процедура.
3. Выполняется некоторый в меру интеллектуальный анализ дерева возможных ходов, в процессе которого отсекаются заведомо неоптимальные ветки и глубоко просчитываются более перспективные. Как раз тут и выполняется знаменитая альфа-бета-процедура.
Блин, вот какими примерами нужно иллюстрировать метод ветвей и границ в курсе математических методов исследования операций! А то нам ну так нудно и надуманно про него рассказывали, что я уж решил, что это что-то ненужное.
Принципа минимакса еще придерживались в романе Филиппа Дика «Солнечная Лотерея» =) Он кстати отлично там быр реализован.
Пройдёт ещё лет двадцать и на шахматных чемпионатах помимо допинг контроля, будет проверка организма на наличие микрочипов — помощников.
самое интересное — это потом стравить между собой два разных алгоритма и посмотреть как они играть будут и кто кого :-)
Камнем преткновения в написании шахматных движков является реализация функции оценки позиции, она и определяет характер игры движка в сложных несбалансированных позициях, можно даже УСЛОВНО разделить шахматные движки на позиционные (приоритетом является оценка позиции) и тактические (приоритетом является перебор большего числа ходов для получения позиций более простых для оценивания), например движок Rybka скорее позиционный, а
Fritz — тактический.
Fritz — тактический.
Приду домой, сведу в баталию предоставленную программу и шахматы мелкмягких в висте!
О результатах отпишусь =)
О результатах отпишусь =)
Обыграл я вашу программу с первого раза, хотя в шахматы играть не очень умею. Так что расти точно есть куда :)
И еще можно упомянуть о эндшпильных таблицах (таблицы Налимова), они представляют собой базу данных из предварительно просчитанных всех возможных вариантов ходов для позиций в которых на доске остается небольшой количество фигур (конечно размер этих таблиц впечатляющий), уже сейчас полностью просчитаны таблицы для 6-ти фигурных и меньше окончаний (оба короля тоже считаются).
Имея такую таблицу в подобном эншпиле шахматному движку не нужно вообще ничего рассчитывать, он всегда абсолютно точно знает оценку позиции, или ничья или какой стороне в какое количество ходов и каким образом ставится мат.
Благодаря этим таблицам компьютер в эншпиле имеет абсолютное превосходство даже над сильнейшими гроссмейстерами мира.
Имея такую таблицу в подобном эншпиле шахматному движку не нужно вообще ничего рассчитывать, он всегда абсолютно точно знает оценку позиции, или ничья или какой стороне в какое количество ходов и каким образом ставится мат.
Благодаря этим таблицам компьютер в эншпиле имеет абсолютное превосходство даже над сильнейшими гроссмейстерами мира.
Про полный перебор всех шахматных комбинаций частенько говорят «слишком сложно».
А если брать численно? Сколько, скажем, floating point operations понадобится.
Может быть есть смысл собрать сеть распределённых вычислений и просчитать ВСЕ ходы, сделав самого крутого шахматного соперника?
А если брать численно? Сколько, скажем, floating point operations понадобится.
Может быть есть смысл собрать сеть распределённых вычислений и просчитать ВСЕ ходы, сделав самого крутого шахматного соперника?
Во-первых, такой мощности сеть собрать невозможно.
Во-вторых, даже если предположить, что соберете — смысл играть? Ясно, что зная наперед все хода, она победит.
В чем суть затеи?
Во-вторых, даже если предположить, что соберете — смысл играть? Ясно, что зная наперед все хода, она победит.
В чем суть затеи?
Суть затеи в том, что мне интересно это реализовать =)
Наверное, именно потому, что почти все считают это невозможным
Наверное, именно потому, что почти все считают это невозможным
тут дело не в ваших способностях, а в вычислительных ресурсах.
число комбинаций для просчета больше, чем число молекул в обозримой вселенной. то есть потребуются невероятно долгие периоды времени даже при условии использования всех существующих вычислительных машин человечества.
задача явно не та
геном человека или те же seti@home интересны людям куда более
а вот если вы придумаете новый алгоритм (читай займетесь не экстенсивным, а интенсивным решением вопроса), то может получиться намного интереснее. по крайней мере вам это толку принесет больше, чем попытка собрать мегакластер
число комбинаций для просчета больше, чем число молекул в обозримой вселенной. то есть потребуются невероятно долгие периоды времени даже при условии использования всех существующих вычислительных машин человечества.
задача явно не та
геном человека или те же seti@home интересны людям куда более
а вот если вы придумаете новый алгоритм (читай займетесь не экстенсивным, а интенсивным решением вопроса), то может получиться намного интереснее. по крайней мере вам это толку принесет больше, чем попытка собрать мегакластер
— Г-голубчики, — сказал Фёдор Симеонович озадаченно, разобравшись в почерках. — Это же п-проблема Бен Б-бецалеля. К-калиостро же доказал, что она н-не имеет р-решения.
— Мы сами знаем, что она не имеет решения, — сказал Хунта, немедленно ощетиниваясь. — Мы хотим знать, как её решать.
— К-как-то ты странно рассуждаешь, К-кристо… К-как же искать решение, к-когда его нет? Б-бессмыслица какая-то…
— Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица — искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, к сожалению, не доступен. По-видимому, я напрасно начал с тобой беседовать на эту тему.
(с) АБС, Понедельник начинается в субботу.
— Мы сами знаем, что она не имеет решения, — сказал Хунта, немедленно ощетиниваясь. — Мы хотим знать, как её решать.
— К-как-то ты странно рассуждаешь, К-кристо… К-как же искать решение, к-когда его нет? Б-бессмыслица какая-то…
— Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица — искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, к сожалению, не доступен. По-видимому, я напрасно начал с тобой беседовать на эту тему.
(с) АБС, Понедельник начинается в субботу.
Суть? Узнать — белые или чёрные выигрывают при правильной игре. :-)
Почти похожая ситуация. (=
для осознания масштабов стоит посмотреть на тему en.wikipedia.org/wiki/Computational_complexity_theory
Причем тут искусственный интеллект. Тут проста перебор всех вариантов.
позвольте поспорить
задача искусственного интеллекта по одному из определений — такая задача, для которой неизвестно точного алгоритмического или аналитического решения. для шахмат из-за огромного числа вариантов такого алгоритмического решения нет
кроме того, в описанном «переборе вариантов» используются, и существенно, разнообразные эвристические, качественные, оценочные параметры и функции, что напрямую относится к инженерии знаний, т.е ИИ
задача искусственного интеллекта по одному из определений — такая задача, для которой неизвестно точного алгоритмического или аналитического решения. для шахмат из-за огромного числа вариантов такого алгоритмического решения нет
кроме того, в описанном «переборе вариантов» используются, и существенно, разнообразные эвристические, качественные, оценочные параметры и функции, что напрямую относится к инженерии знаний, т.е ИИ
вот тут бы уместно было бы «завернуть» оценку задачи в категориях полиномиальностей.
Вот функции оценки тут самое интересное, а к альфа-бета-отсечениям и минимаксному методу можно и путем логических рассуждений прийти
Насколько я знаю, этот подход именно к шахматам устарел, современные сильнейшие программы основаны на многомиллионных базах сыгранных людьми партий.
только дебютов. до 20 хода все дебюты просчитаны и проанализированы. далее начинается игра и продолжается до эндшпиля, когда тоже в принципе все предсказуемо
НЛО прилетело и опубликовало эту надпись здесь
не совсем так
шахматы фишера не обязательны, если вы, например, хотите участвовать в соревнованиях по классическим шахматам или блицу
это действительно очень интересная вариация. основанная на непредсказуемом начальном положении фигур (с рядом ограничений), но пока проводятся только показательные матчи по шахматам фишера параллельно с соревнованиями по традиционным шахматам
шахматы фишера не обязательны, если вы, например, хотите участвовать в соревнованиях по классическим шахматам или блицу
это действительно очень интересная вариация. основанная на непредсказуемом начальном положении фигур (с рядом ограничений), но пока проводятся только показательные матчи по шахматам фишера параллельно с соревнованиями по традиционным шахматам
Ну вот. Опять поламал :'(
[url]http://smages.com/i/4a/2e/4a2e32250669fc21c126734367e3bb45.jpg[/url]
[url]http://smages.com/i/4a/2e/4a2e32250669fc21c126734367e3bb45.jpg[/url]
Огромное спасибо за статью! Сколько раз ломал голову и приходил к выводам Кнута и Мура, но не хватало собранности мыслей, чтобы написать это в программер по-человечески. Когда-то делал одной рекурсивной ф-цией, потом тремся, потом двумя… У вас, как я смотрб, довольно компактно все получилось. Как только найду свободное время, попробую использовать ваш код. Спасибо ещё раз.
А как определяется f(p)?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как компьютеры играют в шахматы